Problems with TT, sometimes makes blunder moves

[hgm]

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.

[flok]

Hmmm.

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

With 256MB hash, embla rev 4080: manual aborted at depth 58, no sign of e1-f2.

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

1024MB hash:

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

with 4GB hash:

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

but with 8GB hash: (manual) aborted at depth 56

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

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)

[hgm]

Well, e1d2 wins just as much as e1f2, right?

[flok]

Oh I was under the impression that e1f2 was a better win or so.
Ok.

[Sven]

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

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.

2) So what was the second bug that you fixed that helped to make your TT work?

[mar]

Oh I was under the impression that e1f2 was a better win or so.
Ok.

Yes, both win (and I think it's ~the same number of moves)

[Sven]

Oh I was under the impression that e1f2 was a better win or so.
Ok.

Yes, both win (and I think it's ~the same number of moves)

Both are mate in 22 moves.

[tttony]

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

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.

2) So what was the second bug that you fixed that helped to make your TT work?

(key & size) did not work because struct hash_entry_s had an extra field called nodes to test perft only with (key % size)

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;

sizeof(hash_entry_s) must be power of two to make the hash (key & size) work, now it's 32 bytes

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);
}

With (key % size) is not necesary to have the struct power of two

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
..

That's because in the ID I have this: (pseudo)

Code: Select all

int bestmove;
int pv[64];
for &#40;depth = 0; depth < MAX_DEPTH; depth++) &#123;
    score = search&#40;..., pv&#41;; // <--- Here change
    if &#40;timeout&#41;                  // it will not print that pv if timeout
        break;

    PrintUciInfo&#40;..., pv&#41;;
&#125;
bestmove = pv&#91;0&#93;; // here is the best move

printf&#40;"bestmove %s\n", strmove&#40;bestmove&#41;);

I now just save the score in a global var only in the root (ply == 0)

Now I have problem with mate value, not work in all positions

[mar]

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;

sizeof(hash_entry_s) must be power of two to make the hash (key & size) work, now it's 32 bytes

Well, that's not very efficient packing of tt entry.
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;
}

fits in 128 bits (16 bytes) and you still have unused byte due to padding requirements.

Anyway, if your entry is 32 bytes then you can use a bucket of 2 entries (assuming your tt is 64-byte [cacheline] aligned)

[hgm]

sizeof(hash_entry_s) must be power of two to make the hash (key & size) work, now it's 32 bytes

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.