Minimax picks a move in a two-player, zero-sum, perfect-information game by assuming both sides play optimally: one player (call it the maximizer) tries to push the final score as high as possible, the other (the minimizer) tries to push it as low as possible, and the recursion alternates between them all the way down to a finished game. It's the same explore-then-undo shape as N-Queens, Sudoku, and Graph Coloring — try a move, recurse, undo it, try the next — but with one difference that changes everything: every other move in the tree isn't yours to choose. It's picked by an adversary trying to make your outcome as bad as possible, not by a constraint you're trying to satisfy. Alpha-beta pruning is a second algorithm layered on top: it returns the exact same answer while skipping branches that provably can't change it, using two running bounds — α (the best score the maximizer can already guarantee) and β (the best the minimizer can already guarantee) — to detect when a branch has nothing left to offer.
The board below is fixed and it's O's turn to move. Nobody can win in one move here, and nobody can be blocked in one move either — the position needs to be searched a few moves deep before the right answer becomes visible. Pick a mode — plain minimax (explores every possibility) or alpha-beta pruning (skips branches it can prove don't matter) — then press Step or Run. Marks in the cells O and X started with stay dark for the whole search; marks the search is currently trying out are drawn in the accent color and undone the moment that branch is fully explored, exactly like a backtracking demo undoing a placement. Watch the node count in both modes — same final answer, different amount of work.
Every leaf of the recursion is a finished game — a win, a loss, or a draw — and gets a numeric
score: this demo scores an X win as 10 - depth and an O win as depth - 10,
so a win found sooner outranks the same kind of win found later (a faster win is strictly better to
have found, a slower loss is strictly better to be stuck with), and a draw is always 0.
Every internal node just asks "which of my children's scores do I want?" — the maximizer's node
takes the highest, the minimizer's node takes the lowest — and that answer bubbles all the way back
to the root as the value of the best move available right now.
The demo's own board makes the case for why this beats a shallow heuristic concretely. A common shortcut — win immediately if you can, otherwise block an immediate threat, otherwise play anywhere — finds neither an immediate win nor an immediate threat to block here, and falls through to "play anywhere," landing on cell 3. Full minimax instead finds that O playing cell 6 forces a win in exactly three more plies, regardless of how X responds: after O takes 6, O has two live three-in-a-row threats at once — row 6-7-8 and diagonal 2-4-6 — sharing no common blocking cell, so X's one reply can only stop one of them. That's a checked result, not an assertion: this exact board, run through the reference implementation below, returns cell 6 with a forced-win score, and running the shallow win-or-block heuristic on the same board returns cell 3, which the same search confirms only holds a draw. Minimax finds the guaranteed win a one-ply heuristic cannot see coming.
function minimax(board, depth, maximizing) {
const w = winner(board);
if (w) return score(w, depth);
if (isFull(board)) return 0; // draw
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of emptyCells(board)) {
board[cell] = mark;
const value = minimax(board, depth + 1, !maximizing);
board[cell] = null; // undo — try the next cell
best = maximizing ? Math.max(best, value) : Math.min(best, value);
}
return best;
}
function score(winnerMark, depth) {
if (winnerMark === 'X') return 10 - depth; // prefer a faster win
if (winnerMark === 'O') return depth - 10; // prefer a slower loss
return 0;
}
function minimaxAB(board, depth, maximizing, alpha, beta) {
const w = winner(board);
if (w) return score(w, depth);
if (isFull(board)) return 0;
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
for (const cell of emptyCells(board)) {
board[cell] = mark;
const value = minimaxAB(board, depth + 1, !maximizing, alpha, beta);
board[cell] = null;
if (maximizing) { best = Math.max(best, value); alpha = Math.max(alpha, best); }
else { best = Math.min(best, value); beta = Math.min(beta, best); }
if (beta <= alpha) break; // the opponent already has a better option elsewhere — stop looking
}
return best;
}Flip which side is maximizing and it doesn't crash — it just quietly picks a worse
move. On this demo's own board, O's four candidate moves score 0, 0, -7, 0
(cells 3, 4, 6, 8) — O wants the lowest score, so the correct pick is cell 6's
-7, the forced win. A version that mixed up maximizing and minimizing for whichever
side is actually moving would take the highest of those four instead, landing on any of
the 0-scored moves — a real, checked example of a sign bug that never throws an error
and never fails a type check, it just silently settles for a draw instead of a forced win.
Alpha-beta pruning never changes the answer — only verify that, don't assume it.
Run this exact board through both modes and both return the identical move (cell 6) and the
identical score (-7); what differs is only how much of the tree got visited —
57 nodes for plain minimax against 40 with alpha-beta, skipping 5
branches it could prove couldn't win. That's the whole guarantee pruning makes: an identical result
for less work, never a different or approximate one.
How much alpha-beta saves depends on the order moves are tried in, though the answer never does. This demo always tries empty cells in ascending index order (3, then 4, then 6, then 8), which happens to reach the true best move (6) third rather than first. Forcing the identical search to try cell 6 first instead — cutting the other three branches short much sooner — brings the node count down to 31; trying it last instead brings it up to 44. All three orderings return the same move and the same score, checked directly against each other, not just claimed — only the amount of pruning changes, which is exactly why real game engines invest effort in move ordering: search the most promising move first and the same guarantee costs less to reach.
Time: O(b^d) in the worst case for plain minimax, where
b is the branching factor (empty cells left) and d is the remaining depth
— exhaustive, since every leaf of the game tree gets visited. Alpha-beta pruning shares the same
worst case but improves to O(b^(d/2)) — effectively searching half as deep for the
same result — when moves happen to be tried in best-first order; this demo's own measured 57-vs-40
and 31-vs-40-vs-44 comparisons above show the real, order-dependent range between those two
extremes on one small board. Space: O(d) for the recursion stack and
the board itself, since only one hypothetical line of play is ever held in memory at a time — the
same space profile as the backtracking pages above, for the same reason.
Scaled up, the gap is dramatic rather than cosmetic: searching tic-tac-toe from a completely
empty board, plain minimax visits 549,946 nodes before returning the well-known
result that perfect play from both sides draws (score 0); alpha-beta pruning, same
board, same left-to-right move order, visits 20,866 — under 4% as many — for the
identical answer. Computed directly, not run live in the browser demo above, the same way
N-Queens' own Complexity section cites its 8×8
attempt count separately from the small board sizes its interactive demo actually runs.
This is the site's first Game Trees entry — the same recursive try-it-then-undo-it shape as N-Queens, Sudoku, Graph Coloring, and Hamiltonian Path / Cycle, turned adversarial: half the branches in the tree are chosen by an opponent trying to minimize your score, not by you searching for one that satisfies a constraint. Minimax's cost still scales with the size of the tree it searches, exhaustive or pruned — for games too large to search at all (a 19×19 Go board's opening branching factor is 361), Monte Carlo Tree Search estimates a move's value from random playouts instead of visiting every branch. Both minimax and MCTS assume the other side is a real adversary; Expectimax replaces that adversary with plain chance — a die, a shuffle, a random tile spawn — and averages over outcomes instead of assuming the worst one. None of the three remembers a position once it's done with it; Transposition Tables cache a fully-evaluated board so a different move order reaching the same position returns its score instantly instead of re-deriving it — including a checked pitfall where combining that cache naively with this page's own alpha-beta pruning returns the wrong answer. A fifth entry, Principal Variation Search, doesn't replace alpha-beta either — it restates this exact search in negamax's single-function form and adds a cheap null-window "is this better, yes or no" question before the expensive one, at the cost of a full re-search whenever that question comes back yes. A sixth, Iterative Deepening, doesn't change how any node gets scored either — it changes how deep the search is even allowed to go before falling back on a heuristic guess, the first entry in this family willing to stop early and estimate rather than search a position all the way to a real outcome. A seventh, Zobrist Hashing, doesn't decide anything or change how deep the search goes either — it's the specific technique that makes Transposition Tables' own cache key cheap to maintain, updating a running hash by one XOR per move instead of rebuilding a key from the whole board on every node. An eighth, Quiescence Search, doesn't decide a move or cache one either — it decides whether a position reached at the search horizon is settled enough to trust a static evaluator's number, keeping a depth-limited search from cutting off mid-capture and misjudging the result. A ninth, MTD(f), computes this exact same alpha-beta value a completely different way: instead of one full-window search, it runs repeated one-point-wide null-window probes against a shared, bound-tagged memory table, narrowing a floor and a ceiling toward each other until they meet at the true value — no full-window search involved at all. See Choosing a Game Tree Search Algorithm for how all ten compare side by side, and when alpha-beta stays the right default versus when one of the other eight fits better.