Problems with TT, sometimes makes blunder moves
Moderators: hgm, Rebel, chrisw
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Problems with TT, sometimes makes blunder moves
That is pretty good. So it seems your hash table is working as it should. This end-game does't have many positions, so you don't need a large hash table, and the tree fits entirely in a pretty small one already. So the replacement scheme is also not important, there just isn't anything to replace.
Re: Problems with TT, sometimes makes blunder moves
Hmmm.
32MB hash:
With 256MB hash, embla rev 4080: manual aborted at depth 58, no sign of e1-f2.
512MB hash:
1024MB hash:
aborted at depth 51, no sign of e1f2
with 4GB hash:
but with 8GB hash: (manual) aborted at depth 56
So:
- 32MB ok
- 64MB fail
- 128MB fail
- 256MB fail
- 512MB ok
- 1024MB fail
- 2048MB fail
- 4096MB ok
- 8192MB fail
(they all do mention checkmate detected)
32MB hash:
Code: Select all
info depth 31 seldepth 33 score cp 978 ebf 2.21 time 1476 nodes 2065159 pv e1f2 e8d7 f2e3 d7e7 e3e4 e7e6 e4d4
info string nps: 1367k, eval: 978, depth: 30, time: 1.476
512MB hash:
Code: Select all
info depth 43 seldepth 45 score cp 9965 ebf 1.16 time 31197 nodes 40327332 pv e1f2 e8d7 f2f3 d7d6 f3e4 d6e6 e2e3 e6d6 e4f5 d6e7 f5e5 e7f7 e5d6 f7e8 e3e4 e8d8 d6e6 d8c7 e4e5 c7c6 e6f7 c6c5 e5e6 c5d4 e6e7 d4e5 e7e8=q e5d5 e8d8 d5c5 d8a5 c5c6 f7f6 c6b7 a5b4 b7c7 f6e5 c7d7 b4b7 d7d8 e5f6 d8e8
info string checkmate detected at 43 (35)
info string nps: 1263k, eval: 9965, depth: 42, time: 31.197
aborted at depth 51, no sign of e1f2
Code: Select all
info depth 51 seldepth 53 score cp 9968 ebf 2.77 time 172939 nodes 241948329 pv e1d2 e8d7 d2e3 d7d6 e3e4 d6e6 e2e3 e6d6 e4f5 d6e7 f5e5 e7d7
Code: Select all
info depth 42 seldepth 44 score cp 9961 ebf 0.59 time 16983 nodes 22568079 pv e1f2 e8d7 f2f3 d7d6 f3f4 d6e6 f4e4 e6d6 e4f5 d6e7 f5e5 e7f7 e5d6 f7g8 e2e4 g8f8 e4e5 f8e8 d6e6 e8f8
info string checkmate detected at 42 (39)
info string nps: 1298k, eval: 9961, depth: 41, time: 16.983
Code: Select all
info depth 56 seldepth 58 score cp 9972 ebf 2.00 time 840866 nodes 1298089272 pv e1d2 e8d7 d2e3 d7e6 e3e4 e6d6 e4f5 d6c5 e2e4 c5d6 f5f6 d6c5 e4e5 c5d5
- 32MB ok
- 64MB fail
- 128MB fail
- 256MB fail
- 512MB ok
- 1024MB fail
- 2048MB fail
- 4096MB ok
- 8192MB fail
(they all do mention checkmate detected)
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Problems with TT, sometimes makes blunder moves
Well, e1d2 wins just as much as e1f2, right?
Re: Problems with TT, sometimes makes blunder moves
Oh I was under the impression that e1f2 was a better win or so.
Ok.
Ok.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Problems with TT, sometimes makes blunder moves
1) Since "key & size" is not the same as "key % size" you probably meant this: you replaced "key & (size-1)" (or "key & (size-4)" ??) by "key % size", right? But I think that is only a small change.tttony wrote:I tested that position with (key & size), I don't use slots and the table just fill 1024 from 1677720 entries, with (key % size) see the mate in 32 in the depth 30
2) So what was the second bug that you fixed that helped to make your TT work?
-
- Posts: 2554
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Problems with TT, sometimes makes blunder moves
Yes, both win (and I think it's ~the same number of moves)flok wrote:Oh I was under the impression that e1f2 was a better win or so.
Ok.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Problems with TT, sometimes makes blunder moves
Both are mate in 22 moves.mar wrote:Yes, both win (and I think it's ~the same number of moves)flok wrote:Oh I was under the impression that e1f2 was a better win or so.
Ok.
-
- Posts: 268
- Joined: Sun Apr 24, 2011 12:33 am
Re: Problems with TT, sometimes makes blunder moves
(key & size) did not work because struct hash_entry_s had an extra field called nodes to test perft only with (key % size)Sven Schüle wrote:1) Since "key & size" is not the same as "key % size" you probably meant this: you replaced "key & (size-1)" (or "key & (size-4)" ??) by "key % size", right? But I think that is only a small change.tttony wrote:I tested that position with (key & size), I don't use slots and the table just fill 1024 from 1677720 entries, with (key % size) see the mate in 32 in the depth 30
2) So what was the second bug that you fixed that helped to make your TT work?
Code: Select all
typedef struct hash_entry_s {
uint64_t key;
int32_t move;
int32_t score;
int8_t depth;
uint32_t flags;
int16_t age;
//uint64_t nodes; // only for perft
} hash_entry_s;
And size = size - 1
Code: Select all
hash->entry = malloc(ttsize * sizeof(hash_entry_s));
hash->size = ttsize - 1;
if (NULL == hash->entry) {
printf("Error: can't malloc! tt_init()");
exit(EXIT_FAILURE);
}
I tested with the HGM position and & is faster than %
The other bug was that the bestmove was not in the previous pv, example:
Code: Select all
..
info depth 4 score cp 795 nodes 3935 qnodes 2637 time 0 nps 3935 hashfull 0 pv f7e5
bestmove f7h6
..
Code: Select all
int bestmove;
int pv[64];
for (depth = 0; depth < MAX_DEPTH; depth++) {
score = search(..., pv); // <--- Here change
if (timeout) // it will not print that pv if timeout
break;
PrintUciInfo(..., pv);
}
bestmove = pv[0]; // here is the best move
printf("bestmove %s\n", strmove(bestmove));
Now I have problem with mate value, not work in all positions
Skiull http://skiull.blogspot.com
-
- Posts: 2554
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: Problems with TT, sometimes makes blunder moves
Well, that's not very efficient packing of tt entry.tttony wrote:sizeof(hash_entry_s) must be power of two to make the hash (key & size) work, now it's 32 bytesCode: Select all
typedef struct hash_entry_s { uint64_t key; int32_t move; int32_t score; int8_t depth; uint32_t flags; int16_t age; //uint64_t nodes; // only for perft } hash_entry_s;
A note about structure packing and alignment:
- a structure will be padded so that it's size is divisible by largest aligment necessary, in yout case uint64_t or 64 bits
- depth is 8 bit but followed by 32-bit flags, to conform to aligment flags will be aligned to 32 bits, so you waste 24 bits
(standard may not agree [reordering won't happen regardless], but 4/4 mainstream compilers do)
so a general rule would be to pack members in descending order of size (and thereby aligment): 64 bit then 32 bit then 16 bit then 8 bit
you can pack score in 16 bits using centipawns
packed move can fit in 16 bits as well
flags (assuming bound type) fits in 2 bits => 1 byte (you can even pack it together with age)
I believe it might be possible to achieve 8 bytes/entry with careful packing (but that'd require some additional magic).
Code: Select all
struct hash_entry
{
uint64_t key;
uint16_t move;
uint16_t score;
uint8_t depth;
uint8_t flags;
uint8_t age;
uint8_t unused;
}
Anyway, if your entry is 32 bytes then you can use a bucket of 2 entries (assuming your tt is 64-byte [cacheline] aligned)
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Problems with TT, sometimes makes blunder moves
No, it will work with any size of the hash entry. Because C pointer arithmetic works in multiples of the object size. You are not performing the AND operation on the address, but on the array index. As long as 'size' is a power of 2 (minus 1) it works.tttony wrote:sizeof(hash_entry_s) must be power of two to make the hash (key & size) work, now it's 32 bytes