Adversarial Search
Searching when someone is fighting back. How a computer plays games with the minimax algorithm, and how alpha-beta pruning lets it look far deeper.
Every search so far assumed the world sits still and waits while you plan. Games break that assumption. In chess or noughts and crosses, an opponent moves right after you do, and they are actively trying to make you lose. This is adversarial search, and it needs a new idea: plan for the best move assuming your opponent also plays their best. That idea is minimax, and this page shows how it works and how alpha-beta pruning makes it fast enough to be useful.
Search with an opponent
The games we care about here have a specific, tidy shape. They are two-player, turn-taking, zero-sum, and perfect-information. That is a mouthful, so unpack it: two players alternate moves, one player's gain is exactly the other's loss (zero-sum), and both can see the whole board (perfect information). Chess, draughts, and noughts and crosses all fit.
We name the two players by what they want. MAX is the player we are planning for, and MAX wants the highest score. MIN is the opponent, and MIN wants the lowest score, because in a zero-sum game a low score for MAX is a win for MIN. The whole challenge is that MAX must choose moves knowing MIN will reply as badly for MAX as possible.
The game tree
We represent a game as a game tree. The root is the current position. Each level down is one move, alternating between MAX and MIN. The leaves are finished positions, and each leaf has a utility: a number saying how good that outcome is for MAX (for example, +1 for a win, 0 for a draw, -1 for a loss).
- A single move by one player is called a ply. MAX moves, then MIN moves, that is two ply.
- Levels alternate: MAX chooses at its levels, MIN chooses at its levels.
- Leaves carry the score. Everything above is worked out from the leaves upward.
The minimax idea
Minimax is how we assign a value to every node in the tree, working from the leaves upward. The rule depends on whose turn it is at that node:
- At a MAX node, take the maximum of the children's values. MAX will pick its best option.
- At a MIN node, take the minimum of the children's values. MIN will pick the option worst for MAX.
Start at the bottom, where the leaves already have values. Each MIN node just above takes the smallest of its leaves. Each MAX node above that takes the largest of those. Keep bubbling values up to the root, and the root's value is the best score MAX can guarantee against a perfect opponent. The move that leads to it is MAX's best move.
Minimax step by step
Take a small tree three levels deep. The root is MAX, its children are MIN, and their children are the leaves.
Notice MAX does not pick the leaf worth 9. That leaf sits under a MIN node, and MIN would never let MAX reach it, MIN would choose the 2 instead. Minimax respects that the opponent gets to reply. This is the single most common mistake students make: never let MAX grab a high leaf that the opponent controls.
The problem: too many nodes
Minimax is correct, but slow. It examines every leaf of the tree. With a branching factor b and a search depth d, that is b^d leaves, the same exponential explosion we met in week 1. For chess, looking just a few moves ahead already means billions of positions.
Here is the good news: you do not actually need to look at every leaf to get the right answer. Often, partway through examining a node's children, you already know that node cannot possibly affect the final decision. When that happens, you can skip the rest of its children entirely. That skipping is called pruning, and the technique is alpha-beta.
Alpha-beta pruning
Alpha-beta pruning gives exactly the same answer as minimax, but skips branches that cannot change the result. It tracks two values as it searches:
- Alpha: the best score MAX can already guarantee so far. It only ever goes up.
- Beta: the best score MIN can already guarantee so far. It only ever goes down.
The rule is short: if at any point alpha is greater than or equal to beta, stop exploring this node's remaining children. The reason is that the two players would never both allow this line to be reached. One of them already has a better option elsewhere, so nothing found here can change the outcome.
Alpha-beta does not change the answer, only the effort. With good move ordering it can roughly halve the effective depth cost, letting a program search about twice as deep in the same time. In games, searching deeper is the difference between weak and strong play, which is why alpha-beta matters so much.
Watch the tree prune itself
This is the payoff. Below is a game tree with MAX at the root (shown as an upward triangle), MIN below (downward triangle), MAX again, then leaf values. Switch between plain minimax and alpha-beta, then step through. Watch values bubble up from the leaves, and in alpha-beta watch whole branches grey out as they are pruned. The leaf counter shows how many leaves each method had to read.
Upward triangles are MAX nodes, downward triangles are MIN nodes, squares are leaf scores.
Key points and practice
- Adversarial search plans for games with an opponent who plays to make you lose.
- MAX maximises the score, MIN minimises it, on alternating levels of the game tree.
- Minimax propagates values from the leaves up: max at MAX nodes, min at MIN nodes.
- The root value is the best score MAX can guarantee against perfect play.
- Alpha-beta pruning gives the same answer while skipping branches that cannot matter, using the rule prune when alpha is greater than or equal to beta.
- Pruning does not change the result, only the speed, letting the search go deeper.
Minimax works from the leaves upward. At a MAX node it takes the maximum of the children's values, because MAX will choose its best option; at a MIN node it takes the minimum, because MIN will choose the option worst for MAX. Leaves carry fixed utility values. The value that reaches the root is the best score MAX can guarantee assuming the opponent also plays optimally, and the child leading to it is MAX's best move.
Alpha-beta pruning skips branches of the game tree that cannot affect the final decision. It tracks alpha, the best value MAX can guarantee so far, and beta, the best MIN can guarantee so far, and stops exploring a node's remaining children when alpha is greater than or equal to beta. It returns exactly the same value as plain minimax; it only reduces the number of nodes examined, which lets the search reach greater depth in the same time.
Because that leaf may sit below a MIN node. MAX only controls its own moves; on the level below, MIN chooses, and MIN will select the child that is worst for MAX, not the high-value leaf. So MAX can only count on the value MIN is willing to allow, which is the minimum of that MIN node's children.
