Bitboard Infrastructure

DARKTHOUGHT makes extensive use of bitboards stored as 64-bit unsigned integers where each bit represents a square of the chess board numbered from a8 = 63 to h1 = 0. Because the bit length of integers differs between compilers, machines, and operating systems, DARKTHOUGHT defines a set of portable data types like unsigned 8, ..., unsigned 64 that are automatically mapped to the appropriate types of the target platform (e.g. unsigned 64 defaults to unsigned long long in GNU C).

In order to simplify the handling of bitboards, DARKTHOUGHT contains an abundant collection of functions and macros that provide efficient implementations of all the needed bitboard operations. Beside the basic bitwise AND, OR, XOR etc. the collection includes cascaded combinations thereof because they are frequently used and may even be executed in one cycle on some machines. The expression (x & ~y),^1.2 for instance, corresponds to a single DEC Alpha instruction. Other important bitboard operations enjoy marvelously simple yet non-obvious formulations due to the wonders of binary subtraction and the two's complement. Two famous members of this class are the expressions (b & -b) and (b & (b - 1)). The first clears all but the least significant 1-bit of a bitboard while the second clears only the least significant 1-bit.

Unfortunately, the central find-bit and population-count operations have higher algorithmic complexity. Although a few CPUs like Motorola PowerPC, Sun UltraSparc and the forthcoming DEC Alpha-21264 feature instruction-level support of these operations, most current machines still require software implementations. The efficiency of the implementations in terms of speed and memory consumption is of crucial importance for bitboard-based chess programs because it tends to limit their overall performance. In this respect, the short expression for clearing the least significant 1-bit gives rise to a neat formulation of an iterative population-count function.

unsigned int iterative_popcount(unsigned_64 b) {
    unsigned int n;
    for (n = 0; b != 0; n++, b &= (b - 1));
    return n;
}

If the given bitboard contains few 1-bits, the loop terminates quickly thus making this short and easily inlinable function run fast. Otherwise, DARKTHOUGHT prefers the following non-iterative formulation that stems from the well-known ``Hacker's Memory'' collection of programming tricks. It performs better than intuitive methods with lookup tables because the tables get either too large or need too many lookups.^1.3

#define m1 ((unsigned_64) 0x5555555555555555)
#define m2 ((unsigned_64) 0x3333333333333333)

unsigned int non_iterative_popcount(const unsigned_64 b) {
    unsigned_32 n;
    const unsigned_64 a = b - ((b >> 1) & m1);
    const unsigned_64 c = (a & m2) + ((a >> 2) & m2);
    n = ((unsigned_32) c) + ((unsigned_32) (c >> 32));
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
    n = (n & 0xFFFF) + (n >> 16);
    n = (n & 0xFF) + (n >> 8);
    return n;
}

The idea of this population-count trick can also be applied to the find-bit problem yielding a find-function without any memory accesses. Unfortunately, however, this find-bit function is slower than fine-tuned table lookups. As executed by DARKTHOUGHT the lookups generate negligible memory traffic and compile to roughly 15 machine instructions on a DEC Alpha while relying on the conditional data-move capabilities of modern CPUs. This clever find-bit implementation further exploits the fact that the number of the least significant 1-bit of a bitboard is equal to the number of the most significant 1-bit of the bitboard xor'ed with itself minus one: FIND LSB(b) = FIND MSB(b ^ (b - 1)).