Minimax (sometimes minmax) is a method in decision theory for minimizing the maximum possible loss. Decision theory in Mathematics and Statistics is concerned with identifying the Values uncertainties and other issues relevant in a given In Statistics, Decision theory and Economics, a loss function is a function that maps an event (technically an element of a Sample space Alternatively, it can be thought of as maximizing the minimum gain (maximin). It started from two player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves. In Game theory and Economic theory, zero-sum describes a situation in which a participant's gain or loss is exactly balanced by the losses or gains of the other Game theory is a branch of Applied mathematics that is used in the Social sciences (most notably Economics) Biology, Engineering, It has also been extended to more complex games and to general decision making in the presence of uncertainty.

Minimax theorem

The minimax theorem states:

For every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that (a) Given player 2's strategy, the best payoff possible for player 1 is V, and (b) Given player 1's strategy, the best payoff possible for player 2 is -V.

Equivalently, Player 1's strategy guarantees him a payoff of V regardless of Player 2's strategy, and similarly Player 2 can guarantee himself a payoff of -V. The name minimax arises because each player minimizes the maximum payoff possible for the other--since the game is zero-sum, he also maximizes his own minimum payoff.

This theorem was established by John von Neumann^[1], who is quoted as saying "As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved". ^[2]

See Sion's minimax theorem and Parthasarathy's theorem for generalizations. In Mathematics, and in particular Game theory, Sion's minimax theorem is a generalization of John Von Neumann 's Minimax theorem. In Mathematics and in particular the study of Games on the unit square, Parthasarathy's theorem is a generalization of Von Neumann's minimax theorem.

Tic-tac-toe

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, his 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 (i. e. , to maximize B's own chances of winning).

Minimax criterion in statistical decision theory

Main article: Minimax estimator

In classical statistical decision theory, we have an estimator δ that is used to estimate a parameter . In statistical Decision theory, where we are faced with the problem of estimating a deterministic Decision theory in Mathematics and Statistics is concerned with identifying the Values uncertainties and other issues relevant in a given In Statistics, an estimator is a function of the observable sample data that is used to estimate an unknown population Parameter (which is called the In Mathematics, Statistics, and the mathematical Sciences a parameter ( G auxiliary measure) is a quantity that defines certain characteristics We also assume a risk function R(θ,δ), usually specified as the integral of a loss function. This article is about the mathematical definition of risk in statistical decision theory In Statistics, Decision theory and Economics, a loss function is a function that maps an event (technically an element of a Sample space In this framework, is called minimax if it satisfies

.

An alternative criterion in the decision theoretic framework is the Bayes estimator in the presence of a prior distribution Π. In Decision theory and Estimation theory, a Bayes estimator is an Estimator or decision rule that maximizes the posterior Expected value A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence. An estimator is Bayes if it minimizes the average risk

Minimax algorithm with alternate moves

A minimax algorithm^[3] is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. In Mathematics, an average, or central tendency of a Data set refers to a measure of the "middle" or " expected " value of In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation Game theory is a branch of Applied mathematics that is used in the Social sciences (most notably Economics) Biology, Engineering, 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. An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing programs to estimate the value 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 A's turn to move, A gives a value to each of his legal moves.

A 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 Horton Conway. This article is on the theory of combinatorial games For the theory that includes games of chance and games of imperfect knowledge see Game theory John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups 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 minimum of the values resulting from each of B's possible replies. For this reason, A is called the maximizing player and B is called the minimizing player, hence the name minimax algorithm. The above algorithm will assign a value of positive or negative infinity to any position since the value of every position will be the value of some final winning or losing position. Often this is generally only possible at the very end of complicated games such as chess or go, since it is not computationally feasible to look ahead as far as the completion of the game, except towards the end, and instead positions are given finite values as estimates of the degree of belief that they will lead to a win for one player or another. Chess is a recreational and competitive Game played between two players.

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. heuristic (hyu̇-ˈris-tik is a method to help solve a problem commonly an informal method 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". In two-player Sequential games a ply refers to one turn taken by one of the players For example, the chess computer Deep Blue (that beat Garry Kasparov) looked ahead 12 plies, then applied a heuristic evaluation function. Deep Blue is a Chess - playing Computer developed by IBM. On 11 May 1997, the machine won a six-game match by two wins to Garry Kasparov (Га́рри Ки́мович Каспа́ров) (born as Garry Kimovich Weinstein on April 13 1963 in Baku, Azerbaijan SSR, Soviet

The algorithm can be thought of as exploring the nodes of a game tree. A node is an abstract basic unit used to build linked Data structures such as trees, Linked lists and computer-based representations of graphs If you're looking for game tree as it's used in game theory (not combinatorial game theory please see Extensive form game. The effective branching factor of the tree is the average number of children of each node (i. In Computing, Tree data structures and Game theory, the branching factor is the number of children of each node. In Computer science, a tree is a widely-used Data structure that emulates a Tree structure with a set of linked nodes e. , the average number of legal moves in a position). The number of nodes to be explored usually increases exponentially with the number of plies (it is less than exponential if evaluating forced moves or repeated positions). Exponential growth (including Exponential decay) occurs when the growth rate of a mathematical function is proportional to the function's current value 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. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources

The performance of the naïve minimax algorithm may be improved dramatically, without affecting the result, by the use of alpha-beta pruning. Alpha-beta pruning is a Search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. Other heuristic pruning methods can also be used, but not all of them are guaranteed to give the same result as the un-pruned search.

Pseudocode

Pseudocode for the minimax algorithm (using an evaluation heuristic to terminate at a given depth) is given below. Pseudocode is a compact and informal high-level description of a Computer programming Algorithm that uses the structural conventions of some Programming language

The code is based on the observation that max(a,b) = − min( − a, − b). This avoids the need for the algorithm to treat the two players separately.

function minimax(node, depth)    if node is a terminal node or depth = CutoffDepth        return the heuristic value of node    else        let α := -∞        foreach child of node                       { evaluation is identical for both players }            let α := max(α, -minimax(child, depth+1))        return α

Example

Suppose the game being played only has a maximum of two possible moves per player each turn. The algorithm generates the tree on the right, where the circles represent the moves of the player running the algorithm (maximizing player), and squares represent the moves of the opponent (minimizing player). If you're looking for game tree as it's used in game theory (not combinatorial game theory please see Extensive form game. Because of the limitation of computation resources, as explained above, the tree is limited to a look-ahead of 4 moves.

The algorithm evaluates each leaf node using a heuristic evaluation function, obtaining the values shown. In Computer science, a leaf node or external node is a node of a Tree data structure that has zero Child nodes Often leaf nodes are The moves where the maximizing player wins are assigned with positive infinity, while the moves that lead to a win of the minimizing player are assigned with negative infinity. At level 3, the algorithm will choose, for each node, the smallest of the child node values, and assign it to that same node (e. In Computer science, a tree is a widely-used Data structure that emulates a Tree structure with a set of linked nodes g the node on the left will choose the minimum between "10" and "+∞", therefore assigning the value "10" to himself). The next step, in level 2, consists of choosing for each node the largest of the child node values. Once again, the values are assigned to each parent node. In Computer science, a tree is a widely-used Data structure that emulates a Tree structure with a set of linked nodes The algorithm continues evaluating the maximum and minimum values of the child nodes alternatively until it reaches the root node, where it chooses the move with the largest value (represented in the figure with a blue arrow). In Computer science, a tree is a widely-used Data structure that emulates a Tree structure with a set of linked nodes This is the move that the player should make in order to minimize the maximum possible loss. In Statistics, Decision theory and Economics, a loss function is a function that maps an event (technically an element of a Sample space

Minimax theorem with simultaneous moves

The following example of a zero-sum game, where A and B make simultaneous moves, illustrates the minimax algorithm. Suppose each player has three choices and consider the payoff matrix for A displayed at right. Assume the payoff matrix for B is the same matrix with the signs reversed (i. e. if the choices are A1 and B1 then B pays 3 to A). Then, the minimax choice for A is A2 since the worst possible result is then having to pay 1, while the simple minimax 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 B2 will produce a better result, no matter what A chooses.

A can avoid having to make an expected payment of more than 1/3 by choosing A1 with probability 1/6 and A2 with probability 5/6, no matter what B chooses. B can ensure an expected gain of at least 1/3 by using a randomized strategy of choosing B1 with probability 1/3 and B2 with probability 2/3, no matter what A chooses. These mixed minimax strategies are now stable and cannot be improved. In Game theory, a player's strategy in a game is a complete plan of action for whatever situation might arise this fully determines the player's behaviour

John von Neumann proved the Minimax theorem in 1928, stating that such strategies always exist in two-person zero-sum games and can be found by solving a set of simultaneous equations. Year 1928 ( MCMXXVIII) was a Leap year starting on Sunday (link will display full calendar of the Gregorian calendar.

Minimax in the face of uncertainty

Minimax theory has been extended to decisions where there is no other player, but where the consequences of decisions depend on unknown facts. For example, deciding to prospect for minerals entails a cost which will be wasted if the minerals are not present, but will bring major rewards if they are. One approach is to treat this as a game against nature, and using a similar mindset as Murphy's law, take an approach which minimizes the maximum expected loss, using the same techniques as in the two-person zero-sum games. Murphy's law is an Adage in Western culture that broadly states "if anything can go wrong it will

In addition, expectiminimax trees have been developed, for two-player games in which chance (for example, dice) is a factor. An expectiminimax tree is a specialized variation of a minimax tree for use in Artificial intelligence systems which play Games of chance.

Minimax in non-zero-sum games

If games have a non-zero-sum in terms of the payoffs between the players, apparently non-optimal strategies may evolve. In Game theory and Economic theory, zero-sum describes a situation in which a participant's gain or loss is exactly balanced by the losses or gains of the other For example in the prisoner's dilemma, the minimax strategy for each prisoner is to betray the other even though they would each do better if neither confessed their guilt. The Prisoner's Dilemma constitutes a problem in Game theory. It was originally framed by Merrill Flood and Melvin Dresher So, for non-zero-sum games, minimax is not necessarily the best strategy.

Maximin in philosophy

In philosophy, the term "maximin" is often used to refer to what John Rawls called The Difference Principle. John Rawls ( February 21, 1921  &ndash November 24, 2002) was an American Philosopher, a Professor of In his book A Theory of Justice, Rawls defined this principle as the rule which states that social and economic inequalities should be arranged so that "they are to be of the greatest benefit to the least-advantaged members of society". A Theory of Justice is a widely-read book of political and Moral philosophy by John Rawls. In other words, an unequal distribution can be just when it maximizes the benefit to those who have the most minuscule allocation of welfare conferring resources (which he refers to as "primary goods").

See also

Notes

External links

• Simple explanation of the algorithm
• Minimax Analysis for Zero Sum Games
• A visualization applet
• "Maximin principle" from A Dictionary of Philosophical Terms and Names.
• Play a betting-and-bluffing game against a mixed minimax strategy
• The Dictionary of Algorithms and Data Structures entry for minimax
• Minimax (with or without alpha-beta pruning) algorithm visualization - game tree (Java Applet)
• CLISP minimax - game.