Minimax Algorithm
What you'll learn: How to compute the optimal move in a two-player zero-sum game by assuming both players play perfectly.
The Core Idea
Imagine playing tic-tac-toe where you want to guarantee the best possible outcome. The minimax algorithm recursively evaluates all possible future game states, assuming you maximize your score while your opponent minimizes it.
The algorithm works backward from terminal game states (wins, losses, draws) up through the game tree:
- Maximizing player (you) picks the move leading to the highest score
- Minimizing player (opponent) picks the move leading to the lowest score for you
- At each level, you alternate between maximizing and minimizing
How It Works
Starting from a current game position:
- Generate all possible moves (children in the game tree)
- For each move, recursively evaluate the resulting position
- If it's the maximizer's turn, return the maximum value among all children
- If it's the minimizer's turn, return the minimum value among all children
- Base case: at terminal states (leaf nodes), return the actual game score
The algorithm assumes perfect play from both sides—your opponent will always make the move that's worst for you (best for them). By "backing up" values through the tree, you find which initial move leads to the best guaranteed outcome.
The Zero-Sum Assumption
Minimax applies to zero-sum games where one player's gain equals the other's loss. What's good for you (+10) is equally bad for your opponent (-10).
Key Takeaway: Minimax finds optimal moves in adversarial games by recursively alternating between maximizing your score and minimizing your opponent's advantage, guaranteeing the best outcome under perfect play.