Chess - Programming - de Bruijn Sequence - Get De Bruijn Sequence

// Initial call: genDeBruijn(0, 64-6);
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
};

NOTE: 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.

Best results are found 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 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.