Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy. It aims to minimize the possible loss for a worst-case (maximum loss) scenario. When dealing with gains, it is referred to as 'maximin' – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.
The concept is central to adversarial settings, where one player's gain is another's loss. In such contexts, minimax provides a conservative strategy: assume the opponent will always choose the action that is worst for you, and select the move that maximizes your guaranteed payoff. This principle underlies many algorithms in machine learning and deep learning, particularly in training generative models and designing robust systems.
Game Theory Foundations
In game theory, the maximin value is the highest value a player can be sure to get without knowing the actions of the other players; equivalently, it is the lowest value the other players can force the player to receive when they know the player's action. The formal definition is: v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}), where i is the index of the player, a_i is the action taken by player i, a_{-i} denotes the actions of all other players, and v_i is the value function of player i.
Calculating the maximin value uses a worst-case approach: for each possible action of the player, check all possible actions of the others and determine the worst combination – the one giving the smallest value. Then, choose the action that makes this smallest value as high as possible. For example, consider a two-player game where the row player can choose T, M, or B, and the column player can choose L or R, with payoffs shown in a table. The row player can play T, guaranteeing a payoff of at least 2 (B is risky with −100, M can yield −10), so v_row_underline = 2. The column player can play L, securing at least 0 (R risks −20), so v_col_underline = 0. If both play their maximin strategies (T, L), the payoff vector is (3, 1).
The minimax value of a player is the smallest value that the other players can force the player to receive, without knowing the player's actions; equivalently, it is the largest value the player can be sure to get when they know the actions of the others. Its formal definition is: v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}). In zero-sum games, the minimax value equals the maximin value for each player, leading to the minimax theorem.
Minimax Theorem and Zero-Sum Games
The minimax theorem, proven by John von Neumann in 1928, states that in finite, two-player, zero-sum games with mixed strategies, the maximin value equals the minimax value. This theorem provides a foundation for equilibrium analysis. In such games, the value of the game is the expected payoff when both players play optimally. The theorem ensures that a player can guarantee at least this value, and the opponent can hold them to at most this value.
For simultaneous-move games, the concept extends to mixed strategies, where players randomize over pure actions. The minimax theorem guarantees the existence of a saddle point in mixed strategies, which is a pair of strategies where neither player can improve their payoff by unilaterally deviating. This result is fundamental in neural network training, where adversarial examples are analyzed using similar worst-case principles.
Applications in Artificial Intelligence
In AI, minimax is widely used in decision-making for games and adversarial scenarios. The classic example is the minimax algorithm for two-player turn-based games like chess, checkers, or tic-tac-toe. The algorithm recursively evaluates the game tree, assuming the opponent plays optimally. At each node, the player chooses the move that maximizes their minimum gain, while the opponent chooses the move that minimizes the player's maximum gain. This is often combined with alpha-beta pruning to reduce computational complexity.
In large language models and transformer architectures, minimax principles appear in adversarial training, where models are trained to be robust against worst-case perturbations. For instance, generative adversarial networks (GANs) use a minimax objective: the generator tries to minimize the discriminator's ability to distinguish real from fake data, while the discriminator tries to maximize its accuracy. This adversarial process is a direct application of minimax in deep learning.
Extensions and Variations
Minimax has been extended to more complex games, including games with chance (like backgammon) using expectiminimax, and games with imperfect information using techniques like counterfactual regret minimization. In reinforcement learning, minimax is used in robust control and multi-agent settings, where agents must account for worst-case opponent behavior. The concept also appears in optimization and statistics, where minimax estimators minimize the maximum risk.
In computer chess and other game-playing AI, minimax with alpha-beta pruning remains a core technique, though modern systems like OpenAI and Google DeepMind often use machine learning approaches that incorporate minimax-like objectives. The principle is also relevant in decision theory for choosing actions under uncertainty, where a decision-maker selects the option that minimizes the worst-case loss.
Historical Context and Related Concepts
The minimax rule has roots in game theory and decision theory, with contributions from mathematicians like John von Neumann and Oskar Morgenstern. It is closely related to the concept of a saddle point in optimization and to the Nash equilibrium in non-zero-sum games. In philosophy, minimax is used in discussions of rationality and risk aversion.
In modern AI, minimax is often contrasted with Bayesian decision theory, which uses prior probabilities rather than worst-case assumptions. While minimax is conservative, Bayesian methods can be more flexible. The choice between them depends on the availability of probabilistic information. In AI research, minimax remains a benchmark for evaluating decision-making algorithms, especially in adversarial environments.
See Also
- Alpha-beta pruning
- Game theory
- Zero-sum game
- Adversarial machine learning