de Bruijn numbers and Zobrist keys.

[Aleks Peshkov]

Last night I got an idea to use a set of 12 different 64-bit de Bruijn sequences for Zobrist keys. All 64 chessboard squares of a single piece-type are encoded as cycling shift of a single de Bruijn.

It is obvious that all 64 rotations of a single de Bruijn base number are different with a large Hamming distance value. I am not a mathematician, but I feel that it is possible to strictly prove, that all rotations of different de Bruijn sequences are never identical.

I think it is practically possible to found a magic 12-number de Bruijn set with a nice average Distance without testing all possible rotation combinations.

[Pradu]

It is obvious that all 64 rotations of a single de Bruijn base number are different with a large Hamming distance value. I am not a mathematician, but I feel that it is possible to strictly prove, that all rotations of different de Bruijn sequences are never identical.

For every de Bruijn sequence, there is atleast one other de Bruijn sequence which is a rotation of the original sequence. I think Gerd called these "even" and "odd" sequences.

[Gerd Isenberg]

Last night I got an idea to use a set of 12 different 64-bit de Bruijn sequences for Zobrist keys. All 64 chessboard squares of a single piece-type are encoded as cycling shift of a single de Bruijn.

It is obvious that all 64 rotations of a single de Bruijn base number are different with a large Hamming distance value. I am not a mathematician, but I feel that it is possible to strictly prove, that all rotations of different de Bruijn sequences are never identical.

I think it is practically possible to found a magic 12-number de Bruijn set with a nice average Distance without testing all possible rotation combinations.

A 64-bit De Bruijn sequence contains 64-overlapped unique 6-bit sequences, thus a ring of 64+5 bits. The five hidden "trailing" zeros are in fact common with the five leading zeros. There are 2^26 = 67108864 odd sequences with 6 leading binary zeros and 2^26 even sequences with 5 leading binary zeros, which may be calcutaled from the odd ones by shifting left one. All rotates left, except by zero or one, leave sequences not longer suited for magic bitscan - since the five leading zero condition no longer holds.

Without rotation, at least 7 bits are common in all 64-bit De Bruijns.
Since we need at least 12*64 keys, and there are 64 rotates (0..63) - there are 64 groups of 12 keys with at least 7 bits common. 64-bit De Bruijns contain 32 ones and 32 zeros. I guess varying popcounts, as provided by some mersenne twister or other random generators adds another degree of freedom in respect to minimize collisions.

I guess your idea may work reasonable since 12 out of 2^26 leaves some choices to pick "random" enough numbers. Anyway, due to the constrains with common bits and constant popcount, I believe De Bruijns and their rotates are not so well suited as "carefully" chosen random keys - you may effectivly "lose" some bits. Hamming distance does not necessarily reflect the "quality" of the zobrist keys.

[wgarvin]

Interesting. What would be the purpose of this? To avoid table lookups when incrementally updating the zobrist key for a move/unmove?

[Aleks Peshkov]

Without rotation, at least 7 bits are common in all 64-bit De Bruijns.

Can you describe what, where and why are the 7 bits property exist?

64-bit De Bruijns contain 32 ones and 32 zeros. I guess varying popcounts, as provided by some mersenne twister or other random generators adds another degree of freedom in respect to minimize collisions.

But the freedom have a cost: you have to test all 12*64 number in all permutations against collisions.

Anyway, due to the constrains with common bits and constant popcount, I believe De Bruijns and their rotates are not so well suited as "carefully" chosen random keys - you may effectivly "lose" some bits. Hamming distance does not necessarily reflect the "quality" of the zobrist keys.

De Bruijn have some nice mathematical properties that limit optimization search space, may be another regular binary function is better or it is possible to prove that de Bruijn sequence have a awfull weakness. But I am not rather happy with random numbers. Random numbers are good enough "in average", but we cannot prove that a given concrete random set is good or bad for the Zobrist hashing.

[Aleks Peshkov]

Interesting. What would be the purpose of this? To avoid table lookups when incrementally updating the zobrist key for a move/unmove?

I think table lookup is faster then anything else. I want to create a table of numbers that are mathematically proven to be good enough.

[Gerd Isenberg]

Can you describe what, where and why are the 7 bits property exist?

The most significant six binary zeros and LSB always set.

[Pradu]

Can you describe what, where and why are the 7 bits property exist?

In 64-bit de Bruijns, there must exist a sequence of 6 0s because 000000 is an index. This can be done by having 6 leading zeros or one zero in the LSB. The reason why the 6 0s can't be placed in the middle is because the index 100000 will occur twice, once because the LSB must be 1 (other wise 000000 will repeat twice), and the second time because there cannot be seven zeros in a row. Therefore, for odd de Bruijns, 6 leading 0s and the 1 after the 6 leading zeros, and also the LSB will be 1 leading to atleast 8 common bits among odd de Bruijns. Similarly for even de Bruijns, the 5 leading 0s, the 1 after the 5 leading zeros, the LSB, and the 1 in front of the LSB will be common leading to atleast 8 common bits among even de Bruijn.

[Gerd Isenberg]

Can you describe what, where and why are the 7 bits property exist?

In 64-bit de Bruijns, there must exist a sequence of 6 0s because 000000 is an index. This can be done by having 6 leading zeros or one zero in the LSB. The reason why the 6 0s can't be placed in the middle is because the index 100000 will occur twice, once because the LSB must be 1 (other wise 000000 will repeat twice), and the second time because there cannot be seven zeros in a row. Therefore, for odd de Bruijns, 6 leading 0s and the 1 after the 6 leading zeros, and also the LSB will be 1 leading to atleast 8 common bits among odd de Bruijns. Similarly for even de Bruijns, the 5 leading 0s, the 1 after the 5 leading zeros, the LSB, and the 1 after the LSB will be common leading to atleast 8 common bits among odd de Bruijn.

Yes, of course - there are even eight fixed bits, e.g. each odd De Bruijn starts with 0000001....B (0x02... or 0x03...) and has LSB set.

[Pradu]

Can you describe what, where and why are the 7 bits property exist?

In 64-bit de Bruijns, there must exist a sequence of 6 0s because 000000 is an index. This can be done by having 6 leading zeros or one zero in the LSB. The reason why the 6 0s can't be placed in the middle is because the index 000001 will occur twice, once because the LSB must be 1 (other wise 000000 will repeat twice), and the second time because there cannot be seven zeros in a row. Therefore, for odd de Bruijns, 6 leading 0s and the 1 after the 6 leading zeros, and also the LSB will be 1 leading to atleast 8 common bits among odd de Bruijns. Similarly for even de Bruijns, the 5 leading 0s, the 1 after the 5 leading zeros, the LSB, and the 1 in front of the LSB will be common leading to atleast 8 common bits among even de Bruijn.

Wouldn't allow me to edit my post after 15 mins so I'm double posting... Changed "index 100000 will occur twice" to "index 000001 will occur twice" (LSB right, MSB left).