minimax: one construct, many systems

Minimax is the principle of choosing the action whose worst possible outcome is as good as possible: minimising your maximum loss. In a two-player zero-sum game it says each player should secure the best payoff they can guarantee whatever the opponent replies. Von Neumann's 1928 minimax theorem proved that in such games, once mixed strategies are allowed, the best value a player can guarantee equals the worst the opponent can hold them to, so the game has a well-defined value. This worst-case decision rule is the same idea that reappears in statistics and in game-playing programs.[1]

Unit

The best payoff a player can guarantee against any opponent reply

Recovery means

Not applicable

Measured by

Found as the value of the game by solving the associated linear program for optimal mixed strategies

In statistical decision theory the minimax rule treats inference as a game against nature: among all possible decision rules, choose the one whose maximum risk (taken over every state nature might be in) is smallest. Wald built his theory of statistical decision functions on exactly this worst-case criterion, and Savage's minimax-regret variant minimises the largest regret rather than the largest loss. It is the same construct as the game-theoretic minimax, with an indifferent nature in place of a strategic opponent, used to pick robust estimators and tests.[2][3]

Unit

The maximum risk (or regret) of a decision rule across states of nature

Recovery means

Not applicable

Measured by

Identified as the rule minimising the supremum of the risk function, often the Bayes rule against a least-favourable prior

In artificial intelligence, minimax is the algorithm a program uses to pick a move in a two-player game by looking ahead down the game tree: it assumes the opponent will always reply with their best move, so it chooses the move that maximises its own guaranteed outcome against that optimal defence. Shannon's 1950 paper on computer chess set out this look-ahead with an evaluation function at the leaves, and it remains the backbone of game-playing AI, usually sped up with alpha-beta pruning. It is the game-theoretic worst-case rule turned into a concrete tree search.[4]

Unit

The backed-up value of a position under assumed optimal play

Recovery means

Not applicable

Measured by

Computed by propagating leaf evaluations up the tree, alternating maximising and minimising levels