Adversarial search: Minimax, α-β pruning & Expectimax

By the end of this page you will be able to take any small game tree, compute its minimax, α-β and expectimax values by hand, name the action the agent should play, say exactly which branches get pruned and why, and explain what breaks when your model of the opponent is wrong.

Why games, and what changes from Chapter 1

In search and informed search the world sat still while you thought, and the answer was a sequence: Left, Left, Up, Right. Now another agent is choosing actions too, and it chooses after seeing what you did. A fixed sequence of moves is worthless: your second move has to depend on what the opponent just played. That one change — a second decision-maker interleaved with yours — is what "adversarial" means, and it changes the type of the answer.

Where the uncertainty comes from

An opponent is only one source of uncertainty; the lecture lists the others, all handled by the same machinery:

• Hidden information — another player's cards: part of the state is invisible.
• Noise — a robot's sensors: you see the state through a distorting lens.
• Too complicated to model — leaves in the wind: deterministic in principle, random in practice.
• Infinitely many configurations — the continuous world isn't pre-discretised.
• More possibilities than any computer can enumerate — tic-tac-toe → checkers → chess.

That last bullet is the one that matters. Chess hides nothing — no dice, no noise, the whole board is visible — and yet no machine and no human will ever play it perfectly. Computational limits produce uncertainty that is, from the agent's point of view, indistinguishable from randomness. Half of this chapter (evaluation functions, depth limits, pruning) exists only because of that.

Seventy-five years of game AI, in one screen

Untestable, but each milestone names an idea you meet again. ("Ply" = one player's move.)

• Checkers. First program 1950; Chinook (1994) the first computer world champion in any game, built on a complete 8-piece endgame database — search from the front, lookup from the back. Solved in 2007 (a draw) with 39 trillion states. Samuel's checkers work is where learning an evaluation function began.
• Chess. Shannon's 1950 recipe is still the one in use: game tree, depth limit, evaluation function. Deep Blue beat Kasparov in 1997 at 200 million positions per second — brute force plus a good EVAL plus α-β, decades before modern learning. Iterative deepening comes from this era.
• Go. Branching factor b > 300, and no hand-written position evaluation ever worked. Monte Carlo tree search (2005–2014) used the win rate of thousands of random playouts instead; AlphaGo learned the evaluation on that skeleton. beyond syllabus

Classifying games along five axes

Before writing an algorithm, work out which game you are in. Five independent questions:

Zero-sum versus general games

Why care about this technicality? Because player two's utility carries no information that player one's doesn't already carry: it is just the negative. So instead of a vector of utilities per node, you can label every node with a single number — player one's utility — and describe both players with two words:

• Player one (call them MAX) wants that number as large as possible.
• Player two (MIN) wants their own utility large, which is the same as wanting that number as small as possible.

One number, two opposite preferences. That is the entire reason the algorithm is called mini-max and not something with a subscript per player.

General games are qualitatively different, not just messier. With independent utilities you get cooperation, indifference, competition, shifting alliances — two players can find a move that helps them both at a third's expense without ever communicating. See generalized minimax: the single number becomes a tuple again.

The standard game formulation

The course focuses on "standard" games: deterministic, fully observable, two-player, turn-taking, zero-sum — one corner of the five-axis space. The rest of this chapter is what you do when you fall out of it.

Compare line by line with the Chapter 1 search problem: $s_0$, $\text{Actions}$, $\text{Result}$ are identical. Two things change. $\text{Player}(s)$ is new, and the goal test has been replaced by a terminal test plus a number — terminating isn't the point, terminating well is, so we carry a real-valued utility instead of a boolean.

The output is a policy, not a plan. Belabour this.

From the notes: "Our goal is to calculate a contingent plan, also called a strategy or policy, which recommends a move for every possible game state." Three words for one object — contingent plan = strategy = policy — and the important word is contingent.

In Chapter 1 the solution to the 8-puzzle was a list, [Up, Left, Left, Down], that you could write on a napkin and hand to someone. Try that in chess. You write [e4, Nf3, Bc4, Qh5, Qxf7#], your opponent plays something other than the moves the napkin silently assumed, and by move two the list is nonsense — possibly not even legal. It failed not because the moves were bad but because it was the wrong type of object.

Formally a policy is a function $\pi : S \to A$ with $\pi(s) \in \text{Actions}(s)$ at every state where it is your turn. Its size is on the order of the number of reachable states, not the length of a path — which is why a game solution is exponentially bigger than a search solution, and why the algorithms below work hard at not writing it down. Minimax computes the policy implicitly: it hands you the values of the children of wherever you are, you take the argmax, and doing that every turn executes the policy without ever storing it. You meet $\pi$ again with exactly this meaning at MDPs and reinforcement learning.

Minimax: the value of a state under optimal play

Read the symbols: $V(s)$ is a single number, the value of state $s$ to MAX; $\text{Result}(s,a)$ is the child you reach by playing $a$; the $\max$ and $\min$ range over the legal actions at $s$. Nothing here is approximate — it is a definition by recursion on the game tree, bottoming out at terminal states.

Note the word guarantee — the strongest claim in this chapter. If minimax says a state is worth $+4$ to you, some strategy of yours gets at least 4 against every possible opponent, and against an optimal one you cannot get more: a floor you can always reach and a ceiling a good opponent can impose.

Drawing the tree

States are nodes, actions are branches. Conventionally, as in the slides:

• MAX nodes — blue, upward-pointing triangles ("push the value up"); value = the maximum over its children.
• MIN nodes — red, downward-pointing triangles; value = the minimum over its children.
• Terminal states — squares, holding the number $\text{Utility}(s)$ directly.

The worked example from the notes

The blue MAX player moves first and chooses Left, Center, or Right. Then the red MIN player picks one of its two replies, trying to make the resulting number as small as possible. The six leaves are $3, 12 \mid 4, 6 \mid 15, 2$.

Working from the leaves upward:

• Left MIN node: $\min(3, 12) = 3$.
• Center MIN node: $\min(4, 6) = 4$.
• Right MIN node: $\min(15, 2) = 2$.
• Root MAX node: $\max(3, 4, 2) = 4$.

The generic pseudocode

Straight from the notes. Two functions: one that picks the move at the root, one recursive routine that computes a value.

function max_decision(state):
    return the action in state.actions that gives
           the max value( state.result(action) )

function value(state):
    if state.is_leaf:
        return state.value
    if state.player is MAX:
        return max over value(state.result(a)) for a in state.actions
    if state.player is MIN:
        return min over value(state.result(a)) for a in state.actions

Three things to note: there is exactly one recursive function, dispatching on whose turn it is (α-β will force us to split it into max_value/min_value); the base case is is_leaf, i.e. Terminal-Test; and max_decision returns an action while value returns a number — the type distinction from the Key idea box, made concrete in code.

The same skeleton with a chance case bolted on is expectiminimax, used in the expectimax section:

function value(state):
    if state.is_leaf:
        return state.value
    if state.player is MAX:
        return max over value(state.result(a)) for a in state.actions
    if state.player is MIN:
        return min over value(state.result(a)) for a in state.actions
    if state.player is CHANCE:
        return sum over P(s) * value(s) for s in state.next_states

One extra branch. That is the whole difference between minimax and expectiminimax.

What minimax costs, and bounded rationality

Minimax as written is exhaustive depth-first search of the game tree with an arithmetic operation on the way back up, so its complexity is DFS's.

Plug in chess

For chess, $b \approx 35$ and $m \approx 100$. So the tree has on the order of

nodes, against roughly $10^{80}$ atoms in the observable universe. Exact solution of chess is not "hard", it is physically impossible. And yet humans play chess well, examining perhaps a hundred positions per move — not with a secret polynomial algorithm but with a good approximate evaluation and a good sense of which few moves are worth looking at.

This is not just an excuse for approximation. "A rational agent maximises expected utility" is vacuous when the maximisation cannot be performed, so Simon treats the cost of deliberating as part of the problem: not "what is the optimal move?" but "what is the best move I can identify with the computation I can afford?" Every technique below — depth limits, evaluation functions, pruning, sampling — answers that second question. Chess engines are not failed exact solvers; they are successful bounded-rational agents.

Resource limits: bounded lookahead and the horizon

The problem: in a realistic game you cannot search to the leaves. The recursion in value() bottoms out at is_leaf, and it never gets there before your clock runs out.

Solution 1: bounded lookahead. Two changes to the algorithm:

1. Search only to a preset depth limit, also called the horizon.
2. When you hit that depth on a non-terminal position, call an evaluation function $\text{EVAL}(s)$ and pretend the number it returns is the utility.

The change to the code is two lines: pass a depth counter down, and replace if state.is_leaf: return state.value with if state.is_leaf or depth == 0: return EVAL(state).

The arithmetic that sets the depth

The slides work a concrete budget, and you should be able to redo it for any numbers on an exam:

• Suppose you have 100 seconds per move and your engine explores 10,000 nodes/second.
• Then you can afford $100 \times 10{,}000 = \mathbf{10^6}$ nodes per move.
• Plain minimax visits about $b^d$ nodes to depth $d$. With $b \approx 35$: $35^4 = 1{,}500{,}625 \approx 10^6$. So $d \approx 4$.

Depth 4 is two moves each, and the slides' verdict is "not so good" — a club player looks further. Exactly: $d = \log_{35}(10^6) = 6/\log_{10}35 \approx 6/1.544 \approx 3.9$. Hold on to this number; α-β pruning will double it.

Depth matters

Two claims from the slides, in order of importance:

1. Evaluation functions are always imperfect. If yours were perfect it would return the true minimax value, you would search depth 1, and the game would be solved. It isn't and you can't.
2. Deeper search ⟹ better play (usually). EVAL's errors at the frontier get filtered on the way up through many layers of max and min: a position that merely looks good at depth 2 has had six more plies of the opponent's best objections applied to it by depth 8. ("Usually" is a real hedge — pathological trees exist where deeper minimax is worse, because it propagates the extreme of a set of noisy estimates. beyond syllabus)

Evaluation functions

Evaluation functions score non-terminals in depth-limited search: "this game isn't over — how good does it look for MAX?" The ideal one returns the position's actual minimax value, which would make bounded lookahead exact — but computing that is the problem we were avoiding, so the ideal defines the target, not a method. In practice the standard form is a weighted linear sum of features:

Naming the symbols: $f_i(s)$ is the $i$-th feature, a number computed cheaply from the board; $w_i$ is its weight, saying how much it matters and in which direction; $\text{EVAL}(s)$ is the resulting score, positive for "good for MAX."

The classic chess example: $w_1 = 9$ with $f_1(s) = (\text{number of white queens} - \text{number of black queens})$. The feature is a difference, so it is automatically zero-sum-symmetric and goes negative when black is ahead, and the weight 9 is the queen's value in pawn units. A full material term is $9\Delta Q + 5\Delta R + 3\Delta B + 3\Delta N + 1\Delta P$, plus positional features: pawn structure, king safety, centre control, mobility, rook on an open file.

What a bad evaluation function does to you

The most famous failure mode is the horizon effect. beyond syllabus Your engine is losing a bishop in three plies, unavoidably — but it can throw away a pawn to check the king and delay the capture past its depth limit. The truncated tree then says "sacrifice the pawn, the position looks fine," so the engine sheds pawn after pawn to push the inevitable just beyond where it can see. EVAL is not wrong about any position it is asked about; it is never asked about the one that matters. The standard fix is quiescence search: at a position with captures pending, extend along forcing moves until things settle, then evaluate. The lesson generalises: a bounded agent's blind spot is exactly where an adversary will aim.

Generalized minimax: non-zero-sum and multiplayer games

If the game is not zero-sum, or has more than two players, the single-number trick fails: you cannot recover players 2 and 3's utilities from player 1's. So you stop trying.

Two-player zero-sum is the special case $u_2 = -u_1$, where "player 2 maximises $u_2$" is literally "player 2 minimises $u_1$" and the second component is redundant. The interesting consequence of the general case: cooperation and competition arise dynamically, without being programmed in. In the tree below players 1 and 2 have identical payoffs everywhere, so they behave like partners against player 3 for free.

Walking Figure 4 node by node

Player 3's row compares third components: $(1,1,6)$ vs $(0,0,7)$ ⟹ $(0,0,7)$; $(9,9,0)$ vs $(8,8,1)$ ⟹ $(8,8,1)$; $(9,9,0)$ vs $(7,7,2)$ ⟹ $(7,7,2)$; $(0,0,8)$ vs $(0,0,7)$ ⟹ $(0,0,8)$ — the entire tuple of the winner moves up each time, and player 3 is indifferent to what it costs the others. Player 2's row compares second components: $(0,0,7)$ vs $(8,8,1)$ ⟹ $(8,8,1)$; $(7,7,2)$ vs $(0,0,8)$ ⟹ $(7,7,2)$. Player 1 at the root compares first components: $(8,8,1)$ vs $(7,7,2)$ ⟹ root value $(8,8,1)$, so player 1 plays Left.

Players 1 and 2 never negotiated, yet both steered toward $(8,8,1)$ and away from player 3's preferred leaves: an alliance emergent from self-interest, because their payoffs happen to align here. Change one leaf and it dissolves, with nothing in the algorithm changing — the coalition structure is a consequence of the numbers, not an input.

Alpha-beta pruning

Minimax visits every node, but the worked example already showed that most of them do not matter: once MIN's left subtree revealed a 3, the rest of that subtree was irrelevant. α-β pruning is the systematic version, and it computes exactly the same root value as minimax while often skipping most of the tree.

What the cutoff test actually means

This is the part everybody memorises and nobody understands, so here it is in slow motion. Consider a MIN node $n$ in the middle of being evaluated. Two facts: (i) MIN takes the minimum over $n$'s children, so $n$'s value can only go down as more children are examined — whatever it ends up as, it is $\le$ anything seen so far at $n$; (ii) somewhere on the path above there is a MAX node that already has an alternative worth $\alpha$.

So if the running value at $n$ reaches $v \le \alpha$, then $n$'s final value is $\le v \le \alpha$, and the MAX node above is comparing "at most $\alpha$" (through $n$) against "$\alpha$, guaranteed" (what it already holds). MAX is never coming down here, and the remaining children can only lower $n$ further. Stop and return $v$ immediately.

The mirror image at a MAX node $n$: its value can only go up, so if the running $v \ge \beta$ then $n$'s final value is $\ge \beta$, the MIN node above already has an option worth $\beta$, and MIN will never come down here either. Stop.

The exact pseudocode

From the slides, verbatim. Note that α-β does need the two cases written separately, because the cutoff test and the bound update are mirror images:

α: MAX's best option on path to root
β: MIN's best option on path to root

def max-value(state, α, β):
    initialize v = -∞
    for each successor of state:
        v = max(v, value(successor, α, β))
        if v ≥ β
            return v            # cutoff: MIN above won't allow this node
        α = max(α, v)
    return v

def min-value(state, α, β):
    initialize v = +∞
    for each successor of state:
        v = min(v, value(successor, α, β))
        if v ≤ α
            return v            # cutoff: MAX above won't come down here
        β = min(β, v)
    return v

Line by line for max-value: v is the best child value so far, starting at $-\infty$ so the first child always improves it; we recurse into each successor passing the current window down; after updating v we test v ≥ β and quit if our value has reached the level MIN can avoid; otherwise we raise α, because if MAX chooses this node it has secured at least v and every deeper node should know.

Two tiny examples, to drill the tests

The classic worked example — step it yourself

A MAX root with three MIN children. Their leaves, left to right, are $[3, 12, 8]$, $[2, \cdot, \cdot]$, $[14, 5, 2]$. (The dots are real numbers; the point of the exercise is that we never find out what they are.) Press Step and read the log line each time — it says exactly what the algorithm is doing and why.

The same traversal in words

1. Root (MAX) starts with $\alpha = -\infty$, $\beta = +\infty$, $v = -\infty$.
2. Node A (MIN), called with $(-\infty, +\infty)$. Leaves 3, 12, 8. After 3: $v = 3$, is $3 \le -\infty$? No, so $\beta \leftarrow 3$. After 12: $v = \min(3,12) = 3$. After 8: $v = 3$. Nothing prunes here — with $\alpha = -\infty$ nothing can prune, since MAX has secured nothing yet. A returns 3.
3. Back at the root: $v = \max(-\infty, 3) = 3$. Is $3 \ge +\infty$? No. So $\alpha \leftarrow 3$. MAX has now secured 3. This single fact is what powers every prune that follows.
4. Node B (MIN), called with $(\alpha=3, \beta=+\infty)$. First leaf: 2. $v = 2$. Test: $2 \le \alpha = 3$? Yes — cut off. Return 2 without looking at B's other two children: B is worth at most 2, MAX already has 3, so B's remaining children are irrelevant regardless of their values.
5. Back at the root: $v = \max(3,2) = 3$. $\alpha$ stays 3.
6. Node C (MIN), called with $(\alpha=3, \beta=+\infty)$. Leaf 14: $v = 14$; is $14 \le 3$? No; $\beta \leftarrow 14$. Leaf 5: $v = 5$; $5 \le 3$? No; $\beta \leftarrow 5$. Leaf 2: $v = 2$; $2 \le 3$? Yes — cut off and return 2. (Here the cutoff saves nothing, because 2 was C's last child anyway. A cutoff on the final child is free but useless.)
7. Root: $v = \max(3,2) = 3$. Done. Root value 3, and the action is the one leading to A — the leftmost move.

Properties of α-β: what it does and doesn't guarantee

Move ordering changes everything

The order of generation matters: more pruning is possible if good moves come first. Re-run the classic example with node A's leaves in the order $[8, 12, 3]$ and less gets pruned; put B's 2 last and B's cutoff never fires at all. In the worst case (worst possible ordering) α-β prunes nothing and costs $O(b^m)$, exactly like plain minimax.

But we cannot order moves by their values — computing the values is the whole problem. So we guess, using cheap heuristics: try captures first in chess, try the move that was best at the previous depth, try killer moves that caused cutoffs in sibling nodes.

That "best at the previous depth" trick is why iterative deepening helps: search to depth 1, then 2, then 3, each pass cheap relative to the next (the last level dominates the node count) and each leaving behind a good first move for the next. The re-searching looks wasteful and is overwhelmingly repaid by the extra pruning. It is also anytime — when the clock runs out you have a complete answer from the last finished depth.

Redo the chess budget with this. Still $10^6$ nodes per move, still $b \approx 35$, but now $\sqrt{35} \approx 5.92$:

Or directly: $b^{m/2} = 35^{4} \approx 10^6$ gives $m = 8$. 1M nodes/move ⟹ depth 8, which the slides call "respectable." Same hardware, same evaluation function, four extra plies — purely from refusing to examine nodes that cannot matter.

Expectimax: games with chance, and opponents who aren't optimal

Minimax rests on one assumption: the other node is a minimiser. Two very common situations break it.

• Genuine chance. Dice in backgammon or Monopoly, Tetris's next piece, a shuffle. The node after your move is not chosen by anybody but sampled, and calling it a minimiser assumes the dice hate you personally.
• Suboptimal opponents. A beginner, a random ghost, a rule-based bot. Assuming they play the most damaging move available is simply a false model of them.

As the notes put it: making worst-case assumptions about stochastic or suboptimal opponents leads to poor decisions. Not merely conservative ones — if you believe every unlikely disaster is certain, you refuse opportunities that are nearly free.

Probability refresher

The course's example: traffic on the freeway. The random variable is $T$ = whether there's traffic; the outcomes are $T \in \{\text{none}, \text{light}, \text{heavy}\}$; the distribution is

Check the normalisation: $0.25 + 0.50 + 0.25 = 1$. Always check — if the weights don't sum to one you forgot an outcome. Capital $T$ is the variable; lower-case values like "light" are its outcomes, and $P(T=t)$ reads "the probability that $T$ takes the value $t$."

Expected value

The airport example. Let $f(\text{traffic})$ be the time it takes to get to the airport:

Two observations. $35$ is not a possible outcome at all — an expectation is a summary, not a prediction — and it sits above the median outcome (30), pulled up by the heavy-traffic tail, so expectations are sensitive to rare extremes. The pessimist answers 60, the optimist 20, expectimax 35: three answers to three different questions.

The expectimax node rules

We model chance as a player in the game tree: instead of $s'$ being the deterministic result of action $a$, it is one of several outcomes, each with a probability. Chance nodes are drawn as circles, and the three node types read:

Names: expectimax = MAX + CHANCE (a random world, no adversary — Tetris); expectiminimax = MAX + MIN + CHANCE (adversary and dice — backgammon); minimax = MAX + MIN (chess). Same code, different node types present.

The worked example

Three actions — Left, Center, Right — each leading to a chance node, with expected values $7$, $7$ and $8$, so the answer is Right. The notes' figure didn't survive into the text, so the probabilities and leaves below are recovered from the slide version of the example rather than invented; they reproduce $7, 7, 8$ exactly.

The arithmetic, written out:

• Left: $\tfrac14(12) + \tfrac14(8) + \tfrac12(4) = 3 + 2 + 2 = 7$.
• Center: $\tfrac12(8) + \tfrac12(6) = 4 + 3 = 7$.
• Right: $\tfrac13(12) + \tfrac23(6) = 4 + 4 = 8$.
• Root: $\max(7, 7, 8) = 8$, so play Right.

Can you prune a chance node?

The slides raise the question — "Expectimax pruning?" over a tree with leaves 3, 12, 9, 2 — and leave it hanging. Here is the answer.

In general, no: you cannot prune at a chance node without bounds on the utilities. The reason is structural. α-β works because a MIN node's running value can only go down and a MAX node's can only go up. Those are monotone one-sided guarantees, and a one-sided guarantee is exactly what lets you say "this can never beat what I already hold."

A chance node has no such property. With two equally likely outcomes and the first evaluated at 3, all you know is that the node is worth $\tfrac12(3) + \tfrac12(V_2) = 1.5 + 0.5 V_2$, and with $V_2$ unconstrained that is any number at all — the second outcome could be $+10^9$ and drag the average anywhere. Averages are not monotone in the outcomes you have seen so far.

Bound the utilities and it changes. beyond syllabus If every leaf lies in $[L, U]$, the best possible completion assigns $U$ to everything unseen and the worst assigns $L$:

If the upper bound already falls at or below $\alpha$, MAX will never come here and you may stop. That is *-minimax (star1/star2 pruning, Ballard 1983), which backgammon engines use; it needs a known finite range for utilities and prunes far less than α-β, because the bounds are loose.

Modelling assumptions: know your opponent

Everything above assumed you knew which kind of node you were looking at. What if you get that wrong? Take the slides' tree: a MAX root whose left option leads to a node with children $\{10, 10\}$ and whose right option leads to one with children $\{9, 100\}$.

• If those are MIN nodes: left $= \min(10,10) = 10$, right $= \min(9,100) = 9$. Play left, value 10.
• If those are chance nodes (say 50/50): left $= 10$, right $= \tfrac12(9) + \tfrac12(100) = 54.5$. Play right, expected value 54.5.

Same numbers, opposite decisions, and the gap is enormous. The slides name the two failure modes:

The 2×2 you should memorise

The lecture demo ran depth-4 Pacman against a depth-2 ghost: +500 for a win, −500 for a loss, −1 per move, 5 games per cell. The slides ask which pair is worst and which is best, and move on — so here are the numbers and the answer.

Summary and what carries forward

The through-line: games require decisions when optimality is impossible. Every technique here responds to that.

Games force efficient use of computation — α-β exists because the budget is finite — and they have produced ideas that outlived them: reinforcement learning out of checkers (Samuel's self-play evaluation tuning), iterative deepening out of chess engineering, Monte Carlo tree search out of Go, and solution methods for partial-information games out of poker. The frontier is not solved: video games present much greater challenges, with $b = 10^{500}$, $|S| = 10^{4000}$ and $m = 10{,}000$.