Evolution
From Minimax to Modern Search
explore all
prune branches
one recursive fn
+ ordering + ID
Core pruning
Alpha-Beta: Cut What Cannot Win
If a move makes β ≤ α, the opponent already has a refutation — cut off remaining siblings without searching them.
Techniques
Layers of a Modern Search
One recursive function for both sides: score = −search(−α, −β). Maximizing and minimizing collapse into a single loop — simpler code, same result as minimax.
Search depth 1, then 2, then 3… Each pass fills the transposition table and produces a principal variation (PV) used to order moves at the next depth. Stoppable anytime — always have a best move ready.
First move at each node gets a full [α, β] window. Later moves use a zero-width scout (−α−1, −α). If a move fails high, re-search with full window. Assumes first move is best (thanks to ordering) — huge speedup.
Static eval at depth 0 is blind to hanging pieces (horizon effect). QSearch extends with captures (and often promotions/checks) until the position is “quiet,” then evaluates. Stand-pat: if eval ≥ α, skip captures.
Same position reached by different move orders shares one Zobrist hash key. Store depth, score, flag (exact / lower / upper bound), and best move. Depth-preferred replacement — skip re-searching known subtrees.
Null-move pruning: if giving a free pass still fails high, cut (not in check, enough material). LMR: reduce depth for late, quiet moves. Aspiration windows: narrow [α, β] around last iteration's score. All guarded — wrong guards cause tactical blindness.
Alpha-beta efficiency depends on trying the best move first. Bad ordering = almost no cutoffs.
- Transposition table best move
- Captures ordered by MVV-LVA (Most Valuable Victim — Least Valuable Aggressor)
- Killer moves (quiet moves that caused cutoffs at this depth)
- History heuristic (quiet moves that caused cutoffs anywhere)
- Remaining quiet moves
Output
What the GUI Sees During Search
UCI info lines (each iterative deepening pass)
Engine reports depth, score in centipawns (or mate in N), nodes searched, nodes/sec, and principal variation — the expected best line.
pv e2e4 e7e5 g1f3 b8c6 f1b5 a7a6
bestmove e2e4 ponder e7e5
Reference
Search Stack Cheat Sheet
| Technique | Purpose | When skipped / guarded |
|---|---|---|
| Negamax | Unified max/min recursion | — |
| Alpha-beta | Prune losing branches | — |
| Iterative deepening | Progressive depth + PV for ordering | Stopped by time / stop |
| PVS | Fast re-search on fail-high | — |
| Quiescence | Fix horizon at leaf | Delta / depth limit in QSearch |
| Transposition table | Cache sub-tree scores | Insufficient stored depth |
| Null-move | Cut if position still good after pass | In check, endgame, shallow |
| LMR | Shallow search for unlikely moves | Captures, checks, PV moves |
| Move ordering | Maximize cutoffs | — |
Search depends on everything below it
Move generation must be perft-correct. Evaluation must be consistent (same sign for both sides). Magic bitboards and make/unmake must be fast — search calls them billions of times per move. Build the foundation first, then stack search on top.
Complete the engine series
Search sits on move gen, attacks, and eval — explore the full stack on FujiBit.
Related: Magic Bitboards · Engine Anatomy · All Blogs