Minimax for two-player games

◈ 3 cards

MAX and MIN alternate levels of a game tree; values back up to the root, giving the best outcome MAX can guarantee against optimal play.

The minimax procedure

For a two-person, zero-sum game (one player's gain is the other's loss), minimax assumes both sides play optimally. The two players are MAX, who tries to maximize the evaluation, and MIN, who tries to minimize it. Label the game tree with alternating MAX and MIN levels:

Leaf nodes get an actual or heuristic value (here: $+ 1$ if MAX wins, $- 1$ if MIN wins, $0$ for a draw).
A MAX node takes the maximum of its children's backed-up values.
A MIN node takes the minimum of its children's backed-up values.

Values propagate up to the root. The root value is the best outcome MAX can guarantee, assuming MIN also plays optimally. That optimality assumption is both the strength (a rational guarantee) and the limit (an irrational opponent may behave differently) of minimax.

n-ply look-ahead and the horizon effect

Real games are too large to search to the end, so programs search n plies deep, apply a heuristic to the leaves, and back the values up. Deeper usually plays better — but not always, and a fixed depth creates the horizon effect: a disaster lurking one ply beyond the cutoff is invisible, so the program may walk into it (e.g. accept a piece that lures it into losing a bigger one). Quiescence / selective deepening (search a few extra plies for volatile positions) softens this but cannot remove it.

Worked example: tic-tac-toe

Encode the board as 9 cells; X is MAX, O is MIN. On a mid-game board where it is X's turn and taking the centre forces a win, minimax recurses to terminal positions, backs up $+ 1/ - 1/0$ , and returns best move (2,2), value +1 (X wins). On an empty board, optimal play by both sides is a draw, so the root value is $0$ — minimax correctly reports tic-tac-toe as a draw under perfect play. The chosen move is the child that achieves the backed-up root value.

The top ply of the worked position, with X to move. Every child is a MIN node and its plate is the value backed up from the whole subtree beneath it. MAX takes the <em>maximum</em>, so the root is +1 and the chosen move is the child that achieves it — (2,2). Note that only one move wins: (1,0) actually loses, and the other three are draws.

The full tree is 258 nodes, so this is a faithful sub-tree: the fourth root child above, expanded one ply. Each MAX node here is itself the root of a further subtree whose value has already been backed up. MIN takes the <em>minimum</em> of +1, 0, 0, 0 — and 0 is exactly the value this branch shows at the root. The next lesson prunes this very node.