Artificial Intelligence · AI Foundations
Game Playing and Minimax
In AI because a second agent who wants the opposite of you turns search into a game tree — and minimax is the rule that picks a move which is safe against that opponent.
Search so far assumed the world did not push back. A two-player game does: after you move, someone who wants a low score for you gets to move. The object of study is a game tree — your choices as MAX nodes, theirs as MIN nodes, and a number at every finished position saying how good that ending is for you. Minimax is the backup that turns those numbers into one safe move at the root. The campus running example is a tiny two-ply club tournament: you play, they play, the match ends, and the scoreboard is already printed on the leaves.
- Artificial Intelligence
- Medium level
- 5 concepts
1An opponent is not noise
In the search lessons, an action had a cost and the world returned the next state. In a two-player zero-sum game the next state is chosen by an agent whose utility is the negative of yours. That is not a random disturbance and not a second copy of you. It is an adversary: given a choice, it will pick the child that is worst for you.
Zero-sum is the modelling decision that makes one number enough. The club awards +1 for a win, 0 for a draw, -1 for a loss, and your opponent's trophy cabinet is the opposite. Chess, draughts and the tiny tournament below are this family. A bargaining table where both sides can gain is not — that needs a different theory, and this lesson does not cover it.
| Setting | Next state chosen by | What you plan against |
|---|---|---|
| Path-finding | You (and a fixed graph) | Cost, not a mind |
| Zero-sum game | You, then an opponent | The worst legal reply |
| Chance game | Dice or a shuffle | A distribution, not a MIN |
Why does an adversarial game setting require minimax rather than standard single-agent path search?
- Adversarial games cannot define numerical utility values for wins or losses
- The game board state is hidden and cannot be observed between turns
- Adversarial games forbid using heuristic evaluation functions at leaf nodes
- The opponent acts strategically to minimise your payoff rather than behaving as neutral environment noise
In zero-sum games, the opponent actively selects moves that minimise the first player utility, requiring game tree minimax formulation.
2The game tree
A game tree is the search tree of the game. The root is the position you are to move from. Every edge is a legal action. After your action the opponent moves, so the next layer of nodes belongs to them. A ply is one layer — one side's turn. Two ply means you move, they move, and in this club tournament the match then ends.
A leaf is a finished position. Its utility is a number written from MAX's point of view: bigger is better for you. The four endings in the running tree score 3, 5, 2 and 9 — club points, not probabilities. Nothing in the tree is hidden: both sides see every legal move and every leaf. That is perfect information, the assumption minimax will spend.
Figure. Two-ply club tree. You move left or right; they pick a leaf under that choice. Leaves are utilities for you: 3, 5, 2, 9. The 9 is the prettiest ending and sits under the opponent's control. Topology only; spacing is not a board.
| Part | Who moves | On this tree |
|---|---|---|
| Root | MAX (you) | left or right |
| Ply 2 | MIN (them) | a leaf under your choice |
| Leaf | nobody — finished | utilities 3, 5, 2, 9 |
3Minimax backup
Minimax fills the tree from the leaves up. A MIN node receives the smallest of its children's values, because the opponent is choosing. A MAX node receives the largest of its children's values, because you are choosing. The root's value is then the outcome if both sides follow that rule all the way down.
On the club tree, MIN L holds 3 and 5 and so is worth 3. MIN R holds 2 and 9 and so is worth 2. MAX holds 3 and 2 and so is worth 3, by taking left. The 9 never happens: the opponent at R would have to donate it, and the rule says they will not.
Backup on the club tree
Leaves under MIN L are 3 and 5; leaves under MIN R are 2 and 9. Root is MAX.
- MIN L = min(3, 5)3
- MIN R = min(2, 9)2
- MAX = max(3, 2)3, action left
Pro tip. If you take right because 9 is visible, MIN answers with 2 and you score worse than the safe 3. The attractive leaf is bait, not a plan.
Coding lab. Minimax value on a game tree runs in the app, with checks on your output.
4What 'optimal' means here
The move minimax publishes is optimal against an opponent who also plays minimax. It maximises the worst-case utility. It does not maximise the average utility, and it does not gamble that the opponent will blunder toward the 9.
If the opponent is sloppy, a riskier line can score more in play than the minimax line. That is a different objective — exploit a model of their mistakes — and it can lose badly if the model is wrong. Minimax's contract is narrower and checkable: if they play perfectly, you still get the root value, here 3.
On the club tree (leaves 3, 5 under left MIN; 2, 9 under right MIN), a classmate takes right 'because 9 is bigger than 3'. What has gone wrong?
- They treated a leaf the opponent controls as if they could choose it, so they planned for 9 and will be handed 2
- They forgot to add the leaf values
- They used a heuristic, which minimax forbids
- They should have averaged 2 and 9
Right belongs to MIN, who will pick 2. The 9 is visible and not choosable by MAX. Averaging would be a chance-node rule, which this tree is not.
5What the guarantee needs
Minimax as stated needs a finite tree, perfect information, deterministic moves, and a utility on every leaf. The club tournament is built to satisfy all four: two ply, open leaves, no dice, numbers already printed. Chess satisfies the first three in principle and fails the first in practice — the tree is finite but too large to finish, which is why the next lesson cuts it off with an evaluation function.
Drop perfect information (a hidden card) or add chance (a die) and the backup changes: you are no longer taking min of known children. Those extensions exist; they are not this lesson. What this lesson owns is the two-player, perfect-information, zero-sum backup and the one move it recommends at the root.
| Assumption | Club tree | Breaks the backup when |
|---|---|---|
| Finite tree | Two ply, then leaves | You cannot reach every leaf |
| Perfect information | All four scores visible | A card or piece is hidden |
| Deterministic moves | Each action has one child | A die or shuffle sits in the tree |
| Zero-sum utility | One number, MAX's view | Both sides can gain at once |
Notes
- An adversarial game is a search in which every other ply is chosen by an opponent who minimises your score.
- Minimax backs a utility up the tree: MAX nodes take a maximum, MIN nodes take a minimum.
- The backed-up value of the root is the outcome if both sides play optimally.
Formulas
- MAX(s) = max over actions a of MIN(result(s, a))
- MIN(s) = min over actions a of MAX(result(s, a))
- At a terminal, the value is the utility of that position
Exam traps & shortcuts
- A MAX node does not average its children — it assumes MIN will pick the worst of them for you.
- The first move you publish is an action at the root, not the whole line of data: the opponent will not follow your favourite branch.
- Minimax is a guarantee against an optimal opponent, not a prediction of a sloppy one.
Recap
Next: alpha-beta pruning.
- Adversary
- The next state is chosen by someone who minimises your score — not by noise, and not by a copy of you.
- Game tree
- MAX layers alternate with MIN layers; a leaf carries a utility from MAX's point of view.
- Backup
- MIN takes the smallest child, MAX the largest. On the club tree that is 3, 2, then 3 by moving left.
- Optimal
- Safe against a perfect opponent. The pretty 9 is not a plan, because MIN will not donate it.
Practise Game Playing and Minimax
Reading is free and needs no account. Practice, mocks and progress live in the app.
- 2 quick checks with worked explanations
- Timed mocks scored with the real marking scheme
- Readiness tracked per topic, kept on your device