4.12 Adversarial search: minimax and alpha-beta pruning

What this is and why it exists

Adding a second agent changes the question being asked. In every search so far you chose a sequence of moves and the world let you carry it out. Here an opponent moves in between, and chooses against you. You are no longer looking for a sequence at all — you are looking for a good first move, given that whatever you plan next will be answered. Minimax is that idea written down honestly. Alpha-beta pruning is the observation that most of the tree cannot change the answer and therefore need not be examined. The evaluation function is the admission that a real game does not fit anywhere.

The vocabulary

• Game tree — the tree of positions, alternating whose turn it is.
• Ply — one move by one player. Two plies make a full round.
• Terminal state — a position where the game has ended.
• Utility — the number attached to a terminal state, from your point of view.
• Minimax value — the value of a position with both sides playing best.
• Alpha — the best value the maximising side is assured of so far.
• Beta — the best value the minimising side is assured of so far.
• Cut-off — stopping the search before the game ends.
• Evaluation function — an estimate of a non-terminal position's worth.
• Quiescence — searching on until the position stops being volatile.

The mental model

Write the game down before writing any algorithm. Who moves, what moves are available in each position, which positions end the game, and what number each ending is worth to you. That last one carries more weight than it seems: everything the search does is an attempt to steer towards a good number, so a badly chosen utility produces a player that pursues the wrong thing very competently. For a win-draw-loss game the usual choice is one, zero and minus one.

Minimax is one sentence. At your own turn take the largest value among the moves; at the opponent's turn take the smallest; at an ending take the utility. Work the values up from the bottom and the number at the root is what the position is worth against best play, with the move that produced it as your answer. Do this by hand once on a tree of a dozen nodes. The alternation feels arbitrary until you have watched a good-looking move collapse because the reply underneath it was terrible, and after that it never feels arbitrary again.

Then notice how much of the tree could not have mattered. Suppose you are the maximising side and you have already found a move worth six. You start examining a second move, and the opponent's first reply to it is worth two. The opponent will take at most two there, possibly less. Two is worse than six, so nothing else under that second move can change your decision, and you can stop looking at it entirely. That is the whole of alpha-beta pruning: carry the best value each side is assured of, and abandon a subtree the moment it cannot beat what is already guaranteed. It returns exactly the same move as minimax. Nothing is approximated. It is worth convincing yourself of that on paper, because it is the rare optimisation that costs nothing.

How much it saves depends entirely on the order you look at moves. With the best move examined first, cutoffs happen almost immediately and the number of positions examined falls to roughly the square root of what minimax would examine — meaning you can search about twice as deep in the same time. With the worst move first it saves nothing at all and you have plain minimax with extra bookkeeping. Every strong program spends real effort on move ordering — trying captures first, trying the move that was best at shallower depth first — and that effort buys more than most algorithmic cleverness.

Real games do not end within reach, so the search stops early and guesses. Chess has more legal positions than there are atoms in your line of sight; the search goes as deep as time allows and then hands the position to an evaluation function that estimates its worth from features — material, position, mobility, or in modern programs a learned network. Every practical player is this compromise, and its playing strength is mostly the quality of that estimate rather than the depth of the search.

Cutting off has a specific failure and it has a name. A search that stops at a fixed depth can push a bad outcome one ply past what it looks at, and report as comfortable a position where the loss is already unavoidable. That is the horizon effect, and a program suffering from it will make pointless delaying moves that shift the disaster out of sight. The standard answer is quiescence search: do not stop in a volatile position, keep following captures and forcing moves until things settle, and only then evaluate. Searching a little deeper on unstable lines and not at all deeper on quiet ones is a better use of the same time than uniform depth.

What you should now be able to explain or do

Formulate a two-player game as players, moves, terminal states and utilities, and say why the utility choice decides what the player pursues. Run minimax on a small tree by hand and give both the value and the move. Apply alpha-beta pruning to the same tree, name which subtrees were skipped, and show the answer is unchanged. Explain the effect of move ordering on how much is saved, in both the best and worst cases. Describe a depth-limited search with an evaluation function, and say what the program's strength then depends on. Recognise the horizon effect from its symptoms and describe quiescence search as the answer.

Check yourself