Traditional chess engines, including this one, operate on a fundamental principle: they evaluate individual board positions as static snapshots, determining whether a position is “good” or “bad” through quantifiable metrics (material count, piece placement, king safety, etc.). The engine doesn’t inherently understand chess strategy or plans-it evaluates millions of positions and selects moves leading to the best-scored positions.

This engine uses hand-crafted evaluation based on:

• Material counting (queen = 9 pawns, rook = 5 pawns, etc.)
• Piece-square tables (e.g. knights in center are better than on rim)
• Static position features

In contrast, modern neural network engines like Stockfish NNUE (Efficiently Updatable Neural Network) and Leela Chess Zero use learned evaluation functions that can implicitly recognize patterns, piece coordination, and positional motifs that emerge from training. These neural approaches evaluate positions by recognizing high-dimensional patterns “learned” from millions of games, rather than explicitly coded heuristics. Note that NNUE in Stockfish replaces only the evaluation function while retaining classical search (alpha-beta with all its pruning and extensions), whereas Leela uses a pure neural approach with Monte Carlo Tree Search.²⁵²⁶

Stockfish (modern) combines the best of both worlds, it uses the efficient search techniques described in this document (alpha-beta, transposition tables, move ordering) and replaces the hand-crafted leaf evaluation with NNUE trained on billions of positions evaluated by classical Stockfish. Importantly, NNUE only handles position evaluation-the classical search algorithm, pruning heuristics, and move ordering remain largely hand-crafted. This “bootstrap” approach leverages human chess insight encoded in both the classical evaluation and search techniques to accelerate training.

AlphaZero and Leela Chess Zero take a more radical approach, they start from zero knowledge (only the rules of chess) and learn entirely through self-play reinforcement learning. AlphaZero’s neural network learns to evaluate positions and suggest moves simultaneously, discovering chess principles independently without human input. This achieved superhuman play in just hours of training, with a more complex and natural playstyle, though requiring massive computational resources.³²⁶

The engine operates in a think-evaluate-move cycle:

Position → Generate Moves → Evaluate → Search → Best Move
     ↑                                              ↓
     └──────────────────────────────────────────────┘

This loop assumes the opponent will always choose the strongest available reply within the search horizon. That worst-case assumption is exactly what makes minimax-style search robust, but it also means the engine is not explicitly optimizing for human fallibility, time pressure, or psychologically awkward positions unless extra heuristics or opponent models are added.¹¹¹

A bitboard is a 64-bit unsigned integer where each bit represents a square on the chessboard. This representation enables highly efficient bitwise operations for move generation and board queries.⁷

typedef uint64_t Bitboard;

The chessboard is mapped to bits in little-endian rank-file mapping:

a8 b8 c8 d8 e8 f8 g8 h8    8 | 56 57 58 59 60 61 62 63
a7 b7 c7 d7 e7 f7 g7 h7    7 | 48 49 50 51 52 53 54 55
a6 b6 c6 d6 e6 f6 g6 h6    6 | 40 41 42 43 44 45 46 47
a5 b5 c5 d5 e5 f5 g5 h5    5 | 32 33 34 35 36 37 38 39
a4 b4 c4 d4 e4 f4 g4 h4    4 | 24 25 26 27 28 29 30 31
a3 b3 c3 d3 e3 f3 g3 h3    3 | 16 17 18 19 20 21 22 23
a2 b2 c2 d2 e2 f2 g2 h2    2 |  8  9 10 11 12 13 14 15
a1 b1 c1 d1 e1 f1 g1 h1    1 |  0  1  2  3  4  5  6  7
                               -------------------------
                                a  b  c  d  e  f  g  h

The engine uses piece-centric bitboards where each piece type has its own bitboard:

typedef struct {
    // White pieces
    Bitboard pawn_w, knight_w, bishop_w, rook_w, queen_w, king_w;
    
    // Black pieces
    Bitboard pawn_b, knight_b, bishop_b, rook_b, queen_b, king_b;
    
    // Derived occupancy masks
    Bitboard occupancy;       // All pieces
    Bitboard occupancyWhite;  // White pieces
    Bitboard occupancyBlack;  // Black pieces
    
    // Game state
    int turn;            // WHITE=1 or BLACK=0
    int castling;        // Bitfield: KQkq
    int epSquare;        // En passant target square
    int halfmoves;       // 50-move rule counter
    int fullmoves;       // Move number
    
    // Cached king positions
    int whiteKingSq;
    int blackKingSq;
    
    // Zobrist hash
    Bitboard hash;
    
    // Attack bitboard
    Bitboard attacks;
} Board;

Bitboards are useful because the primitive operations of chess become primitive operations of the CPU. Placing pieces, removing them, finding occupancies, generating pushes, and iterating through piece lists. Instead of looping over 64 squares and branching repeatedly, the engine can often express the same logic with a handful of branch-light integer operations.

Two patterns show up constantly:

• Masking: isolate a subset of squares with &
• Iteration by least-significant bit: repeatedly extract one piece with ctzll, then clear it with bb &= bb - 1

LSB iteration is especially important because it turns a dense 64-square board scan into a loop over only the occupied squares.

Space Efficiency: 12 bitboards (64 bytes) store the entire position, compared to 64-element arrays (256+ bytes).

Parallel Operations: A single instruction can operate on all 64 squares simultaneously:

// Check if any pawns are on the 7th rank
bool pawnsOnSeventh = (pawn_w & RANK_7) != 0;

// Get all white pieces in one operation
Bitboard whitePieces = pawn_w | knight_w | bishop_w | rook_w | queen_w | king_w;

White pawns on rank 2:

Bitboard pawn_w = 0x000000000000FF00;

Binary representation:
0000000000000000  (rank 8)
0000000000000000  (rank 7)
0000000000000000  (rank 6)
0000000000000000  (rank 5)
0000000000000000  (rank 4)
0000000000000000  (rank 3)
1111111111111111  (rank 2) ← Pawns here
0000000000000000  (rank 1)

Each move is encoded in a compact structure:

typedef struct {
    int fromSquare;     // Origin (0-63)
    int toSquare;       // Destination (0-63)
    int promotion;      // Promoted piece type (-1 if none)
    int castle;         // Castling type (0 if not castling)
    int validation;     // LEGAL, ILLEGAL, or NOT_VALIDATED
    int pieceType;      // Moving piece type
    int score;          // Move ordering heuristic
    bool exhausted;     // Search tracking flag
} Move;

1. Generate Pseudo-Legal Moves
2. Apply Move on Copy Board
3. Check if King is Under Attack
4. Filter Illegal Moves (leaving king in check)
5. Return Legal Move List

Pawns have the most complex movement rules:

void pawnSingleAndDblPushes(Board board, Bitboard* single, Bitboard* dbl) {
    // Single push: shift pawns one rank forward
    *single = board.turn ? board.pawn_w << 8 : board.pawn_b >> 8;
    *single &= ~board.occupancy;  // Remove blocked squares
    
    // Double push: pawns on starting rank move two squares
    *dbl = board.turn ? 
        (board.pawn_w & PAWN_START_WHITE) << 16 : 
        (board.pawn_b & PAWN_START_BLACK) >> 16;
    
    // Can only double-push if both squares are empty
    *dbl &= ~board.occupancy;      // Destination must be empty
    // Shift back to intermediate square, intersect with single-push
    // to ensure path is clear, then shift forward again
    *dbl = board.turn ? *dbl >> 8 : *dbl << 8;
    *dbl &= *single;               // Square in between must be empty
    *dbl = board.turn ? *dbl << 8 : *dbl >> 8;  // Restore to destination
}

/* Implementation comment: The intermediate shifts ensure the square between
 * the starting position and destination is empty. While this could be
 * optimized with a direct mask, this approach clearly expresses the logic. */

Pawn promotions generate four moves per promoting pawn (queen, rook, bishop, knight):

if (isPromoting) {
    int promotions[] = {QUEEN_W, ROOK_W, BISHOP_W, KNIGHT_W};
    for (int i = 0; i < 4; i++) {
        Move move = {from, to, promotions[i], 0, turn ? PAWN_W : PAWN_B};
        // Validate and add move
    }
}

To determine if a square is attacked:

bool isSquareAttacked(const Board board, int square) {
    Bitboard sqBb = SQUARE_BITBOARDS[square];
    Bitboard pawn = board.turn ? board.pawn_b : board.pawn_w;
    Bitboard king = board.turn ? board.king_b : board.king_w;
    Bitboard knight = board.turn ? board.knight_b : board.knight_w;
    Bitboard bishop = board.turn ? board.bishop_b : board.bishop_w;
    Bitboard rook = board.turn ? board.rook_b : board.rook_w;
    Bitboard queen = board.turn ? board.queen_b : board.queen_w;
    
    // Check queen attacks (both diagonal and orthogonal)
    while (queen) {
        int sq = __builtin_ctzll(queen);
        
        // Queens attack like bishops and rooks combined
        Bitboard attacks = getBishopAttacks(sq, board.occupancy);
        attacks |= getRookAttacks(sq, board.occupancy);
        
        if (attacks & sqBb) return true;
        
        queen &= queen - 1;  // Remove this queen, check next
    }
    
    // Check bishop attacks (diagonal)
    while (bishop) {
        int sq = __builtin_ctzll(bishop);
        Bitboard attacks = getBishopAttacks(sq, board.occupancy);
        if (attacks & sqBb) return true;
        bishop &= bishop - 1;
    }
    
    // Check rook attacks (orthogonal)
    while (rook) {
        int sq = __builtin_ctzll(rook);
        Bitboard attacks = getRookAttacks(sq, board.occupancy);
        if (attacks & sqBb) return true;
        rook &= rook - 1;
    }
    
    // Check knight attacks
    while (knight) {
        int sq = __builtin_ctzll(knight);
        if (KNIGHT_MOVEMENT[sq] & sqBb) return true;
        knight &= knight - 1;
    }
    
    // Check pawn attacks
    while (pawn) {
        int sq = __builtin_ctzll(pawn);
        
        if (board.turn) {
            // Check if black pawn attacks this square
            if (PAWN_B_ATTACKS_EAST[sq] & sqBb) return true;
            if (PAWN_B_ATTACKS_WEST[sq] & sqBb) return true;
        } else {
            // Check if white pawn attacks this square
            if (PAWN_W_ATTACKS_EAST[sq] & sqBb) return true;
            if (PAWN_W_ATTACKS_WEST[sq] & sqBb) return true;
        }
        pawn &= pawn - 1;
    }
    
    // Check king attacks
    while (king) {
        int sq = __builtin_ctzll(king);
        if (KING_MOVEMENT[sq] & sqBb) return true;
        king &= king - 1;
    }
    
    return false;
}

Sliding pieces (bishops, rooks, queens) require ray-based attack generation that depends on board occupancy. A rook on d4 has different moves when the board is empty versus when pieces block its rays.

The natural approach is, for each square and occupancy pattern, compute attacks on-the-fly with ray tracing. But ray tracing is expensive. A position may need to check thousands of sliding piece attacks during search.

The solution is to pre-compute all possible attack patterns and use pseudo-perfect hashing to retrieve them in $ O(1) $ time.

. . . . . . . .     0 0 0 0 0 0 0 0
. . . . 1 . . .     0 0 0 0 1 0 0 0
. . . . 1 . . .     0 0 0 0 1 0 0 0
. . . . 1 . . .     0 0 0 0 1 0 0 0
. 1 1 1 . 1 1 .     0 1 1 1 0 1 1 0  ← Rook on e4
. . . . 1 . . .     0 0 0 0 1 0 0 0
. . . . 1 . . .     0 0 0 0 1 0 0 0
. . . . . . . .     0 0 0 0 0 0 0 0

ROOK_MAGICS[28] = 0xd14880480100080ULL;

// Attack lookup tables
Bitboard BISHOP_ATTACKS[64][512];   // 64 squares × max 512 patterns
Bitboard ROOK_ATTACKS[64][4096];    // 64 squares × max 4096 patterns

void initBishopRookAttackTables() {
    for (int square = 0; square < 64; square++) {
        // Initialize rook attack tables
        Bitboard rookMask = rookMovement(square);      // Get relevant squares
        int rookRelevantBits = ROOK_RELEVANT_BITS[square];
        int rookVariations = 1 << rookRelevantBits;   // 2^bits patterns
        
        for (int i = 0; i < rookVariations; i++) {
            // Generate specific occupancy pattern
            Bitboard occupancy = occupancyMask(i, rookRelevantBits, rookMask);
            
            // Compute magic index
            Bitboard index = (occupancy * ROOK_MAGICS[square]) >> (64 - rookRelevantBits);
            
            // Store pre-computed attacks
            ROOK_ATTACKS[square][index] = rookAttacksOnTheFly(square, occupancy);
        }
        
        // Initialize bishop attack tables
        Bitboard bishopMask = bishopMovement(square);     // Get relevant diagonal squares
        int bishopRelevantBits = BISHOP_RELEVANT_BITS[square];
        int bishopVariations = 1 << bishopRelevantBits;  // 2^bits patterns
        
        for (int i = 0; i < bishopVariations; i++) {
            // Generate specific occupancy pattern for diagonals
            Bitboard occupancy = occupancyMask(i, bishopRelevantBits, bishopMask);
            
            // Compute magic index
            Bitboard index = (occupancy * BISHOP_MAGICS[square]) >> (64 - bishopRelevantBits);
            
            // Store pre-computed attacks
            BISHOP_ATTACKS[square][index] = bishopAttacksOnTheFly(square, occupancy);
        }
    }
}

Bitboard getRookAttacks(int square, Bitboard occupancy) {
    occupancy &= ROOK_MOVEMENT[square];           // Apply mask
    occupancy *= ROOK_MAGICS[square];             // Multiply by magic
    occupancy >>= 64 - ROOK_RELEVANT_BITS[square]; // Shift to index
    return ROOK_ATTACKS[square][occupancy];       // Table lookup
}

int ROOK_RELEVANT_BITS[64] = {
    12, 11, 11, 11, 11, 11, 11, 12,    // Rank 1: corners need 12 bits
    11, 10, 10, 10, 10, 10, 10, 11,    // Rank 2-7: edges need 11, center 10
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    11, 10, 10, 10, 10, 10, 10, 11,
    12, 11, 11, 11, 11, 11, 11, 12     // Rank 8
};

The evaluation function assigns a numerical score to a position from the current side’s perspective:

$$ \text{eval}(p) = \begin{cases} +\infty & \text{if } p \text{ is checkmate for player} \ -\infty & \text{if } p \text{ is checkmate for opponent} \ 0 & \text{if } p \text{ is drawn/equal} \

0 & \text{if } p \text{ favors player} \ < 0 & \text{if } p \text{ favors opponent} \end{cases} $$

The engine uses material + piece-square tables evaluation:

int PIECE_HEAD_VALUES[] = {
    100,    // White pawn
    320,    // White knight
    330,    // White bishop
    500,    // White rook
    900,    // White queen
    2000,   // White king (UNUSED)
    -100,   // Black pawn
    -320,   // Black knight
    -330,   // Black bishop
    -500,   // Black rook
    -900,   // Black queen
    -2000   // Black king (UNUSED)
};

int PAWN_W_POS[] = {
     0,   0,   0,   0,   0,   0,   0,   0,  // Rank 1 (pawns can't be here)
     5,  10,  10, -20, -20,  10,  10,   5,  // Rank 2 (starting position)
     5,  -5, -10,   0,   0, -10,  -5,   5,  // Rank 3
     0,   0,   0,  20,  20,   0,   0,   0,  // Rank 4 (central control)
     5,   5,  10,  25,  25,  10,   5,   5,  // Rank 5 (advanced pawns)
    10,  10,  20,  30,  30,  20,  10,  10,  // Rank 6 (near promotion)
    50,  50,  50,  50,  50,  50,  50,  50,  // Rank 7 (almost promoting)
     0,   0,   0,   0,   0,   0,   0,   0   // Rank 8 (promotion square)
};

int KNIGHT_W_POS[] = {
    -50, -40, -30, -30, -30, -30, -40, -50,  // Rank 1 (back rank bad)
    -40, -20,   0,   5,   5,   0, -20, -40,  // Rank 2
    -30,   5,  10,  15,  15,  10,   5, -30,  // Rank 3
    -30,   0,  15,  20,  20,  15,   0, -30,  // Rank 4 (ideal squares)
    -30,   5,  15,  20,  20,  15,   5, -30,  // Rank 5
    -30,   0,  10,  15,  15,  10,   0, -30,  // Rank 6
    -40, -20,   0,   0,   0,   0, -20, -40,  // Rank 7
    -50, -40, -30, -30, -30, -30, -40, -50   // Rank 8 (back rank bad)
};

int evaluate(Board board, int gameResult) {
    if (gameResult == DRAW) return 0;
    if (gameResult == WHITE_WIN) return MAX_EVAL;
    if (gameResult == BLACK_WIN) return MIN_EVAL;
    
    int score = 0;
    
    // Iterate through all piece types
    for (int pieceType = 0; pieceType < 12; pieceType++) {
        Bitboard pieces = *(&board.pawn_w + pieceType);
        
        while (pieces) {
            int square = __builtin_ctzll(pieces);  // Get LSB position
            
            // Add material value
            score += PIECE_HEAD_VALUES[pieceType];
            
            // Add positional value
            score += PIECE_SQUARE_TABLES[pieceType][square];
            
            pieces &= pieces - 1;  // Clear LSB
        }
    }
    
    return score;
}

Black piece-square tables are vertically flipped versions of white tables:

// Black pawn values are white values mirrored and negated
int PAWN_B_POS[64] = mirror_and_negate(PAWN_W_POS);

More sophisticated engines include:

Chess engines use minimax - the assumption that both players play optimally. This engine implements the negamax variant, which simplifies implementation by treating both players symmetrically:

The negation (-negamax) switches perspective between players: each player maximizes their own score, which is the negative of their opponent’s score. This is mathematically equivalent to classical minimax (which alternates between max and min nodes) but requires writing only one function.¹¹¹¹²

Alpha-beta pruning eliminates branches that cannot influence the final decision:

Pruning condition: If $ \alpha \geq \beta $, stop searching - opponent won’t allow this position.

            Root (α=-∞, β=+∞)
           /     |      \
      Move A  Move B  Move C
       /  \      |       |
     ...  ...   ...     ...
     
At Move A: after searching left child, α = 50
           Right child returns -60
           No update since -60 < 50
           
At Move B: Returns 70
           Update α = 70 (new best)
           
At Move C: First child returns 40
           Since 40 < α=70, skip remaining children
           Opponent won't allow this worse position

static int alphabeta(Board board, int depth, int alpha, int beta, SearchContext* ctx) {
    ctx->nodesSearched++;
    int origAlpha = alpha;
    
    // Transposition table probe (check if we've seen this position)
    TTEntry entry = getTTEntry(board.hash);
    if (board.hash == entry.zobrist && entry.depth >= depth) {
        if (entry.nodeType == EXACT) {
            return entry.eval;  // Exact previous evaluation
        } else if (entry.nodeType == LOWER) {
            alpha = max(alpha, entry.eval);  // At least this good
        } else if (entry.nodeType == UPPER) {
            beta = min(beta, entry.eval);  // At most this good
        }
        
        if (alpha >= beta) {
            return entry.eval;  // Cutoff
        }
    }
    
    // Generate all legal moves
    Move moves[256];
    int moveCount = legalMoves(&board, moves);
    
    // Terminal node check (checkmate/stalemate/draw)
    int result = gameResult(board, moves, moveCount);
    if (result) {
        int eval = evaluate(board, result);
        // Prefer faster mates
        if (result != DRAW)
            eval += (ctx->maxDepth - depth) * (board.turn ? 1 : -1);
        return eval * (board.turn ? 1 : -1);
    }
    
    // Leaf node evaluation
    if (depth == 0) {
        return evaluate(board, result) * (board.turn ? 1 : -1);
    }
    
    // Move ordering (see next section)
    score_moves(board, entry, moves, moveCount);
    
    int eval = MIN_EVAL;
    Move bestMove;
    int nextMove;
    
    // Iterate through moves in order
    while ((nextMove = select_move(moves, moveCount)) != -1) {
        if (moves[nextMove].validation == LEGAL) {
            Board child = board;
            pushMove(&child, moves[nextMove]);
            
            // Recursive call with negated window
            int childEval = -alphabeta(child, depth - 1, -beta, -alpha, ctx);
            
            if (childEval > eval) {
                eval = childEval;
                bestMove = moves[nextMove];
                
                if (depth == ctx->maxDepth) {
                    ctx->bestMove = bestMove;  // Update root best move
                }
            }
            
            alpha = max(alpha, childEval);
            
            // Beta cutoff
            if (alpha >= beta) {
                break;
            }
        }
    }
    
    // Store in transposition table
    addTTEntry(board, eval, bestMove, depth, beta, origAlpha);
    
    return eval;
}

Without pruning, the search tree has branching factor $ b \approx 35 $ (average legal moves):

Alpha-beta can achieve $ O(b^{d/2}) $ with perfect move ordering.²¹³

Rather than searching directly to the target depth, the engine searches depth 1, then depth 2, then depth 3, and so on until reaching the requested depth:

int search(Board board, int depth, SearchContext* ctx) {
    memset(&ctx->bestMove, 0, sizeof(Move));
    ctx->nodesSearched = 0;

    int eval = 0;
    for (int d = 1; d <= depth; d++) {
        ctx->maxDepth = d;
        eval = alphabeta(board, d, MIN_EVAL, MAX_EVAL, ctx);
        if (ctx->onDepthComplete)
            ctx->onDepthComplete(d, eval, ctx->nodesSearched);
    }
    return eval;
}

This looks wasteful — why repeat work already done at shallower depths? The answer is that the overhead is negligible. Because the search tree grows geometrically, the last iteration dominates:

For $ b \approx 35 $, the overhead is about 3%. In practice it’s closer to 20% because earlier depths are cheap but not free.

The real benefit comes from move ordering. After completing depth $ d $, the best move is stored in the transposition table. At depth $ d+1 $, score_moves() retrieves it and tries it first. This means the PV move is always searched before any other move — dramatically increasing the chance of early alpha-beta cutoffs. In the worst case (random move ordering) alpha-beta is $ O(b^d) $; with the TT move tried first it approaches the $ O(b^{d/2}) $ ideal.

The iterative deepening loop also enables per-depth info lines to be emitted over UCI, so GUIs can display search progress during a long think.

When finding checkmate, the engine prefers faster mates:

if (result != DRAW) {
    eval += (ctx->maxDepth - depth) * (board.turn ? 1 : -1);
}

This adds a bonus proportional to how quickly the mate occurs:

• Mate in 1 ply: bonus = maxDepth - 1
• Mate in 10 ply: bonus = maxDepth - 10

Ensures mate-in-2 is preferred over mate-in-5. In real engines this is usually implemented with dedicated mate scores such as MATE - ply, but the idea is the same: preserve the winning result while ordering faster mates above slower ones and slower losses above immediate ones.

Advanced engines extend search with quiescence search - searching only captures/checks at leaf nodes to avoid horizon effect:

if (depth == 0) {
    return quiescence_search(board, alpha, beta);
}

This prevents bad evaluations when a capture is about to dramatically change the position.¹⁴

Chess positions can be reached via different move orders:

e4 → e5 → Nf3 → Nc6      (Position A)
    vs
Nf3 → Nc6 → e4 → e5      (Same Position A)

Without caching, the engine would re-evaluate identical positions multiple times, wasting computation.¹⁵

Search can revisit the same position through reversible move sequences, so repetition handling matters. Transposition tables reduce duplicated work, but they do not by themselves solve repetition semantics. Engines need history-aware draw detection and the halfmove clock. The relevant rules are threefold repetition and the fifty-move rule for claimable draws, with fivefold repetition and the seventy-five-move rule treated as automatic draws under current FIDE rules.^20212223

The engine uses Zobrist hashing to assign an almost-unique 64-bit signature to a position. That signature serves as the transposition table key.⁵¹⁶

typedef struct {
    Bitboard zobrist;   // Position hash (key)
    int eval;           // Stored evaluation
    Move move;          // Best move from this position
    int depth;          // Search depth when evaluated
    int nodeType;       // EXACT, LOWER, or UPPER bound
} TTEntry;

When a node is stored:

void addTTEntry(Board board, int eval, Move move, int depth, int beta, int alpha) {
    TTEntry entry;
    
    if (eval <= alpha)
        entry.nodeType = UPPER;  // Opponent can do better
    else if (eval >= beta)
        entry.nodeType = LOWER;  // We can do better
    else
        entry.nodeType = EXACT;  // Evaluation within window
    
    entry.eval = eval;
    entry.move = move;
    entry.depth = depth;
    entry.zobrist = board.hash;
    
    TT_TABLE[entry.zobrist % TT_SIZE] = entry;
}

TTEntry getTTEntry(Bitboard zobrist) {
    return TT_TABLE[zobrist % TT_SIZE];
}

Collision handling: Simple replacement scheme - new entries overwrite old ones. More sophisticated engines use:

• Two-tier tables (always replace vs depth-preferred)
• Aging (prefer recent positions)
• Bucket systems (multiple entries per hash)

TTEntry entry = getTTEntry(board.hash);

if (board.hash == entry.zobrist && entry.depth >= depth) {
    if (entry.nodeType == EXACT) {
        return entry.eval;  // Direct return
    } else if (entry.nodeType == LOWER) {
        alpha = max(alpha, entry.eval);
    } else if (entry.nodeType == UPPER) {
        beta = min(beta, entry.eval);
    }
    
    if (alpha >= beta) {
        return entry.eval;  // Cutoff
    }
}

Depth check: Only use stored evaluation if it was computed at equal or greater depth.

const int TT_SIZE = 100000;
TTEntry TT_TABLE[100000];

With roughly 40 bytes per entry, this table uses:

Modern engines use gigabytes of transposition table memory.

Transposition tables are essential for modern chess engines.

A naive position hash (e.g., hashing all piece positions) would require $ O(n) $ computation per position. With millions of positions evaluated, this is too slow.

Solution: Zobrist hashing provides $ O(1) $ incremental updates.

Pre-compute random 64-bit numbers for each:

• Piece type on each square: PIECES[12][64]
• Castling rights: CASTLE[16] (4 castling bits → $ 2^4 = 16 $ states)
• En passant square: ENPASSANT[64]
• Side to move: WHITE_MOVE

Bitboard PIECES[12][64];    // [piece_type][square]
Bitboard CASTLE[16];        // [castling_rights]
Bitboard ENPASSANT[64];     // [ep_square]
Bitboard WHITE_MOVE;

The position hash is the XOR of all applicable components. This works because each factor that changes legal play must contribute its own random key: piece-square occupancy, castling rights, en passant state, and side to move. If any of those differ, the resulting signature should differ as well, which is exactly what the transposition table needs. In careful implementations, the en passant component is only hashed when an en passant capture is actually legal; otherwise two positions that are equivalent for repetition purposes can receive different keys.⁵¹⁶

Where $ \bigoplus $ denotes XOR.

Bitboard hash(const Board board) {
    Bitboard hash = 0LL;
    
    // XOR in castling rights
    hash ^= CASTLE[board.castling];
    
    // XOR in all pieces
    for (int i = 0; i < 12; i++) {
        Bitboard bb = *(&board.pawn_w + i);
        while (bb) {
            int square = __builtin_ctzll(bb);
            hash ^= PIECES[i][square];
            bb &= bb - 1;
        }
    }
    
    // XOR in en passant square
    if (board.epSquare != -1) {
        hash ^= ENPASSANT[board.epSquare];
    }
    
    // XOR in side to move
    if (board.turn == WHITE) {
        hash ^= WHITE_MOVE;
    }
    
    return hash;
}

When making a move, update the hash incrementally:

// Remove piece from origin square
board.hash ^= PIECES[pieceType][fromSquare];

// Add piece to destination square
board.hash ^= PIECES[pieceType][toSquare];

// If capture occurred, remove captured piece
if (capturedPiece != EMPTY) {
    board.hash ^= PIECES[capturedPiece][toSquare];
}

// Update en passant
if (board.epSquare != -1) {
    board.hash ^= ENPASSANT[oldEpSquare];  // Remove old
}
if (newEpSquare != -1) {
    board.hash ^= ENPASSANT[newEpSquare];  // Add new
}

// Update castling rights
board.hash ^= CASTLE[oldCastling];
board.hash ^= CASTLE[newCastling];

// Toggle side to move
board.hash ^= WHITE_MOVE;

XOR properties make this work:

• $ a \oplus a = 0 $ (XORing twice removes)
• $ a \oplus 0 = a $ (identity)
• XOR is commutative and associative

Random numbers are generated at engine startup:

void initZobrist() {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 64; j++) {
            PIECES[i][j] = randomBitboard();
        }
    }
    for (int i = 0; i < 64; i++) {
        ENPASSANT[i] = randomBitboard();
    }
    for (int i = 0; i < 16; i++) {
        CASTLE[i] = randomBitboard();
    }
    WHITE_MOVE = randomBitboard();
}

Bitboard randomBitboard(void) {
    Bitboard r = 0;
    for (int i = 0; i < 64; i++) {
        Bitboard tmp = (Bitboard)rand() % 2;
        r |= tmp << i;
    }
    return r;
}

With 64-bit hashes, collision probability is astronomically low:

For $ n = 10^9 $ positions (deep search):

Even with billions of positions, collisions are extremely rare (less than 3 in 10,000 searches). Modern engines accept this negligible risk, as verification costs would exceed collision costs.

Zobrist hashing has two critical properties:

1. Uniqueness: Random XOR produces uniformly distributed hashes
2. Incrementality: Move updates are $ O(1) $ XOR operations

This makes it the gold standard for chess position hashing.

Alpha-beta pruning effectiveness depends on move order. Searching the best move first maximizes cutoffs:

Example: At depth 6 with $ b=35 $:

• Random order: ~1.8 billion nodes
• Perfect order: ~43,000 nodes
• ~42,000x speedup

The engine uses multiple heuristics to score moves:

void score_moves(const Board board, const TTEntry entry, Move moves[], int cmoves) {
    Move pvMove = {0};
    if (board.hash == entry.zobrist && entry.nodeType < UPPER)
        pvMove = entry.move;

    for (int i = 0; i < cmoves; i++) {
        Move* move = &moves[i];

        // 1. Hash move (best from previous iteration) gets highest priority
        if (both_moves_are_equal(pvMove, *move)) {
            move->score = MAX_MOVE_SCORE;  // 1000
        } else {
            bool isCapture = enemyOccupancy & SQUARE_BITBOARDS[move->toSquare];
            bool isEnPassant = board.epSquare == move->toSquare;

            if (isEnPassant) {
                move->score = PAWN_EXCHANGE_VALUE;  // equivalent to pawn captures pawn
            } else if (isCapture) {
                // 2. MVV-LVA: pre-scaled victim table minus attacker table
                move->score = VICTIM_PIECES[capturedPiece] - ATTACKING_PIECES[move->pieceType];
            }
            // Non-captures score 0 and are searched last
        }
    }
}

Prioritize captures by:

1. Victim value (capturing queen > capturing pawn)
2. Attacker value (pawn captures queen > queen captures pawn)

Victim values are pre-scaled (pawn = 1600, queen = 14400) and attacker values use a separate scale (pawn = 100, queen = 500), so high-value captures always outrank low-value ones regardless of attacker:

• Pawn captures queen: $ 14400 - 100 = 14300 $
• Queen captures pawn: $ 1600 - 500 = 1100 $

This encourages trading low-value pieces for high-value pieces.¹⁷

Using lookup tables (VICTIM_PIECES[] and ATTACKING_PIECES[]) avoids computing piece values inline and keeps the scoring branch-free. The large victim scale ensures capture ordering is dominated by the victim’s value, not the attacker’s.

Moves are selected using partial sorting - only the best unmoved move is found each iteration:

int select_move(Move moves[], int cmoves) {
    int bestScore = 0;
    int indx = -1;
    
    for (int i = 0; i < cmoves; i++) {
        if (!moves[i].exhausted && moves[i].score >= bestScore) {
            bestScore = moves[i].score;
            indx = i;
        }
    }
    
    if (indx != -1) {
        moves[indx].exhausted = true;
    }
    
    return indx;
}

This is more efficient than full sorting when alpha-beta cutoffs occur early.

The hash move (best move from transposition table) gets highest priority:

if (entry.zobrist == board.hash) {
    score += 10000;  // Guaranteed first
}

This creates a positive feedback loop:

1. Best move from previous search gets tried first
2. Causes early cutoffs, confirming it’s strong
3. Gets stored back in transposition table
4. Prioritized again in future searches

Good move ordering reduces nodes by ~200x.^13171819

CFLAGS = -O3 -march=native -flto

• -O3: Aggressive optimization (loop unrolling, inlining, etc.)
• -march=native: Use CPU-specific instructions (POPCNT, BMI2)
• -flto: Link-time optimization (whole-program analysis)

Modern CPUs have hardware instructions for bit manipulation:

// Count pieces on bitboard
int count = __builtin_popcountll(bitboard);

// Find first piece
int square = __builtin_ctzll(bitboard);

// Remove first piece
bitboard &= bitboard - 1;  // Clear LSB trick

Pre-compute expensive operations:

// Pre-computed
Bitboard attacks = KNIGHT_MOVEMENT[square];

// vs On-the-fly (much slower)
Bitboard attacks = computeKnightAttacks(square);

Memory-speed tradeoff: Tables use ~1 MB but provide ~100x speedup.

sizeof(Move) = 32 bytes  // Compact representation

Keeping moves small improves cache locality:

• 256 moves = 8 KB (fits in L1 cache)
• Faster iteration during move ordering

Pre-compute occupancy masks once per position:

void computeOccupancyMasks(Board* board) {
    board->occupancyWhite = board->pawn_w | board->knight_w | ...;
    board->occupancyBlack = board->pawn_b | board->knight_b | ...;
    board->occupancy = board->occupancyWhite | board->occupancyBlack;
}

Avoids recomputing these ORs in every getRookAttacks() call.

int whiteKingSq;  // Cached king position
int blackKingSq;

Finding the king requires scanning a bitboard (ctzll). Caching eliminates this:

// Cached access (O(1))
int kingPos = board.whiteKingSq;

// vs Scanning (O(1) but slower constant)
int kingPos = __builtin_ctzll(board.king_w);

Evaluation is only called at depth 0 or terminal nodes:

if (depth == 0 || gameOver) {
    return evaluate(board, result);
}

Don’t waste time evaluating at every node - search deeper instead.

Instead of fully sorting 40 moves:

// Partial sort: only find best unmoved move
int select_move(Move moves[], int count) {
    int bestIndex = -1;
    int bestScore = MIN_INT;
    
    for (int i = 0; i < count; i++) {
        if (!moves[i].exhausted && moves[i].score > bestScore) {
            bestScore = moves[i].score;
            bestIndex = i;
        }
    }
    
    moves[bestIndex].exhausted = true;
    return bestIndex;
}

Complexity:

• Full sort: $ O(n \log n) $ upfront
• Partial sort: $ O(n) $ per move, but alpha-beta often cuts off early

If only 5 moves are tried before cutoff, partial sorting is ~8x faster.

Typical performance on modern hardware:

Each 2-ply depth increase multiplies search time by ~50x.