Adversarial Search: Minimax Algorithm — Beginner-Friendly Notes

1. When Minimax Is Used

Two-player, zero-sum, turn-taking, fully observable, deterministic games (chess, tic-tac-toe, checkers) where opponent also plays optimally. One player maximises, other minimises — hence minimax.

Not for single-agent puzzles (use A*) — for multi-agent competitive (see Module 1 environment types).

2. Game Tree

• Nodes = board states, edges = moves. Leaves = terminal states with utility (e.g., +1 win, -1 loss, 0 draw from MAX's view).
• MAX (our agent) tries to maximise utility; MIN (opponent) tries to minimise it. Both play perfectly.

3. How Minimax Works (recursively)

Minimax(node, isMax):
  if terminal(node): return utility(node)
  if isMax:
    best = -∞
    for child in children(node):
      best = max(best, Minimax(child, false))
    return best
  else:  # MIN
    best = +∞
    for child in children(node):
      best = min(best, Minimax(child, true))
    return best

To choose a move: at root (MAX), pick child with highestMinimax value.

4. Tiny Example — Tic-Tac-Toe

       MAX (root)
      /   |   \
    MIN  MIN  MIN   ← opponent minimises
   / \   / \  / \  ← MAX again
  +1 -1 +1 0 ...

Minimax propagates leaf utilities upward: MIN picks minimum of its children, MAX picks maximum — value at root is the game outcome under optimal play.

5. Properties

Property	Value
Complete	Yes (finite tree)
Optimal	Yes vs optimal opponent (perfect play)
Time	$O(b^m)$ — visits all leaves
Space	$O(b \cdot m)$ (DFS-like)

$m$ = depth, $b$ = branching.

6. Limits & Next Fix

• Too slow for chess ($b≈35, m≈50$) — cannot search to terminal. In practice, cut off at depth limit and use evaluation function (heuristic score) instead of true utility + Alpha-Beta pruning (next topic) to skip branches.

7. One-Line Summary

Minimax computes the optimal move against an optimal opponent by recursively maximising at MAX nodes and minimising at MIN nodes over terminal utilities, with $O(b^m)$ time.

8. Quick Self-Check

1. Why does MIN minimise the same utility that MAX maximises?
2. What do you replace terminal utility with when tree is too deep?