Chess engines are one of the best case studies in competitive programming for how search and heuristics combine to solve a problem that's too big to brute-force. A chess position has a branching factor of roughly 35, and a full game lasts ~40–80 moves per side — the game tree is astronomically larger than what any computer could ever fully explore. Everything an engine does is about making a huge search space tractable.

This post walks through the algorithms modern engines are built from, roughly in the order you'd add them if you were building one yourself: representation → move generation → search → evaluation → modern neural approaches.

1. Board Representation

Before you can search anything, you need a fast way to represent the board and generate moves.

8x8 array

The simplest approach — a char board[8][8]. Easy to reason about, but slow: move generation and attack detection require scanning rows/columns/diagonals cell by cell.

Bitboards

Almost every serious engine (Stockfish, Leela, etc.) uses bitboards: a uint64_t where each bit represents one of the 64 squares. You keep one bitboard per piece type per color (12 total), plus some derived ones (all white pieces, all black pieces, all occupied squares).

cppuint64_t whitePawns, whiteKnights, whiteBishops, whiteRooks, whiteQueens, whiteKing; uint64_t blackPawns, blackKnights, blackBishops, blackRooks, blackQueens, blackKing; uint64_t occupied = whitePawns | whiteKnights | ... | blackKing;

The magic is that most chess operations become bitwise operations, which are extremely fast:

Is e4 occupied? occupied & (1ULL << E4) All squares a knight on e4 attacks: a precomputed knightAttacks[E4] bitboard. Sliding piece attacks (rook/bishop/queen) use magic bitboards — a perfect-hash technique where you multiply the occupancy mask by a precomputed "magic number" to index directly into a lookup table of attack sets, computed once at startup.

Bitboards make things like "count all squares attacked by black" a single popcount instruction rather than a loop.

1. Move Generation

Move generation must be both fast and correct — a single missed pin or illegal castling rule causes silent bugs deep in search. Key components:

Pseudo-legal move generation: generate all moves ignoring whether your own king ends up in check. Legality filtering: after generating a pseudo-legal move, check if it leaves your king in check (often by checking if the king's square is attacked after making the move, or precomputing pins). Special cases: castling (rights, squares must be empty and not attacked), en passant, and promotion all need dedicated handling.

A common correctness-testing technique is Perft (performance test): count the total number of leaf nodes reachable at a fixed depth from the starting position, and compare against known correct values. If your engine's perft numbers don't match published values at depth 5–6, you have a move generation bug.

1. Search: Exploring the Game Tree

Minimax

The foundational algorithm. Assume both players play optimally: the side to move maximizes the evaluation, the opponent minimizes it.

cppint minimax(Position pos, int depth, bool maximizing) { if (depth == 0 || isGameOver(pos)) return evaluate(pos); if (maximizing) { int best = -INF; for (Move m : generateMoves(pos)) best = max(best, minimax(makeMove(pos, m), depth — 1, false)); return best; } else { int best = INF; for (Move m : generateMoves(pos)) best = min(best, minimax(makeMove(pos, m), depth — 1, true)); return best; } }

This is correct but explores every node — exponential in depth, with base ~35. Depth 4 is already ~1.5 million positions.

Alpha-Beta Pruning

Alpha-beta cuts off branches that can't possibly affect the final decision, without changing the result. It tracks:

alpha: the best score the maximizer can guarantee so far. beta: the best score the minimizer can guarantee so far.

If at any point alpha >= beta, the rest of that branch is irrelevant — prune it.

cppint alphaBeta(Position pos, int depth, int alpha, int beta, bool maximizing) { if (depth == 0) return evaluate(pos); if (maximizing) { int best = -INF; for (Move m : generateMoves(pos)) { best = max(best, alphaBeta(makeMove(pos, m), depth — 1, alpha, beta, false)); alpha = max(alpha, best); if (beta <= alpha) break; // beta cutoff } return best; } else { int best = INF; for (Move m : generateMoves(pos)) { best = min(best, alphaBeta(makeMove(pos, m), depth — 1, alpha, beta, true)); beta = min(beta, best); if (beta <= alpha) break; // alpha cutoff } return best; } }

With a perfect move ordering, alpha-beta reduces the effective branching factor from ~35 to ~√35 ≈ 6 — this is why move ordering (searching the best-looking moves first) is one of the most important optimizations in a chess engine, even more so than raw search speed.

Move Ordering Heuristics

Since alpha-beta's power depends entirely on searching good moves early, engines use several ordering tricks:

Hash move: the best move from a previous search of this position (from the transposition table), tried first. MVV-LVA (Most Valuable Victim – Least Valuable Attacker): try captures of high-value pieces with low-value pieces first (e.g., pawn takes queen before queen takes pawn). Killer moves: quiet moves that caused a beta cutoff at the same depth in a sibling branch — likely to be good again. History heuristic: a table tracking how often a move has historically caused cutoffs, used as a tiebreaker.

Transposition Tables

Different move orders can reach the same position (a "transposition"). A transposition table is a hash table (keyed by a Zobrist hash of the position) storing previously computed evaluations, so the engine never re-searches a position it has already solved to sufficient depth.

Zobrist hashing: assign a random 64-bit number to every (piece, square) combination, plus side-to-move and castling/en-passant state. The position's hash is the XOR of all applicable random numbers — updating it incrementally after a move is O(1).

Iterative Deepening

Rather than searching directly to depth N, the engine searches depth 1, then 2, then 3, ... up to N, using the previous iteration's best move to improve move ordering in the next. This seems wasteful, but because the tree grows exponentially, the cost of all previous shallow searches is small compared to the deepest one — and it gives you an "anytime" algorithm: you can stop at any point (e.g., when your clock runs low) and still have a usable answer.

Quiescence Search

If you stop searching at a fixed depth in the middle of a capture sequence, you get the horizon effect — e.g., you stop right after your queen captures a pawn, without seeing that the opponent recaptures your queen next move. Quiescence search extends the search at leaf nodes, but only considering "noisy" moves (captures, checks, promotions) until the position becomes "quiet," giving a much more stable evaluation.

Other Search Enhancements

Null move pruning: give the opponent a free extra move (skip your turn) and see if you're still winning — if so, the position is so good that you can prune deeply here, since real moves are only better. Late move reductions (LMR): search moves that are ordered late (i.e., probably not good) at reduced depth first, only doing a full-depth re-search if they unexpectedly look promising. Aspiration windows: instead of searching with a full [-INF, INF] window, guess a narrow window around the previous iteration's score — much faster if the guess is close, with a fallback to re-search wider if it fails. Principal Variation Search (PVS): assume the first move searched is best; search all other moves with a minimal [alpha, alpha+1] window just to prove they're worse, and only do a full re-search if one surprisingly beats alpha.

1. Evaluation Function

Search needs a way to score positions where it stops looking further. Classical (hand-crafted) evaluation combines many terms:

Material: sum of piece values (pawn = 1, knight/bishop ≈ 3, rook = 5, queen = 9 — with engines using finer-tuned values). Piece-square tables: bonus/penalty for each piece type based on which square it occupies (e.g., knights are worth more in the center than in the corner). Pawn structure: penalties for doubled, isolated, or backward pawns; bonuses for passed pawns. King safety: pawn shield presence, open files near the king, attacker counts. Mobility: number of legal moves/attacked squares available to each side. Piece coordination: bishop pairs, rooks on open files, control of key outposts.

Classical engines (like older Stockfish versions) hand-tuned these weights, often using automated tuning against large game databases.

NNUE (Efficiently Updatable Neural Network)

Modern top engines (Stockfish since 2020, and others) replaced hand-crafted evaluation with NNUE: a small neural network that takes the position (encoded as sparse features — essentially "which piece is on which square, relative to each king") and outputs an evaluation score.

The "efficiently updatable" part is the key engineering trick: because only a couple of pieces change per move, the network's first-layer activations can be updated incrementally rather than recomputed from scratch, making it fast enough to call millions of times per second on a CPU — no GPU required. This is why Stockfish, a pure alpha-beta engine, could adopt a neural evaluation without losing its search speed advantage.

1. The Other Paradigm: Monte Carlo Tree Search (MCTS)

AlphaZero and its successors (Leela Chess Zero) use a fundamentally different search algorithm: MCTS, guided by a neural network trained through self-play reinforcement learning.

MCTS works by repeating four steps many times per move:

Selection: walk down the tree from the root, picking children according to a formula (like PUCT) that balances exploiting known-good moves and exploring under-tried ones. Expansion: once you reach a node not yet expanded, add its children. Evaluation: instead of a random rollout to the end of the game (as in classic MCTS for other games), AlphaZero-style engines ask a neural network directly for a position evaluation and a policy (probability distribution over promising moves). Backpropagation: propagate that evaluation back up the tree, updating visit counts and average values along the path.

Unlike alpha-beta's fixed-depth, node-by-node exhaustive exploration, MCTS spends its computational budget adaptively — exploring promising lines much more deeply than unpromising ones, guided entirely by the network's judgment.

This is genuinely a different philosophy: alpha-beta engines like Stockfish search narrowly and deep with strong pruning; MCTS engines like Leela search broadly, letting the policy network suggest where to look and the value network judge what it finds.

1. Endgame Tablebases & Opening Books

Two more pieces round out a complete engine:

Opening books: precomputed databases of strong opening moves (from grandmaster games or engine analysis), used instead of searching from scratch in well-known positions. Endgame tablebases (e.g., Syzygy tablebases): for positions with few pieces left (commonly ≤7), the exact outcome (win/loss/draw and moves-to-mate) has been computed exhaustively via retrograde analysis — working backward from checkmate positions. When a search reaches a tablebase position, the engine gets a perfect answer instantly instead of searching further.

Putting It All Together

A modern classical engine's move loop looks roughly like:

for depth = 1 to maxDepth (iterative deepening): run alpha-beta search with: — transposition table lookups/stores — move ordering (hash move, MVV-LVA, killers, history) — null move pruning, LMR, aspiration windows — quiescence search at leaf nodes — NNUE evaluation at leaves — tablebase probes near the endgame if time is up: stop and return best move found so far

Neural MCTS engines swap the entire alpha-beta search out for the four-step MCTS loop, but still rely on the same board representation and move generation machinery underneath.

If you want a rewarding project, building a basic engine that does bitboards + alpha-beta + a simple material/PST evaluation is very achievable, and you can incrementally bolt on transposition tables, quiescence search, and eventually NNUE as separate milestones — each one is individually a fun and self-contained problem to implement and test.

If there's interest, I can follow up with a deeper dive into any single piece here — magic bitboards, NNUE architecture, or MCTS/PUCT in detail.