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`, ...,

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)` =

Created by Ernst A. Heinz, Thu Dec 16 23:28:11 EST 1999