No history yet

Bitboard Foundation

Bitboards The Foundation of Speed

High-performance chess engines abandon the intuitive 8x8 array representation in favor of a more abstract, yet computationally superior, structure: the bitboard. A bitboard maps the entire 64-square chessboard onto a single 64-bit unsigned integer, typically a uint64_t. Each bit corresponds to a specific square, where a 1 signifies the presence of a piece and a 0 signifies its absence.

This mapping is standardized. Bit 0 represents square a1, bit 1 represents b1, and so on, up to bit 63 for square h8. This seemingly simple change is profound. Instead of looping through an array, an engine can query and manipulate the state of multiple squares simultaneously using a single CPU instruction. Entire sets of pieces can be represented and moved with bitwise logic, unlocking massive parallelism at the hardware level.

A complete board position is not a single bitboard but a collection of them. Typically, an engine maintains twelve bitboards for the pieces (white pawns, white knights, ..., black kings) and several utility bitboards for occupancy. Occupancy masks, representing all white pieces, all black pieces, and all occupied squares, are derived from the piece sets using bitwise operations. This structure allows for incredibly fast queries, such as "what are all the empty squares?" or "which pieces are attacking square e4?"

// A simplified bitboard representation in C++

#include <cstdint>

using U64 = uint64_t;

struct BoardState {
    // Piece bitboards
    U64 pieceBB[12]; // P, N, B, R, Q, K, p, n, b, r, q, k

    // Occupancy bitboards (derived)
    U64 whitePiecesBB;
    U64 blackPiecesBB;
    U64 allPiecesBB;

    // Other state info
    bool whiteToMove;
    int castlingRights; // e.g., using a bitmask
    int enPassantSquare; // -1 if none
};

Bitwise Operations

The power of the bitboard representation is unlocked through bitwise logic. Instead of conditional checks and loops, engines use AND (&), OR (|), XOR (^), NOT (~), and bit shifts (<<, >>) to generate moves and evaluate positions. For example, to find all squares occupied by any piece, you simply OR the white piece and black piece bitboards together. To find all empty squares, you invert the resulting occupancy board. Adding a piece to a square is an OR operation with a mask for that square; removing it is an AND operation with the inverse mask.

all_pieces=white_pieces ∣ black_pieces\text{all\_pieces} = \text{white\_pieces} \ | \ \text{black\_pieces}

Critically, this model allows engines to leverage special-purpose, low-latency CPU instructions. The POPCNT (population count) instruction instantly returns the number of set bits in a 64-bit integer, providing a near-instant count of pieces or controlled squares. Bit Scan Forward (BSF) and Bit Scan Reverse (BSR) find the index of the least or most significant set bit, respectively. This is essential for iterating over the pieces on a bitboard without a conventional loop, leading to dramatic speedups in move generation. This low-level optimization is also a key enabler for (Single Instruction, Multiple Data) approaches, where multiple board states can be processed in parallel.

// High-performance iteration over set bits (pieces)
// This avoids a 64-iteration loop.

void print_piece_squares(U64 piece_bitboard) {
    while (piece_bitboard) {
        // Get index of the least significant bit (LSB)
        int square_index = __builtin_ctzll(piece_bitboard);

        // ... do something with the square index ...
        // e.g., std::cout << square_index << std::endl;

        // Clear the LSB to proceed to the next bit
        piece_bitboard &= piece_bitboard - 1;
    }
}

Memory and State

Performance at this level also requires careful consideration of memory layout. The entire state of a chess engine—bitboards, side to move, castling rights, en passant square, halfmove clock—is often packed into a cache-aligned structure. Proper memory alignment ensures that the CPU can load this data into its fastest caches in a single operation, avoiding performance penalties from misaligned memory accesses. This is particularly crucial when using SIMD instructions, which often have strict alignment requirements. The result is a compact, cache-friendly representation of the game that can be copied and modified with minimal overhead, a necessity for deep search algorithms that explore millions of positions per second.

Quiz Questions 1/6

What is the primary data structure used for a bitboard in a high-performance chess engine?

Quiz Questions 2/6

How would an engine typically calculate a bitboard representing all occupied squares?

With this foundation, the engine is prepared for the core task of move generation, where bitwise logic truly shines.