Minimax method or theorem

Minimax (sometimes minmax) is a method in decision theory for minimizing the maximum possible loss. 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. It has also been extended to more complex games and to general decision-making in the presence of uncertainty. A simple version of the algorithm 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. Minimax theorem with simultaneous moves. The following example of a zero-sum game, where A and B make simultaneous moves, illustrates the minimax algorithm. If each player has three choices and the payoff matrix for A is:

	B chooses B1	B chooses B2	B chooses B3
A chooses A1	+3	-2	+2
A chooses A2	-1	0	+4
A chooses A3	-4	-3	+1

and B has the same payoff matrix with the signs reversed (i.e. if the choices are A1 and B1 then B pays 3 to A) then the simple 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. Minimax theory has been extended to decisions where there is no other player, but where the consequences of decisions depend on unknown facts. In addition, expectiminimax trees have been developed, for two-player games in which chance is a factor. If games have a non-zero-sum in terms of the payoffs between the players, apparently non-optimal strategies may evolve. 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. So, for non-zero-sum games the best strategy is not necessarily minimax.