Zobrist key random numbers
Posted: Thu Jan 22, 2009 12:05 am
Has anyone done any sort of study (excluding the Wendroff/Warnock paper in the JICCA) on the random numbers you use for hashing?
I was looking for an assignment for a parallel programming course, and decided to use the random number generation of the Zobrist values as a relatively simple project. Crafty needs 788 numbers. 768 are used by the piece tables, 6 for each side, 64 squares per piece which is 12 * 64 or 768. I also have 16 EP target square random numbers that are used to alter the hash when an EP capture on a specific square is possible. Now up to 784. I then have 4 more for castling rights, since each side can castle to either side.
I first tested the basic numbers I get from the PRNG I use in Crafty, and discovered that the min hamming distance between any two numbers in that set was 14 bits which seemed low. I tested the numbers in two of the other programs I use for testing and found similar results. I then wrote a pretty brain-dead (but parallel) algorithm to start generating random numbers and replacing one of the original 788 if the new number increased the min hamming distance. I've had this running for about 2 hours and have raised the min hamming distance from 14 to 23. But at 23, the changes are becoming _very_ infrequent, and while each update improves the overall hamming distance average, pulling 23 up to 24 has not happened yet. I'm going to let this grind overnight on an 8-cpu machine to see if 24 is reachable.
My questions are:
(1) does anyone know how to compute the theoretical minimum hamming distance in a set of 788 64 bit numbers that can be produced? In my case, can this be raised to 24 or beyond? (I have the test set to stop when the PRNG starts to "cycle".
(2) has anyone tested their numbers and tried alternative generators to see if this can be improved on? I am currently using the existing Crafty PRNG, but am going to replace it with a 64 bit version from the internet when the current run goes long enough to convince me it is not going to improve things any further.
Once I get this done, I am going to release Crafty version 23.0, which will include these hard-coded numbers. The version number will change because this will break old opening books that used different RNs to produce the hash signatures stored in those books. Anyone can copy them if they want. But I am curious just how "good" these numbers can be...
I was looking for an assignment for a parallel programming course, and decided to use the random number generation of the Zobrist values as a relatively simple project. Crafty needs 788 numbers. 768 are used by the piece tables, 6 for each side, 64 squares per piece which is 12 * 64 or 768. I also have 16 EP target square random numbers that are used to alter the hash when an EP capture on a specific square is possible. Now up to 784. I then have 4 more for castling rights, since each side can castle to either side.
I first tested the basic numbers I get from the PRNG I use in Crafty, and discovered that the min hamming distance between any two numbers in that set was 14 bits which seemed low. I tested the numbers in two of the other programs I use for testing and found similar results. I then wrote a pretty brain-dead (but parallel) algorithm to start generating random numbers and replacing one of the original 788 if the new number increased the min hamming distance. I've had this running for about 2 hours and have raised the min hamming distance from 14 to 23. But at 23, the changes are becoming _very_ infrequent, and while each update improves the overall hamming distance average, pulling 23 up to 24 has not happened yet. I'm going to let this grind overnight on an 8-cpu machine to see if 24 is reachable.
My questions are:
(1) does anyone know how to compute the theoretical minimum hamming distance in a set of 788 64 bit numbers that can be produced? In my case, can this be raised to 24 or beyond? (I have the test set to stop when the PRNG starts to "cycle".
(2) has anyone tested their numbers and tried alternative generators to see if this can be improved on? I am currently using the existing Crafty PRNG, but am going to replace it with a 64 bit version from the internet when the current run goes long enough to convince me it is not going to improve things any further.
Once I get this done, I am going to release Crafty version 23.0, which will include these hard-coded numbers. The version number will change because this will break old opening books that used different RNs to produce the hash signatures stored in those books. Anyone can copy them if they want. But I am curious just how "good" these numbers can be...