wgarvin wrote:Interesting. What would be the purpose of this? To avoid table lookups when incrementally updating the zobrist key for a move/unmove?
I am also very interested in this, but not because of table lookups.
I am interested in finding what would be an optimal, or at least close to optimal, set of hash codes. One reason is that random is almost always pretty good, but might, on occasion, return a bad result (e.g., two zobrist keys that are very, very close.) Also, I would like my zobrist codes to stay the same between runs of the program so I always get the same results. Presently, I accomplish this by using a pseudo-random number generator and always giving it the same seed. But I have noticed that by changing the seed, sometimes I get better results form one seed than from another. Sure would be nice to find the best possability ...
De Bruijn sequence as a generator of 768 64-bit sets is not limited to 6-bit subsequence, we can freely construct a longer one and use a small part of it, knowing that this part is following the properties of the whole.
Aleks Peshkov wrote:De Bruijn sequence as a generator of 768 64-bit sets is not limited to 6-bit subsequence, we can freely construct a longer one and use a small part of it, knowing that this part is following the properties of the whole.
That sounds better. 128(+6)-bit or even 256(+7)-bit De Bruijns with 128 unique 7-bit or 256 unique 8-bit sequences and to chose some 64-bit subset with respect to Hamming distance and all recombinations of disjoint N-tuple keys with N let say from 2 to some max value to prove all xor-sums are not zero.
What about Hamming distance of all 768 keys is less/equal than Hamming distance of all 786*(786-1)/2 xor sums of all distinct two key-combinations - is that possible?
I did not order a back-issue from the Warnock/Wendroff paper yet. Of course Hamming distance is related to error correcting codes.
from rec.games.chess 1994
Tony Warnock
The following paper descibes a method of generating the numbers for a hash table. By using error correcting codes, we ensure that positions that are close on the board are not close in the hash space. Some experiments showed that we got an improvement in collision rate compared to using a random set of numbers.
MacWilliams and Sloane's book on error correcting codes has
the gory details about the theory and programming.
Tony Warnock & Burton Wendroff:
"Search Tables in Computer Chess"
ICCA Journal (March 1988), pp. 10-13.
Aleks Peshkov wrote:De Bruijn sequence as a generator of 768 64-bit sets is not limited to 6-bit subsequence, we can freely construct a longer one and use a small part of it, knowing that this part is following the properties of the whole.
That sounds better. 128(+6)-bit or even 256(+7)-bit De Bruijns with 128 unique 7-bit or 256 unique 8-bit sequences and to chose some 64-bit subset with respect to Hamming distance and all recombinations of disjoint N-tuple keys with N let say from 2 to some max value to prove all xor-sums are not zero.
What about Hamming distance of all 768 keys is less/equal than Hamming distance of all 786*(786-1)/2 xor sums of all distinct two key-combinations - is that possible?
online de Bruijn generator
I fear that we start to create some home-made pseudo-random function with unknown hidden properties. Knuth thinks that it is a big mistake. Too many freedom in search space to be lost.
