chess:programming:de_bruijn_sequence
Table of Contents
Chess - Programming - de Bruijn Sequence
A de Bruijn Sequence represents all possible sequences of a given length in a way that is as compressed as possible.
It can be used to build a private bitScanForward routine, and to get the LSB (Least Significant Bit).
A chess board is conveniently 8 x 8 squares, and these can be represented by the numbers 0-63, which is a nice fit for a six-bit long De Bruijn sequence.
- 64-bit De Bruijn Sequences are 64(+5 wrapped)-bit strings, containing 64 overlapping unique sub-strings (ld(64)==6-bits).
- Because multiplying a De Bruijn Sequence with a single bit or power of two value acts like a shift left, this multiply with extracting the upper six bits by shift right 64-6=58 is a well known bitscan-approach to determine the index/position of a single isolated one in a 64-bit word.
- The are 67,108,864 == 0x4000000 == 2^26 Sequences with start index 0 and therefore last index 32 (last index requires wrap of the 5 upper bits, which are all zero).
- There are 64 times more sequences by rotating the initial one.
- So in total 2^32 possible 64*6bit De Bruijn Sequences!
De Bruijn for B(2,4)
The cyclic sequence 0000100110101111 of length 16 is a de Bruijn sequence for n = 4.
The 16 unique sub-strings of length 4 when considered cyclicly are:
0000,0001,0010,0100,1001,0011,0110,1101,1010,0101,1011,0111,1111,1110,1100,1000
Taking each 4-bits
0000100110101111
returns:
0000
0001
0010
0100
1001
0011
0110
1101
1010
0101
1011
0111
1111
1110
NOTE: The last 3 wraps around to the start to get the 4th digit.
de Bruijn values
| n | de Bruijn |
|---|---|
| 1 | 01 |
| 2 | 1100 |
| 3 | 00010111 |
| 3 | 01110100 |
| 4 | 0000100110101111 |
| 4 | 1111011001010000 |
| 5 | 11010100111011000101111100100000 |
| 6 | 0000001000011000101001111010001110010010110111011001101010111111 |
De Bruijn Sequence on a Chess Board
TODO
Why does the standard numbering equation for de Bruijn sequences give differing results for dB(16,4) and dB(2,16), when both are 16 bits? De Bruijn sequences are numbered by the equation dB(k,n) = ((k!)^(k^(n-1)))/(k^n). When we have dB(2,16), the computed value is of the order 2.1598E+9859 . For dB(16,4), the computed value is of the order 2.7629E+54556. Yet, both sequences are represented within just 64K bytes of memory. Only one of these computations can be correct.
References
chess/programming/de_bruijn_sequence.txt · Last modified: 2021/10/30 16:52 by peter