Adversarial search and minimax

In an ordinary search problem the world just sits there while you plan a route: the maze doesn't move its walls to trap you. But now imagine planning your next move in chess, or tic-tac-toe, or the pebble game Nim. There is someone on the other side of the board, and every good move you can make, they are trying to stop. Your search is no longer against a passive maze — it is adversarial.

This page is about the cleanest version of that fight. We restrict ourselves to games that are:

For every such game there is a single, beautiful algorithm that plays it perfectly: minimax. It answers the only question that matters — what is my best move, assuming my opponent is as clever as I am?

The game tree

We call the two players MAX and MIN. By convention MAX moves first and wants the final score to be as large as possible; MIN wants it as small as possible. Because they alternate, the whole game unrolls into a game tree: the root is the current position (MAX to move), each edge is a legal move, and one full move by one player is called a ply. MAX nodes and MIN nodes therefore alternate level by level as we go down.

At the bottom sit the terminal positions — checkmate, a full board, the last pebble taken. Each terminal leaf is labelled with a utility: a number saying how good that ending is for MAX. A common convention is +1 for a MAX win, 0 for a draw, and -1 for a loss — but any numbers work, and bigger is always better for MAX, worse for MIN.

Define the value of a node by working up from the leaves:

The minimax value of the root is the score of the game under optimal play by both sides, and MAX's best move is the child that achieves it.

Backing the values up

The definition is recursive, but the picture makes it obvious. Below is a small game tree, two ply deep: a MAX root (a ▲), three MIN nodes beneath it (each a ▼), and nine terminal leaves whose utilities are already known. Step through the animation and watch the values get backed up, one level at a time, from the leaves to the root.

Read it from the bottom. Each MIN node assumes MAX will be forced into the worst of its options, so it takes the minimum of its three leaves: \min(3,12,8)=3, \min(2,4,6)=2, \min(14,5,2)=2. Now the root is a MAX node choosing among three moves worth 3, 2 and 2, so it takes the maximum: \max(3,2,2)=3. The minimax value of the game is 3, and MAX's best move is the left branch — the only one that guarantees it.

Notice what MAX does not do: it does not chase the tempting 14 or 12 in the other branches. Those leaves live under a MIN node, and a rational MIN would never hand them over — it would steer to the 2 instead. Minimax plans against the opponent's best reply, not its most generous one.

Minimax in code

The whole algorithm is one short recursion. We store the game tree as a nested structure — a leaf is just a number (its utility), and an internal node is a list of its children. A single function walks the tree, flipping between "take the max" and "take the min" at each level. Press Run:

// A leaf is a number (its utility for MAX); a node is a list of children. type Tree = number | Tree[]; // Root is a MAX node with three MIN children (matching the diagram above). const game: Tree[] = [ [3, 12, 8], // MIN node: min = 3 [2, 4, 6], // MIN node: min = 2 [14, 5, 2], // MIN node: min = 2 ]; function minimax(node: Tree, isMax: boolean): number { if (typeof node === "number") return node; // terminal: return its utility const values = node.map((child) => minimax(child, !isMax)); return isMax ? Math.max(...values) : Math.min(...values); } // The root is MAX. Score each top move, then choose the best. const moveValues = game.map((child) => minimax(child, false)); const rootValue = Math.max(...moveValues); const best = moveValues.indexOf(rootValue); console.log("Backed-up value of each move:", moveValues.join(", ")); console.log("Minimax value at the root:", rootValue); console.log("MAX should play branch", best + 1, "for a guaranteed", rootValue);

That single toggle — isMax flipping on every recursive call — is the entire idea of adversarial search: as we descend the tree we alternate between the player who maximises and the player who minimises, and the values ripple back up to tell MAX what to do.

It can't, not fully. Minimax as written explores the tree all the way to the terminal leaves, but the game tree of chess has something like 10^{40} reachable positions (and Go is far worse) — you could not enumerate them before the sun burns out. The fix is depth-limited search: descend only a fixed number of ply, then stop at a cutoff even though the game isn't over.

But a cutoff position has no true utility yet — nobody has won. So we estimate it with an evaluation function: a heuristic that guesses the utility of a non-terminal position (in chess, roughly "material plus king safety plus pawn structure…"). Minimax then backs up these estimates instead of exact utilities. Every strong classical game engine is exactly this: minimax to some depth, an evaluation function at the cutoff, and clever pruning to search deeper. The idea is unchanged — only the leaves became educated guesses.

The single most common mistake is to maximise at every level. Half the nodes in the tree are MIN nodes, and a MIN node takes the minimum of its children — it models an opponent working against you. If you take the max everywhere you are pretending the opponent will kindly help you win. Back the value up as max, min, max, min… down the alternating levels; get the direction wrong at one level and the whole answer is off.

Second subtlety: minimax assumes the opponent plays optimally, so its move is the best against a perfect adversary — the safe, worst-case choice. Against a weak opponent that same move can be needlessly cautious: minimax will happily settle for a guaranteed draw rather than gamble on a win, because it refuses to count on the opponent blundering. Playing to exploit a beatable opponent is a different (and harder) problem than playing not to lose.