Zobrist key independence

[hgm]

Zobrist hashing requires roughly 64 (squares) x 6 (piece types) x 2 (colors) = 768 keys. (Actually 32 less, for the squares inaccessible by Pawns, but then you also need some keys for turn to move and castling / e.p. rights. With 64-bit keys there must always be collisions, as the number of possible chess positions is far larger than 2^64. (More like 2^160, actually.) For TT hashing we don't care too much, though, if there are collisions with keys for wildly different positions, as these will never occur in the same search tree. What does hurt are low-order dependencies, where just a few keys XORed together produce 0.

So we want a set of keys that is as free from the lowest-order dependencies as possible. Now we can take 8 different keys out of 768 in slightly over 2^61 ways (768!/(760!*8!)). With randomly chosen 64-bit keys there is a 1-in-2^64 probability for each of those XOR combinations of eight to be 0. So it is not too far-fetched that we will be spared the misfortune of having 8 keys that XOR to 0 (an 8th-order dependency). But having a 9th-order dependency seems unavoidable, as there are nearly 2^68 combinations of 9 keys possible, so that we expect 0 to be hit by them on average 16 times. The probability that it will then happen 0 times is exp(-16) or about 10^-7.

With a smaller number of keys the probability of those having a dependency of a given order of course becomes smaller. In a set of (say) 200 keys, one can select 10 of those in 200!/(190!*10!) ~ 2^54 ways. So with a random set of 200 64-bit keys you would almost certainly have no 10th-order dependency, and even the chances of having no 12th-order dependency would be pretty good.

Redistributing the pain

Now we can reduce the number of required independent keys enormously, by making use of the fact that in common chess positions some combinations of Zobrist keys can never occur, so that they do not need to be independent. E.g. there will surely be only a single King of each color, so only one of the 64 of its Zobrist keys can occur. We can construct the 64 King keys using only 6 keys from the 'maximally independent' set of keys (the 'basis keys'), by assigning a key to each bit of the square number, and then XORing all the keys corresponding to the bits in the square number that are 1. That will cause 3rd-order dependency in the King keys, but that doesn't matter, as there will only be a single one of those in the total key. So that the fact that that same contribution could also have been made by several pairs of keys (e.g. 1 = 2^3 = 4^5 = ...) is harmless: we cannot confuse it with positions that had two Kings, as these will not occur. Even the fact that a1 has the same key as an empty square is harmless: the confusion between a1 being King or empty will always be resolved by whether there is a King elsewhere.

For other pieces it is a bit more tricky. If we are willing to ignore positions with 'super-numerary' pieces (e.g. 3 Rooks; who would ever promote to Rook if he already has two?), we could in theory encode the Rook constellation in 12 bits (2 for each square number). But encoding those bits by a key for each, like with the King location, would not give a Zobrist encoding, as the Rooks would be considered distinguishable. What we are looking for is a set of 64 Zobrist 'proto-keys' without any 4th-order (or lower) dependencty. By primitive trial and error I was able to construct such a set o 16-bit keys: just generate 64 random 16-bit keys, and calculate and tabulate all XOR's of pairs of those (and single ones), to see if a duplicat occurs. If no two pairs give the same result, no four of them will give zero. The same algorithm applied to 15-bit keys did not give any result in decent time. (Perhaps expert in generation of magics would know how to do better!)

From this set of 64 proto-keys, plus 16 64-bit basis keys, one can construct 64 Rook keys as follows: assign each of the 16 basis keys to a bit of the proto-keys, and XOR those that correspond to set bits of the proto-key for a given square with each other to make the 64-bit key for that square. The same set of 64 proto-keys can be used for all piece types that are present in maximally two copies. I would think it acceptable for N, B, R and Q; this allows one super-numerary Q. But it would run the risk of confusing positions with 3 Knights with those that have a fewer number, although that risk is not very large: with 16-bit proto-keys to encode 2^11 constellations of two identical pieces, only 1/32 of the 2^16 possible proto-keys are used by the two-piece constellations. And the 3% of 3-Knight positions that would also be in use by a 2-Knight positions will likely have the two Knights in completely different locations, not likely to occur in the same tree. One could throw in a 17th basis key XORed into all 64 Knight keys; that would allow distinguishing positions with even and odd number of Knights, so that 3-Knight positions could only collide with single-Knight positions (which occupy only 64 out of 2^16 = 1/1024 of the proto-key space).

For Pawns one could simply use 48 basis keys, one for each square that can have a Pawn. The total number of basis keys needed to construct the 768-key set this way is thus 2*48 + 8*16 + 2*6 = 96 + 128 + 12 = 236 keys. The number of keys that we really want to be independent is thus reduced by more than a factor 3! The chances on even an 11th-order dependency in a so much smaller set are only 1 in 8, as one can choose 11 out of 236 basis keys in about 2^61 ways.

[D Sceviour]

I assume this was in response to the post on Hamming Distance. If the hamming distance of the zobrist keys are zero, then there is a likelihood of hash key failure, especially with lock-less hashing. As a curiosity, I tested the polyglot keys and found:

minimum hamming distance = 18
maximum hamming distance = 44
average hamming distance = 31

A set of 781 fully random 64-bit numbers produced:

minimum hamming distance = 19
maximum hamming distance = 46
average hamming distance = 32

[hgm]

Well, Hamming distance is completely irrelevant, as I explained in the other thread. (Except when it is 0, of course, which is just another way of saying they are equal). With 64-bit keys you can have perfect sets of 64 keys with all Hamming distances equal to 2, while you can have the worst possible dependence for unequal keys in a set of 4 keys with a minimum Hamming distance of 42.

What I propose here is just some elaboration on an idea I had in connection with the thread on 'dense board representations' used as hash keys.

[bob]

I think you were in that discussion with me (among others) when I first broached this subject here years ago. The point that was made was that pure hamming distance between two numbers is not so important unless you are only doing a 2 ply search. For a 3 ply search you would want every possible triplet to have the maximum hamming distance. With today's 30 ply searches being the norm, now you need every one of those combinations, from 2 to 30 plies to have the maximum hamming distance. This becomes pretty much nonsensical. And probably not doable unless you allow for a min of something _very_ small. Perhaps the question should be rephrased into "how many bits do we need in the signature to produce a minimum hamming distance of X given todays deep searches?"

Back when, I did this for any pair of Zobrist numbers, and I could not measure any improvement or change with my original set of numbers, where the only condition I look out for is no two numbers are equal. Using the max just between pairs, I ran thousands of test positions, and found no appreciable effect. Yes the node counts change, because the hash signatures change, which alters the transposition table replacements. Eventually, you and others convinced me that this was leading nowhere. I came to agree.

[hgm]

Yes, that is a good account of things.

BTW, I understand now why I could not find a set of 64 15-bit proto-keys without a 4th-order dependency. There are 635,376 combinations of 4 keys, so with a probability of 1/2^16 of being 0 one expects 9.7 of those to XOR to 0. The probability that none of those does is then exp(-9.7) = 1 in 16,000. So after on average 16,000 trials one expects to find the ' lucky combination'. That was doable. With 15 bits the expected number of 0 combinations doubles to 19.4, and the probability for having none becomes exp(-19.4) ~ 1 in 256 million. That just takes too many attempts.

One would need a more directed algorithm than just randomly trying, against such odds.

For up to 3 pieces all combinations of 6 proto-keys should be unequal to 0. There are ~75M such combinations. For a proto-key length of 23 bits that would give on average 75M/8M = 8.9 combinations equal to zero, so exp(-8.9) = 1/7613 probability that none do. That should make it easy to find one by ranomly trying. So one would need 23 basis keys to construct the 64 Zobrist keys or a piece type of which there can be 3. That is still nearly a factor 3 better than using a separate basis key for all 64.

In summary:
* a single piece requires 6 basis keys...
* a pair requires 16 basis keys...
* a triple requires 23 basis keys ...
... to guarantee that all constellations of that many pieces or fewer will make a different contribution to the hash key.

For Pawns all combinations of 8 proto-keys must be different, so all combinations of 16 proto-keys (out of 48) must be unequal to 0. There are 48!/(32!*16!) ~ 2^41 such combinations. In principle one could use the random try method to find a set of 48 38-bit proto-keys all combinations of which avoid 0. It would be too hard to generate all combinations of 8 keys (out of 48) and check those for duplicats, though. But what one can do is randomly generate a set of 43-bit proto-keys, and just take your chances with that. There would be a 75% probability that these do not contain any 16th-order dependency. And it would still save 5 keys over using 48 basis keys to encode the 43 proto-key bits.

Perhaps a more pragmatic approach for the Pwns would be to drop the requirement to uniquely encode Pawn structures with 6 Pawns (of the same color) in the same file, and such. E.g. only worry about positions with up to two equal-colored Pawns per file. There are 15 constellations of 2 Pawns in one file, 6 with one, and one with none, so 22 in total. It requires minimally 5 bits to encode that many different cases, and indeed 5 bit turns out to be enough: { 0D, 10, 15, 17, 1E, 1F } is a set of 6 proto-keys that provide unique encoding up to pairs. That would require 5 instead of 6 basis keys per file. Triple-Pawns could be confused with smaller Pawn constellations and themselves.

[ttruscott]

I could find a set of 64 13-bit keys pretty quickly. I'm not sure how to attach the program, but the idea is:

Have a list of n keys and a table of all-pairs of hashes of the n keys.
Repeat until n==64: find a "random" key that can be xor-ed with each of the n keys without conflicting with an existing hash, and then add it to the table so now there are n+1 keys.

It couldn't find a set of 12-bit keys, and suspect finding it "randomly" is unlikely.

There are some papers about goodness of Zobrist hashing ("tabulation hashing") but I think all the math assumes the keys are totally randomly generated. The papers say the average case is good and the worst case is unlikely. But suppose one has generated a set of keys. Wouldn't it be nice to know if they are accidentally bad? Suppose a set of 64-bit keys has all the lower-32 bits zero (yes, impossibly unlikely but ...). I'd say the "power" of the hash has been reduced to that of 32-bit keys. For a given set of keys it would be nice to be able estimate this reduction.

[ttruscott]

Uh oh, bug in program. Nevermind But really, I worry about non-random modifications to the keys unless the effects are well understood. E.g. it is temping to make color its own bit in the key. A feature is that one can immediately determine the side to move. But if all the positions being considered have white to move, the effectiveness of the hash is reduced by a full bit.

[hgm]

I would call the effect of what I propose here 'completely understood'. The basis keys are still completely random, so any square key built by XOR-ing those under control of the proto-keys would still be completely random. The only trick is that you use dependent keys (i.e. combinations of already existing keys) where this can never be expressed because the keys will never be used together due to the limitations on material composition. So that you will have fewer collisions between positions that do occur in a normal game.

And yes, it is a trade-off. It would probably completely wreck the engine for playing 3 Queens versus 7 Knights. (For which the evaluation would be no good anyway...)

I will try your algorithm, as indeed this looks more efficient.

As to veryfying the key set: with the conventional 768-key set it is quite feasible to hash all 75M combinations of 3 keys and look for a duplicat, detecting all 6th-order dependencies. There are 14G combinations of 4 keys, hashing all those would require really big memory. But I guess it could be done in parts at the expense of doing it repeatedly: just hash a certain range of an imaginary 32G table, ignoring every combination that falls outside of the range. Each table element would store the full 64-bit key, and an index collision would be re-hashed to the next free entry. That would catch all 8th-order dependencies. And, as I calculated, that is the best you can expect for purely random keys.

[hgm]

Your algorithm works great. I limited the attempt to add a new key to the set to 1000 tries, and start from scratch if it doesn't find one, to provide some primitive method of backtracking if it has painted itself in a corner:

Code: Select all

#include <stdio.h>

#define NKEY 64
#define NBIT 13

int ht[1<<NBIT], key[NKEY];

int try()
{
  int i, j, k, n;
  for(i=0; i<1<<NBIT; i++) ht[i] = 0;
  ht[0] = 1;
  for(i=0; i<NKEY; i++) {
    n = 0;
   retry:
    if(n++ > 1000) return 1;
    k = key[i] = rand()*rand()>>6 & (1<<NBIT)-1;;
    if(ht[k]) goto retry;
    for(j=0; j<i; j++) {
      int m = k ^ key[j];
      if(ht[m]) goto retry;
    }
    ht[k] = 1;
    for(j=0; j<i; j++) {
      int m = k ^ key[j];
      ht[m] = 1;
    }
  }
  return 0;
}

int main()
{
  int i;
  for(i=0; try(); i++) {
    if((i & 0xFFF) == 0) printf("%d\n", i); fflush(stdout);
    if(i > 1e6) return 0;
  }
  printf("solution found after %d tries\n", i);
  for(i=0; i<NKEY; i++) printf("%2d. %05x\n", i, key[i]);
  return 0;
}

For 13 bits it indeed finds a key set very fast (after 20 back-tracks). For 12 bits it doesn't find anything. Increasing the number of individual key retries to 10000 doesn't help.

This cuts another 8x3 = 24 keys from the basis set, leaving 212 keys. Plus whatever is needed for stm and castling / e.p. rights.

Hiding the castling-rights

BTW, the castling rights can be 'hidden' in the Rook keys: it is also possible to encode 66 rook states with 4th-order-independent 13-bit keys, adding keys for virgin_a1 and virgin_h1. The pure castling right is then the XOR of the virgin and non-virgin key for that square, and Rook moves / captures would always use the non-virgin key.

There are 9 e.p.-states, this requires 4 basis keys. Unfortunately there is one state too many to do with 3 basis keys.

[hgm]

How about piece triplets?

Using the same algorithm, but now for triples of keys, it was possible to generate a set of 20-bit proto-keys for 64 squares of which any XOR of three (or fewer) of those is unique. It could even find a set of 66 such proto-keys. (But with difficulty; it took 15k restarts, while 64 keys took only 24!) People that prefer to make accomodations for a third piece of a certain type can do this by means of 20 basis keys, instead of the usual 64. That is 7 more keys than are needed for for a pair of pieces, but then there is no performance degradation at all (rather than catastrophic failure) when a third piece of that type appears. This can even be done for Rooks + castling rights.

The required number of basis keys to allow up to three of each N, B, R, Q would then be 2*4*20 + 2*6 (Kings) + 2*48 (Pawns) + 4 (e.p.) + 1 (stm) = 269. A 10th-order dependency in a randomly chosen set of 64 such keys is unlikely; even for an 11th-order dependency the chances are about 60% to have it.