zobrist key and TT

Code, algorithms, languages, construction...
Post Reply
geko
Posts: 34
Joined: Mon Aug 01, 2011 5:11 pm

zobrist key and TT

Post by geko » Sat Jun 01, 2013 11:01 pm

Running the normal search many times the numbers of nodes are same, but
if regenerate the zobrist key with different random numbers, the nodes in search are different, this does not happen with others engine.

I've a bug in transposition table?

example of nodes:
first search

info score cp 0 depth 1 nodes 22 time 0 pv e2e4
info score cp 0 depth 2 nodes 84 time 1 pv e2e4 e7e5
info score cp 0 depth 3 nodes 661 time 1 pv e2e4 d7d5 e4d5
info score cp 0 depth 4 nodes 2571 time 5 pv d2d4 d7d5 e2e3 c7c6
info score cp 0 depth 5 nodes 13606 time 21 pv e2e4 d7d5 e4e5 e7e6 d2d4
info score cp 0 depth 6 nodes 20344 time 40 pv e2e4 d7d5 e4e5 f7f6 d1h5 e8d7 h5h3 e7e6
info score cp 0 depth 7 nodes 47748 time 76 pv e2e4 d7d5 e4e5 d5d4 f1b5 c8d7 b5e2 b8c6
info score cp 0 depth 8 nodes 440951 time 361 pv e2e4 e7e5 f1c4 b8c6 g1f3 f8b4 e1g1 f7f6
info score cp 0 depth 9 nodes 1207691 time 1101 pv d2d4 d7d5 e2e3 c8f5 c2c4 e7e6 c4d5 e6d5 f1b5 c7c6
info score cp 0 depth 10 nodes 921565 time 1679 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 c4d5 e6d5
info score cp 0 depth 11 nodes 1759248 time 2712 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 g1f3 c8d7 c4d5
bestmove d2d4 ponder d7d5

second search with new random numbers
info score cp 0 depth 1 nodes 22 time 0 pv e2e4
info score cp 0 depth 2 nodes 84 time 1 pv e2e4 e7e5
info score cp 0 depth 3 nodes 661 time 1 pv e2e4 d7d5 e4d5
info score cp 0 depth 4 nodes 2571 time 4 pv d2d4 d7d5 e2e3 c7c6
info score cp 0 depth 5 nodes 13606 time 19 pv e2e4 d7d5 e4e5 e7e6 d2d4
info score cp 0 depth 6 nodes 20344 time 39 pv e2e4 d7d5 e4e5 f7f6 d1h5 e8d7 h5h3 e7e6
info score cp 0 depth 7 nodes 47749 time 75 pv e2e4 d7d5 e4e5 d5d4 f1b5 c8d7 b5e2 b8c6
info score cp 0 depth 8 nodes 424805 time 344 pv e2e4 e7e5 f1c4 b8c6 g1f3 f8b4 e1g1 f7f6
info score cp 0 depth 9 nodes 1128129 time 1026 pv d2d4 d7d5 e2e3 c8f5 c2c4 e7e6 c4d5 e6d5 f1b5 c7c6
info score cp 0 depth 10 nodes 930673 time 1599 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 c4d5 e6d5
info score cp 0 depth 11 nodes 1733064 time 2606 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 g1f3 c8d7 c4d5
bestmove d2d4 ponder d7d5

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: zobrist key and TT

Post by hyatt » Sun Jun 02, 2013 6:15 am

geko wrote:Running the normal search many times the numbers of nodes are same, but
if regenerate the zobrist key with different random numbers, the nodes in search are different, this does not happen with others engine.

I've a bug in transposition table?

example of nodes:
first search

info score cp 0 depth 1 nodes 22 time 0 pv e2e4
info score cp 0 depth 2 nodes 84 time 1 pv e2e4 e7e5
info score cp 0 depth 3 nodes 661 time 1 pv e2e4 d7d5 e4d5
info score cp 0 depth 4 nodes 2571 time 5 pv d2d4 d7d5 e2e3 c7c6
info score cp 0 depth 5 nodes 13606 time 21 pv e2e4 d7d5 e4e5 e7e6 d2d4
info score cp 0 depth 6 nodes 20344 time 40 pv e2e4 d7d5 e4e5 f7f6 d1h5 e8d7 h5h3 e7e6
info score cp 0 depth 7 nodes 47748 time 76 pv e2e4 d7d5 e4e5 d5d4 f1b5 c8d7 b5e2 b8c6
info score cp 0 depth 8 nodes 440951 time 361 pv e2e4 e7e5 f1c4 b8c6 g1f3 f8b4 e1g1 f7f6
info score cp 0 depth 9 nodes 1207691 time 1101 pv d2d4 d7d5 e2e3 c8f5 c2c4 e7e6 c4d5 e6d5 f1b5 c7c6
info score cp 0 depth 10 nodes 921565 time 1679 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 c4d5 e6d5
info score cp 0 depth 11 nodes 1759248 time 2712 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 g1f3 c8d7 c4d5
bestmove d2d4 ponder d7d5

second search with new random numbers
info score cp 0 depth 1 nodes 22 time 0 pv e2e4
info score cp 0 depth 2 nodes 84 time 1 pv e2e4 e7e5
info score cp 0 depth 3 nodes 661 time 1 pv e2e4 d7d5 e4d5
info score cp 0 depth 4 nodes 2571 time 4 pv d2d4 d7d5 e2e3 c7c6
info score cp 0 depth 5 nodes 13606 time 19 pv e2e4 d7d5 e4e5 e7e6 d2d4
info score cp 0 depth 6 nodes 20344 time 39 pv e2e4 d7d5 e4e5 f7f6 d1h5 e8d7 h5h3 e7e6
info score cp 0 depth 7 nodes 47749 time 75 pv e2e4 d7d5 e4e5 d5d4 f1b5 c8d7 b5e2 b8c6
info score cp 0 depth 8 nodes 424805 time 344 pv e2e4 e7e5 f1c4 b8c6 g1f3 f8b4 e1g1 f7f6
info score cp 0 depth 9 nodes 1128129 time 1026 pv d2d4 d7d5 e2e3 c8f5 c2c4 e7e6 c4d5 e6d5 f1b5 c7c6
info score cp 0 depth 10 nodes 930673 time 1599 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 c4d5 e6d5
info score cp 0 depth 11 nodes 1733064 time 2606 pv d2d4 d7d5 e2e3 e7e6 c2c4 c7c6 f1e2 f8e7 g1f3 c8d7 c4d5
bestmove d2d4 ponder d7d5

If you change the Zobrist numbers it should always change the node counts, unless you test with such a large TT that overwriting never happens. It will certainly change my node counts in Crafty, as will changing the table size, or the replacement strategy... I would expect exactly the same behavior for any chess engine...

syzygy
Posts: 148
Joined: Sun Oct 16, 2011 4:21 pm

Re: zobrist key and TT

Post by syzygy » Sun Jun 02, 2013 5:40 pm

geko wrote:Running the normal search many times the numbers of nodes are same, but
if regenerate the zobrist key with different random numbers, the nodes in search are different, this does not happen with others engine.
This is normal. It does happen in all other engines.

The reason is simple: differs Zobrist keys means different positions map to the same entry or bucket of entries. If this is not enough explanation, then you need to spend some time trying to understand how hash tables work.

Post Reply