How do I test the quality of the Zobrist keys?

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jesper_nielsen

How do I test the quality of the Zobrist keys?

Post by jesper_nielsen » Mon Sep 03, 2007 11:17 am

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

Alessandro Scotti

Re: How do I test the quality of the Zobrist keys?

Post by Alessandro Scotti » Mon Sep 03, 2007 11:45 am

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!

User avatar
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?

Post by hgm » Mon Sep 03, 2007 12:11 pm

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...).

Aleks Peshkov
Posts: 886
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: How do I test the quality of the Zobrist keys?

Post by Aleks Peshkov » Mon Sep 03, 2007 1:24 pm

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.

pijl

Re: How do I test the quality of the Zobrist keys?

Post by pijl » Mon Sep 03, 2007 2:03 pm

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:

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.

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: How do I test the quality of the Zobrist keys?

Post by bob » Mon Sep 03, 2007 2:23 pm

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.

User avatar
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?

Post by hgm » Mon Sep 03, 2007 2:42 pm

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 3:00 pm, edited 1 time in total.

Aleks Peshkov
Posts: 886
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: How do I test the quality of the Zobrist keys?

Post by Aleks Peshkov » Mon Sep 03, 2007 2:50 pm

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
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

Re: How do I test the quality of the Zobrist keys?

Post by pijl » Mon Sep 03, 2007 3:01 pm

Aleks Peshkov wrote:
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
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.

User avatar
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?

Post by hgm » Mon Sep 03, 2007 3:02 pm

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).
Nonsense. You would have the same problem with

Code: Select all

0xAAAAAAAA55555555
0xAAAAAAAAAAAAAAAA
0x55555555AAAAAAAA
0x5555555555555555

Post Reply