Bitboards for Chess, in depth: square mapping, set-wise move generation, magic and PEXT sliders, and perft testing

Mapping squares to bits

The first decision is which bit is which square. The most common choice is little-endian rank-file (LERF): a1 is bit 0, b1 is bit 1, h1 is bit 7, a2 is bit 8, and h8 is bit 63. A square's index is 8 * rank + file with both counted from zero. With this mapping, moving one rank north is a left shift by 8, one file east is a left shift by 1, and the diagonals are shifts by 7 and 9.

A position is then a dozen bitboards, one per piece type and colour, plus derived sets kept in sync: white = OR of white pieces, black, and occupied = white | black. Side to move, castling rights, en passant square and move counters are stored alongside. Many engines also keep a 64-entry mailbox array (which piece is on square s) because answering that question from twelve bitboards takes up to twelve tests.

Shifts, masks and knights

Shifts are not quite enough on their own, because the board is 8 squares wide but the integer is one long line. Shifting h1 east by 1 lands on a2, a different rank. The fix is to mask out squares that would wrap. Shifting east, clear anything that lands on the a-file; shifting west, clear the h-file. Knights jump two files, so they also need masks for the a- and b-files, and for the g- and h-files.

M64 = (1 << 64) - 1                      # Python ints are unbounded; C uses uint64_t
FILE_A = 0x0101010101010101
FILE_H = FILE_A << 7
NOT_A  = ~FILE_A & M64
NOT_H  = ~FILE_H & M64
NOT_AB = ~(FILE_A | FILE_A << 1) & M64
NOT_GH = ~(FILE_H | FILE_H >> 1) & M64

def north(b): return (b << 8) & M64
def south(b): return b >> 8
def east(b):  return (b << 1) & NOT_A & M64
def west(b):  return (b >> 1) & NOT_H

def knight_attacks(b):
    """Attack set of every knight in b at once."""
    return (((b << 17) & NOT_A)  | ((b << 15) & NOT_H) |
            ((b << 10) & NOT_AB) | ((b << 6)  & NOT_GH) |
            ((b >> 15) & NOT_A)  | ((b >> 17) & NOT_H) |
            ((b >> 6)  & NOT_AB) | ((b >> 10) & NOT_GH)) & M64

def squares(b):
    """Iterate set bits: isolate the lowest, then clear it."""
    while b:
        lsb = b & -b
        yield lsb.bit_length() - 1
        b &= b - 1

assert knight_attacks(1 << 6) == 0xA01000      # g1 -> e2, f3, h3

The masks follow the destination: a jump that moves east must not land on the files it would wrap into. The final & M64 matters only in Python; in C the shifts on uint64_t drop overflowing bits automatically. The bit iteration idiom, b &= b - 1 to clear the lowest set bit, compiles to a single BLSR instruction on CPUs with BMI1, and finding the index is a count of trailing zeros. In C these are __builtin_ctzll and __builtin_popcountll; C++20 adds std::countr_zero and std::popcount.

In practice engines precompute knight and king attacks into 64-entry tables at startup, because a table load is cheaper than eight shifts. The set-wise form above remains useful in evaluation, for example to compute every square attacked by all white knights in one expression.

Set-wise pawn moves

Pawns are where set-wise generation shines. All white single pushes are one expression, and double pushes are a second push restricted to pawns that just reached the third rank:

RANK_3 = 0x0000000000FF0000
RANK_8 = 0xFF00000000000000

def white_pawn_moves(pawns, empty, enemy):
    single = north(pawns) & empty
    double = north(single & RANK_3) & empty
    cap_w  = ((pawns << 7) & NOT_H) & enemy        # capture towards the a-file
    cap_e  = ((pawns << 9) & NOT_A) & enemy        # capture towards the h-file
    promos = (single | cap_w | cap_e) & RANK_8
    return single, double, cap_w, cap_e, promos

To turn a target set back into moves, iterate its bits and subtract the shift: a pawn on target square t of single came from t - 8, of cap_e from t - 9. The cost is proportional to the number of moves, not the number of pawns or squares examined. Black is the mirror image with right shifts. A useful trick is to flip the board with a byte swap so that one generator serves both colours.

Sliding pieces: rays, magics and PEXT

Rooks, bishops and queens are the hard part, because their attacks depend on blockers. A rook on d4 attacks along its file and rank until it hits a piece. The simplest correct method walks each ray square by square. It is the reference implementation every faster method must agree with:

def rook_attacks_slow(sq, occupied):
    att, r, f = 0, sq // 8, sq % 8
    for dr, df in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        rr, ff = r + dr, f + df
        while 0 <= rr < 8 and 0 <= ff < 8:
            t = 8 * rr + ff
            att |= 1 << t
            if occupied >> t & 1:          # blocker: include it (may be a capture), stop
                break
            rr, ff = rr + dr, ff + df
    return att

Magic bitboards replace the loop with a lookup. For each square, the relevance mask is the set of squares whose occupancy could change the attacks. Edge squares are excluded, because a piece on the edge cannot block anything beyond it. A rook in the corner has 12 relevant squares and a rook on d4 has 10. Every subset of the mask is a possible blocker configuration, so a corner rook has 2¹² = 4,096 of them. The trick is to find a 64-bit constant, the magic, such that ((occupied & mask) * magic) >> (64 - bits) maps every configuration to an index where configurations with different attack sets never collide. Configurations with the same attack set may share a slot.

import random

def subsets(mask):
    """Carry-Rippler: enumerate every subset of mask."""
    sub = 0
    while True:
        yield sub
        sub = (sub - mask) & mask
        if sub == 0:
            return

def find_magic(sq, mask, attacks_fn, rng=random.Random(1), tries=10_000_000):
    bits = bin(mask).count("1")
    shift = 64 - bits
    occs = list(subsets(mask))
    refs = [attacks_fn(sq, o) for o in occs]
    for _ in range(tries):
        # sparse candidates (AND of three randoms) succeed far more often
        magic = rng.getrandbits(64) & rng.getrandbits(64) & rng.getrandbits(64)
        table = [None] * (1 << bits)
        for o, a in zip(occs, refs):
            i = ((o * magic) & M64) >> shift
            if table[i] is None:
                table[i] = a
            elif table[i] != a:
                break                        # harmful collision: try another magic
        else:
            return magic, shift, table
    raise RuntimeError(f"no magic for square {sq}")

Search runs once, offline, and the magics are pasted into the engine as constants. At run time, a rook lookup is an AND, a multiply, a shift and a load. With a fixed shift per square the rook tables total 102,400 entries and the bishop tables 5,248, about 800 KB and 41 KB of 64-bit attack sets. Queens are the OR of the rook and bishop lookups. Variants squeeze the tables further, for example by sharing storage across squares, at the cost of a more complicated search.

PEXT bitboards use the BMI2 instruction PEXT (parallel bits extract), which gathers the bits of occupied selected by mask into a dense index directly: table[_pext_u64(occupied, mask)]. No magic is needed and the index is perfect. The caveat is hardware. On AMD processors before Zen 3, PEXT was implemented in microcode and was much slower than a multiply, so engines that ship binaries typically offer a separate BMI2 build and detect the CPU rather than assume PEXT is fast.

Older alternatives such as rotated bitboards, which kept extra copies of the board rotated 90 and 45 degrees so each ray became contiguous bits, are now mainly of historical interest. Kogge-Stone fills compute attacks for many sliders at once with shifts and are still useful for set-wise evaluation.

Perft: proving the generator correct

Move generators fail quietly. An engine with a missing en passant edge case plays fine for thousands of games, then loses one or crashes. The standard defence is perft: count the leaf nodes of the legal move tree to a fixed depth and compare against published values. From the starting position the counts are 20 at depth 1, 400 at depth 2, 8,902 at depth 3, 197,281 at depth 4 and 4,865,609 at depth 5.

def perft(pos, depth):
    if depth == 0:
        return 1
    total = 0
    for move in pos.legal_moves():
        pos.make(move)
        total += perft(pos, depth - 1)
        pos.unmake(move)
    return total

def divide(pos, depth):
    """Per-root-move counts: diff against a trusted engine to find the broken move."""
    for move in pos.legal_moves():
        pos.make(move)
        print(move, perft(pos, depth - 1))
        pos.unmake(move)

The starting position exercises almost nothing interesting, so also run positions designed to stress castling, promotions, en passant and pins. The widely used "Kiwipete" position from the Chess Programming Wiki is the usual next step. When a count disagrees, divide prints per-move subtotals. Compare them with a trusted engine's output for the same position, descend into the move whose count differs, and repeat until one position shows the bug. Also cross-check every fast slider lookup against rook_attacks_slow over random occupancies; it takes seconds and catches bad magics immediately.

Failure modes

• File wrap. A missing mask after an east or west shift makes pieces teleport from the h-file to the a-file of the next rank. Perft catches it, usually at depth 2 or 3.
• Mapping mismatches. Mixing LERF with a big-endian mapping, or FEN parsing that starts at a8 while the board starts at a1, silently mirrors the board. Write a round-trip test: FEN to bitboards and back.
• Undefined shifts in C. Shifting a 64-bit value by 64 or more is undefined behaviour. Code such as 1ULL << sq with a bad square index fails differently per compiler. So does 1 << sq with a 32-bit int literal, a classic bug.
• Pseudo-legal versus legal. Generating moves that leave the king in check and filtering later is a valid design. Forgetting to filter, or filtering with a check test that ignores pins, gives wrong perft counts.
• Derived sets out of sync. If make or unmake updates a piece bitboard but not occupied, the next slider lookup is wrong. Assert the invariant in debug builds.
• Assuming PEXT is fast. Shipping a PEXT-only build to CPUs where it is microcoded can make the engine far slower than the magic build.

Trade-offs

Bitboards also make incremental position hashing natural: Zobrist hashing XORs one random key per piece-square change during make and unmake, keyed by the same square indices.

What to do next

1. Pick LERF, write the square-name helpers and a FEN round-trip test first.
2. Implement the shift helpers with file masks and the knight table; check g1 gives 0xA01000.
3. Write set-wise pawn moves for both colours, including double pushes, captures and promotions.
4. Implement slow ray attacks, then magic lookups, and cross-check them over a million random occupancies.
5. Write perft and divide, match the start position to depth 5, then Kiwipete and other published test positions.
6. Benchmark nodes per second before and after each optimisation, and add a PEXT build only behind CPU detection.
7. Move on to search: alpha-beta, move ordering and the transposition table.