I'm making this chess engine, well, attempting to make a chess engine. A few of the confusing things that keep popping up are these seemingly arbitrary arrays of numbers from 0 to 63, the so-called "De Bruijn sequence" and a function that no one on the internet seems to understand fully. A person tried to figure it out here. the code goes like this:
const int BitTable[64] = {
63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
58, 20, 37, 17, 36, 8
};
int pop_1st_bit(uint64 *bb) {
uint64 b = *bb ^ (*bb - 1);
unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
*bb &= (*bb - 1);
return BitTable[(fold * 0x783a9b23) >> 26];
}
uint64 index_to_uint64(int index, int bits, uint64 m) {
int i, j;
uint64 result = 0ULL;
for(i = 0; i < bits; i++) {
j = pop_1st_bit(&m);
if(index & (1 << i)) result |= (1ULL << j);
}
return result;
}
the post I specified above did a great deal of explaining what the code is doing (finding the least significant bit and turning it into a 64 array index and vice versa), but it is still a mystery as for the how it's doing it. The origins of the mysterious BitTable[64] array and the 0x783a9b23 magic number are up in the air.
To add further confusion that is not the only mysterious array and magic number that pops up in chess programming, here are a few more taken from the chess programming wiki:
const int index64[64] = {
0, 1, 48, 2, 57, 49, 28, 3,
61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22,
45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16,
54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10,
25, 14, 19, 9, 13, 8, 7, 6
};
/**
* bitScanForward
* @author Martin Läuter (1997)
* Charles E. Leiserson
* Harald Prokop
* Keith H. Randall
* "Using de Bruijn Sequences to Index a 1 in a Computer Word"
* @param bb bitboard to scan
* @precondition bb != 0
* @return index (0..63) of least significant one bit
*/
int bitScanForward(U64 bb) {
const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
assert (bb != 0);
return index64[((bb & -bb) * debruijn64) >> 58];
}
That 25 year old code uses a whole different array of seemingly random numbers and the "magic number" 0x03f79d71b4cb0a89 (?) and shifts a bit expression bb & -bb by 58 of all numbers (why!?). here's another one:
const int index64[64] = {
0, 47, 1, 56, 48, 27, 2, 60,
57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44,
38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53,
34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24,
13, 18, 8, 12, 7, 6, 5, 63
};
/**
* bitScanForward
* @author Kim Walisch (2012)
* @param bb bitboard to scan
* @precondition bb != 0
* @return index (0..63) of least significant one bit
*/
int bitScanForward(U64 bb) {
const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
assert (bb != 0);
return index64[((bb ^ (bb-1)) * debruijn64) >> 58];
}
The same confusing "magic number", but a different array and bit expression bb ^ (bb-1). And of course, another one.
const int lsb_64_table[64] =
{
63, 30, 3, 32, 59, 14, 11, 33,
60, 24, 50, 9, 55, 19, 21, 34,
61, 29, 2, 53, 51, 23, 41, 18,
56, 28, 1, 43, 46, 27, 0, 35,
62, 31, 58, 4, 5, 49, 54, 6,
15, 52, 12, 40, 7, 42, 45, 16,
25, 57, 48, 13, 10, 39, 8, 44,
20, 47, 38, 22, 17, 37, 36, 26
};
/**
* bitScanForward
* @author Matt Taylor (2003)
* @param bb bitboard to scan
* @precondition bb != 0
* @return index (0..63) of least significant one bit
*/
int bitScanForward(U64 bb) {
unsigned int folded;
assert (bb != 0);
bb ^= bb - 1;
folded = (int) bb ^ (bb >> 32);
return lsb_64_table[folded * 0x78291ACF >> 26];
}
That one has a different array, magic number, and bit shifts it by 26 (again, why!?). the point is, I want to know how do people come up with these arrays and numbers, that is the core of my question. I am aware that there are some high-level mathematics involved, but surely you don't have to have a Phd in computer science to pick up a hobby in chess programming... right?
