chess:programming:de_bruijn_sequence
This is an old revision of the document!
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 Sequence on a Chess Board
References
chess/programming/de_bruijn_sequence.1635602393.txt.gz · Last modified: 2021/10/30 13:59 by peter