Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):
    1. Base: depth 0 (terminal nodes). v(s) = U(s) by definition.
    2. 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:
  1. For Min node under A: v = min(3, 0) = 0.
  2. For Min node under B: v = min(-2, 1) = -2.
  3. 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

  1. Define a terminal state in a game tree.
  2. Write the minimax recurrence for a node where Min moves.
  3. 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?