Game Theory

Minimax Search

A game theory search tree algorithm optimized with Alpha-Beta pruning.

What is Minimax Search?

Minimax is a backtracking decision tree search algorithm used in game theory and decision making for zero-sum, two-player games (like Tic-Tac-Toe or Chess). One player tries to maximize their score (Maximizer), while the opponent tries to minimize it (Minimizer). Alpha-Beta pruning is an optimization that discards subtrees that are guaranteed to have worse scores, decreasing node evaluations up to 50%.

Key Characteristics:

  • Backtracking recursion across depth levels
  • Maximizer selects maximum score; Minimizer selects minimum score
  • Pruning limits nodes visited based on alpha/beta bounds
  • Optimal choice selection for both players

Complexity Analysis

Avg Time Complexity: O(b^d) Minimax, O(b^(d/2)) Alpha-Beta best case (b = branch, d = depth)
Space Complexity: O(d) stack search space
Best Case: O(b^(d/2)) (highly ordered trees pruned early)
Worst Case: O(b^d) (no branches pruned)

How it Works Step-by-Step

  1. Recurse: Traverse down tree until terminal leaf state node.
  2. Evaluate: Calculate board evaluation score at leaf nodes.
  3. Propagate: Minimizer pulls minimum child value; Maximizer pulls maximum.
  4. Pruning: Terminate searching child branches if beta <= alpha.

Code Implementation

Worked Trace Example

Alpha-Beta Pruning on nodes:
1. Left branch returns evaluation score 3.
2. Right child evaluation node returns 2.
3. Minimizer knows parent cannot accept value > 2, so remaining right siblings are pruned.