Overlapped Zobrist keys array
Moderators: hgm, Rebel, chrisw
-
- Posts: 27814
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Overlapped Zobrist keys array
What I don't like about the Polyglot scheme is that it requires a pre-defined table of 64-bit numbers. It would be much better to have a scheme based on Zobrists generated from some simple iterative pseudo-random number generator, like r[n+1] = MAGIC_CONST1*r[n] + MAGIC_CONST2*r[n-1], or something like that, where you would need only two magic constants and a start value to generate the entire set.
-
- Posts: 438
- Joined: Mon Apr 24, 2006 8:06 pm
Re: Overlapped Zobrist keys array
I never tried this myself, but error-correcting codes provides a lot of theory about Zobrist hashing. In his PhD thesis, Jean-Christophe Weill mentioned using BCH codes for his chess program.stegemma wrote:But, if we have less keys, wath about to compute the best ones, instead to generate them randomly? thinking on the way keys will be overlapped, maybe, maybe De Bruijn sequences can be used....
http://www.recherche.enac.fr/~weill/pub ... dJCW.ps.gz
(in French)
http://en.wikipedia.org/wiki/BCH_code
I never tried to understand, but it looks very interesting.
I doubt that maximizing Hamming distance is optimal.
Rémi
-
- Posts: 27814
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Overlapped Zobrist keys array
Actually _maximizing_ Hamming distance is totally disastrous. This was discussed here before: there exists an algorithm to generte a set of keys with maximum Hamming distance for a iven number of keys and key length. But then every key turns out to be the XOR of two other keys from the set!
-
- Posts: 438
- Joined: Mon Apr 24, 2006 8:06 pm
Re: Overlapped Zobrist keys array
https://chessprogramming.wikispaces.com/BCH+Hashing
is an interesting read, too.
Rémi
edit: unfortunately, the paper is not available for download. the table on page 63 of JCW's PhD thesis is interesting. It indicates that BCH codes of size 51 perform as well as random codes of size 67, in terms of the number of protected bits.
is an interesting read, too.
Rémi
edit: unfortunately, the paper is not available for download. the table on page 63 of JCW's PhD thesis is interesting. It indicates that BCH codes of size 51 perform as well as random codes of size 67, in terms of the number of protected bits.
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Overlapped Zobrist keys array
I thought this had been debunked? What matters is whether two *combinations* of various table entries can collide, not how close two individual table entries come to colliding. Hamming distance is not a very effective predictor of this. (IIRC its not hard to construct a set of keys with high hamming distance between all pairs, that still have high numbers of collisions. Searching old threads here will probably turn up some examples?)plattyaj wrote:The concept that needs to be preserved in any approach to hash keys is that you want to have a large Hamming distance between one key and another:
http://en.wikipedia.org/wiki/Hamming_distance
If you can generate a set of keys that have a good hamming distance it will work fine for the hash table.
Now, why you would write an assembler program and then add the overhead of reading unaligned words and shifting is another matter
Andy.
[Edit: okay, say you have three entries for white pawns on C4,D5,E6. Choose two random numbers for C4 and D5. Then XOR those together and use the result for E6. Any two of those keys should have a decent hamming distance between them, and yet any position with those three pawns will have the same zobrist key as the equivalent position with them removed.]
Consider this: On any given square, at most one piece can be present at any time. So you have 12 different entries that represent a piece on that square, but no two of those entries are going to be combined at the same time into any zobrist key for a chess position. They need to be different, but the amount of independence between them is irrelevant. But if you consider the 64 entries for a given piece type+color, it is probably more relevant to minimize collisions of pairs or triples of those.
Also consider: a chess position may have as many as 8 pawns of a color, but it is unlikely to have more than 2 queens or 3 other pieces. So it may be more important to pick the 64 pawn entries for each color so that they are "hard" to get collisions among (when some combination of them are combined together) compared to picking the 64 entries for some other piece type.
But in practice, all of this is moot, because choosing good random numbers (using a good PRNG, not something stupid like srand!) gives great results. I don't recall anybody showing a systematic way of choosing zobrist table entries that actually gives noticably lower numbers of collisions than simply choosing random 64-bit values for each entry.
-
- Posts: 201
- Joined: Thu Mar 22, 2007 7:12 pm
- Location: Netherlands
Re: Overlapped Zobrist keys array
You can take this to its logical conclusion: use a single 64 bit value per color/piece combination, and rotate it by the square number. This only takes 96 bytes in total.
The processor rotate instructions can be accessed via a compiler intrinsic, or you can use e.g. in C++:
The processor rotate instructions can be accessed via a compiler intrinsic, or you can use e.g. in C++:
Code: Select all
inline u64 rotate_left(u64 x, int distance) { return (x << distance) | (x >> (64 - distance)); }
-
- Posts: 27814
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Overlapped Zobrist keys array
Well, this is very close to the 63-bit overlap scheme, that gave very poor reslt when I tried it. But perhaps it would perform better if you would use DeBruijn numbers; I did not try that.
-
- Posts: 859
- Joined: Mon Aug 10, 2009 10:05 pm
- Location: Italy
- Full name: Stefano Gemma
Re: Overlapped Zobrist keys array
I like it... good move!Jan Brouwer wrote:You can take this to its logical conclusion: use a single 64 bit value per color/piece combination, and rotate it by the square number. This only takes 96 bytes in total....
I thanks all the ones who answer in this thread. I've read the suggested links, someone is too complex, for my matematical knowledge, but i've found some usefull information.
So the idea of overlapped Zobrist key is almost good and some other people already uses this method, in various forms. Maybe combining overlapped keys, rotations and De Bruijn sequences can give some interesting result. Anybody wants to try can give us a feedback...
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Overlapped Zobrist keys array
Another thread about this topic from January this year:stegemma wrote:I would like to add to my program a transposition table and i'm studying Zobrist key. The first thing i've seen is that this method requires
http://www.talkchess.com/forum/viewtopic.php?t=26152
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Overlapped Zobrist keys array
The only quality that the Zobrist keys need is a collision rate that is not significantly above the theoretical minimum. This is easily measured experimentally, and you do not have to worry about any correlation between Hamming distances between pairs of keys and minimum collision rate.plattyaj wrote:The concept that needs to be preserved in any approach to hash keys is that you want to have a large Hamming distance between one key and another:
http://en.wikipedia.org/wiki/Hamming_distance
If you can generate a set of keys that have a good hamming distance it will work fine for the hash table.
Andy.