Adversarial Search and Games

The search problems of the last lessons had one agent moving through a passive world: the map does not rearrange itself to keep you from Bucharest. A game breaks that assumption. A second agent takes turns with you, sees the same board, and chooses its moves to make yours turn out badly. Its goals are in direct conflict with yours, and that conflict is what makes the setting adversarial. Planning ahead now requires anticipating an opponent who is also planning ahead.¹

This lesson treats the cleanest version of that problem: deterministic, turn-taking, two-player, zero-sum games of perfect information — chess, checkers, Go, tic-tac-toe. Both players see the whole board (perfect information), no dice intervene (deterministic), and one player's gain is exactly the other's loss (zero-sum). We call the two players MAX and MIN: MAX moves first and wants to maximize a final numeric outcome, MIN wants to minimize it. The messier cases — dice, hidden cards, fog of war — are the subject of the companion lesson, Games of Chance and Imperfect Information.

A game as a search problem

A game is a search problem with a few extra pieces. The state space and the transition model carry over unchanged from ordinary search; what is new is that two players alternate control, and terminal states carry a numeric payoff rather than a plain goal flag.²

The utility function is the whole point of contact between the game's rules and the search. In chess the outcome is a win, loss, or draw, worth $+1$, $0$, or $\frac{1}{2}$; backgammon payoffs range from $0$ to $+192$. A game is zero-sum when the total payoff to all players is the same constant for every terminal state — chess is zero-sum because every game pays out $0+1$, $1+0$, or $\frac{1}{2}+\frac{1}{2}$. (Constant-sum would be the more honest name, but zero-sum is traditional.) In a two-player zero-sum game one number suffices: MAX's utility, with MIN's being its negation, so a single value $U$ at each terminal state describes the outcome for both.

$S_0$, $\text{Actions}$, and $\text{Result}$ together define the game tree: a tree whose nodes are game states and whose edges are moves, with the two players' moves alternating level by level.

For tic-tac-toe the tree has fewer than $9!=362,880$ terminal nodes, small enough to draw. Chess has over $10^{40}$ nodes — a construct we can reason about but never build. Either way, it is MAX's job to search enough of the tree to decide what to do; the part actually examined is a search tree superimposed on the full game tree.

Optimal decisions: the minimax value

In an ordinary search problem the solution is a sequence of actions to a goal. In a game MIN gets a say between every pair of MAX's moves, so MAX cannot commit to a fixed sequence. MAX needs a strategy: a move for the initial state, then a move for each state that could result from every MIN reply, and so on down. The strategy that is optimal against an opponent who also plays optimally is captured by a single quantity per node, the minimax value.

Read the definition as a simple pessimistic rule: assume your opponent will always make your best move as bad as possible, then pick the move that leaves you best off under that assumption. Writing that as a recurrence, the minimax value is the utility at a leaf, a max over successors at a MAX node, and a min over successors at a MIN node:

The values are computed bottom-up: leaves get their utilities, and the min/max choices are backed up the tree as the recursion unwinds. Consider a two-ply tree — one move by MAX, one reply by MIN, so two half-moves, or two plies. The three MIN nodes each take the minimum of their three leaves; the root MAX node then takes the maximum of those three backed-up values.

The first MIN node backs up $\min (3,12,8)=3$; the other two back up $2$ and $2$; the root backs up $\max (3,2,2)=3$. The minimax decision at the root is the move $a_1$ that achieves this value — the move to the highest-valued successor. Because MAX assumes MIN plays optimally, this choice maximizes the worst case. If MIN ever plays worse than optimally, MAX only does better; a different strategy might exploit a specific weak opponent, but never at less risk against a strong one.

The minimax algorithm

The recurrence turns directly into a recursive, depth-first procedure. MAX-VALUE and MIN-VALUE call each other, walking all the way down to the leaves and backing values up; the top-level MINIMAX-DECISION returns the action whose successor has the best backed-up value.

Minimax performs a complete depth-first exploration of the game tree. If the tree has maximum depth $m$ and there are $b$ legal moves at each point, the time cost is $O(b^m)$ and the space cost is $O(bm)$ (generating all actions at once) or $O(m)$ (one at a time). For real games $O(b^m)$ is hopeless — chess has $b\approx 35$ and $m\approx 100$ — but this algorithm is the mathematical foundation on which every practical game player is built. The rest of the lesson is a sequence of ways to compute the same decision, or a good approximation of it, without paying the full $b^m$.

Alpha–beta pruning

The problem with minimax is the exponent, and we cannot remove it — but we can roughly halve it. Once a refutation to a move is found, there is no need to know how bad the move is, only that it is worse than something already available; the minimax value of the root can often be determined without examining every leaf. Alpha–beta pruning exploits this: run the same depth-first minimax search, but stop exploring a branch the moment it is clear that branch cannot affect the final decision. Applied to minimax it returns exactly the same move; it skips work that provably does not matter.³

Return to the two-ply tree. Suppose the search has finished the first MIN node, learning its value is $3$, so the root is worth at least $3$. Now it begins the second MIN node and finds its first leaf is $2$. That MIN node takes a minimum, so its value is at most $2$ — already below the $3$ MAX can guarantee elsewhere. MAX would never choose this branch, so its remaining leaves are irrelevant and can be pruned, unexamined. Writing the root's value as a formula makes the independence explicit: with the two unexamined leaves of the second node called $x$ and $y$,

The value of the root, and therefore MAX's decision, is independent of $x$ and $y$. Whatever they are, $z\le 2<3$, so that middle branch loses. Those leaves never needed to be looked at.

The general principle names two bounds carried down each path of the search:

Concretely: at a MAX node, if the running value $v$ ever reaches $\beta$ or above, MIN (higher up) would never let the game come here, so we stop and return $v$ (a beta cutoff). Symmetrically, at a MIN node, if $v$ drops to $\alpha$ or below, MAX would never come here, so we return $v$ (an alpha cutoff). The algorithm is minimax with exactly those two extra tests plus the bookkeeping to pass $\alpha$ and $\beta$ down.

Alpha–beta returns the identical value minimax would, so it is a pure efficiency win: it prunes only branches that cannot change the answer. On any tree it visits a subset of the nodes minimax would, and often it prunes entire subtrees rather than a few leaves.

Move ordering

How much alpha–beta saves depends entirely on the order in which moves are tried. If MIN's best replies are examined first, cutoffs happen early and whole subtrees vanish; if the worst are tried first, nothing prunes. In the tree above, the two leaves under the middle node were pruned only because its low value $2$ appeared before its higher siblings.

With perfect ordering — best moves always examined first — alpha–beta needs to examine only $O(b^{m/2})$ nodes instead of $O(b^m)$. The effective branching factor drops from $b$ to $\sqrt{b}$: for chess, from $35$ to about $6$. Put differently, in the same amount of time alpha–beta searches roughly twice as deep as plain minimax. With random ordering the count is about $O(b^{3m/4})$ for moderate $b$. Perfect ordering is of course unattainable (a function that always knew the best move could just play the game), but cheap heuristics get close: try captures first, then threats, then forward moves. Dynamic schemes go further — killer moves reorder to try moves that caused cutoffs elsewhere, and a transposition table hashes previously evaluated positions so that different move orders leading to the same board are not re-searched.

A worked pruning trace

The two-ply picture shows that pruning happens; a slightly larger tree shows how the $(\alpha ,\beta )$ window produces the cutoffs. Take a three-ply tree — MAX at the root, MIN below, MAX below that, then leaves — with three children everywhere and the twelve leaves, read left to right, equal to $3,12,8,2,4,6,14,5,2,11,7,9$ grouped into four MIN nodes. (Here the bottom search level is a MAX level, so each of the four grand-nodes below the root is a MIN node over three MAX leaves; we take the leaves directly to keep the arithmetic short.) Walk the depth-first search carrying $(\alpha ,\beta )$, opening at $(-\infty ,+\infty )$ at the root.

The first MIN node is explored with $(\alpha ,\beta )=(-\infty ,+\infty )$. Its leaves $3,12,8$ give $v=3$; no leaf ever drops to $\alpha =-\infty$, so nothing prunes and it returns $3$. Back at the root, $\alpha \leftarrow \max (-\infty ,3)=3$: MAX can already guarantee $3$.

The second MIN node inherits $(\alpha ,\beta )=(3,+\infty )$. Its first leaf is $2$, so $v=2$. The MIN-node test $v\le \alpha$ fires — $2\le 3$ — an alpha cutoff: MAX would never enter this node, so its remaining leaves $4,6$ are pruned. It returns $2$; the root's $\alpha$ stays $3$.

The third MIN node inherits $(3,+\infty )$. Leaf $14$ gives $v=14$; then $\beta \leftarrow \min (+\infty ,14)=14$, leaf $5$ gives $v=5$, $\beta \leftarrow 5$, leaf $2$ gives $v=2$. No cutoff ($v$ never fell to $\alpha =3$ before the last leaf; the check $2\le 3$ would fire on the very last child, saving nothing), so it returns $2$. The root's $\alpha$ stays $3$.

The fourth MIN node inherits $(3,+\infty )$. Leaf $11$ gives $v=11$, $\beta \leftarrow 11$; leaf $7$ gives $v=7>3$, no cutoff, $\beta \leftarrow 7$; leaf $9$ leaves $v=7$. It returns $7$. Root: $\alpha \leftarrow \max (3,7)=7$. The root value is $\max (3,2,2,7)=7$, and MAX plays toward the fourth node.

Of twelve leaves, two were pruned — the $4$ and $6$ under the second node — because that node's opening leaf $2$ already fell at or below the guarantee of $3$. Order matters exactly here: had the second node's leaves arrived as $6,4,2$, the value $2$ would surface only on the third leaf and nothing would prune. The trace also shows the asymmetry of the bounds. $\alpha$ tightened only at the root (a MAX node); $\beta$ tightened only inside each MIN node and reset to $+\infty$ on entry, because the root imposes no upper bound on a first-level MIN node.

Imperfect real-time decisions

Alpha–beta prunes a great deal, but it still searches all the way to terminal states for at least part of the tree, and for chess that depth is unreachable in the minutes a move is allowed. Claude Shannon's 1950 proposal was to cut off the search early and apply a heuristic evaluation function to nonterminal positions, treating them as if they were terminal. Two substitutions turn minimax into a real-time player: replace $\text{Utility}$ with an estimate $\text{Eval}(s)$, and replace $\text{Terminal-Test}$ with a cutoff test$\text{Cutoff-Test}(s,d)$ that stops at some depth $d$.⁴

In practice the cutoff test is a fixed depth limit combined with iterative deepening: search to depth $1$, then $2$, then $3$, returning the best move from the deepest search that finished before time ran out. Iterative deepening also supplies the move ordering that makes alpha–beta efficient, since each pass seeds the next.

Evaluation functions

An evaluation function returns an estimate of the expected utility from a position, exactly as the heuristics of informed search estimated distance to a goal. A good one must (1) order terminal states the same way the true utility does — wins above draws above losses — (2) compute quickly, and (3) correlate strongly with the real chance of winning at nonterminal states.

Most evaluation functions are a weighted linear function of features $f_i$ of the position, each weighted by $w_i$:

For chess the features are things like material — pawn $=1$, knight or bishop $=3$, rook $=5$, queen $=9$ — plus pawn structure and king safety. Summing feature contributions assumes each feature is independent of the others, which is false (a bishop is worth more in an open endgame), so strong programs use nonlinear combinations. The weights need not come from a human: they can be learned from data by the machine-learning techniques of a later module, and learning applied to chess confirms that a bishop is indeed worth about three pawns.

The horizon effect

Cutting off search introduces its own error. A crude material-only evaluation may misjudge a position because the decisive event lies just beyond the depth limit — the classic case being a piece about to be captured on the very next ply. The fix for wild swings is to keep searching non-quiescent positions (those with a favorable capture pending) a little deeper until they settle down, a technique called quiescence search.

Harder to remove is the horizon effect. It arises when the opponent is about to inflict serious, unavoidable damage, and the searching player finds a sequence of pointless delaying moves that pushes that damage past the depth limit — over the search's horizon. The program sacrifices material to postpone a loss it cannot prevent, sees only that the loss has vanished from view, and rates the sacrifices as good moves when they merely made things worse.

A singular extension mitigates it: a move that is clearly better than all alternatives is remembered and allowed to extend the search past the normal limit, deepening only the few lines where it matters. Forward pruning goes the other way, cutting some moves immediately (as beam search keeps only the $n$ best-looking moves) — faster but dangerous, since the true best move might be among those discarded.

Everything so far assumes a deterministic game of perfect information: no dice, and both players see the whole board. Loosen either assumption — add a random roll, or hide part of the state — and the minimax value has to be replaced by an expectation, and the search by something that reasons about what the agent cannot see. This continues in Games of Chance and Imperfect Information, which develops expectiminimax for stochastic games, belief-state reasoning for partially observable ones, and the line from Deep Blue's alpha–beta to AlphaGo's learned evaluation and Monte Carlo tree search.