Minimax
Minimax is a decision rule for two-player, zero-sum, perfect-information games in which each player assumes the opponent will reply as damagingly as possible, so that a player picks the move whose worst-case outcome is the best available. It has two linked lives: as a theorem of game theory, proved by John von Neumann, about the value every finite zero-sum game possesses, and as a recursive algorithm that walks a game tree, scores the leaves, and backs the scores up to the root so that a program can choose a move in chess, checkers, tic-tac-toe or any similar contest.
The theorem came first: in 1928 John von Neumann published Zur Theorie der Gesellschaftsspiele (On the Theory of Parlor Games) in Mathematische Annalen, proving that every finite two-person zero-sum game has a value, and that each player has a (possibly randomized) strategy guaranteeing at least that value no matter what the other does. A game is zero-sum when one player's gain is exactly the other's loss, so there is no cooperation to find and no joint surplus to split. In such a game, the amount Max can guarantee by maximizing the minimum payoff equals the amount Min can hold Max to by minimizing the maximum payoff, and this shared number is the value of the game. For games of perfect information like chess, pure strategies already suffice, but for games with hidden information such as matching pennies or poker-like bluffing, the guarantee generally requires mixing strategies randomly. Von Neumann and Oskar Morgenstern built the 1944 book Theory of Games and Economic Behavior on this foundation, and the result is a direct ancestor of the later Nash equilibrium, which extends the idea beyond zero-sum settings.
The algorithm turns that guarantee into a search procedure: build the tree of positions reachable by alternating moves, assign each leaf a numerical score from the viewpoint of one player (called Max), and then propagate scores upward, taking the maximum at positions where Max moves and the minimum at positions where the opponent (Min) moves. The value that arrives at the root is the best result Max can force against perfect play, and the child that supplied it is the move to play. Claude Shannon laid out this scheme for computer chess in his 1950 paper Programming a Computer for Playing Chess, in Philosophical Magazine, proposing a fixed-depth search with a static evaluation function at the frontier, because full chess trees are far too large to expand to their true endings. A common implementation trick, negamax, exploits the zero-sum symmetry: the value of a position for one player is the negative of its value for the opponent, so a single function handles both sides by negating the returned score.
A worked example makes the backing-up rule concrete, and it also exposes what the rule means. Suppose Max has three moves, A, B and C, and each leads to a position where Min chooses between two replies. Under A the leaves score 3 and 5, under B they score 2 and 9, and under C they score 6 and 4. Min will pick the smaller score in each pair, so the three branches are worth 3, 2 and 4 to Max, and Max chooses C, even though B contains the largest leaf anywhere in the tree, the 9. That 9 is unreachable against a sensible opponent, since Min would simply answer B with the 2. The diagram below traces the same calculation step by step.
The cost of the method is its branching: a search to depth d in a game with about b legal moves per position visits on the order of b to the power d positions, and chess's branching factor of roughly thirty-odd legal moves makes exhaustive search hopeless beyond a few plies. That is why practical programs combine minimax with a depth limit, an evaluation function (material, mobility, king safety and so on, hand-tuned or learned), iterative deepening, and above all alpha-beta pruning, which returns exactly the same answer as plain minimax while skipping branches that cannot matter. Quiescence search, which keeps extending lines until captures and checks settle down, patches the horizon effect, where a fixed cutoff makes a program miss an imminent loss just beyond the last ply it examined.
The most common misconception is that minimax finds the objectively best move; in truth it finds the best move relative to the evaluation function at the search horizon, and it assumes an opponent who is as rational as the model says. With a flawed evaluation, perfect minimax over it is only as good as its leaf scores. In games that are not zero-sum, or that involve hidden information, a naive minimax may be wrong, and the assumption of a perfect adversary can make a program needlessly pessimistic against a weak human opponent. Today the same worst-case logic lives on in chess engines such as Stockfish, in adversarial robustness and minimax training objectives for generative adversarial networks, in robust optimization, and as the thing that Monte Carlo tree search and AlphaZero-style systems approximate with sampled, learned evaluations instead of exact backups.
Read minimax as the formal meaning of playing safe against a thinking opponent: a theorem that says a guaranteed-value strategy exists, and a tree-walking procedure that finds it by assuming every opponent reply is the worst one.