Overlapped Zobrist keys array

[Rémi Coulom]

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

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.

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

[hgm]

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!

[Rémi Coulom]

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.

[wgarvin]

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.

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

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

[Jan Brouwer]

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

Code: Select all

inline u64 rotate_left(u64 x, int distance) { return (x << distance) | (x >> (64 - distance)); }

[hgm]

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.

[stegemma]

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 like it... good move!

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

[Gerd Isenberg]

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

Another thread about this topic from January this year:
http://www.talkchess.com/forum/viewtopic.php?t=26152

[jwes]

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.

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.

[hgm]

That Hamming distance of key pairs is completely meaningless is trivially proven:

XORing two keys K1 and K2 with the same constant C (so you get C^K1 and C^K2) preserves their Hamming distance. But take three keys from the set, and K1^K2^K3, and (C^K1) ^ (C^K2) ^ (C^K3) = C ^(K1^K2^K3). Now if you pick C = K1^K2^K3, the latter is zero. So the tranformed keys, which have just the same Hamming distance as the original keys, have K1^K2^K3 = 0, a dependency of the worst kind (part from two keys being equal).