Null Move Pruning is a fourth refinement layered on top of alpha-beta pruning, and unlike Principal Variation Search, MTD(f), or the Killer Move Heuristic, it doesn't touch move ordering or the search window's bookkeeping — it asks a single, aggressive question at every node before trying any real move at all: "if I skipped my turn entirely and let the opponent move right away, would I still be doing fine?" If a quick, artificially shallow search of that hypothetical — the null move — already proves the position is at least as good as the search needs (it fails high against the current bound), the assumption is that a real move, which the mover actually gets to choose, can only do at least as well — so the whole branch gets pruned without ever searching a single real reply. This only makes sense for a search that's already depth-limited and backed by a static evaluator, the way Iterative Deepening's own page is — there's no "remaining budget" to hand to the opponent for free in an exhaustive search that always plays to a real, finished game.
Same fixed board as Minimax and Iterative Deepening, O to move, searched to a depth limit with Iterative Deepening's own line-counting heuristic at any cutoff instead of a real finished game. Pick a mode — plain depth-limited alpha-beta, or alpha-beta with null move pruning layered on top — a depth limit, and a reduction (R), the number of extra plies skipped past the normal one when probing the null move. Press Step or Run. A null-move probe is logged when it starts and when it resolves; watch for a prune line immediately after one — that's the whole branch getting skipped on the probe's word alone.
The bet null move pruning makes is that having a move to make is never a disadvantage —
whatever the opponent could achieve against a mover who does nothing, a mover who gets to actually
choose from every legal option should be able to match or beat it. Encoding "do nothing" costs
nothing to the recursion itself: the board doesn't change, only the side to move flips and the depth
counter jumps forward by 1 + R instead of the usual 1, pretending
R extra plies of search budget have already been spent for free. That reduced-depth probe
is cheap for exactly the reason Iterative Deepening's
own page measures a shallower pass costing less than a deeper one — fewer plies of real branching
before the heuristic cutoff fires. If even that cut-rate probe reports the position is already good
enough, the full-price search of every real move is skipped entirely.
Checked at a scale where it matters: searching this page's demo board from a completely empty 9-cell grid (the same empty-board comparison Minimax's, Iterative Deepening's, and Killer Move Heuristic's own pages all cite separately from their small interactive boards) to a depth limit of 5 with a reduction of 3, plain depth-limited alpha-beta visits 1,787 nodes; alpha-beta with null move pruning visits 803 — 55.1% fewer, for the identical final value, checked directly rather than assumed. Two settled implementation rules are baked into the reference code below, not just asserted: never attempt a null move at the root (depth 0) — the root's actual answer is the move itself, not just a fail-high proof that some move exists — and never attempt two null moves back to back (a probe's own recursive call is entered with null moves disabled), since stacking hypothetical free turns for both sides at once no longer approximates anything about the real game.
// heuristic() and score() are unchanged from iterative-deepening.html's own reference
// implementation, reused verbatim — the same line-counting static evaluator, the same
// depth-prefers-a-faster-win terminal scoring.
function nullMoveSearch(board, depth, maximizing, alpha, beta, depthLimit, R, allowNull) {
const w = winner(board);
const empties = emptyCells(board);
if (w || empties.length === 0) return score(w, depth); // real, finished game
if (depth >= depthLimit) return heuristic(board); // out of budget — guess instead
if (allowNull && depth > 0 && depth + R < depthLimit) {
// the null move itself: board unchanged, turn flips, depth jumps by 1 + R.
// allowNull is false on the way in, so this probe can't chain a second null move.
const nullScore = nullMoveSearch(board, depth + 1 + R, !maximizing, alpha, beta, depthLimit, R, false);
if (maximizing && nullScore >= beta) return beta; // "fine without moving" -> fine full stop
if (!maximizing && nullScore <= alpha) return alpha;
}
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of empties) {
board[cell] = mark;
const value = nullMoveSearch(board, depth + 1, !maximizing, alpha, beta, depthLimit, R, true);
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) break;
}
return best;
}A reduction that lands the probe exactly on the depth cutoff trusts a raw heuristic guess
over any real search — and it can pick a genuinely worse move, not just report a slightly-off
score. Take a small, hand-built position: O at cell 3, X
at cell 5, X to move, searched to depth limit 3 with R = 1. A real,
full depth-limited search of every one of X's seven replies finds the true best move is cell
4 (the center), worth 12 — none of X's other six replies clear
9. Null move pruning, searching the identical position with the identical settings,
settles for cell 0 instead, worth only 9 — a different, worse move,
confirmed by rerunning both searches over all seven replies and comparing move-for-move, not just
comparing final scores. The mechanism is visible in the numbers: once X plays cell 4, it's O's turn
at depth 1, and depth + R (1 + 1 = 2) is less than the depth limit
(3), so a null probe fires — but the probe's own target depth,
depth + 1 + R (1 + 1 + 1 = 3), lands exactly on the depth limit.
The probe never explores a single real reply for O; it falls straight through to
heuristic(board) with X's center mark already placed, and that raw heuristic value is
9 — which is ≤ alpha (already 9 from X's earlier, worse
replies), so the branch is pruned on the spot. The branch that would have proven X's center move is
actually worth 12 never gets the chance, because the probe assigned to check it did no
real search at all. Real engines guard against exactly this by refusing to null-move once too little
depth remains for the probe to do genuine work, and by re-verifying a null-move cutoff with an
ordinary search before trusting it outright near the horizon — safeguards this reference
implementation deliberately leaves out to keep the failure visible.
A reduction that's too small relative to the remaining depth is a pure performance
own-goal — never wrong, just slower, sometimes drastically so. On the empty-board sweep
above, R = 1 at a depth limit of 9 (a full, real game)
visits 80,790 nodes against plain alpha-beta's 20,866 —
3.9x more, for the exact same final answer, checked directly. The probe itself
is the cost: when R barely shortens the remaining search, the "cheap" null-move check
at every node costs nearly as much as just trying the real moves would have, and on this sweep it
essentially never pays for itself by triggering a cutoff, so every node pays the probe's overhead on
top of its own normal work. The identical technique at R = 4 on the same
depth-9 search instead saves a modest 8.8% (19,036 nodes) — same code, same board,
opposite outcome, purely from how generously the reduction cuts into the probe's own budget.
Time: O(b^d) worst case, the same order as plain depth-limited
alpha-beta, since a null probe that never triggers a cutoff still falls through to a normal search of
every real move afterward — the probe is pure addition, never a substitute. Whether it comes out
ahead or behind in practice depends entirely on R relative to the depth budget at hand,
measured directly above across nine combinations of depth limit and reduction on the identical empty
board: savings ranged as high as 53.3% (depth limit 3, R=1: 78 vs. 167 nodes) down
to a 3.9x cost increase (depth limit 9, R=1) for the same technique with the
reduction tuned wrong. Space: O(d), unchanged from
Minimax — a null-move probe recurses like any other call and
returns before the real move loop begins, never holding more than one line of play in memory
regardless of mode.
This is the site's twelfth Game Trees entry, and a fourth refinement on alpha-beta alongside Principal Variation Search, MTD(f), and the Killer Move Heuristic — none of the four compete with each other, and a real engine typically runs several at once. Where the other three only ever change how the same nodes get searched (move order, window width, probe-and-remember), null move pruning is the first willing to skip an entire branch on a cheap hypothetical's word alone, the same trust-a-shortcut trade Iterative Deepening's own heuristic cutoff already makes at the depth limit, just applied one layer earlier, before any real move at a node is tried at all. See Choosing a Game Tree Search Algorithm for how all twelve compare side by side, and when this page's own aggressive shortcut is worth the risk this page's own Pitfalls section measures.