Minimax
Minimax is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for minimizing the possible loss for a worst case 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 the 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.
Game theory
In general games
The maximin value is the highest value that the 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. Its formal definition is:Where:
- is the index of the player of interest.
- denotes all other players except player.
- is the action taken by player.
- denotes the actions taken by all other players.
- is the value function of player.
For example, consider the following game for two players, where the first player may choose any of three moves, labelled,, or, and the second player may choose either of two moves, or. The result of the combination of both moves is expressed in a payoff table:
.
For the sake of example, we consider only pure strategies. Check each player in turn:
- The row player can play, which guarantees them a payoff of at least . Hence:.
- The column player can play and secure a payoff of at least . Hence:.
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 other players. Its formal definition is:
The definition is very similar to that of the maximin value – only the order of the maximum and minimum operators is inverse. In the above example:
- The row player can get a maximum value of or , so:
- The column player can get a maximum value of , or . Hence:
Intuitively, in maximin the maximization comes after the minimization, so player tries to maximize their value before knowing what the others will do; in minimax the maximization comes before the minimization, so player is in a much better position – they maximize their value knowing what the others did.
Another way to understand the notation is by reading from right to left: When we write
the initial set of outcomes depends on both and We first marginalize away from, by maximizing over to yield a set of marginal outcomes which depends only on We then minimize over over these outcomes.
Although it is always the case that and the payoff vector resulting from both players playing their minimax strategies, in the case of or in the case of cannot similarly be ranked against the payoff vector resulting from both players playing their maximin strategy.
In zero-sum games
In two-player zero-sum games, the minimax solution is the same as the Nash equilibrium.
In the context of zero-sum games, the minimax theorem is equivalent to:
For every two-person zero-sum game with finitely many strategies, there exists a value and a mixed strategy for each player, such that
Equivalently, Player 1's strategy guarantees them a payoff of regardless of Player 2's strategy, and similarly Player 2 can guarantee themselves a payoff of −. The name minimax arises because each player minimizes the maximum payoff possible for the other – since the game is zero-sum, they also minimize their own maximum loss.
See also example of a game without a value.
Example
The following example of a zero-sum game, where A and B make simultaneous moves, illustrates maximin solutions. Suppose each player has three choices and consider the payoff matrix for A displayed on the table. Assume the payoff matrix for B is the same matrix with the signs reversed. Then, the maximin choice for A is A2 since the worst possible result is then having to pay 1, while the simple maximin choice for B is B2 since the worst possible result is then no payment. However, this solution is not stable, since if B believes A will choose A2 then B will choose B1 to gain 1; then if A believes B will choose B1 then A will choose A1 to gain 3; and then B will choose B2; and eventually both players will realize the difficulty of making a choice. So a more stable strategy is needed.Some choices are dominated by others and can be eliminated: A will not choose A3 since either A1 or A2 will produce a better result, no matter what B chooses; B will not choose B3 since some mixtures of B1 and B2 will produce a better result, no matter what A chooses.
Player A can avoid having to make an expected payment of more than by choosing A1 with probability and A2 with probability The expected payoff for A would be in case B chose B1 and in case B chose B2. Similarly, B can ensure an expected gain of at least, no matter what A chooses, by using a randomized strategy of choosing B1 with probability and B2 with probability. These mixed minimax strategies cannot be improved and are now stable.
Maximin
Frequently, in game theory, maximin is distinct from minimax. Minimax is used in zero-sum games to denote minimizing the opponent's maximum payoff. In a zero-sum game, this is identical to minimizing one's own maximum loss, and to maximizing one's own minimum gain."Maximin" is a term commonly used for non-zero-sum games to describe the strategy which maximizes one's own minimum payoff. In non-zero-sum games, this is not generally the same as minimizing the opponent's maximum gain, nor the same as the Nash equilibrium strategy.
In repeated games
The minimax values are very important in the theory of repeated games. One of the central theorems in this theory, the folk theorem, relies on the minimax values.Combinatorial game theory
In combinatorial game theory, there is a minimax algorithm for game solutions.A simple version of the minimax algorithm, stated below, deals with games such as tic-tac-toe, where each player can win, lose, or draw. If player A can win in one move, their best move is that winning move. If player B knows that one move will lead to the situation where player A can win in one move, while another move will lead to the situation where player A can, at best, draw, then player B's best move is the one leading to a draw. Late in the game, it's easy to see what the "best" move is. The minimax algorithm helps find the best move, by working backwards from the end of the game. At each step it assumes that player A is trying to maximize the chances of A winning, while on the next turn player B is trying to minimize the chances of A winning.
Minimax algorithm with alternate moves
A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent's possible following moves. If it is AA possible allocation method consists in assigning a certain win for A as +1 and for B as −1. This leads to combinatorial game theory as developed by John H. Conway. An alternative is using a rule that if the result of a move is an immediate win for A, it is assigned positive infinity and if it is an immediate win for B, negative infinity. The value to A of any other move is the maximum of the values resulting from each of B
This can be extended if we can supply a heuristic evaluation function which gives values to non-final game states without considering all possible following complete sequences. We can then limit the minimax algorithm to look only at a certain number of moves ahead. This number is called the "look-ahead", measured in "plies". For example, the chess computer Deep Blue looked ahead at least 12 plies, then applied a heuristic evaluation function.
The algorithm can be thought of as exploring the nodes of a game tree. The effective branching factor of the tree is the average number of children of each node. The number of nodes to be explored usually increases exponentially with the number of plies. The number of nodes to be explored for the analysis of a game is therefore approximately the branching factor raised to the power of the number of plies. It is therefore impractical to completely analyze games such as chess using the minimax algorithm.
The performance of the naïve minimax algorithm may be improved dramatically, without affecting the result, by the use of alpha–beta pruning. Other heuristic pruning methods can also be used, but not all of them are guaranteed to give the same result as the unpruned search.
A naïve minimax algorithm may be trivially modified to additionally return an entire Principal Variation along with a minimax score.