Zobrist key independence

[bob]

I had forgotten, but Burt Wendroff (LAChex chess program) wrote a paper and published it in the ICGA journal, on this very topic. Data would be FAR out of date today, as back then 8-10 plies was fairly good even for supercomputers...

[hgm]

Do you remember whether he discussed methods to reduce collisions by improving key independence? Or was it just about measuring the frequency of collisions within real chess trees?

[hgm]

Eliminating e.p. keys

It occurred to me that if one is really stingy, one could hide some of the four e.p. keys too:

It seems that not making accomodations for a second Queen would be asking for trouble. So in any case you would need to use 13 basis keys for constructing 64 Queen keys such that they are free from 4th-order dependency. The trick now is to encode the e.p. rights together with the Queen constellation, in the two-Queen sector. The idea is that in the game phase where there could be two Queens, e.p. captures are not very likely, and vice versa, so that we don't care very much if positions with 2 Queens can collide with positions that have e.p. rights. Positions with e.p. rights are rare anyway, and when a 2-Queen constellation can be mistaken for another (0-, 1- or 2-)Queen constellation with e.p. rights, the chances are pretty good that that position with e.p. rights in practice does not exist, because the Pawn constellation is not compatible with it.

So the idea is to use 14-bit instead of 13-bit proto-keys for the Queen, which allows construction of 72 (instead of 64) 4th-order-independent proto-keys. Unfortunately I did manage at most 69 such proto-keys with 13 bits. Of the 72 keys constructed from this, 64 will then serve as Queen keys, the remaining 8 as e.p. keys (one for each file). This guarantees that all constellations of 0 or 1 Queen, with or without e.p. rights, together with all constellations of 2 Queens and no e.p. rights, will have different hash key. (In so far that the 14 basis keys used for their construction were also fully independent.)

This means only a single extra basis key is needed to account for e.p. status.

[Gerd Isenberg]

Do you remember whether he discussed methods to reduce collisions by improving key independence? Or was it just about measuring the frequency of collisions within real chess trees?

Tony Warnock, Burton Wendroff (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1

Its about BCH Hashing. They used a BCH signature length of 81 (or more) bits to protect 16 bits from the full position string of 749 (64*12 - 2*2*8 + 4 + 8 + 1) bits, which is sufficient to avoid collisions within an 8 ply search. They refer "MacWilliams, Sloane (1981). The Theory of Error-Correcting Codes" for deeper insight

[hgm]

Interesting. I will try if I can find the article. I still have a box of old ICGA Journals somewhere.

Perhaps the methods can even be combined: what I address here is methods to redistribute key collissions in the key space, concentrating them in areas that are very unlikely to be sampled by actual search trees (e.g. because they involve positions with three Bishops), and that way rarifying them in the areas that matter. But this just reduces the set of keys that one would like to be as independent as possible from 749 to some 260. Perhaps the BCH method could be used to make those 260 as good as possible.

Exploiting color binding

BTW, it just occurred to me that about half the constellations with two Bishops (namely on the same shade) will be quite rare too. So dropping the requirement that their encoding should be unique would reduce the proto-key length for a Bishop pair from 13 to 12 bits, eliminating another two basis keys. That brings the number of required basis keys down to 2*(6 (K) + 48 (P) + 13 (N) + 12 (B) + 13 (R + castling) + 14 (Q + e.p.) ) + 1 (stm) = 213 keys. The price is greatly driving up the collision rate for positions with three N, B, R or Q, two Q with e.p. rights, or Bishop anti-pairs.

Better than bargained for?

I have the feeling that this scheme also ameliorates the effect of the unavoidable higher-order dependencies there will be in the basis keys. E.g. if we would have a 10th-order dependency there, (meaning there exist 10 keys in the set that XORed together produce 0), and the keys were directly used for squares, a position can be turned into another one with the same key by making 10 'point mutations' (i.e. adding or deleting the pieces on the squares corresponding to the involved key). And point mutations are easy to make in a chess tree (capture a piece, and move back). If a basis key represents a bit in in the proto-key for a pair of pieces, though, the flip of a bit of the proto-key in general will cause that key to encode a position where both pieces have a different location. Plus that there is a fair chance that the modified proto-key is invalid for any constellation of upto 2 pieces: the encoding of pairs with 13 bits is rather generous; in principle there are only 64*63/2 constellations of a pair of pieces, plus 64 of a single piece and one of none, total 2081 valid encodings out of 2^13 = 8192. So only 25.4% of the codes is valid, and in 3 out of 4 cases incorporating the alternative basis key that the dependency would also allow you would be ruled out. As this holds for any basis key that was representing a bit of a proto-key for a pair, the chances that the alternative way to make the total hash key out of basis keys would correspond to a valid position becomes really bleak. And for those that do, the number of point mutations to the board would in general be far higher than the number of replaced basis keys, making it more difficult to bridge the difference with chess moves.

I am now starting to wonder if an encoding scheme based on triples of pieces would not be superior because of this effect. It would need 42 more basis keys, no doubt lowering the order of the worst dependency in that set. But each basis key that can be substituted for another because of the dependency would have far less impact, as when it corresponded to a bit of a 3-piece proto-key it would almost always collide it with a 3-piece constellation, unreachable by chess moves. And you would not get a dramatic performance collapse on under-promotion.

[hgm]

Again e.p.

In what I said before over the e.p. keys I overlooked that these are not colored. So if we try to absorb those with the Queen keys, there is no need to absorb all 8 of them in the Queen keys for one color. We could absorb 4 in the Queen keys of white, and the other 4 in the Queen keys of black. As I wrote, a set of 13 proto-keys for describing a pair of pieces can be extended with 5 additional keys, ao no problem to fit half the e.p. keys in there. This means that positions with 2 Queens of the same color can still reliably have half of the e.p. rights, if the opponent only has a single (or no) Queen. Without using any extra basis key.

As was discussed in connection to castling rights, a triplet of pieces can absorb two extra keys. Which, in the case of Rooks can be used for castling. In a simlar way, the set of proto-keys for Knight and Bishop triplets could be expanded with 2 proto-keys (without any need to make those longer), for indicating e.p. rights. That way positions with e.p. rights would only compete with positions with three Knights or Bishops, which would probably be preferable over having them compete with positions with two Queens. With a triplet of Bishops we cannot exploit their color binding; only 1/4 of the positions can be discarded because they have all three on the same color, which is not enough reduction to get by with a 1-bit-shorter proto-key. So such a 'triplet encoding' would use 2*(6 (K) + 20 (N+e.p.) + 20 (B+e.p.) + 20 (R + castling) + 13 (Q) + 48 (P) ) + 1 (stm) = 255 basis keys.

There are 2^58 combinations of 10 (out of 255) basis keys, and slightly over 2^62 combinations of 11 keys. That means a set of 255 randomly chosen 64-bit basis keys will more often than not have no 11th-order dependency, and are at most 12th-order dependent. Each of the 12 mutations would often correspond to displacement of two pieces, or (even more often) growing one or two extra pieces (to bring the total to three), or creating an invalid key. If it involved a King key it could correspond to a large King displacement. This can be beefed up by shuffling the square numbers used to construct the King keys. Only for Pawn keys each key correspond to appearence or disappearence of a single Pawn somewhere. But Pawns are rather immobile pieces, and a position with an extra Pawn somewere else could very well be completely unreachable in any number of moves, even if it did appear on a square that was not already occupied by something else.

Unfortunately we often do not use all 64 key bits, though: with 32-bit signature and a 256MB hash table of 64-byte buckets (i.e. 4M = 2^22 buckets) we effectively only have a 54-bit key. But such a key still has a 40% chance of being free of 9th-order dependencies (9 keys can be chosen out of 255 in 1.2*2^53 ways), so that the worst dependency is 10th-order.

[hgm]

Improving the King keys

If we use the obvious numbering of board squares (a1=0, b1=1, ...) to derive the King keys for the squares, a1 and b1 would only differ (XOR-wise) by a single basis key, and could thus be confused if that basis key is involved in some high-order dependency with other basis keys. This would lead to confusion of positions that have a chess-wise difference of only a single move. This is not good, as it increases the chances that we collide with a position that is also in the tree. And this problem would exist no matter where the King is; there will always be a square next to it that differs only in the lsb of the file number, and one that will differ only in the lsb of the square number (e.g. on e4 you would have f4 and e3).

We can improve this by shuffling the square numbers before we use them to construct the King keys. If we view the bits of a 3-bit file number as coordinates in a 3-dimensional space, the numbers 0 to 7 will correspond to the corners of a cube in that space. These will be separated by an edge (12x), a face diagonal (12x) or a body diagonal (4x), with Hamming distance 1, 2 or 3, respectively. We can tabulate all the Hamming distances for a certain assignment of numbers to files:

Code: Select all

     a b c d e f g h
     0 3 5 6 2 1 7 4
     
a 0  - 2 2 2 1 1 3 1
b 3  2 - 2 2 1 1 1 3
c 5  2 2 - 2 3 1 1 1
d 6  2 2 2 - 1 3 1 1
e 2  1 1 3 1 - 2 2 2
f 1  1 1 1 3 2 - 2 2
g 7  3 1 1 1 2 2 - 2
h 4  1 3 1 1 2 2 2 -

The farther a table item is from the main diagonal of this table, the more King moves it would take to cover the distance, as Kings can move only a single file per turn. (Forget castling; that changes also many other things.) The only 1 close to the diagonal is the Hamming distance between the d- and e-file; all other 1s correspond to at least 3 King moves.

Note that cyclically shifting the numbering scheme 4 files (i.e. swapping the codes for abcd with those for efgh) leaves the table unaltered, and would be as satisfactory. The ranks could use the same numbering scheme.

To eliminate the d-e problem we now use different encoding of rank on the files a-d from what we use on the files e-h. And because the same HD=1 problem would occur when moving between ranks 4-5, we use different file numbering for ranks 0-4 and ranks 5-8. Another way of saying this is that we take a board that numbered the files and ranks as above, but then divide it into four 4x4 quarters, and shuffle these around. In octal:

Code: Select all

8  42 41 47 44 62 61 67 64
7  72 71 77 74 52 51 57 54
6  12 11 17 14 32 31 37 34
5  22 21 27 24 02 01 07 04
4  60 63 65 66 40 43 45 46
3  50 53 55 56 70 73 75 76
2  30 33 35 36 10 13 15 16
1  00 03 05 06 20 23 25 26
    a  b  c  d  e  f  g  h

We see that the d-e and 4-5 problem has disappeared by this; on crossing into another quarter we now always change both the file and the rank encoding, so at least 2 bits in the total encoding. The point is that all Hamming distances of files and ranks within a quarter are still 2, so that changing a single bit must always bring you to another quarter. And because the other (file or rank) then stays the same, you will always get a square that is four files or ranks away. So any single-bit change will need at least 4 King moves to bridge.

[hgm]

Some more musings about Kings

To be frank, I am not sure how much all this King stuff helps. The King really seems a special case, because you know there will always be one and only one. Suppose every King key would have a 6th-order dependency with the basis keys used for the other pieces. That means all positions collide with other positions that can be derived from it with 6 point mutations, one of those involving a King. But such positions will always contain an invalid number of Kings (usually 2), so they won't occur in the tree, and you don't care about the collision. To get a position you could collide with you would need at least two different King point mutations, and if both are 6th order, together these would cause 10 other point mutations, in addition to moving the King elsewhere (often over a large distance). That seems safe enough, as good as a 12th-order dependency.

So it seems calculating the 64 King keys as XORs of 5 randomly chosen basis keys used for the other pieces (one from each piece type of the same color), wouldn't be all that bad. The collisions resulting from that would all involve relocations / appearence / removal of pieces of the same color, so that you would need double the number of ply to reach those.

[hgm]

Some experimental data

I rigged up KingSlayer to do collect a bit of statistics on key collisions. Normally KingSlayer uses all 64 bits of the key and more (the incremental evaluation) to identify an entry, but to get enough collisions to be statistically relevant in a reasonable time I changed this a bit. It still stores the full 64 bit as signature, but I count a collision if only a certain sub-set of those bits match. (Hash probes are only accepted by the search, though, if the full key matches.) I count such a partial match as a collison when the other key bits are not the same. To be able to see what kind of positions collide, I also store the full position (packed in 32 bytes) in the TT. In case of a detected collision, both the sought position and the one in the TT are printed to a log file, like:

Code: Select all

0000000002000000000500000000b00a00000000000500000000000000000000 key=ea275f3c76b51c34 addr=00051c34
0000000000000005000000a00200b00000b00050000000000000000000000000 key=c51f5f3cc3c51c34 mask=000fffff

I used a shortened key of 39 bits: 20 bits in the index (addressing 1M buckets of 2 entries each), and 19 in the signature. Then I let the engine play out the KRRKNN end-game from the position, at 40 moves/min.

[d]8/8/3nn3/4k3/8/4KR2/4R3/8 w - - 0 1

This typically took about 80M nodes. At first I tried with the normal, randomly chosen Zobrist keys. This recorded 177 collisions in 78M probes, or 1 in 440K. This is about what one would expect with a 19-bit signature (probability for accidental match: 1 in 512K). Only 34 different collisions occurred; the others of the 177 were repetitions of those. Some collisions occured only once in the game, others many dozen times.

Then I tried to improve the keys of the Rooks and Knights, using 13 of their original 64 keys to construct a 'harmlessly dependent' set of 64 in the manner discussed here, and discarding the other 51 keys. This gave me 84 collisions in 60M probes. (The game length is not always the same, as the opponent (Fairy-Max) randomizes its moves.) That is 1 in 721K. Somewhat less, but not spectacular. In the 84 was a unique set of 30, about the same as with random keys.

For the next try I made sure the basis keys from which the pair keys were constructed were completely independent, by setting them to 1, 2, 4, 8, ... rather than to random numbers. Since I only had to bother about white Rooks and black Knights, I needed only 26 such independent keys, which with a key length of 39 is of course perfectly possible. The 2 x 64 King keys were still random 64-bit numbers. This reduced the number of collisions to 4 (1 in 22M) Apparently the quality of the basis keys from which the pair keys are constructed is quite important. The colliding positions were (5=wR, b=bN, 2=wK, a=bK):

Code: Select all

0000000500005000b0020000000000000000000000000000000000000000000a key=8837c939d13ba922 addr=000ba922
02000000000500000005000000000b0000b00a00000000000000000000000000 key=5e1fc9392f6ba922 mask=000fffff

000000000000000000020000000005b0000000b000000000000000a005000000 key=50c25d79ee4b46c5 addr=000b46c4
02000050000000000000000000000b0000005000000b0a000000000000000000 key=174a5d79b1eb46c5 mask=000fffff

0000000000050000002000000050000000b000000000000000a0000000000000 key=baa8ce99f5d15588 addr=00015589
00000500000000000000000002000000000050b00000b00000000000000000a0 key=0670ce99f7415588 mask=000fffff

500000000000000000000000000000000000b000020000a00000000000000000 key=b7b1facda496c37e addr=0006c37f
00000050000000000000000000000000000020000000000000a0000000000000 key=a0f9facde286c37e mask=000fffff

All of these have both Kings in a different location, which amounts to four point mutations. The Rooks and Knights also modify their location (or their number), but even if both pieces of a pair move, this could just be a consequence of the change of a single bit in the proto-key for their constellation. (It does mean that we have to be more unlucky for the distance between them could be bridged by chess moves within the tree, though.) Perhaps some improvement of the keys is still possible by not just assigning the protokeys randomly to the board squares, but in such a way that a single move of the piece type they are for would never result in flipping of a single bit in the proto-key. (As was discussed above for King, where the square numbers had the role of proto-keys.)

In the final test I also encoded the Kings by a 'harmlessly dependent' set of keys, which required 6 basis keys for each King. These basis keys were also chosen as 1ull<<N. This took 2*13 + 2*6 = 38 bits of the shortened key; the remaining bit was the stm key. (Which KingSlayer applies only to the index, not to the signature, effectively expanding the key to 65 bit.) As expected, this completely eliminated all collisions.

[chrisw]

Some experimental data

I rigged up KingSlayer to do collect a bit of statistics on key collisions. Normally KingSlayer uses all 64 bits of the key and more (the incremental evaluation) to identify an entry, but to get enough collisions to be statistically relevant in a reasonable time I changed this a bit. It still stores the full 64 bit as signature, but I count a collision if only a certain sub-set of those bits match. (Hash probes are only accepted by the search, though, if the full key matches.) I count such a partial match as a collison when the other key bits are not the same. To be able to see what kind of positions collide, I also store the full position (packed in 32 bytes) in the TT. In case of a detected collision, both the sought position and the one in the TT are printed to a log file, like:

Code: Select all

0000000002000000000500000000b00a00000000000500000000000000000000 key=ea275f3c76b51c34 addr=00051c34
0000000000000005000000a00200b00000b00050000000000000000000000000 key=c51f5f3cc3c51c34 mask=000fffff

I used a shortened key of 39 bits: 20 bits in the index (addressing 1M buckets of 2 entries each), and 19 in the signature. Then I let the engine play out the KRRKNN end-game from the position, at 40 moves/min.

[d]8/8/3nn3/4k3/8/4KR2/4R3/8 w - - 0 1

This typically took about 80M nodes. At first I tried with the normal, randomly chosen Zobrist keys. This recorded 177 collisions in 78M probes, or 1 in 440K. This is about what one would expect with a 19-bit signature (probability for accidental match: 1 in 512K). Only 34 different collisions occurred; the others of the 177 were repetitions of those. Some collisions occured only once in the game, others many dozen times.

Then I tried to improve the keys of the Rooks and Knights, using 13 of their original 64 keys to construct a 'harmlessly dependent' set of 64 in the manner discussed here, and discarding the other 51 keys. This gave me 84 collisions in 60M probes. (The game length is not always the same, as the opponent (Fairy-Max) randomizes its moves.) That is 1 in 721K. Somewhat less, but not spectacular. In the 84 was a unique set of 30, about the same as with random keys.

For the next try I made sure the basis keys from which the pair keys were constructed were completely independent, by setting them to 1, 2, 4, 8, ... rather than to random numbers. Since I only had to bother about white Rooks and black Knights, I needed only 26 such independent keys, which with a key length of 39 is of course perfectly possible. The 2 x 64 King keys were still random 64-bit numbers. This reduced the number of collisions to 4 (1 in 22M) Apparently the quality of the basis keys from which the pair keys are constructed is quite important. The colliding positions were (5=wR, b=bN, 2=wK, a=bK):

Code: Select all

0000000500005000b0020000000000000000000000000000000000000000000a key=8837c939d13ba922 addr=000ba922
02000000000500000005000000000b0000b00a00000000000000000000000000 key=5e1fc9392f6ba922 mask=000fffff

000000000000000000020000000005b0000000b000000000000000a005000000 key=50c25d79ee4b46c5 addr=000b46c4
02000050000000000000000000000b0000005000000b0a000000000000000000 key=174a5d79b1eb46c5 mask=000fffff

0000000000050000002000000050000000b000000000000000a0000000000000 key=baa8ce99f5d15588 addr=00015589
00000500000000000000000002000000000050b00000b00000000000000000a0 key=0670ce99f7415588 mask=000fffff

500000000000000000000000000000000000b000020000a00000000000000000 key=b7b1facda496c37e addr=0006c37f
00000050000000000000000000000000000020000000000000a0000000000000 key=a0f9facde286c37e mask=000fffff

All of these have both Kings in a different location, which amounts to four point mutations. The Rooks and Knights also modify their location (or their number), but even if both pieces of a pair move, this could just be a consequence of the change of a single bit in the proto-key for their constellation. (It does mean that we have to be more unlucky for the distance between them could be bridged by chess moves within the tree, though.) Perhaps some improvement of the keys is still possible by not just assigning the protokeys randomly to the board squares, but in such a way that a single move of the piece type they are for would never result in flipping of a single bit in the proto-key. (As was discussed above for King, where the square numbers had the role of proto-keys.)

In the final test I also encoded the Kings by a 'harmlessly dependent' set of keys, which required 6 basis keys for each King. These basis keys were also chosen as 1ull<<N. This took 2*13 + 2*6 = 38 bits of the shortened key; the remaining bit was the stm key. (Which KingSlayer applies only to the index, not to the signature, effectively expanding the key to 65 bit.) As expected, this completely eliminated all collisions.

That's interesting stuff. Any chance you could eventually generate these key sets for all pieces and publish? Maybe a collection of different sets. Then we could just upload and use as a resource, Muller-Keys.