Adversarial Search and Minimax

Searching for a route differs from playing a game in one decisive respect: in a game, someone else moves next, and they are trying to make you lose. You cannot plan a fixed sequence of actions, because your opponent's replies are not yours to choose. Adversarial search handles this by assuming the opponent plays as well as possible, and computing the best response to that.

A. The game tree

Two players, conventionally MAX (who moves first and maximises) and MIN (who minimises the same quantity). A game tree has the initial position at the root, one branch per legal move, alternating layers of MAX and MIN nodes, and terminal positions at the leaves carrying a utility - the payoff to MAX.

Because MIN's utility is the negation of MAX's, this is a zero-sum game: what one gains the other loses exactly. That is what allows a single number per leaf to describe the outcome for both.

B. The minimax value

The value of a node is defined recursively:

$$\textsc{Minimax}(s) = \begin{cases} \textsc{Utility}(s) & \text{if } s \text{ is terminal},\\[4pt] \max_{a} \textsc{Minimax}(\textsc{Result}(s, a)) & \text{if } s \text{ is a MAX node},\\[4pt] \min_{a} \textsc{Minimax}(\textsc{Result}(s, a)) & \text{if } s \text{ is a MIN node}. \end{cases}$$

MAX picks the largest value among the children; MIN picks the smallest. Values propagate from the leaves up to the root, and MAX's best move at the root is the one leading to the child whose value equals the root's.

What the assumption buys, and what it costs. Minimax assumes the opponent plays optimally. Against an optimal opponent the value is exactly what MAX can guarantee, so it is a genuine worst-case guarantee, not a prediction. Against a weak opponent it is conservative: it may pass up a trap that a fallible opponent would fall into.

C. Working a tree by hand

A three-ply tree: the root is MAX, its three children are MIN nodes, each with three terminal children.

The MIN layer. Each MIN node takes the minimum of its children:

$$B = \min(3, 12, 8) = 3, \qquad C = \min(2, 4, 6) = 2, \qquad D = \min(14, 5, 2) = 2 .$$

The root. MAX takes the maximum:

$$\textsc{Minimax}(\text{root}) = \max(3, 2, 2) = 3 .$$

MAX should move to $B$, guaranteeing at least 3.

Note how little the large leaf values matter. The $12$ under $B$ and the $14$ under $D$ are never obtained, because MIN would never allow them - MIN moves to the $3$ and the $2$ respectively. Only the minima of each branch survive.

D. Alpha-beta pruning

Minimax examines every leaf, which is hopeless for real games - the tree grows exponentially with depth. Alpha-beta pruning computes the identical value while skipping branches that provably cannot affect it.

Two values are carried down the search, defined by Russell & Norvig as:

• $\alpha$ - the value of the best (highest-value) choice found so far at any choice point along the path for MAX;
• $\beta$ - the value of the best (lowest-value) choice found so far along the path for MIN.

The search prunes the remaining branches at a node as soon as the node's value is known to be worse than the current $\alpha$ (for MAX) or $\beta$ (for MIN).

E. Pruning the tree, step by step

Tracing the same tree left to right:

Node $B$. Examine $3$, $12$, $8$. Nothing can be pruned - this is the first branch and MAX has no $\alpha$ yet. $B = 3$, so the root sets $\alpha = 3$: MAX can already guarantee 3.

Node $C$. Examine the first leaf, $2$. $C$ is a MIN node, so its final value is at most $2$ - MIN can only go lower from here.

But MAX already has a guaranteed 3 elsewhere. A branch worth at most 2 will never be chosen over one worth 3, regardless of what the remaining leaves contain. So the leaves $4$ and $6$ are never examined. This is the prune.

Node $D$. Examine $14$: value so far $14$, still above $\alpha = 3$, no prune. Examine $5$: value so far $5$, still above $3$. Examine $2$: value $2$. $D = 2$.

Root. $\max(3, 2, 2) = 3$ - the same answer as full minimax.

Alpha-beta examined 7 of the 9 leaves, pruning $C$'s second and third children.

Running it prints value 3 from both methods, examined: [3, 12, 8, 2, 14, 5, 2] (seven leaves), and the two pruned leaves.

F. Why move ordering decides everything

Pruning depends on finding good moves early. If MAX's best move is examined first, $\alpha$ rises immediately and prunes aggressively. If it is examined last, there is nothing to prune against until the end.

With perfect ordering, alpha-beta examines roughly $O(b^{m/2})$ nodes instead of $O(b^m)$ for branching factor $b$ and depth $m$. That halved exponent means searching twice as deep in the same time - the difference between an amateur and an expert program.

Perfect ordering requires knowing the answer in advance, so real programs approximate it with heuristics: try captures first, try the move that was best at the previous shallower depth, and so on.

G. When the tree is too large regardless

Even halved, the exponent defeats games like chess or Go. Practical programs stop early and apply an evaluation function to non-terminal positions, estimating the utility rather than computing it.

This introduces two new problems worth naming. The horizon effect is the tendency to push an unavoidable loss just past the search depth, so it looks avoided when it is merely out of sight. And the evaluation function must be applied at quiescent positions - stopping in the middle of an exchange gives a badly wrong estimate, so search is extended until things settle.

Historically, alpha-beta search was conceived by John McCarthy in 1956; its correctness and time complexity were established by Knuth and Moore in 1975.

Key takeaways

• Adversarial search assumes an optimal opponent, making the minimax value a worst-case guarantee.
• MAX maximises, MIN minimises, and values propagate from the leaves to the root.
• Our tree: MIN nodes $3, 2, 2$; root value $3$; MAX plays to $B$.
• Alpha-beta returns the identical value while skipping provably irrelevant branches - 7 leaves instead of 9 here.
• $\alpha$ is MAX's best guarantee so far, $\beta$ is MIN's; a branch is cut once it cannot beat them.
• Move ordering determines the benefit; perfect ordering roughly halves the effective depth exponent.

What's next

Minimax assumes strict opposition. Most real strategic situations are not zero-sum - players may both gain or both lose, and "optimal play" needs redefining. That generalisation is Game Theory and Nash Equilibrium.