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
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!
As I did use a rather aggressive size reduction of my Zobrist-key table in micro-Max (making it a table of bytes, rather than 64-bit 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 64-byte arrays, independently assigning every square the status empty (50% probability), Pawn (25%) or a randomly chosen other piece, where furthermore non-empty squares were randomly assigned black or white color. For each of those I calculated the key, and hashed the full 64-byte strings and the full 64-bit 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 16-bit randoms, rather than the 32-bit on which I had counted...).
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 64-bit keys (and at least 10 for the 32-bit part, if this part is stored in TT). The better is better, but will need too much computation time.
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 64-bit keys (and at least 10 for the 32-bit 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:
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.
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.
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...
Last edited by hgm on Mon Sep 03, 2007 5:00 pm, edited 1 time in total.
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:
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 chess-position 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:
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 chess-position hash (all empty squares are encoded with implicit 0).
Forget about the 2nd key, it has no real meaning in this example.
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.
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 chess-position hash (all empty squares are encoded with implicit 0).
