jwes wrote:One simple way to test the Zobrist keys is to add a second hash key to the hash entry. Then if the first key matches and the second does not, you have a false match and by comparing the number of false matches to the expected number, you can tell how good your Zobrist keys are. The advantage of this is that you can test your Zobrist keys in actual game play, which is where you really want them to work.
Another thing that just occurred to me is that if the problem with your Zobrist keys is in the bits used to generate the address, it will be seen not as excessive false matches, but as unbalanced loading of the hash table.
Instead of storing a second key, the entire board can be stored with 256 bits with four bits per square encoding. This will cover the case were both key sets are faulty or otherwise of poor quality.
Too many false matches will also show up with poor space utilization.
There is plenty of evidence that 64 bits is sufficient for current hardware. Consider: there have been lots of different deep movepath enumeration run (perft) using 64 codes and no record of false matches as all the counts are the same regardless of experimenter and program.
Last edited by sje on Thu Jan 22, 2009 8:53 pm, edited 1 time in total.
Your last point is the reason why I don't like to test the key in an actual engine hashing scheme. Either I just randomly generate Chess positions (placing the nominal number of Kings, Queens etc. randomly on a board), and fill a table with keys for them until I find a collissions (and then count these), or I just examine the keys themselves by looking for the smallest dependent subsets.
A related idea to test for validity is to purposely degrade the hash codes by having all but the bottom 24 or so bits be zero, and perhaps also shrinking the table entry count. This will introduce plenty of false matches that might otherwise take a year of testing with 64 bit codes.
The idea is to try and get the rest of the program to seize up early and often should false matches cause bad data to escape from the transposition system encapsulation.
This is what I usually do (shortening the key). My engines do not use 64-bit keys in the first place, as I only store a 32-bit signature, and the hash-bucket is identified by 21 bits (for 128MB hash). So that is only 53 bits.
That means that in general I already get dependencies in real life with some combinations of 6 keys. Which is just as well, as you can test that in a few minutes by putting all combinations of 3 keys in a hash table.
With a bit of luck, after a few tries, I don't have any collisions, meaning I have no 6-key dependences.
