Search

The search subsystem is responsible for finding the best move in a given position. It explores the game tree using a sophisticated combination of algorithms, pruning techniques, and heuristics that have been refined over decades of computer chess research.

Negamax with Alpha-Beta Pruning

At its core, the search uses the Negamax framework with alpha-beta pruning — the standard game-tree search for two-player zero-sum games. The key insight is that a position's value for the side to move is the negation of its value for the opponent, which simplifies the min-max recursion into a single function.

The main entry point is Negamax::iterativeDeepening(), which repeatedly calls Negamax::search() at increasing depths. Each iteration starts with a narrow aspiration window around the previous iteration's score; if the search fails high or low, the window is widened and the iteration is restarted. This approach significantly reduces the number of nodes explored while still guaranteeing correctness.

Principal Variation Search (PVS)

Once the first move at each node has been searched with a full window, subsequent moves are searched with a zero window (alpha, alpha+1). If a zero-window search fails high, the move is re-searched with the full window. Because move ordering is usually excellent, the vast majority of moves are quickly refuted by the zero-window probe.

Pruning and Reduction Techniques

The following techniques are applied to reduce the search tree size without compromising the quality of the best move:

Technique	Description	Location in tree
Null-move pruning	Gives the opponent a free move; if they still can't beat beta, the position is likely too good	Internal nodes
Late Move Reductions (LMR)	Moves ordered late in the list are searched at reduced depth	Internal nodes, quiet moves
Futility pruning	Near leaf nodes, moves that cannot possibly raise alpha are skipped	Near leaves (depth ≤ 3)
Reverse futility pruning	If the static eval is far above beta, a beta cutoff is returned immediately	Near leaves
Singular extensions	When the transposition table move is significantly better than all alternatives, extend its search by 1 ply	Internal nodes
Check extensions	Positions where the side to move is in check are extended to avoid missing forced mates	All nodes
Delta pruning	In quiescence search, captures that cannot raise alpha even with the best possible material gain are skipped	Quiescence nodes

Quiescence Search

At the leaves of the main search, Negamax::quiescence() continues searching all captures and check evasions until the position is "quiet" — no more tactical exchanges are possible. This prevents the horizon effect, where the engine misjudges a position because it stops searching right before a queen capture or a checkmate.

Move Ordering

Effective move ordering is the single most important factor for alpha-beta efficiency: if the best move is searched first, the remaining moves are quickly pruned. The MovePicker class yields moves in the following priority order:

1. Hash move — The best move from the transposition table. If the current position has been searched before, this move is overwhelmingly likely to be the best or near-best.
2. Winning captures — Captures whose Static Exchange Evaluation (SEE) is positive, ordered by SEE value. A queen capturing a defended pawn loses material (SEE < 0) and is demoted.
3. Killer moves — Quiet moves that caused a beta cutoff at sibling nodes at the same ply. The engine stores two killer moves per ply.
4. Counter moves — The last quiet move that refuted the opponent's previous move.
5. Quiet moves — All remaining moves, sorted by a history heuristic score that accumulates statistics about which moves cause cutoffs across the entire search.
6. Losing captures — Captures with SEE < 0, tried last as a last resort.

See also

MovePicker, SearchHeuristics

Multi-Threaded Search (Lazy SMP)

The engine supports multi-threaded search using the Lazy SMP approach. Multiple threads search the same root position independently at slightly staggered depths (thread 0 searches depth d, thread 1 searches d+1, etc.). All threads share a single lock-free transposition table, so discoveries made by one thread immediately benefit the others through hash table lookups.

This approach is remarkably simple and effective: it requires no split-point synchronisation, no complex work-stealing, and scales well up to 8-16 threads on modern hardware. The thread count is configurable via the UCI Threads option.

See also

Negamax, ISearch