Zobrist key independence

[hgm]

Sure, if anything good comes out of this, I will surely make it public. But I don't know how far I am from having something that would work for a fully populated board, now that the experiment has shown how sensitive one is to the quality of the basis keys. For KRRKNN it is simple to make sure the basis keys used for the construction of the square keys are as independent as possible, as the key space is small enough to make them completely independent. It is not clear to me how I could guard against unlucky low order of a dependence in a set of some 200 keys. A set of 200 randomly picked 64-bit keys will on average contain some 5 13th-order dependencies. (You can select 13 keys out of 200 in 200!/(187!*13!) = 5*2^64 ways.) With the construction of proto-keys, however, we saw that a selective algorithm had no problem to find a set of 68 13-bit proto-keys free of 4th-order dependency. While you can pick 4 keys out of 68 in 99*2^13 ways. So you expect 99 4th-order dependencies, and then the probability to have none will be only exp(-99) < 1e-43. So by selective construction you can do far better than with random choice. But the algorithm worked by tabulating all products of all sub-sets of keys with a number of members half the order you want to avoid. For 2 out of 68 (to avoid 4th order) that is doable. For 7 out of 200 (to avoid any 14th-order dependency) it is not.

[hgm]

The effect of basis-key dependence

Even with 200 basis keys there must be dependencies: with 64-bit keys only 64 or fewer can be independent. For a random set we will almost certainly have several 13th-order dependencies, meaning there are XOR 'products' of 13 basis keys that equal zero. For basis keys that correspond to a Zobrist key for an individual square and piece type, this would correspond to appearence / disapperence of a piece on that square. For each basis key that corresponds to a bit in a proto-key for a pair or triplet, it could correspond to displacement of all the pieces, or disappearence or appearence of some. And there also is a fair chance that it corresponds to a proto-key that was not in use for the pair or triplet encoding (but could be formed only by a number of triplet or quadruple pieces of that type, respectively).

The board modification brought about by a basis key from a pair thus seems larger than that of a plain piece-square key, but we should keep in mind that disappearence of a piece corresponds to at least 2 chess moves, while relocating a single piece might only take one.

One way to ensure that the flip of a bit in a proto-key for a triplet causes a big change (i.e. large in the metric of chess moves), would be to make sure that for a 1- or 2-piece constellation it always results in the code for a 3-piece constellation (or is even invalid for that). This can be achieved by making sure the Hamming distance between the (XOR) product of every two proto-keys (or all single proto-keys) is at least 2. Then a single bit flip can never conver two 1- or 2-piece constellations into each other. That means we must get 3-piece constellations (or worse), and these are not really supposed to occur in the tree at all, or are only reachable through a (usually many moves distant) promotion. When we encode the Queen as a pair we would only have to give all 1-Queen constellations a minimum Hamming distance of 2, so that a bit-flip automatically produces the proto-key of a 2-Queen constellation.

A double bit flip in a triplet proto-key could still produce another 1- or 2-piece constellation, but the odds are against that: only 0.2% of all triplet codes corresponds to such constellations. The 3-piece constellations only make up 4%; in 96% of the cases flipping multiple proto-key bits would gives you a code that only one (or sometimes a few) 4-piece constellations could produce.

For pair proto-keys the conditionon Hamming distance turns out to be easy to achieve. A set of 68 independent 13-bit proto-keys can still be found with this additional condition on Hamming distance. (Fit for encoding Queen and e.p. rights.) To make triplet proto-keys with 20 bits is a bit harder; I could not get a solution for a set of 66 anymore, but 65 keys is still doable. But that means that the nice idea of indicating castling rights by two extra Rook states doesn't work anymore in triplet encoding.

When we use triplet encoding (and if we do that for the Rook we would almost certainly also do that for the Knights), we can still use an alternative trick: The castling keys can be identical to the keys for a Knight in the corner! (Or, in Chess960, in the start location of the Rooks.) Normally using a key twice gives the worst possible dependency; you can no longer distinguish whether the position has both traits or neither. But you cannot have castling rights if there is a Knight where the virgin Rook has to be, so 'both' is excluded. The down-side is that this castling right then competes with the possibility to have a third Knight. For this reason it would be preferable to use corner Bishop codes for the castling right rather than Knight codes, as there never is any reason to have a third Bishop in the opening phase (when castling is still possible). But this could also be the reason for not using a triplet code for the Bishops at all.

[chrisw]

Sure, if anything good comes out of this, I will surely make it public.

that would be good, because there’s quite a bit of specialist logic going into your solving this problem, which I am sure most of us won’t want to either have to either fully wrap our heads around, nor have to repeat. Once done once, the wheel (or better set of wheels) and so on.

Anyway, I name your potential full chess sets of hashes “Muller Hashes”.

But I don't know how far I am from having something that would work for a fully populated board, now that the experiment has shown how sensitive one is to the quality of the basis keys. For KRRKNN it is simple to make sure the basis keys used for the construction of the square keys are as independent as possible, as the key space is small enough to make them completely independent. It is not clear to me how I could guard against unlucky low order of a dependence in a set of some 200 keys. A set of 200 randomly picked 64-bit keys will on average contain some 5 13th-order dependencies. (You can select 13 keys out of 200 in 200!/(187!*13!) = 5*2^64 ways.) With the construction of proto-keys, however, we saw that a selective algorithm had no problem to find a set of 68 13-bit proto-keys free of 4th-order dependency. While you can pick 4 keys out of 68 in 99*2^13 ways. So you expect 99 4th-order dependencies, and then the probability to have none will be only exp(-99) < 1e-43. So by selective construction you can do far better than with random choice. But the algorithm worked by tabulating all products of all sub-sets of keys with a number of members half the order you want to avoid. For 2 out of 68 (to avoid 4th order) that is doable. For 7 out of 200 (to avoid any 14th-order dependency) it is not.

[Rebel]

I tried something else and so far have surprising results in the sense I got far less hash collisions than reported by Bob and HGM.

Instead of storing the whole board in the HT I calculate a checksum for the board, 64 squares, piece type * square number and store that value as a checksum in the HT. With a HT lookup the checksum should match, else collision.

Tried 46 positions average 30 seconds - 2 minutes and on only 4 occasions got just one collision, one position I got 2 collisons, one for white, one for black.

And now I am wondering why I get so few, notable with a 48 bit key (!)

For the record, I do store the whole key in the HT.

Addition - To test its reliability I tested it also without the castling rights and then (as it should) many collisions were reported.

[chrisw]

I tried something else and so far have surprising results in the sense I got far less hash collisions than reported by Bob and HGM.

Instead of storing the whole board in the HT I calculate a checksum for the board, 64 squares, piece type * square number and store that value as a checksum in the HT. With a HT lookup the checksum should match, else collision.

You must have already made a fix for square a1 = 0 ?

Tried 46 positions average 30 seconds - 2 minutes and on only 4 occasions got just one collision, one position I got 2 collisons, one for white, one for black.

And now I am wondering why I get so few, notable with a 48 bit key (!)

For the record, I do store the whole key in the HT.

Addition - To test its reliability I tested it also without the castling rights and then (as it should) many collisions were reported.

[hgm]

How many collisions did you expect, based on the number of buckets in your hash table, and the number of hash probes done?

[Rebel]

I tried something else and so far have surprising results in the sense I got far less hash collisions than reported by Bob and HGM.

Instead of storing the whole board in the HT I calculate a checksum for the board, 64 squares, piece type * square number and store that value as a checksum in the HT. With a HT lookup the checksum should match, else collision.

You must have already made a fix for square a1 = 0 ?

No!

But square a1 in my board concept is "1"

[chrisw]

I tried something else and so far have surprising results in the sense I got far less hash collisions than reported by Bob and HGM.

Instead of storing the whole board in the HT I calculate a checksum for the board, 64 squares, piece type * square number and store that value as a checksum in the HT. With a HT lookup the checksum should match, else collision.

You must have already made a fix for square a1 = 0 ?

No!

But square a1 in my board concept is "1"

How very Roman of you!

[Rebel]

How many collisions did you expect, based on the number of buckets in your hash table, and the number of hash probes done?

Some stats:

Code: Select all

POS     HT lookups     Found Keys       Collisions
Pos 1   21.558.717   2.855.652 (13%)         0
Pos 2   50.555.311   5.499.316 (10%)         0
Pos 3   58.852.315   7.175.444 (12%)         0
Pos 4   75.216.172  14.076.588 (18%)         1

What did I expect you ask, well, with only a 48 bit key a lot more than you and Bob reported.

[hgm]

But what I reported was for a key that was artificially shortened to 39 bits. The other bits just served the function of your check sum, to detect collisions. So with 48 bits you should expect far fewer collisions than I reported.

The key issue is how large your hash table was. If you had only 1 bucket, with an 48-bit key you would expect only 1 collison in 256 billion probes. If you had 16M buckets you would expect 16M times as many, i.e. one collision every 16M probes.