Introduction

Modern chess engines use alpha-beta pruning with aggressive move ordering and selective search extensions as the primary tree search method. Stockfish, the strongest traditional engine, searches 60-100+ million positions per second using iterative deepening, null-move pruning, late move reductions, and transposition tables. AlphaZero and its successors introduced Monte Carlo Tree Search (MCTS) combined with neural network evaluation, replacing handcrafted evaluation functions. The current state of the art is a hybrid approach — Stockfish's NNUE (Efficiently Updatable Neural Network) combines traditional alpha-beta search with a neural network evaluation, outperforming both pure classical and pure neural approaches.

Minimax and Alpha-Beta Pruning

1Minimax tree (depth 3):
2        MAX
3       / | \
4     MIN MIN MIN
5    / \  |   / \
6   3  5  2  9  1     ← leaf evaluations
7
8Alpha-Beta prunes branches that cannot affect the result:
9        MAX (α=-∞, β=+∞)
10       / | \
11     MIN  |  MIN
12    / \   |    \
13   3  5   2    [pruned — already found 5 > 2]
14
15Result: same as minimax, fewer nodes evaluated

Alpha-beta pruning eliminates branches that provably cannot influence the final decision. With perfect move ordering, it reduces the effective branching factor from ~35 to ~6 in chess, examining the square root of the nodes minimax would require.

Move Ordering and Search Enhancements

1Modern alpha-beta search with enhancements:
2
31. Iterative Deepening
4   Search depth 1, then depth 2, ..., up to depth N
5   Use results from depth N-1 to order moves at depth N
6
72. Transposition Table (Zobrist hashing)
8   Hash each position → look up previously computed evaluations
9   Avoid re-searching positions reached by different move orders
10
113. Killer Move Heuristic
12   Track moves that caused beta cutoffs at each depth
13   Try these "killer moves" early in sibling nodes
14
154. History Heuristic
16   Track how often each move causes cutoffs across the entire search
17   Prioritize historically effective moves
18
195. Principal Variation Search (PVS)
20   Search the first (best-guess) move with full window
21   Search remaining moves with null window (α, α+1)
22   Re-search with full window only if null window fails high

Move ordering is the single most important factor for alpha-beta efficiency. The best move should be searched first to maximize pruning. Modern engines combine hash table moves, captures (MVV-LVA ordering), killer moves, and history scores to achieve near-optimal ordering.

Selective Search: Pruning and Reductions

1Late Move Reductions (LMR):
2  Move 1-4: search at full depth
3  Move 5+:  search at reduced depth (depth - 1 or depth - 2)
4  If reduced search returns surprisingly high score → re-search at full depth
5
6Null Move Pruning:
7  "What if I skip my turn?"
8  If opponent's best response still leaves me ahead → prune this branch
9  Reduces effective depth by 2-3 plies
10
11Futility Pruning:
12  Near leaf nodes, if static eval + margin < alpha
13  → skip this move (it cannot possibly raise alpha)
14
15Multi-Cut Pruning:
16  If multiple moves at a node cause cutoffs in shallow search
17  → the node is likely a cutoff at full depth too

These techniques let engines search 20-30 plies deep in the same time a pure alpha-beta search would manage 10-12 plies. The tradeoff is occasional tactical oversights, mitigated by verification searches and quiescence search at leaf nodes.

Quiescence Search

1Standard search reaches depth limit:
2  Position: White queen takes Black knight (capture in progress)
3  Static eval: +3.0 for White
4
5  But Black can recapture next move!
6  After recapture: +0.0 (equal)
7
8Quiescence search:
9  At leaf nodes, continue searching ONLY captures and checks
10  Until position is "quiet" (no pending captures/checks)
11  This prevents the "horizon effect" — pushing problems past search depth

Quiescence search extends the search selectively at leaf nodes to avoid evaluating tactically unstable positions. Without it, an engine might evaluate a position as winning right before a recapture turns it into a loss.

NNUE: Neural Network Evaluation in Stockfish

1Traditional evaluation:
2  score = material + piece_activity + king_safety + pawn_structure + ...
3  ~100 hand-tuned parameters
4
5NNUE evaluation (Stockfish 12+):
6  Input: piece positions on the board (768 binary features)
7  Architecture: sparse input → 256-node hidden layer → 32 → 32 → 1
8  Incremental update: only recompute changed piece features on each move
9  ~10M parameters, trained on billions of self-play positions
10
11Key insight: NNUE is fast enough for alpha-beta search
12  Traditional eval: ~2ns per position
13  NNUE eval:        ~5ns per position (with incremental updates)
14  Full neural net:  ~1ms per position (too slow for alpha-beta)

NNUE (Efficiently Updatable Neural Networks) gives Stockfish neural network-quality evaluation while maintaining the speed needed for deep alpha-beta search. The network is updated incrementally — when a piece moves, only the affected input features change, so most of the computation is reused.

Monte Carlo Tree Search (AlphaZero Approach)

1MCTS with neural network (AlphaZero/Leela Chess Zero):
2
31. SELECT: traverse tree using UCB formula
4   UCB(node) = Q(node) + c * P(node) * sqrt(N(parent)) / (1 + N(node))
5   Q = average value, P = policy prior from neural net, N = visit count
6
72. EXPAND: add new node to tree
8
93. EVALUATE: neural network returns (value, policy)
10   value: estimated win probability for current player
11   policy: probability distribution over legal moves
12
134. BACKUP: propagate value estimate up the tree
14
15Repeat 800-100,000 times per move (depending on hardware)

MCTS does not search exhaustively — it samples the tree, focusing on promising lines. The neural network provides both position evaluation (replacing handcrafted eval) and move prioritization (replacing move ordering heuristics). AlphaZero demonstrated superhuman play using MCTS alone, without any chess-specific knowledge beyond the rules.

Stockfish vs Leela Chess Zero

1Stockfish (NNUE + alpha-beta):
2  - Searches 60-100M positions/sec on CPU
3  - Depth 30-40+ in middlegame
4  - Deterministic given same time
5  - Runs on any hardware
6
7Leela Chess Zero (MCTS + deep neural network):
8  - Searches 40-80K positions/sec on GPU
9  - Depth varies (MCTS doesn't have fixed depth)
10  - Stochastic (randomized search)
11  - Requires GPU for competitive play
12
13Current standing (2024-2025):
14  - Stockfish is stronger in rapid/blitz (more nodes/sec matters)
15  - Both are ~3500+ Elo (far beyond any human)
16  - TCEC and CCC tournaments show Stockfish leading

Common Pitfalls

• Confusing search depth with strength: A deeper search is not always better if the evaluation function is poor. NNUE at depth 20 outperforms a handcrafted eval at depth 25 because the evaluation accuracy matters more than raw depth in complex positions.
• Ignoring the horizon effect: Without quiescence search, engines misjudge positions where a capture sequence is in progress. The engine sees a "winning" position that is actually losing after forced exchanges. Always extend search through tactical sequences.
• Over-pruning in tactical positions: Aggressive pruning (null move, LMR, futility) works well in quiet positions but can miss tactical shots. Modern engines reduce pruning aggressiveness when in check, when captures are available, or when the position is detected as sharp.
• Assuming MCTS is always superior to alpha-beta: MCTS excels with strong neural network evaluation and GPU hardware, but alpha-beta with NNUE achieves comparable or better results on commodity CPUs. The choice depends on available hardware and evaluation function quality.
• Overlooking transposition table collisions: Zobrist hashing can produce hash collisions where different positions map to the same entry. While rare, this can cause incorrect evaluations. Modern engines use verification techniques and larger hash tables to minimize collision impact.

Summary

• Alpha-beta pruning with move ordering remains the foundation of the strongest engines (Stockfish)
• NNUE combines neural network evaluation with alpha-beta search speed — the current state of the art
• MCTS with deep neural networks (AlphaZero/Leela Chess Zero) offers an alternative approach requiring GPU hardware
• Selective search techniques (LMR, null move pruning, futility pruning) enable 30+ ply searches in practical time
• Quiescence search prevents tactical errors at leaf nodes by extending through captures and checks
• Stockfish with NNUE currently leads in computer chess, combining the best of classical search and neural evaluation