Adversarial Search & Games (Minimax, Alpha-Beta)

What You'll Learn

Understand two-player zero-sum games as a search problem
Run the minimax algorithm and back up values through a game tree
See why games differ from single-agent search — a hostile, unpredictable opponent
Apply a fixed-ply cutoff with a heuristic evaluation function when the tree is too deep
Perform alpha-beta pruning and explain why it never changes the result

Prerequisites: Modules 4–6 (Problem Solving & State Spaces, Uninformed Search, and Informed Search & A*). You should be comfortable with state spaces, search trees, and heuristic evaluation before starting.

Games as Search Problems

A game tree in which MAX and MIN alternate at successive levels — Searching with an opponent — MAX and MIN alternate levels; MAX cannot simply pick the best leaf because MIN replies to minimise MAX's score. *(From the course slides.)*

Games have always been a proving ground for artificial intelligence — from Shannon and Turing's first chess programs to Deep Blue and AlphaGo. Two-person board games such as tic-tac-toe, chess and Go are in one sense just search problems, but they are markedly harder than the puzzles of the previous modules, for two reasons:

Why games are harder than puzzles

A hostile, unpredictable opponent. In the 8-puzzle the world only does what we tell it. In a game a second agent moves too — and does so to hurt us. We cannot know in advance which move the opponent will choose, so we must plan for the worst.
We must search moves and countermoves. Every one of our moves invites a reply, which invites our counter-reply, and so on. The search must interleave our decisions with the opponent's.

We restrict attention to the classic, well-behaved case: two-player, zero-sum, perfect-information games. Two-player means exactly two agents alternate turns. Zero-sum means what is good for one player is exactly as bad for the other — there is a single number (the utility) that one side wants to push up and the other wants to push down. Perfect information means both players see the entire state at all times (no hidden cards, no dice).

Player	Goal	Chooses
MAX	Maximise the final score (the utility).	The move leading to the highest-valued child.
MIN	Minimise MAX's score (the opponent).	The move leading to the lowest-valued child.

The two players take turns, so the levels (called plies) of the game tree alternate: a MAX level, then a MIN level, then MAX again, and so on down to the leaves. The root is MAX — the player "to move" for whom we are computing the best action.

The Minimax Algorithm

The core idea of minimax is to assume that both players play optimally — MAX always maximises, MIN always minimises — and then compute, for every node, the value it would have under that assumption. This is the node's minimax value. Because a node's value depends on its children, we compute values bottom-up: from the leaves back toward the root.

The three rules for backing up a value

A leaf (a terminal position, or a cutoff node) gets its utility value directly.
A MAX node takes the maximum of its children's values — MAX will steer toward the best.
A MIN node takes the minimum of its children's values — MIN will steer toward the worst (for MAX).

Once the root has a value, MAX plays the move that leads to the highest-valued child. That move is guaranteed to be the best possible against an optimal opponent.

A four-level game tree with values propagating up to a root value of 3 — A 4-level MAX/MIN game tree; values propagate up — MAX takes the max of its children, MIN the min — giving the root value 3. *(From the course slides.)*

Read the tree above from the bottom up. The leaves carry their utility values, handed to them directly. One level up sits a row of MIN nodes: each takes the minimum of the leaves beneath it, because MIN, moving next, will always pick the outcome worst for MAX. Above them sit MAX nodes, each taking the maximum of the MIN values below — MAX picks whichever branch offers the largest guaranteed value. Continuing this alternation all the way up, the root ends up with value 3: the best score MAX can force, and the number that identifies MAX's optimal opening move.

A second minimax game tree worked bottom-up, alternating min and max at each level — Another minimax tree; work bottom-up, alternating min and max at each level. *(From the course slides.)*

The same recipe applies to any finite game tree: label the leaves, then repeatedly collapse the deepest unlabelled level — taking a minimum under MIN nodes and a maximum under MAX nodes — until only the root remains. Here is the standard recursive formulation:

function MINIMAX-DECISION(state) returns an action
    return the action a in ACTIONS(state)
           maximising MIN-VALUE(RESULT(state, a))

function MAX-VALUE(state) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state)
    v := −∞
    for each a in ACTIONS(state) do
        v := MAX(v, MIN-VALUE(RESULT(state, a)))
    return v

function MIN-VALUE(state) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state)
    v := +∞
    for each a in ACTIONS(state) do
        v := MIN(v, MAX-VALUE(RESULT(state, a)))
    return v

MAX-VALUE and MIN-VALUE call each other, descending the tree; each returns as soon as it hits a terminal state and then backs up the max (or min) of the recursive results. MINIMAX-DECISION at the root simply picks the action whose subtree returned the best value.

Properties of minimax

Complete — yes, provided the game tree is finite.
Optimal — yes, against an optimal opponent. (Against a fallible opponent it never does worse, and may do better.)
Time — O(b^m), where b is the branching factor and m is the maximum depth: minimax examines every node.
Space — O(bm) with a depth-first implementation.

For real games, b^m is astronomical. Chess has b ≈ 35 and games run 80+ plies, so the full tree has on the order of 10¹²⁰ nodes — complete minimax is impossible. That is the problem the rest of this module solves.

Worked Example: Nim

To see minimax back up real win/loss labels, take a variant of Nim from the course slides. We start with a single pile of tokens. A move splits one pile into two piles of different sizes — for example a pile of 6 may become 5+1 or 4+2, but not 3+3. Play alternates; the player who cannot move loses (a pile of 1 or 2 cannot be split into two unequal non-empty piles). Because the piles only ever get smaller, the whole state space of a small game can be searched exhaustively.

The complete state space of a small game of Nim — The state space for a variant of Nim — each move splits a pile into two unequal piles; leaves are positions with no legal move. *(From the course slides.)*

Every path from the root to a leaf is a complete game. A leaf is a position in which the player to move has no legal split — and therefore loses. To decide whether the first player has a forced win, we score each leaf and run minimax over the whole tree.

Exhaustive minimax over the Nim state space, labelling every node a win or loss — Exhaustive minimax for Nim — each leaf is a win (1) for MAX or a loss (0); values back up to label every node a forced win or loss. *(From the course slides.)*

Score each leaf as 1 if it is a win for MAX and 0 if it is a loss, then back the values up with the usual rule. At a MAX node the value is the maximum of its children: MAX is happy if any child leads to a win (a single 1 makes the node 1). At a MIN node the value is the minimum: MIN is happy if any child leads to a MAX loss (a single 0 makes the node 0). Propagating these 1s and 0s upward labels every node as a forced win or a forced loss. The label that reaches the root tells the first player, before a single token is moved, whether perfect play guarantees them the game — and the winning child at each node is exactly the move to make.

The pay-off of exhaustive minimax

When the tree is small enough to expand fully, minimax does not merely estimate — it solves the game. Every node is definitively a win or a loss, so from the starting position we already know the outcome under perfect play, together with the exact move to reach it at every step. This is precisely how games like tic-tac-toe (and, with vast computation, checkers) have been solved outright.

When the Tree Is Too Big: Fixed-Ply Search & Evaluation Functions

Nim was small enough to solve completely. Chess and Go are not: we can never expand the tree down to its true leaves. The practical answer is to search to a fixed depth — a fixed number of plies determined by the time and memory available — then stop and apply a heuristic evaluation function to score the nodes at that cutoff depth, exactly as if they were leaves. Minimax those scores back up as usual, and MAX plays the resulting best move.

Fixed-ply (depth-limited) minimax

Choose a depth d (the ply) that fits the available time/memory.
Expand the game tree to depth d only.
Score each cutoff node with an evaluation function E(n) that estimates how good the position is for MAX.
Back the estimates up with ordinary minimax; MAX plays the best move found.

The evaluation function is the heart of a game-playing program. A classic one from the slides is the “most winning lines” heuristic for games like tic-tac-toe:

E(n) = M(n) − O(n)

Here M(n) is the number of complete lines (rows, columns, diagonals) still open to MAX — lines containing none of the opponent's marks — and O(n) is the number still open to the opponent. A large positive E(n) means MAX has many ways to win and the opponent few; a negative value means the reverse. It is cheap to compute yet captures real positional strength.

Counting the winning lines open to each player to compute the evaluation function — The “most winning lines” evaluation E(n) = M(n) − O(n), where M(n) is MAX's open winning lines and O(n) is the opponent's. *(From the course slides.)*

Two-ply minimax on the opening move of tic-tac-toe using the evaluation function — Two-ply minimax on tic-tac-toe's opening move (after Nilsson, 1971), using E(n) at the cutoff depth. *(From the course slides.)*

Two-ply minimax applied to a tic-tac-toe position, scored with a heuristic at the cutoff — Two-ply minimax applied to a tic-tac-toe position (after Nilsson, 1971); when the tree is too deep to reach the end, cut off and score with a heuristic. *(From the course slides.)*

In these two-ply examples the search looks ahead just two moves: MAX's candidate move, then each of MIN's replies. The positions two plies down are scored with E(n) = M(n) − O(n), the MIN nodes take the minimum of their children (the opponent's best reply), and the root MAX node takes the maximum — selecting the opening move with the strongest guaranteed evaluation.

The horizon effect

Fixed-ply search has a dangerous blind spot. Because the search simply stops at depth d, a decisive event lurking just beyond the cutoff — a checkmate, a queen capture, a forced loss — is invisible. The program may score a position as excellent when disaster (or a win) sits one ply past its horizon. Deeper search pushes the horizon back but never removes it; techniques such as quiescence search (extending the search through unstable positions) exist precisely to soften this effect.

Alpha-Beta Pruning

Plain minimax explores every branch of the tree — including a great many that cannot possibly change the final decision. Alpha-beta pruning is a way to skip those branches while returning exactly the same move as full minimax. It does so by carrying two bounds down the tree as it searches:

The two bounds and the two cutoffs

α (alpha) = the best (highest) value MAX can guarantee so far along the current path.
β (beta) = the best (lowest) value MIN can guarantee so far along the current path.
Alpha cutoff: prune below a MIN node as soon as its value drops to ≤ α of some MAX ancestor — MAX would never let the game reach here, so the remaining children are irrelevant.
Beta cutoff: prune below a MAX node as soon as its value rises to ≥ β of some MIN ancestor — MIN would never allow it, so stop.

Alpha-beta pruning on a game tree, with several branches cut off — Alpha-beta pruning on a game tree — branches B, D and E are cut because they cannot change the value that propagates to the root; the answer (3) is identical to full minimax but far fewer nodes are examined. *(From the course slides.)*

Follow the reasoning drawn on the figure. Exploring the first subtree fixes a value of 3 there, so the root MIN context gives node A a β of 3. When we then start expanding B and see a child worth 5, B is a MAX node whose value can only grow — it is already 5 > 3, so MIN above would never choose B: B is β-pruned and its remaining children go unexamined. Moving on, node C establishes an α of 3 for the branches beneath it. Now D yields a child worth 0; since 0 < 3 = α, MAX would never come this way — D is α-pruned. Likewise E produces a 2, and 2 < 3, so E is α-pruned too. After all this cutting, the value that backs up to the root is 3 — identical to full minimax, but reached after visiting far fewer nodes.

Why alpha-beta is a free lunch

Alpha-beta returns exactly the same move as minimax — it only ever removes branches that provably cannot affect the backed-up value, so correctness is untouched. What it changes is cost. With perfect move ordering (best moves examined first) it examines only about the square root of the nodes minimax would, an effective time of O(b^m/2) instead of O(b^m). In practical terms that lets a program search roughly twice as deep in the same amount of time — an enormous gain in playing strength for no loss in accuracy.

Exercise

Three problems, building from mechanical to conceptual. Work each on paper before opening the solution — backing up a game tree by hand once is worth ten readings.

1

Back up a game tree with minimax

The root is a MAX node with three children, each a MIN node. The leaves (left to right) are: under the first MIN node 3, 12, 8; under the second 2, 4, 6; under the third 14, 5, 2. Compute the minimax value of the root and state MAX's best move (left, middle or right).

                    MAX
              ┌──────────┼──────────┐
            MIN        MIN         MIN
          ┌──┼──┐    ┌──┼──┐     ┌──┼──┐
          3 12  8    2  4  6    14  5  2

Each MIN node takes the minimum of its three leaves:

Left MIN = min(3, 12, 8) = 3
Middle MIN = min(2, 4, 6) = 2
Right MIN = min(14, 5, 2) = 2

The root MAX takes the maximum of the MIN values: max(3, 2, 2) = 3. So the minimax value of the root is 3, and MAX's best move is the left branch (the only child worth 3). Note how MIN's replies pull the middle and right branches down to 2 — MAX cannot bank the tempting leaves 12 or 14, because MIN would never allow them.

2

Which leaves can alpha-beta skip?

On the same tree, evaluate the leaves strictly left to right and apply alpha-beta pruning. List which leaves can be skipped (never examined), and explain why.

Walk it through left to right:

Left MIN: examine 3, 12, 8 → value 3. Root now has α = 3. (All three leaves are needed here; there is no earlier bound to prune against.)
Middle MIN: examine the first leaf 2. This MIN node can only go down from 2, so its value is already ≤ 2 < α = 3. MAX would never choose this branch → α-cutoff: skip leaves 4 and 6.
Right MIN: examine the first leaf 14 (no cutoff yet — 14 > 3). Examine the next leaf 5: the MIN value is now ≤ 5, still not below α, so keep going. Examine 2: MIN value is now ≤ 2 < 3 → but this is the last leaf anyway, so nothing remains to prune.

Leaves skipped: the middle branch's 4 and 6. Alpha-beta examines 7 of the 9 leaves and still returns the correct root value 3 and best move (left). With this particular ordering only two leaves are saved; a better move ordering (largest MIN values first) would prune more — which is the point of exercise 3.

3

Why doesn't alpha-beta change the answer?

Explain (a) why alpha-beta pruning always returns the same minimax value and move as full minimax, and (b) what determines how much pruning actually happens.

(a) It never changes the answer because it only ever cuts branches that cannot affect the backed-up value. A branch is pruned exactly when its value has already fallen outside the [α, β] window — meaning a rational MAX (or MIN) ancestor would never allow play to reach it. Since those branches could not have altered the parent's max or min in the first place, discarding them leaves every backed-up value identical to full minimax. Alpha-beta changes only which nodes are visited, never which value is computed.

(b) Move ordering determines how much it prunes. Cutoffs happen soonest when the best moves are examined first, because a strong early value tightens α or β immediately and disqualifies everything worse. With perfect (best-first) ordering alpha-beta reaches its optimum, examining only about O(b^m/2) nodes — effectively doubling the search depth. With the worst ordering it prunes nothing and degenerates back to plain minimax. In practice, programs invest heavily in good move ordering (e.g. trying previously best moves first) precisely to maximise these cutoffs.

Recap & Where Next

You now know

Games as search: two-player, zero-sum, perfect-information contests where MAX maximises and MIN minimises, alternating plies.
Minimax backs values up bottom-up — leaves get utilities, MAX nodes take the max, MIN nodes take the min — and is optimal against an optimal opponent (Nim solved this way; full chess cannot be).
Fixed-ply cutoff + evaluation functions (e.g. E(n) = M(n) − O(n)) let us play games too big to solve, at the price of the horizon effect.
Alpha-beta pruning returns the identical move as minimax while skipping branches outside the [α, β] window — with good move ordering, roughly O(b^m/2), effectively doubling search depth.

This completes the search unit of the course: from uninformed search (Module 5), through informed search and A* (Module 6), to adversarial search here — the three pillars of classical AI problem solving. Coming next in the syllabus, the focus shifts from searching to reasoning: knowledge representation, logic and inference, expert systems, and finally machine learning.