Game playing and minimax
Minimax is the fundamental algorithm for computing optimal moves in finite, deterministic, zero-sum, perfect-information games by searching the game tree and choosing moves by backward induction.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Game-playing algorithms are used by engineers when designing AI agents for board games, automated decision systems, adversarial planning and testing. The minimax algorithm gives a provably optimal move against a perfect adversary in deterministic, zero-sum, perfect-information games; this forms the basis for stronger methods (alpha–beta pruning, Monte Carlo tree search) and practical game agents.
Key ideas
- Turn-taking / ply: one move by one player is called a ply. A complete pair of moves (max then min) is two plies.
- State: a complete description of the board and whose turn it is. Represented as nodes in the game tree.
- Game tree: a rooted tree where each node is a state, edges are legal moves, the root is the current state, and leaves are terminal states.
- Terminal state: a state with no legal moves (game over). At a terminal state we use the utility function to assign a numeric value to that state.
- Utility function: a function U(state) that gives a numerical payoff from max player's viewpoint (higher is better for max). For a zero-sum game, min's payoff is -U(state).
- Zero-sum: a game where the sum of the players' utilities is zero for every outcome. This means one player's gain is the other's loss.
- Deterministic: the next state is completely determined by the current state and a chosen move (no chance nodes).
- Perfect information: all players fully observe the state (no hidden cards or simultaneous moves).
- Minimax value (v(s)): the value assigned to state s assuming both players play optimally; formally defined by backward induction:
- If s is terminal, v(s) = U(s).
- If s is a max node (max to move), v(s) = max_{a in Actions(s)} v(Result(s,a)).
- If s is a min node (min to move), v(s) = min_{a in Actions(s)} v(Result(s,a)).
Exact statement (Minimax correctness for finite trees):
- Theorem: In a finite, deterministic, zero-sum, perfect-information, two-player game with a well-defined utility function on terminal states, the minimax values computed by backward induction give the value of the game at each state, and there exist pure (non-randomized) optimal strategies for both players that achieve these values.
- Assumptions: finite tree (no infinite loops), deterministic moves, perfect information, utilities defined for all terminal nodes, two players with opposite utilities (zero-sum).
- Proof sketch (by induction on depth):
- Base: depth 0 (terminal nodes). v(s) = U(s) by definition.
- Inductive step: assume v(t) is correct for all nodes of depth <= k. Consider node s of depth k+1. If s is max node, each child t = Result(s,a) has correct value v(t) by IH, so max over children gives value max_a v(Result(s,a)). This is exactly the value s can force when max chooses best a, because min will respond optimally thereafter; similarly for min nodes. Hence v(s) is correct. QED.
What to draw for a typical exam diagram: draw a rooted tree of depth 3 (root is max), with branching factor 2 at each node. Label root as s0 (Max), label children as s1 (Min) and s2 (Min). Label terminal nodes with utilities (e.g. +3, 0, -2, +1). Show arrows to children. Annotate the computed v values at each internal node by writing the max or min result next to the node (e.g., at a Min node show min(3,0) = 0). Also show chosen optimal move by thicker arrow or check mark.
Notes on practical use and limits:
- For large games (Chess, Go), full minimax is infeasible because of exponential growth. Use heuristics, depth limits and evaluation functions, and optimizations (alpha–beta pruning). Alpha–beta maintains the minimax result but prunes subtrees that cannot influence the final decision. In the best case with perfect move ordering, alpha–beta reduces the time complexity to O(b^(m/2)) with the same O(m) space; in the worst case it remains O(b^m).
- Depth-limited minimax uses an evaluation function E(s) to estimate v(s) at a cutoff depth.
Complexity definitions (to be used in exam answers): define branching factor b (average number of legal moves per state) and maximum search depth m (in plies). Then time complexity is O(b^m) and (if implemented by recursion storing current path only) space complexity is O(m).
Formulas
v(s) = U(s) where s is terminal; U(s) is the utility of state s (unitless payoff), applies only at terminal states.
v(s) = max_{a in Actions(s)} v(Result(s,a)) for s where Max moves; v(s) is unitless.
v(s) = min_{a in Actions(s)} v(Result(s,a)) for s where Min moves; v(s) is unitless.
Time complexity T = O(b^m) where b is branching factor (moves per state, unit: moves/state) and m is maximum depth in plies (unit: plies); applies to plain minimax without pruning.
Space complexity S = O(m) if using depth-first search and storing a path; applies when recursion stack stores only current path.
Remember these Python syntax lines for implementation (examples to memorize):
def minimax(state, player): — function header
for move in legal_moves(state): — iterate moves
if terminal(state): return utility(state) — terminal test
best = -math.inf / best = math.inf — initialize for max/min (requires import math); alternatively, float('-inf') / float('inf')
best = max(best, value) / best = min(best, value) — update value
return best — return minimax value
Worked examples
Example 1 — textbook tree (step-by-step): Consider the tree: root is Max with two moves A and B.
- Move A leads to a Min node with two terminal children with utilities +3 and 0.
- Move B leads to a Min node with two terminal children with utilities -2 and +1. Compute v for each node. Steps:
- For Min node under A: v = min(3, 0) = 0.
- For Min node under B: v = min(-2, 1) = -2.
- For root (Max): v = max(0, -2) = 0. So Max should choose move A. Final answer (bold): the minimax value at the root is 0, and the optimal move is A.
Example 2 — Python program: full minimax for Tic-Tac-Toe (complete code). This program computes the best move for 'X' assuming both players play optimally and prints chosen move index and resulting board. Indexing is 0..8 arranged row-major (0 top-left, 4 center, 8 bottom-right).
# Tic-Tac-Toe minimax (works as a stand-alone script)
import math
def print_board(b):
for i in range(3):
print('|'.join(b[3*i:3*i+3]))
print()
def winner(b):
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)]
for i,j,k in lines:
if b[i] != ' ' and b[i] == b[j] == b[k]:
return b[i]
if ' ' not in b:
return 'Draw'
return None
def utility(b):
w = winner(b)
if w == 'X':
return 1
if w == 'O':
return -1
return 0
# prioritize center then corners then sides for deterministic choice
MOVE_ORDER = [4,0,2,6,8,1,3,5,7]
def legal_moves(b):
return [i for i in MOVE_ORDER if b[i] == ' ']
def minimax(b, player):
w = winner(b)
if w is not None:
return utility(b)
if player == 'X': # Max
best = -math.inf
for mv in legal_moves(b):
b[mv] = 'X'
val = minimax(b, 'O')
b[mv] = ' '
if val > best:
best = val
return best
else: # Min
best = math.inf
for mv in legal_moves(b):
b[mv] = 'O'
val = minimax(b, 'X')
b[mv] = ' '
if val < best:
best = val
return best
def best_move(b, player):
moves = legal_moves(b)
best_mv = None
if player == 'X':
best = -math.inf
for mv in moves:
b[mv] = 'X'
val = minimax(b, 'O')
b[mv] = ' '
if val > best:
best = val
best_mv = mv
else:
best = math.inf
for mv in moves:
b[mv] = 'O'
val = minimax(b, 'X')
b[mv] = ' '
if val < best:
best = val
best_mv = mv
return best_mv
if __name__ == '__main__':
# Sample 1: empty board, X to move
board = [' '] * 9
print('Initial board:')
print_board(board)
mv = best_move(board, 'X')
print('Best move index for X:', mv)
board[mv] = 'X'
print('Board after best move:')
print_board(board)
# Sample 2: a midgame position
board2 = ['X','O','X',
' ','O',' ',
' ',' ','X']
print('Midgame board:')
print_board(board2)
mv2 = best_move(board2, 'O')
print('Best move index for O:', mv2)
board2[mv2] = 'O'
print('Board after O best move:')
print_board(board2)
Sample input: (the program has no external input; it uses the two hard-coded sample boards)
Exact output (copy-paste these lines including blank lines):
Initial board: | | | | | |
Best move index for X: 4 Board after best move: | | |X| | |
Midgame board: X|O|X |O| | |X
Best move index for O: 5 Board after O best move: X|O|X |O|O | |X
(Here the program finds center (4) as best for X on empty board and move 5 for O in the midgame example.)
Note: If you change MOVE_ORDER, the program may choose a different equally-good move for symmetric boards; the minimax values remain the same.
Common mistakes
- Off-by-one in depth (mixing plies and turns). Always measure depth in plies.
- Using average instead of max/min when combining child values.
- Forgetting to restore the state after recursion when implementing moves in-place.
- Reporting complexity as O(b^d) where d is number of moves instead of plies; be precise: d = max plies searched.
For your exam
Types of questions you will see:
- Definitions: define game tree, terminal state, utility, minimax value; state the minimax recurrence precisely.
- Short notes: explain why minimax is correct for finite perfect-information games; explain complexity and memory usage.
- Derivations / proofs: prove minimax correctness by induction (show base and inductive step), derive time complexity O(b^m).
- Numerical/tree questions: given a labeled tree, compute minimax values on internal nodes and mark optimal moves; draw tree and annotate.
- Programming: write minimax pseudocode or actual code for a small game (Tic-Tac-Toe), explain terminal test and utility.
What full-marks answers include:
- Precise definitions of terms mentioned in the question.
- Exact minimax recurrence and clear identification of max/min nodes.
- If asked, a short induction proof of correctness mentioning base case and inductive step.
- Complexity analysis with definitions of b and m and final O(b^m) result and space O(m).
- For tree problems: a neat labeled sketch showing values at leaves and computed values at internal nodes; indicate chosen moves.
Quick check
- Define a terminal state in a game tree.
- Write the minimax recurrence for a node where Min moves.
- What is the time complexity of plain minimax in terms of branching factor b and depth m?
Answers: 1. A state with no legal moves (game over); 2. v(s) = min_{a in Actions(s)} v(Result(s,a)); 3. O(b^m)
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?