Understanding Minimax
In a zero-sum game one player’s gain is exactly the other’s loss, so there is no scope for mutual benefit and no reason to expect cooperation. Minimax responds to this by pessimism about the opponent: evaluate each available move by the worst outcome it could lead to if the opponent plays as well as possible, and choose the move whose worst case is best.
Applied to a game tree the rule becomes a recursive evaluation. Terminal positions are scored from the perspective of the first player. At nodes where that player moves, the value is the maximum over children; at nodes where the opponent moves, it is the minimum. Values propagate to the root, and the move leading to the best-valued child is selected.
Full evaluation is impossible for any interesting game, since tree size grows exponentially with depth. Two adjustments make it practical. Alpha-beta pruning tracks bounds on what each player can already guarantee and abandons branches that provably cannot change the result, returning exactly the same move while examining far fewer nodes. And search is cut off at a fixed depth, with a heuristic evaluation function estimating positions that are not terminal.
The theoretical foundation is von Neumann’s minimax theorem, which establishes that every finite two-player zero-sum game has a well-defined value, achieved by both players when mixed strategies are permitted. This is what makes minimax more than a heuristic: it identifies genuinely optimal play rather than merely cautious play, within this class of games.
Example of Minimax
Consider a shallow tree where the maximizing player chooses between two moves. Move A leads to opponent replies valued 3 and 5; move B leads to replies valued 2 and 9. The opponent minimizes, so A is worth 3 and B is worth 2.
The maximizing player therefore selects A, worth 3, even though B contains the single highest payoff of 9. That 9 would only be reached if the opponent blundered, and minimax assumes they will not: it optimizes the guaranteed outcome, not the hoped-for one.
Alpha-beta pruning reaches the same conclusion faster. Having established that A guarantees 3, the search examines B, finds a reply worth 2, and can immediately stop exploring B: the opponent already has a reply making B no better than 2, which is worse than 3, so B’s remaining branches cannot change the decision.
Frequently Asked Questions
Does alpha-beta pruning change the chosen move?
No. It returns exactly the same result as full minimax, having only skipped branches that provably could not influence it. Its benefit is entirely in the number of nodes examined, which with good move ordering can be dramatically smaller.
Why assume the opponent plays optimally?
Because it yields a guarantee. The value obtained is achievable no matter what the opponent does, so any deviation on their part can only help. Assuming a weaker opponent might score better against that specific opponent but forfeits the guarantee against a strong one.
Does minimax apply outside zero-sum games?
Not directly. Its logic depends on the opponent’s interests being exactly opposed to yours. Where players have partly aligned interests, the relevant solution concept is Nash equilibrium rather than minimax.
The Bottom Line
Minimax chooses the move with the best guaranteed outcome against perfect opposition, propagating values through a game tree by alternating maximization and minimization. Alpha-beta pruning makes it tractable, and von Neumann’s theorem gives it a firm foundation for finite zero-sum games.