Author: Gerd Isenberg
Date: 05:09:21 12/30/03
Hi all,
64-bit De Bruijn Sequences are 64(+5 wrapped)-bit strings, containing 64
overlapping unique ld(64)==6-bit substrings. 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 (1).
I tried following recursive algorithm to determine De Bruijn Sequences and i was
very surprised about the amount:
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!
// initial call: genDeBruijn(0, 64-6);
// with empty doSomeThingWithDeBruijn it takes
// ~3 minutes on my Athlon XP2.8+
unsigned int foundCount= 0;
void genDeBruijn(BitBoard sequence, int bitpos)
{
static BitBoard uniqueCheck = 0;
unsigned int uniqueIdx = (unsigned int) (sequence>>bitpos) & 63;
if ( (uniqueCheck & bitmask[uniqueIdx]) == 0 )
{
if ( bitpos == 0 )
{
foundCount++;
doSomeThingWithDeBruijn(sequence);
}
else
{
uniqueCheck |= bitmask[uniqueIdx];
if ( bitpos == 1 )
{
genDeBruijn(sequence|1, 0);
}
else
{
genDeBruijn(sequence, bitpos-1);
genDeBruijn(sequence|bitmask[bitpos-1], bitpos-1);
}
uniqueCheck &= ~bitmask[uniqueIdx];
}
}
}
BitBoard bitmask[64] =
{
0x0000000000000001,0x0000000000000002,0x0000000000000004,0x0000000000000008,
0x0000000000000010,0x0000000000000020,0x0000000000000040,0x0000000000000080,
0x0000000000000100,0x0000000000000200,0x0000000000000400,0x0000000000000800,
0x0000000000001000,0x0000000000002000,0x0000000000004000,0x0000000000008000,
0x0000000000010000,0x0000000000020000,0x0000000000040000,0x0000000000080000,
0x0000000000100000,0x0000000000200000,0x0000000000400000,0x0000000000800000,
0x0000000001000000,0x0000000002000000,0x0000000004000000,0x0000000008000000,
0x0000000010000000,0x0000000020000000,0x0000000040000000,0x0000000080000000,
0x0000000100000000,0x0000000200000000,0x0000000400000000,0x0000000800000000,
0x0000001000000000,0x0000002000000000,0x0000004000000000,0x0000008000000000,
0x0000010000000000,0x0000020000000000,0x0000040000000000,0x0000080000000000,
0x0000100000000000,0x0000200000000000,0x0000400000000000,0x0000800000000000,
0x0001000000000000,0x0002000000000000,0x0004000000000000,0x0008000000000000,
0x0010000000000000,0x0020000000000000,0x0040000000000000,0x0080000000000000,
0x0100000000000000,0x0200000000000000,0x0400000000000000,0x0800000000000000,
0x1000000000000000,0x2000000000000000,0x4000000000000000,0x8000000000000000
};
This De Bruijn Sequence generator is very helpfull in finding constants, to do a
kind of double bitscan - finding move indices with from- and to-squares as
single isolated bit bitboards. I found best results so far with the difference
of the two bits, multiplying with some value based on the found DeBruijn
sequence, and shifting the product 64-N bits right.
idx = ((tobitboard - frombitboard) * f(deBruijn)) >> (64-N);
Even f(deBruijn) = deBruijn gives interesting result, but xor with some constant
pattern like 0x101010 is more promising.
Doing move-generation in Steffan Westcott's way, using direction wise sets for
sliding pieces, and with all disjoint piece sets, it is possible to get an index
range of 8K (8192 = 2*64*64). Each unique move index of this scheme does not
only map unique move from-to-squares, but also the kind of piece.
Cheers and a happy new year,
Gerd
(1) Charles E. Leiserson, Harald Prokop, Keith H. Randall:
"Using De Bruijn Sequences to Index a 1 in a Computer Word"
MIT Laboratory for Computer Science, Cambridge, MA 02139, USA
July 7, 1998
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.