Minimax

In a two-player zero-sum game, one player maximizes a utility function while the other minimizes it. Minimax computes the optimal strategy assuming both players play optimally.

Algorithm

``` function minimax(state, depth, maximizing): if state is terminal or depth == 0: return utility(state) if maximizing: v = -infinity for action in actions(state): v = max(v, minimax(result(state, action), depth - 1, False)) return v else: v = infinity for action in actions(state): v = min(v, minimax(result(state, action), depth - 1, True)) return v ```

At every node, alternate: max picks the best child for max, min picks the worst (for max) child.

Properties

• Optimal: yes, against an optimal opponent.
• Complete: yes if game tree is finite.
• Time: $O(b^m)$ — branching factor to the depth of the tree.
• Space: $O(bm)$ — current path only.

Game-tree size as the limit

Tic-tac-toe: trivial, full tree fits in memory. Chess: $b \approx 35, m \approx 80$, tree size $\sim 10^{120}$. Go: $b \approx 250, m \approx 150$. Full enumeration is hopeless. Two coping mechanisms:

1. Cutoff depth + evaluation function: stop at fixed depth, return a heuristic estimate instead of true terminal utility. 2. Pruning (next lesson): cut off branches that can't influence the final value.

Evaluation functions

For chess: material count + positional features + king safety + pawn structure + ... A well-engineered evaluation function plus depth-limited minimax beat human grandmasters in 1997 (Deep Blue).

The modern lesson, post-AlphaGo: learned evaluation functions (neural networks trained via self-play) outperform hand-engineered ones at every game we've tested. The minimax framework persists; the evaluation is now neural.

Multi-player games

With $k$ players, replace the scalar utility with a $k$-vector. Each player maximizes their own component. Generalizations like paranoid search (assume all other players gang up on you) are common in practice.

Imperfect information

Minimax assumes both players see the same state. Poker, bridge, Stratego have hidden information — the algorithms there (CFR, counterfactual regret minimization) are different beasts. Minimax remains the backbone of perfect-information games like chess and Go.