The site's ten Game Trees entries split the same way Network Flow's six did: seven of them are genuinely competing answers to the same question — "what should I play right now" — and three aren't competing at all. Minimax, Expectimax, Monte Carlo Tree Search, Principal Variation Search, MTD(f), Killer Move Heuristic, and Iterative Deepening all decide a move; every one of their own closing paragraphs frames itself against the others in exactly those terms. Transposition Tables decides nothing — it's a cache that keeps any of the tree-searching four (not MCTS, not Expectimax — see the last section) from re-deriving a position it's already fully solved. Zobrist Hashing decides even less: it's the technique that makes the cache's own key cheap to maintain, one step further removed from "what should I play" than the cache itself. Quiescence Search decides something different again — not a move, not a cache key, but whether a position reached at a depth-limited search's own cutoff is settled enough to hand to a static evaluator at all. So this guide asks three questions to place the seven real algorithms, then treats the cutoff check, the cache, and its key in turn.
This is the fork Expectimax's own page draws first: "the future isn't fully mine to choose" has two
different causes, and confusing them is a silent, checked failure, not a crash. If a die, a shuffle, or a
random tile spawn decides what happens next — nobody is trying to beat you, the outcome is just
uncertain — that's Expectimax's exact setting: it reuses
minimax's max-node shape but replaces the minimizer with a chance node that averages its
children instead of picking the worst one. Mistake a chance node for a min node — assume the worst face
always comes up, the way an adversary would force it — and the page's own Push-to-21 demo shows the
damage directly: the true expected value from a fresh hand, EV[0] = 15.86, collapses to
exactly 12.00 once averaging is swapped for a minimum, and the optimal stand threshold shifts
from total 14 to total 12. No error is raised either way — it just quietly assumes an opponent is rolling
the dice against you.
If instead a real opponent is choosing moves to make your outcome worse — the setting Minimax, MCTS, Principal Variation Search, and Iterative Deepening all share — the next question is about the tree's size, not its uncertainty.
This site's own tic-tac-toe demo board (four empty cells, O to move) can: it's small enough that Minimax, Principal Variation Search, and Iterative Deepening all use it directly, and each one reaches a genuine win, loss, or draw at every leaf rather than a guess. A 19×19 Go board cannot — its opening branching factor is 361, per Minimax's own Complexity section, deep enough that no computer has ever searched it exhaustively. That size gap is the whole reason this question comes before anything else in the adversarial branch.
When the answer is yes, Minimax with alpha-beta pruning is the default: exhaustive, exact, and its own pruning only ever removes branches it can prove don't matter, never changes the answer. Checked directly on this site's own board: plain minimax and alpha-beta return the identical move and score every time, differing only in nodes visited — 57 against 40 here, 549,946 against 20,866 from a completely empty board. If move ordering is already decent, Principal Variation Search can layer on top as a refinement, not a replacement — see the note below on when that actually pays off, because it doesn't always. So can MTD(f), a second, independent refinement that trades scout searches for repeated null-window probes against a shared memory table instead — its own note below covers when that trade wins and when it doesn't. So can the Killer Move Heuristic, a third, independent refinement that spends almost nothing — a depth-indexed list of at most two cell numbers — to guess which move is worth trying first, and composes cleanly with either of the other two.
When the answer is no, the tree is too big to finish, and the next question decides which of two very different fallbacks fits.
Both remaining entries exist because a full search can't complete, and both trade exactness for a budget — but they spend that budget on opposite resources. Iterative Deepening needs a heuristic: a fast, static guess at who's winning from a non-terminal position, used the instant a depth-limited search runs out of budget before the game runs out of moves. It runs the same alpha-beta search repeatedly — depth 1, then depth 2, then deeper — always keeping a complete, usable answer on hand the moment the clock stops, and reusing each pass's best root move to speed up the next. That overhead is real, not the near-free cost the textbook geometric-series argument promises for a large, steady branching factor: checked directly, redoing every shallower pass costs 2.10× a single direct depth-4 search on this site's own small board (84 vs. 40 nodes, with root-move reuse) and still 2.28× from an empty board (47,534 vs. 20,866) — tic-tac-toe's own shrinking branching factor never gets large or stable enough for the "shallow passes are nearly free" argument to actually kick in.
Monte Carlo Tree Search needs no evaluation function at all — only "is this move legal" and "who just won," per its own page, the same two questions any playable game already answers. It substitutes random playouts and a visit count for a hand-tuned heuristic entirely, which is exactly why it's the approach that made strong computer Go possible: nobody had (or arguably has, even now) a reliable static evaluator for a mid-game Go position, but simulating a finished game with random moves needs no domain expertise beyond the rules. The cost is a different kind of risk: checked on this site's own seed, the most-visited move can be wrong, and not just briefly — cell 4 leads after 20 simulations, cell 6 (the true forced win) takes the lead at simulation 25, loses it again for simulations 26 through 34, then finally takes it for good at 35. Given enough simulations MCTS converges to the right answer (an offline sweep found the correct move in all 200 of 200 independently seeded runs), but "enough" isn't a fixed, guaranteed count the way Iterative Deepening's own depth-limited search always returns a complete, defined answer at whatever depth it reaches.
So: a reliable static evaluator you can compute cheaply at a cutoff → Iterative Deepening. No such evaluator, but simulating a legal random game to its actual end is cheap → MCTS.
Iterative Deepening's own heuristic only gets asked to judge a position once, at whatever ply the
depth budget runs out — and Quiescence Search exists
because that ply can land in the middle of a forced trade, where the static number is actively
misleading rather than merely approximate. Checked directly on quiescence search's own five-ply
capture-chain model: a plain depth-limited search's answer flickers between right and wrong depending
on exactly where the horizon falls — +1, 0, +1, 0, +1 across depths 1 through 5, wrong at
every even depth despite depth 4 being a strictly deeper search than depth 3. Quiescence search's fix
is to keep searching through capturing moves specifically, regardless of the depth counter, until the
position has no capture left on the table at all — checked on the same model, that returns the true
value (+1) at every one of the same five depth settings. It isn't a sixth way to decide a
move, any more than Transposition Tables or Zobrist Hashing are: it only ever pairs with a
depth-limited search that already needs one, sharpening what that search's cutoff is allowed to
trust.
Principal Variation Search only ever applies
once Minimax with alpha-beta has already been chosen — it restates that exact search in negamax's
single-function form and adds a cheap null-window "is this better, yes or no" scout before every full
search after the first, paying for a re-search only when a scout unexpectedly says yes. It shares
alpha-beta's own O(b^d) worst case exactly, and checked directly across three move orderings
on this site's own board, it is not reliably faster: with the board's natural order it
costs 51 nodes against plain alpha-beta's 40 (two re-searches paid for);
reorder so the true best move goes first and the two tie exactly at 29, zero
re-searches; force the worst order and PVS costs 60 against alpha-beta's
49 — still behind. The empty-board sweep is where it earns its keep: 18,111
nodes against alpha-beta's 20,866, about 13% fewer, for only 13 re-searches across the
whole tree. Reach for it once move ordering is already decent and the tree is large enough for the
pruning gains to outweigh the occasional re-search — not as a default swap-in for alpha-beta on a small
tree, where a bad ordering can make it the slower choice.
MTD(f) also only ever applies once Minimax with alpha-beta has
been chosen, and like Principal Variation Search it's a refinement rather than a competing path — but
it takes the null-window idea to its logical extreme instead of using it as a decoration. No full-window
search ever runs at all: MTD(f) probes with a one-point-wide window centered on a guess, reads which
direction the probe fails in, and narrows a floor and a ceiling toward each other one probe at a time
until they meet at the exact value. That only works because it keeps what Principal Variation Search's
own scouts throw away — the bound each null-window probe proves — tagged in a shared memory table so a
later probe can reuse it instead of re-deriving it. Checked directly on this site's own board, the
standard first guess of 0 converges in 3 probes and 49
total lookups (40 freshly evaluated, 9 reused); a first guess of
-10 takes 4 probes and 56 total lookups — worse than
plain alpha-beta's single-pass 40. The empty-board sweep is where, like Principal
Variation Search, it earns its keep regardless of guess quality: at most 6,099 total
lookups across every first guess tested, against plain alpha-beta's 20,866. Reach for
it once alpha-beta is already the right choice and either the tree is large enough for cross-probe
memory reuse to dominate, or a decent first guess is already on hand (an iterative-deepening pass's own
previous-depth value, for instance) — not as a default swap-in on a small tree with no good guess
available, where the extra probes can cost more than they save.
The Killer Move Heuristic also only ever applies once Minimax with alpha-beta has been chosen, and unlike Principal Variation Search or MTD(f) it doesn't touch the search window at all — it only reorders the moves a node tries, remembering which move caused a beta cutoff at each search depth and trying that move first the next time a different branch reaches the same depth. Checked directly on this site's own board across three root orderings: with the board's natural order it costs 39 nodes against plain alpha-beta's 40; reorder so the true best move goes first and the two tie exactly at 29, since an already-optimal order leaves nothing for the heuristic to improve on; force the worst order and the killer heuristic holds at 39 while plain alpha-beta climbs to 49 — its edge only grows as the given ordering gets worse. The empty-board sweep is where it's most striking: 8,038 nodes against alpha-beta's 20,866, a 61.5% reduction that beats Principal Variation Search's own empty-board figure (18,111) at a fraction of the bookkeeping — no re-searches, no scores to reconcile, just up to two remembered cell numbers per depth. Reach for it as the cheapest of these three refinements to add, and freely alongside either of the others — neither PVS's window-narrowing nor MTD(f)'s probe-and-remember loop cares what order a node's own moves are tried in, only what values come back.
Transposition Tables doesn't decide a move by any mechanism at all — it caches a fully-evaluated board by its own contents, so a different move order reaching the identical position returns its score instantly instead of re-deriving it. That only matters to algorithms that re-derive the same position more than once by design: Minimax's plain recursion visits a repeated position from scratch every time, and checked directly, a transposition table catches 16 of those repeats on this site's own board (33 freshly evaluated instead of 57) and 10,690 of them from an empty one (5,478 fresh instead of 549,946) — under 1% of the uncached count gets computed even once. Principal Variation Search and Iterative Deepening both benefit the same way, and both pages make the comparison from their own side too: Transposition Tables' own closing paragraph calls itself "the kind of hint" Iterative Deepening needs, and Iterative Deepening's own page independently notes it gets that same strong first guess for free from its own previous pass instead of a hashed cache. Expectimax's and MCTS's own pages call a transposition table "orthogonal" to what they do — "never answering the same question twice, chance node or adversary or otherwise" — but neither page demonstrates an actual cache-hit count for it the way Minimax, Principal Variation Search, and Iterative Deepening's own pages all do on this exact board.
Pairing a transposition table with alpha-beta pruning specifically needs one more idea neither page
builds by itself, and the two pitfalls that describe it are the same fact seen from opposite sides.
Transposition Tables' own Pitfalls section shows that caching alpha-beta's raw returned value and reusing
it elsewhere is unsafe — a pruned branch's return value can be only a bound, not the exact score,
and checked directly, storing it uncritically flips the empty board's proven-drawn result from
0 to a false 1. Principal Variation Search's own null-window scouts are, in its
own words, "a search strategy built specifically to return a bound instead of an exact value whenever a
full search isn't needed" — the exact shape of value a naive transposition table cache can't tell apart
from an exact one. Real engines fix this by tagging every cached entry exact, lower-bound, or upper-bound,
and only trusting a bound when the current search window actually needs that direction — bookkeeping
neither page builds itself, both flag as the reason they don't.
MTD(f) is where that exact tagging finally gets built, since its
entire driver loop depends on being able to tell an exact value apart from a bound — see its own aside
above.
Zobrist Hashing is one level further removed still — it doesn't cache anything itself, it's the technique that makes Transposition Tables' own cache key cheap to build. That page's reference implementation rebuilds its key from the whole board on every single node, hit or miss; Zobrist hashing precomputes one random number per (square, mark) and maintains a running hash with one XOR per move made and one per move undone instead. Checked directly on this site's own board: the naive key touches all 9 cells per node, 513 touches total across 57 nodes; Zobrist touches 112 — a 4.6× reduction that only grows with board size, since a real board's key rebuild scales with its square count while a Zobrist update never does. The tradeoff Zobrist Hashing's own Pitfalls section names and checks directly: a from-scratch board-string key can never collide, but a fixed-width hash can, and does — checked at a deliberately narrow 16-bit width, two genuinely different positions land on the identical hash. Real engines use 64-bit keys specifically because a narrower one collides sooner than intuition expects.
| Entry | Time | Space | Decides via | Reach for it when |
|---|---|---|---|---|
| Minimax + alpha-beta | O(b^d), O(b^(d/2)) best case | O(d) | exhaustive adversarial search to a real outcome | real adversary, tree small enough to search exactly |
| Expectimax | O((b·s)^d) | O(target) this demo, O(d) generally | exhaustive search, chance nodes averaged not minimized | no adversary, true probabilities known, tree small enough to search exactly |
| Monte Carlo Tree Search | O(n·d) for n simulations | O(n) | random playouts + UCB1 explore/exploit | tree too large to finish, no reliable static evaluator exists |
| Principal Variation Search | O(b^d), shared with alpha-beta | O(d) | negamax + null-window scouts, re-search on fail-high | refining alpha-beta once move ordering is already decent |
| MTD(f) | O(b^d) per probe, shared with alpha-beta | O(distinct positions) | repeated null-window probes against a shared exact/lower/upper-bound table | refining alpha-beta with a large tree or a decent first guess on hand |
| Killer Move Heuristic | O(b^d), shared with alpha-beta | O(d) | depth-indexed memory of cutoff-causing moves, tried first at a sibling branch | refining alpha-beta cheaply, alongside PVS or MTD(f) or on its own |
| Iterative Deepening | O(b^d), same order as one search to depth d | O(d) | successive depth-limited alpha-beta passes, heuristic at cutoff | tree too large to finish, a cheap reliable evaluator exists, need an anytime answer |
| Transposition Tables | O(b^d) worst case, collapses toward distinct positions | O(distinct positions) | caches a fully-evaluated position by its own contents | paired with Minimax, PVS, or Iterative Deepening — any search that re-derives the same position via a different move order |
| Zobrist Hashing | O(1) per move to update, vs. O(board size) to rebuild | O(squares × distinct pieces) | XORs one precomputed random number in or out per move | maintaining a Transposition Tables key cheaply, once the board is large enough that rebuilding it from scratch every node is real cost |
| Quiescence Search | O(c^k), c ≤ b restricted to captures only | O(k) | keeps following captures past the depth budget until the position is quiet | paired with Iterative Deepening (or any depth-limited search) whenever cutoffs can land mid-capture |