How do I test the quality of the Zobrist keys?
Moderators: hgm, Dann Corbit, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
How do I test the quality of the Zobrist keys?
Hi Good People!
I recently had my very first confirmed zobrist key collision in an endgame with very few pieces. (Maybe i should start validating the moves retrieved from the hash table?!)
This got me thinking.
My Zobrist keys have been generated with a pseudo random generator provided by the dotnet framework.
Is there a way to determine if the keys are "good" or "bad"
And will it make a practical difference in the strength of an engine
Kind regards,
Jesper
I recently had my very first confirmed zobrist key collision in an endgame with very few pieces. (Maybe i should start validating the moves retrieved from the hash table?!)
This got me thinking.
My Zobrist keys have been generated with a pseudo random generator provided by the dotnet framework.
Is there a way to determine if the keys are "good" or "bad"
And will it make a practical difference in the strength of an engine
Kind regards,
Jesper
Re: How do I test the quality of the Zobrist keys?
Get the keys from Fruit and you should be fine. It should also be possible to use pseudo random keys though, if the generator is good (older versions of Glaurung include a good generator IIRC).
For Hamsters I have downloaded a few data sets from www.random.org and converted those to 64 bit integers, which is another viable option.
Make sure the collision depends on the key quality and not on a bug though!
For Hamsters I have downloaded a few data sets from www.random.org and converted those to 64 bit integers, which is another viable option.
Make sure the collision depends on the key quality and not on a bug though!
 hgm
 Posts: 25941
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: How do I test the quality of the Zobrist keys?
As I did use a rather aggressive size reduction of my Zobristkey table in microMax (making it a table of bytes, rather than 64bit integers) I did some testing to make sure this would not have any ill side effect. To this end I just generated random positions as 64byte arrays, independently assigning every square the status empty (50% probability), Pawn (25%) or a randomly chosen other piece, where furthermore nonempty squares were randomly assigned black or white color. For each of those I calculated the key, and hashed the full 64byte strings and the full 64bit key. On hits I then compared the strings, and counted the instances where they were different (meaning a key collision occured).
Later, for bug hunting in Joker I used a secondary key calculated as SUM PieceType*SqrNr*SqrNr. I stored this key in an extra field of the hash entry (added for the purpose), and compared it with the value calculated from the board, counting the number of differences. In my case the differences turned out to be due to an error in the differential update of the hash key (the null move would sometimes use the same update as the hash move), which I could have also caught by calculating the hash key from scratch and comparing it to the differentially updated value. But this way would catch other errors as well (and actually did, as it also turned out that the random routine I used only delivered 16bit randoms, rather than the 32bit on which I had counted...).
Later, for bug hunting in Joker I used a secondary key calculated as SUM PieceType*SqrNr*SqrNr. I stored this key in an extra field of the hash entry (added for the purpose), and compared it with the value calculated from the board, counting the number of differences. In my case the differences turned out to be due to an error in the differential update of the hash key (the null move would sometimes use the same update as the hash move), which I could have also caught by calculating the hash key from scratch and comparing it to the differentially updated value. But this way would catch other errors as well (and actually did, as it also turned out that the random routine I used only delivered 16bit randoms, rather than the 32bit on which I had counted...).

 Posts: 886
 Joined: Sun Nov 19, 2006 8:16 pm
 Location: Russia
Re: How do I test the quality of the Zobrist keys?
http://en.wikipedia.org/wiki/Hamming_distance
Your should maximize the worst popcount(Zobkey ^ Zobkey[j]) values. So, you need to generate a random value and test its Hamming Distance against all previous zobrist values. If the Distance is too small you drop this random number and try next. In one old CCC post I saw recommendation to keep distance at least 24 for 64bit keys (and at least 10 for the 32bit part, if this part is stored in TT). The better is better, but will need too much computation time.
Your should maximize the worst popcount(Zobkey ^ Zobkey[j]) values. So, you need to generate a random value and test its Hamming Distance against all previous zobrist values. If the Distance is too small you drop this random number and try next. In one old CCC post I saw recommendation to keep distance at least 24 for 64bit keys (and at least 10 for the 32bit part, if this part is stored in TT). The better is better, but will need too much computation time.
Re: How do I test the quality of the Zobrist keys?
Aleks Peshkov wrote:http://en.wikipedia.org/wiki/Hamming_distance
Your should maximize the worst popcount(Zobkey ^ Zobkey[j]) values. So, you need to generate a random value and test its Hamming Distance against all previous zobrist values. If the Distance is too small you drop this random number and try next. In one old CCC post I saw recommendation to keep distance at least 24 for 64bit keys (and at least 10 for the 32bit part, if this part is stored in TT). The better is better, but will need too much computation time.
Hamming distance is not everything.
Using the following (not so random numbers) have a great hamming distance, but a lousy value as zobrist key:
0xffffffffffffffff
0x0000000000000000
0xffffffff00000000
0x00000000ffffffff
As long as you have constellations like this in your zobrist set, you have a high probability of collisions (despite the high hamming distance).
So, you need to maximize the minimum number of keys that will xor to another key. I never did this analysis myself, but I can imagine that it may take a while to complete it.
Richard.
Re: How do I test the quality of the Zobrist keys?
One simple test is to measure the hamming distance between any two Zobrist numbers (hamming distance is the number of bits that are different between two binary values). The minimum hamming distance between pairs of numbers is an interesting value. If you have several pairs with very small hamming distances, you have a higher probability of a collision when you use those numbers.
For any single value, you can have a Zobrist number with a hamming distance of 64. (a and the binary complement of a, for example). I don't know that anyone has ever computed the minimum hamming distance between any two values in a set of N values. But if you have pairs with a distance of 1 or 2 or 3 (or even 0 heaven forbid) you need to replace one of those values.
For any single value, you can have a Zobrist number with a hamming distance of 64. (a and the binary complement of a, for example). I don't know that anyone has ever computed the minimum hamming distance between any two values in a set of N values. But if you have pairs with a distance of 1 or 2 or 3 (or even 0 heaven forbid) you need to replace one of those values.
 hgm
 Posts: 25941
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: How do I test the quality of the Zobrist keys?
I don't see this. So what if there are two randoms that only differ by 1 bit? And perhaps two others which differ in a single other bit. How would that increase the number of collisions? Would it be easier for all the other randoms to XOR into a value with a single 1 bit than to any other particular value? I don't think that is the case.
I agree with Richard. The only thing that matters is the smallest number of key components that can XOR to zero (and can occur together in the key, i.e. belong to different squares).
It still seems to me that in practice this number is so large that you could not find it through exhaustive search on all triples, quadruples, etc. The best way probably would be to just hunt for collisions with randomly picked subsets of key components until you find a collision (hashing as many keys as possible, comparing each new key to all keys you have stored). Once you find duplicates, remember them, and the reproduce the generation process, checking each key to the set of duplicates and save the full board position when you get a match. If on a later match you have a different board position, you had a collision. The number of differences between the board position will tell you how many randoms had to be XORed to produce the zero. Determine the minimum of this number over your run. If it seems suspiciously low compared to other collisions, try replacing one of the randoms in the set of differences, and repeat the procedure. Remember the randoms of the best run you had.
I suspect that in practice, it is exceedingly unlikely that you could ever improve on your first pick...
I agree with Richard. The only thing that matters is the smallest number of key components that can XOR to zero (and can occur together in the key, i.e. belong to different squares).
It still seems to me that in practice this number is so large that you could not find it through exhaustive search on all triples, quadruples, etc. The best way probably would be to just hunt for collisions with randomly picked subsets of key components until you find a collision (hashing as many keys as possible, comparing each new key to all keys you have stored). Once you find duplicates, remember them, and the reproduce the generation process, checking each key to the set of duplicates and save the full board position when you get a match. If on a later match you have a different board position, you had a collision. The number of differences between the board position will tell you how many randoms had to be XORed to produce the zero. Determine the minimum of this number over your run. If it seems suspiciously low compared to other collisions, try replacing one of the randoms in the set of differences, and repeat the procedure. Remember the randoms of the best run you had.
I suspect that in practice, it is exceedingly unlikely that you could ever improve on your first pick...
Last edited by hgm on Mon Sep 03, 2007 3:00 pm, edited 1 time in total.

 Posts: 886
 Joined: Sun Nov 19, 2006 8:16 pm
 Location: Russia
Re: How do I test the quality of the Zobrist keys?
The only problem value is 0. If your zobrist numbers have a good Hamming Distance against 0, the above problem is gone. This is because 0 is the most common implicit member of any chessposition hash (all empty squares are encoded with implicit 0).pijl wrote: Hamming distance is not everything.
Using the following (not so random numbers) have a great hamming distance, but a lousy value as zobrist key:
0xffffffffffffffff
0x0000000000000000
0xffffffff00000000
0x00000000ffffffff
Re: How do I test the quality of the Zobrist keys?
Forget about the 2nd key, it has no real meaning in this example.Aleks Peshkov wrote:The only problem value is 0. If your zobrist numbers have a good Hamming Distance against 0, the above problem is gone. This is because 0 is the most common implicit member of any chessposition hash (all empty squares are encoded with implicit 0).pijl wrote: Hamming distance is not everything.
Using the following (not so random numbers) have a great hamming distance, but a lousy value as zobrist key:
0xffffffffffffffff
0x0000000000000000
0xffffffff00000000
0x00000000ffffffff
Key 1 in the list is the same as key3^key4.
Isn't that a problem?
Hamming distance is irrelevant. Dependency between the bits is much more important.
Richard.
 hgm
 Posts: 25941
 Joined: Fri Mar 10, 2006 9:06 am
 Location: Amsterdam
 Full name: H G Muller
 Contact:
Re: How do I test the quality of the Zobrist keys?
Nonsense. You would have the same problem withAleks Peshkov wrote: The only problem value is 0. If your zobrist numbers have a good Hamming Distance against 0, the above problem is gone. This is because 0 is the most common implicit member of any chessposition hash (all empty squares are encoded with implicit 0).
Code: Select all
0xAAAAAAAA55555555
0xAAAAAAAAAAAAAAAA
0x55555555AAAAAAAA
0x5555555555555555