Minimax

Definition: Minimax is an algorithm for minimizing the maximum possible loss for opponents in competitive two-player games. It uses a game tree where maximizing players choose moves with the highest score while minimizing opponents choose moves with the lowest score, alternating until leaf nodes are reached.

How does it work?

The minimax algorithm operates on a game tree representing all possible moves and counter-moves. At each level of the tree, players alternate between maximizing their score and minimizing their opponent's score. The algorithm assumes both players play optimally.

Key characteristics of games suitable for minimax:

No cycles - The game cannot return to a previously seen state
Perfect information - Both players know the complete game state
No chance elements - No dice or shuffled cards affect outcomes
Zero-sum - One player's gain is the other's loss

Algorithm Steps

Generate the complete game tree from current position to terminal states
Assign utility values to all terminal states (win/lose/draw or numerical scores)
Work backwards: at minimizing levels, take the minimum of children; at maximizing levels, take the maximum
Repeat until the root is reached; the best move is the one leading to the highest-valued child

Example: A Simple Game

Consider a game where Alice places a coin on the starting circle. Players alternate moving the coin along lines:

Alice moves first, choosing between connected circles
Bob moves second, trying to maximize his payoff
The game ends when the coin reaches a numbered circle
The number represents how much Alice pays Bob

At each blue (Bob's turn) circle, he chooses the highest value. At each pink (Alice's turn) circle, she chooses the lowest value. This alternating selection propagates up the tree to determine optimal play.

Variants

Maximin - Maximize the minimum achievable outcome (opposite philosophy)
Minimin - Minimize the minimum (not optimal for competitive games)
Maximax - Maximize the maximum (optimistic, used in some game AI)

Applications

Game AI - Chess programs, checkers, tic-tac-toe, go engines
Election methods - Condorcet method
Decision theory - Game-theoretic optimization
Board game engines - Computer opponents in video games

Limitations

Game trees grow exponentially with depth
Most practical games (chess, go) have trees too large to explore completely
Requires pruning techniques (like alpha-beta pruning) for real-world use
Only works for deterministic, perfect-information, zero-sum games

Theorem

The Zermelo theorem in game theory states that any finite, deterministic, perfect-information, two-player game is solvable. This means either:

The first player has a winning strategy
The second player has a winning strategy
Both players can force a draw