Definition
In noughts and crosses, your best move depends on what your opponent will do next, which depends on what you will do after that. How can a computer plan against someone trying to beat it?
Adversarial search plans moves in games where agents have opposing goals. Minimax models a two-player, zero-sum game as a game tree: the maximising player picks moves that maximise the outcome, assuming the minimising opponent picks moves that minimise it. Values are computed from the end positions, called terminal states, back up the tree, so each move's value is the best outcome achievable against perfect play.
In simple words
Before moving, you imagine: "If I play here, what is my opponent's best reply? And then my best answer to that?" You assume your opponent is clever, and choose the move whose worst case is best for you.
Overview
- Adversarial search plans moves in games where an opponent works against you.
- Minimax assumes both players play perfectly: MAX picks the highest value, MIN the lowest.
- Values are computed at terminal positions and backed up the game tree.
- Real games are too large to search fully, so a depth limit and an evaluation function are used.
- The idea goes back to John von Neumann's minimax theorem of 1928.
- IBM's Deep Blue, which beat Garry Kasparov in 1997, used minimax with alpha-beta pruning.
Why it matters
Game playing was one of AI's earliest testbeds and drove famous milestones, from draughts in the 1950s to Deep Blue's chess victory in 1997. Minimax also models any situation where an opponent reacts: security, negotiation and auctions.
Key terms
- Game tree
- A tree of positions: each level is one player's possible moves.
- Zero-sum game
- A game where one player's gain is exactly the other's loss.
- MAX and MIN
- The player trying to maximise the score and the opponent trying to minimise it.
- Terminal state and utility
- A game-ending position and its score, such as +1 win, 0 draw, −1 loss.
- Ply
- One move by one player; a depth of 4 ply is two moves each.
- Evaluation function
- An estimate of how good a non-terminal position is, used when the tree is too deep to search fully.
Types
Games are classified into several types, and each type needs a different search method.
1. Deterministic, perfect-information, zero-sum games
Two-player games with no chance, where both players see everything and one player's gain is the other's loss.
- How it works: Plain minimax (with alpha-beta pruning) applies directly to these games.
- Example: Tic-tac-toe, chess, checkers and Go.
- When to use it: Use minimax with an evaluation function and depth limit for these classic board games.
2. Stochastic games (games of chance)
Games that include dice, cards or other randomness.
- How it works: Expectiminimax adds chance nodes whose value is the probability-weighted average of their children.
- Example: Backgammon and Ludo, where dice decide which moves are possible.
- When to use it: Use expectiminimax when randomness affects outcomes between moves. Because every chance node multiplies the tree by the number of outcomes, searches must stay shallow.
3. Imperfect-information games
Games where some information is hidden from players.
- How it works: Players reason about the possible hidden states (belief states); methods include counterfactual regret minimisation.
- Example: Poker and bridge; Libratus beat top poker professionals in 2017.
- When to use it: Use specialised algorithms; plain minimax cannot handle hidden information. Bluffing and hidden cards make reasoning about the opponent's beliefs part of good play.
4. Depth-limited minimax with evaluation functions
Searching only a few moves ahead and scoring the positions there with a heuristic.
- How it works: An evaluation function adds weighted features, such as material and mobility in chess, to estimate who is winning.
- Example: Counting queen = 9, rook = 5, bishop and knight = 3, pawn = 1 to compare chess positions.
- When to use it: Use it for any large game; better evaluation functions matter more than slightly deeper search.
5. Monte Carlo tree search (MCTS)
Estimating move values by playing many random or guided games to the end.
- How it works: It repeatedly selects, expands, simulates and backs up results, balancing exploration and exploitation with the UCT formula.
- Example: AlphaGo (2016) combined MCTS with neural networks to beat Lee Sedol at Go.
- When to use it: Use it for games with huge branching factors where good evaluation functions are hard to write.
Explained in detail
How minimax computes values
Start at the terminal positions and score them from MAX's point of view: +1 for a win, 0 for a draw, −1 for a loss. Move up one level. At a position where MIN is to move, its value is the minimum of its children's values, because MIN will choose the reply that is worst for MAX. At a position where MAX is to move, its value is the maximum of its children's values. Continue to the root. MAX then plays the move leading to the child with the highest value. The result is the best outcome MAX can guarantee, whatever MIN does.
Too many positions
| Game | Typical branching factor | Positions (rough) | Fully searchable? |
|---|---|---|---|
| Noughts and crosses | about 5 | Under 6,000 legal positions | Yes, instantly |
| Draughts (checkers) | about 8 | About 5 × 10²⁰ | Solved in 2007 after years of computing |
| Chess | about 35 | 10⁴⁰ or more | No |
| Go (19 × 19) | about 250 | About 2 × 10¹⁷⁰ | No |
For large games, minimax is cut off at a fixed depth and an evaluation function estimates the value of positions there. In chess, a simple one counts material: a pawn is 1, a knight or bishop 3, a rook 5, a queen 9, plus bonuses for king safety and centre control. IBM's Deep Blue searched around 200 million positions per second with a carefully tuned evaluation function and beat world champion Garry Kasparov in a six-game match in May 1997.
Beyond minimax
- Alpha-beta pruning, on the next page, skips branches that cannot affect the decision.
- Games with chance, such as backgammon or Ludo, use expectiminimax, averaging over dice outcomes.
- Monte Carlo tree search plays many random games from a position and uses the results to guide the search.
- DeepMind's AlphaGo, which beat Lee Sedol at Go in 2016, combined Monte Carlo tree search with neural networks that evaluated positions and suggested moves, learned from games and self-play.
Minimax also shapes how we think about AI safety and security: a defender planning against an attacker assumes the attacker will choose the most damaging move, exactly the worst-case reasoning minimax uses.
How it works
- Represent positions, legal moves, terminal tests and utilities.
- Write a recursive function that returns a position's value.
- At terminal positions, return the utility.
- At MAX's turn, return the maximum of the children; at MIN's, the minimum.
- For large games, stop at a depth limit and use an evaluation function.
In code
from functools import lru_cache
LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(b):
for a, c, d in LINES:
if b[a] != "." and b[a] == b[c] == b[d]:
return b[a]
return None
@lru_cache(maxsize=None)
def minimax(b, player):
w = winner(b)
if w:
return 1 if w == "X" else -1
if "." not in b:
return 0
values = []
for i, cell in enumerate(b):
if cell == ".":
nxt = b[:i] + player + b[i+1:]
values.append(minimax(nxt, "O" if player == "X" else "X"))
return max(values) if player == "X" else min(values)
def best_move(b, player="X"):
moves = [i for i, c in enumerate(b) if c == "."]
score = lambda i: minimax(b[:i] + player + b[i+1:], "O" if player == "X" else "X")
return max(moves, key=score) if player == "X" else min(moves, key=score)
print("Value of the empty board:", minimax("." * 9, "X"), "(0 = a draw with perfect play)")
board = "XO.XO...." # X to move: X can win on square 6
print("Best move for X:", best_move(board))
print("Positions evaluated:", minimax.cache_info().currsize)Output
Value of the empty board: 0 (0 = a draw with perfect play) Best move for X: 6 Positions evaluated: 5478
Try it yourself
Thinking two moves ahead
X has two in the left column; O has two in the middle column. X is to move.
Backing up values
Put the steps of minimax in order.
- 1Generate the game tree to the terminal positions or a depth limit
- 2Play the root move with the highest value
- 3At MAX levels take the maximum of the children
- 4Score the leaves with utilities or an evaluation function
- 5At MIN levels take the minimum of the children
Common mistakes
- Scoring positions from the wrong player's point of view.
- Trying to search the full tree of chess or Go.
- Using a poor evaluation function and blaming the search.
Check yourself
Summary
- Minimax plans against an opponent by backing up values through a game tree.
- MAX takes maxima, MIN takes minima; the root value is the guaranteed outcome.
- Large games need depth limits, evaluation functions and smarter search.
Read it. Now try it yourself.
Open the interactive activityFinished reading?
Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · IBM: Deep Blue · Google DeepMind: AlphaGo