The Killer Move Heuristic is a move-ordering refinement layered on top of alpha-beta pruning: whenever a move causes a beta cutoff at some search depth, remember it — not by which position it was played in, the way Transposition Tables key their own cache, but by which depth (ply from the root) the cutoff happened at. The next time the search reaches a different branch at that same depth, try the remembered move first, ahead of whatever order move generation would otherwise offer. The bet is narrow but often pays off: a move that refuted one line at depth d frequently refutes a sibling line at the same depth too, because the reason it worked — it blocks the opponent's strongest threat, or completes one of your own — is often a property of the position's shape at that depth, not of the exact sequence of moves that got there. Alpha-beta already visits every legal move regardless of order and never changes its answer because of it — reordering can only change how many branches get pruned before the rest are proven not to matter, never what the search eventually returns.
Same fixed board as Minimax and Principal Variation Search, O to move. Pick a mode — plain alpha-beta, or alpha-beta with the killer heuristic layered on top — and a root order, which controls what sequence the root tries its four candidate cells in (the killer heuristic itself only ever reorders moves at depth 1 and below; the root's own order is this page's explicit dial instead, same convention as Principal Variation Search's demo). Press Step or Run. A move tried because it's a remembered killer for its depth is logged as such; watch the log for a cutoff line recording a fresh killer, and then for that same cell jumping to the front of a later sibling branch's move order.
Alpha-beta prunes hardest when the best move at a node is tried first — the sooner a strong
reply is found, the sooner alpha (or beta) tightens, and the sooner later
siblings fail the cutoff test without needing to be searched at all. Nothing about a fresh node
tells the search which of its legal moves is strongest before trying any of them — except one
thing memory can supply cheaply: what worked last time the search stood at the same depth,
in a different branch. Two sibling subtrees at the same depth are different positions, but they
often share the same tactical shape — the same square blocks the same kind of threat, or completes
the same kind of line — so a move that caused a cutoff once is a better-than-random guess at what
will cause one again.
Keying that memory by depth rather than by position is the whole trick, and it's also the thing easiest to get wrong (see Pitfalls below). A Transposition Table only pays off when the exact same position recurs — a real transposition, the same board reached by a different move order — which on a board this small and a game this short is rare. A depth-indexed killer list needs no such coincidence: it fires on structural similarity between different positions at the same ply, a far more common event than two branches converging on the literal same board. That's also exactly why it's a weaker signal than a transposition table hit — a killer is a guess, not a certainty, and trying it first only helps if it's still a legal move in the branch that reaches for it (usually true early in a game with many empty cells, never guaranteed).
function alphaBeta(board, depth, maximizing, alpha, beta) {
const w = winner(board);
const empties = emptyCells(board);
if (w || empties.length === 0) return score(w, depth);
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of empties) {
board[cell] = mark;
const value = alphaBeta(board, depth + 1, !maximizing, alpha, beta);
board[cell] = null; // undo
best = maximizing ? Math.max(best, value) : Math.min(best, value);
if (maximizing) alpha = Math.max(alpha, best); else beta = Math.min(beta, best);
if (beta <= alpha) break; // cutoff
}
return best;
}
function alphaBetaKiller(board, depth, maximizing, alpha, beta, killers) {
const w = winner(board);
let empties = emptyCells(board);
if (w || empties.length === 0) return score(w, depth);
// move remembered killers for this depth to the front, but only the ones
// that are actually still legal (still empty) in THIS branch
const stored = killers[depth] || [];
const front = stored.filter(c => empties.includes(c));
const rest = empties.filter(c => !front.includes(c));
empties = front.concat(rest);
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of empties) {
board[cell] = mark;
const value = alphaBetaKiller(board, depth + 1, !maximizing, alpha, beta, killers);
board[cell] = null;
best = maximizing ? Math.max(best, value) : Math.min(best, value);
if (maximizing) alpha = Math.max(alpha, best); else beta = Math.min(beta, best);
if (beta <= alpha) {
// this move caused the cutoff -- remember it for this depth, most-recent first, cap 2
let k = (killers[depth] || []).filter(c => c !== cell);
k.unshift(cell);
killers[depth] = k.slice(0, 2);
break;
}
}
return best;
}
// root call: alphaBetaKiller(board, 0, false, -Infinity, Infinity, {})Skip the legality filter on a stored killer and the search doesn't just get slower — it
returns a wrong score, checked directly. The reference implementation above filters
stored down to front before trying anything, because a killer remembered
from one branch is frequently not an empty cell in a different branch at the same depth —
measured directly on this page's own board, 13 of the killer lookups performed
during the small demo search land on an already-occupied cell, and 5,161 do from a
completely empty starting board. Delete that filter — try every remembered killer regardless of
whether the cell is still empty — and the search silently plays into an occupied square, overwriting
whatever mark was already there instead of raising an error. On this page's own demo board the
correct value is -7 (matching Minimax's and
Principal Variation Search's own figure
for the identical position); the unfiltered version returns 0, claiming a drawn
position that isn't one, while visiting 66 nodes — more than plain
alpha-beta's own 39, not fewer, since a corrupted board can dodge the real
terminal conditions and wander deeper than a legal game ever could. From a completely empty board
the gap is worse: the correct value is 0 (perfect tic-tac-toe is a proven draw), the
unfiltered version returns -5 — claiming O can force a win from the very first move —
while visiting 63,705 nodes against the filtered version's 8,038
and plain alpha-beta's own 20,866. The bug doesn't just fail to help; it actively
costs more than doing nothing at all, in both correctness and time.
Key the killer list by board position instead of by depth and the heuristic survives —
correctness holds — but most of its benefit quietly disappears, checked directly. Swap
killers[depth] for killers[boardSignature] everywhere above and every
value returned is still exactly right, since a legal, correctly-filtered reorder never changes
alpha-beta's answer, only its node count. But on this page's own small demo board a
position-indexed table only ever fires on a genuine transposition — the exact same board reached by
a different move order — which barely happens on a board this size: node count comes back at
40, identical to plain alpha-beta with no benefit at all, because none of the
positions visited during that particular search repeat. From an empty board, real transpositions do
start to occur, so position-indexing isn't worthless — 11,775 nodes, a real
improvement over alpha-beta's 20,866 — but it still leaves most of the win on the
table next to depth-indexing's 8,038. The lesson isn't that position-keying is
broken; it's that it answers a narrower, rarer question ("has this exact position been
seen before") when the heuristic's whole value comes from answering a much more common one instead
("has this depth seen a move like this work before").
Time: O(b^d) worst case, identical to plain alpha-beta's own
bound — a bad killer list can only ever cost the price of trying one extra move first before
falling back to the normal order, never change what gets visited overall, since every legal move
still gets tried exactly once either way. The realized savings depend entirely on how often a
remembered killer is both still legal and actually still good where it's tried. Checked directly on
this page's own small demo board across three root orderings: with the board's natural order (3,
4, 6, 8), plain alpha-beta visits 40 nodes against the killer heuristic's
39; reorder so the true best move goes first and the two tie exactly at
29, since an already-optimal order leaves the heuristic nothing to improve on;
force the worst root order instead (best move tried last) and plain alpha-beta climbs to
49 while the killer heuristic holds at 39 — the heuristic's
edge grows precisely when the given move order is worse, never shrinks below matching it. The
pattern is far sharper from a completely empty board with no favorable root reordering at all
(fixed left-to-right order, cells 0 through 8): plain alpha-beta visits 20,866
nodes, the killer heuristic visits 8,038 — a 61.5% reduction,
recovering more of the loss from a naive move order than
Principal Variation Search's own empty-board
figure (18,111, about 13% fewer) manages on the identical board, at a fraction of
that page's bookkeeping — no null-window re-searches, no scores to reconcile, just a handful of
remembered cell numbers. Space: O(d) extra — one short list (capped at
two entries here, matching common practice) per depth of the tree, nowhere near
Transposition Tables' own
O(distinct positions) cost, because a killer list only ever needs to be as deep as the
search itself, never as wide as every position that search has ever visited.
This is the site's tenth Game Trees entry, and like Principal Variation Search and MTD(f) it isn't a competing way to decide a move — it's a third, independent refinement that only ever applies once Minimax with alpha-beta pruning has already been chosen. Where Principal Variation Search spends a cheap null-window question to confirm the assumed-best move and MTD(f) spends repeated null-window probes against a shared bound table to narrow toward the exact value, the killer heuristic spends almost nothing — a depth-indexed list holding at most two cell numbers — to guess which move is worth trying first, and it's the only one of the three whose worst case never costs more nodes than doing nothing at all. It composes cleanly with either: neither PVS's window-narrowing nor MTD(f)'s probe-and-remember loop cares what order the moves inside a node are tried in, only what values come back, so a real engine can (and typically does) run all three side by side, with the killer heuristic feeding both a better first guess. It doesn't touch Transposition Tables' or Zobrist Hashing's own concerns either — nothing here is cached and no position is ever hashed — and it's orthogonal to Iterative Deepening and Quiescence Search too, both of which decide how deep or how far to search rather than which move to try first at a node already reached. See Choosing a Game Tree Search Algorithm for how all ten compare side by side, including where this page's own depth-indexed memory fits next to Transposition Tables' position-indexed one.