Testing Hash Table with perft

[Felpo]

Hi all,
I finally find the time to restart working on my engine. I rewrited it form scratch, starting from a move generator. Now it pass a lot of test without errors. As a next step, I implemented the hash tables with zobrist keys.
I decidet to test the quality using a perft version probing the hash table for the moves count already scanned. I' dont know if this is a good practice, let me know what you think about.
Anyway, a part some initial bugs, all seems work fine ( and pass the same tests I used for the regular perft, with some bug discovering position I found on the net ) but.... I decided to play a little more, and going deeper from the initial position: count is ok until perft 8... but at perft 9 the count breaks.
So the question: breaking perft 9 is still acceptable ? I know that at perft 9 from start position promotions starts to play, but other tests with near promotions works just fine...
A little more note: I use 21 bit from the Zobrist key to address the positions in the hash table, I have a key for any piece/color/square plus one for each castling and ep. To generate the random I used a twisted mersenne generator, attaching two int tro form a 64 bit long.
Thanks all !

[hgm]

How much of the key do you save in the hash table as signature? Using hash at some point you will get collisions that produce a wrong perft count.

To make sure that this is not the problem, you can use a second 64-bit key (e.g. calculated from swapping white and back Zobrists).

[Felpo]

Hi,
Thanks for interesting in my problem. Well, at present, and even if it is silly, I store the entire key in the hash entry as a confirm. So the collision I suppose to have should be the really bad ones: different tables whit same key... This should happen rarely ( or at least not so often to compromise a perft 9 ? ). I suspect there is some error in the incremental update, because when I had some error there I had wrong count even at perft 5.
I did a Zobrist incremental/recalc comparision sanity check, but running it at perft 9 will be eternous .

[smrf]

At http://www.chessbox.de/Compu/schachzahl4_e.html you will find some more perfted examples, maybe they could help to locate the problem.

[Felpo]

Well,
I'm debugging rigth now, and I found a really stupid missing ZKey update during the castling . If this is the problem, it is strange it will affect the perft count so far away...

[sje]

There have been at least TWO separate perft 11 calculations using different hash codes with 64 bit keys and both came up with the same result.

The probability of a false positive match with decently generated 64 bit keys is likely about the same as the probability of hardware failure.

[Felpo]

To Steven:
Thanks, this is such a statistic I was looking for. I did discover a bug in unpdating incrementally the key during castling. Now I'm doing the test at perft 9. Couriously the bug didn't produce errors at perft 8.


To Reinhald:
I know that site, is one of the reference used to do my test case, furthermore I use a test suite found, if I remember well, with Roce.
Thanks to all,
Felix

[sje]

For your convienience:

Code: Select all

[] emptran 9
Na3 85,849,641,909
Nc3 109,418,317,145
Nf3 108,393,009,416
Nh3 86,659,653,631
a3 74,950,758,099
a4 101,265,301,849
b3 96,577,095,997
b4 97,442,160,946
c3 108,697,368,719
c4 120,549,219,832
d3 176,976,245,463
d4 227,220,482,342
e3 259,522,947,791
e4 263,561,543,780
f3 68,094,899,093
f4 84,792,070,664
g3 99,646,370,024
g4 92,281,289,941
h3 74,778,417,365
h4 102,853,440,161
Depth: 9   Count: 2,439,530,234,167   Elapsed: 889.812  (2.74163e+09 Hz / 3.64747e-10 s)

[diep]

Hi all,
I finally find the time to restart working on my engine. I rewrited it form scratch, starting from a move generator. Now it pass a lot of test without errors. As a next step, I implemented the hash tables with zobrist keys.
I decidet to test the quality using a perft version probing the hash table for the moves count already scanned. I' dont know if this is a good practice, let me know what you think about.
Anyway, a part some initial bugs, all seems work fine ( and pass the same tests I used for the regular perft, with some bug discovering position I found on the net ) but.... I decided to play a little more, and going deeper from the initial position: count is ok until perft 8... but at perft 9 the count breaks.
So the question: breaking perft 9 is still acceptable ? I know that at perft 9 from start position promotions starts to play, but other tests with near promotions works just fine...
A little more note: I use 21 bit from the Zobrist key to address the positions in the hash table, I have a key for any piece/color/square plus one for each castling and ep. To generate the random I used a twisted mersenne generator, attaching two int tro form a 64 bit long.
Thanks all !

Really, testing hashtable performance with perft is not a very clever idea.

That's like measuring MTD performance on random search trees, instead of a good program (actually that's what happened to MTD) and cry victory based upon worlds most inefficient search.

Of course statistical it is the case that when something is really inefficient that some random tweak already works.

Don't read me wrong: MTD is a real invention.

Why not grab crafty source code to measure different hashtable setups, uncle Bob would be really wanting to help you out i bet.

Vincent

[hgm]

He is not measuring performance, but correctness...