Principal Variation Search (PVS, also called NegaScout) is a second refinement layered on top of alpha-beta pruning, built on a reformulation called negamax: instead of writing separate maximizing and minimizing branches, one recursive function always returns a score from the perspective of whichever side is about to move, and every call to a child negates that child's return value — "good for my opponent" becomes "bad for me" with a single sign flip, so the same code serves both sides. PVS's own idea sits on top of that: assume good move ordering means the first move tried at each node is probably the best one, search it with the normal full window, and then for every sibling after it, first run a cheap null-window scout — the narrowest possible window, just wide enough to ask "is this move better than what I've already got, yes or no?" A scout that says no is exactly as good as a full search for pruning purposes, at a fraction of the cost. A scout that says yes means the sibling might actually be the new best move, and its real value is still unknown — that one branch gets re-searched with the full window to find out how much better it is.
Same fixed board as Minimax and Transposition Tables, O to move, needing a few plies of search before the right answer becomes visible. Pick a mode — plain alpha-beta (identical algorithm to Minimax's own page, X-positive/O-negative scoring) or Principal Variation Search (negamax's convention instead: every value is from the mover's own point of view, always positive for whoever is about to move) — and an order, which controls what sequence the root tries its four candidate cells in. Press Step or Run. A scout entering a cell is logged as "null window"; when a scout comes back suggesting a move might be better than assumed, watch for the explicit re-search step that follows it.
A null-window search is cheap for the same reason alpha-beta pruning is cheap: the tighter the
window between α and β, the sooner some child's value pushes past it and the rest of that node's
children get skipped. A window of width one — (alpha, alpha + 1) in negamax's
integer-scored world here — is the tightest window that still means something, and it makes every
node underneath it prune as aggressively as it possibly can. The scout isn't trying to find the
sibling's exact value; it only needs one bit of information — "better than the current best, or
not" — and a maximally narrow window is the cheapest possible way to ask exactly that question,
nothing more.
What a failed (low) scout proves is enough on its own: the move is no better than what's already been found, so its exact value never matters and the search moves on, having paid for a heavily-pruned search instead of a full-width one. What a scout that fails high proves is weaker — only that the true value is at least somewhere past the window's edge, not what it actually is, because a null window forces cutoffs the instant the true value is confirmed to exceed it, before the search underneath has done the work to pin the value down exactly. That's the same "a pruned search returns a bound, not necessarily an exact value" fact Transposition Tables' own Pitfalls section runs into when caching alpha-beta's raw output — PVS runs into the identical fact from the other direction, by choosing to prune this aggressively on purpose and then having to pay for a re-search whenever that choice doesn't pan out.
function negamax(board, depth, color, alpha, beta) {
const w = winner(board);
if (w) return color * score(w, depth);
if (isFull(board)) return 0; // draw
const mark = color === 1 ? 'X' : 'O';
let best = -Infinity;
for (const cell of emptyCells(board)) {
board[cell] = mark;
const value = -negamax(board, depth + 1, -color, -beta, -alpha);
board[cell] = null; // undo
best = Math.max(best, value);
alpha = Math.max(alpha, best);
if (alpha >= beta) break; // same cutoff as alpha-beta, one inequality instead of two
}
return best;
}
// root call for O to move: negamax(board, 0, -1, -Infinity, Infinity)
// (color: +1 scores from X's point of view, -1 scores from O's)
function pvs(board, depth, color, alpha, beta) {
const w = winner(board);
if (w) return color * score(w, depth);
if (isFull(board)) return 0;
const mark = color === 1 ? 'X' : 'O';
let best = -Infinity;
let first = true;
for (const cell of emptyCells(board)) {
board[cell] = mark;
let value;
if (first) {
value = -pvs(board, depth + 1, -color, -beta, -alpha); // full window — this is the assumed-best move
} else {
value = -pvs(board, depth + 1, -color, -alpha - 1, -alpha); // null window: "better than alpha, yes or no?"
if (value > alpha && value < beta) {
value = -pvs(board, depth + 1, -color, -beta, -alpha); // scout failed high — find out for real
}
}
board[cell] = null;
best = Math.max(best, value);
alpha = Math.max(alpha, best);
if (alpha >= beta) break;
first = false;
}
return best;
}Skip the re-search and a scout's fail-high bound gets trusted as if it were exact —
checked directly, this silently overstates a position's value, not a crash or an obviously bad
move. Deleting the re-search branch above (always keeping the null-window result even
when it exceeds α) still finds the correct move on this page's own small demo board — cell 6,
value 7, just cheaper (37 nodes instead of 51) — every one of this board's four root branches
happens to land on the right number anyway, so testing only against this board would call the
broken version a free speedup and ship it. Run the identical broken search from a completely
empty board instead and it returns cell 0 with value 1 — claiming X can force a win
from the very first move. The true value, confirmed three separate ways (plain minimax, plain
alpha-beta, and the correctly re-searching Principal Variation Search above, all three agreeing),
is 0: perfect play from an empty tic-tac-toe board is a draw, the well-known result
Minimax's own Complexity section also cites. Both versions
even pick the same opening cell — 0 is a perfectly fine move to play either way — so the
bug hides behind a move choice that looks completely reasonable and only shows up in the claimed
score.
PVS is not strictly faster than plain alpha-beta — checked directly across three move orderings, mediocre ordering makes it slower, not faster. With this board's natural order (3, 4, 6, 8), alpha-beta visits 40 nodes; PVS visits 51, paying for 2 re-searches along the way. Reorder the same four root candidates so the true best move (cell 6) goes first and the two modes tie exactly — 29 nodes each, 0 re-searches, because every later scout correctly proves its sibling worse on the first try and none of them ever needs a second look. Force the worst order instead — cell 6 tried last — and alpha-beta reaches 49 while PVS reaches 60, still with 2 re-searches. The pattern holds because PVS's cost has two parts working in opposite directions: null-window scouts prune harder than alpha-beta would on the same node, but every scout that fails high pays for its own search a second time on top of the first — and how often that happens is entirely a property of how good the move ordering already was, the same dependency Minimax's own Pitfalls section already showed for plain alpha-beta, now with a second way to lose ground instead of just one way to gain it.
Time: O(b^d) worst case, identical to alpha-beta's own bound —
nothing about PVS changes what happens when move ordering gives no useful information at all, and
the extra re-search work on a fail-high scout means a genuinely unlucky ordering can cost more
nodes than plain alpha-beta would have spent on the same tree, not fewer, exactly as measured
above (51 vs. 40, and 60 vs. 49). The saving only shows up in aggregate, and only when scouts fail
high rarely enough that the pruning they buy outweighs the re-searches they cause. Searching from
a completely empty board with a fixed left-to-right cell order (0 through 8, no favorable
reordering at all) makes that case concretely: plain minimax visits 549,946
nodes, alpha-beta 20,866, and PVS 18,111 — about 13% fewer than
alpha-beta — while paying for only 13 re-searches across the entire tree.
Computed directly, not run live in the browser demo above, the same way
Minimax's own Complexity section cites its empty-board
figures separately from what its small interactive demo actually runs. Space:
O(d), same as plain minimax and alpha-beta — negamax still holds only one
hypothetical line of play in the recursion stack at a time; nothing about restructuring the
search into full-window and null-window calls changes what has to stay in memory. That's a
different trade than Transposition Tables
makes, which spends real memory — O(distinct positions) — specifically to avoid
redoing work, where PVS spends nothing extra in space and instead bets that most redone work
(the null-window scouts) will be cheap.
This is the site's fifth Game Trees entry, alongside Minimax with Alpha-Beta Pruning, Monte Carlo Tree Search, Expectimax, and Transposition Tables — but unlike the other three siblings that answer "what should I play right now" a genuinely different way (sampling instead of search, averaging instead of assuming an adversary, caching instead of re-deriving), PVS doesn't compete with alpha-beta at all. It's the same exhaustive adversarial search, restated in negamax's single-function form and given one more tool — a cheap first question before the expensive one — that only pays off when the move ordering feeding it is already decent. Real engines pair it with Transposition Tables for exactly that reason: a cached move from a previous, shallower search is a strong first guess at what to try first, which is precisely the ingredient PVS needs to avoid re-searching everything it touches. A sixth entry, Iterative Deepening, is exactly the search structure real engines wrap around that pairing: run to depth 1, then depth 2, then deeper, feeding PVS a strong first guess from each finished pass and always keeping a complete answer ready the instant the clock runs out. A seventh, Zobrist Hashing, is what actually makes that pairing cheap in practice: it's the technique behind the transposition table's own key, letting a previous-pass lookup and this page's own null-window scout both share one running hash updated by a single XOR per move instead of a key rebuilt from the whole board. A ninth, MTD(f), takes this page's own null-window idea and stops using it as a decoration on a full-window search entirely — every single probe it runs is a null window, and instead of throwing away a scout's proven bound the way this page's own re-search step does, it keeps that bound, tagged, in a shared memory table for the next probe to reuse. See Choosing a Game Tree Search Algorithm for how all ten compare side by side, including when this page's own refinement is actually worth its re-search cost and when it isn't.