Minimax Algorithm With Alternate Moves Minimax Theorem With

The minimax algorithm is a recursive algorithm for choosing the next move in 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 maximises 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.

One allocation method is to assign a certain win for A as +1 and for B as −1. This leads to combinatorial game theory as developed by John Conway.

An alternative is to use 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. (A is called the maximizing player and B is called the minimizing player), hence it is called the 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 possible 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.

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" or " ply".

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 childrenTrees (structure) A child node or descendant node is a node in a tree data structure that is linked to by a parent node. Thinking of the tree as a directed graph, node A is a child of node B if and only if node A is a sucessor node of B''. A node with no of each node (i.e., the average number of legal moves in a position). The number of nodes to be explored usually increases exponentiallyIn mathematics, a quantity that grows exponentially is one that grows at a rate proportional to its size. Anything that grows by the same percentage every year (or every month, day, hour etc. is growing exponentially. For example, if the average number of with the number of plies (it is less than exponential if evaluating forced move s or repeated positions). 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 impossible to completely analyze games such as chess using the minimax algorithm.

The performance of the naive minimax algorithm may be improved dramatically, without affecting the result, by the use of alpha-beta pruningAlpha-beta pruning is a technique to reduce the number of nodes evaluated by the minimax algorithm for two-player games. It prunes out parts of the search tree that are so good for one player that the opponent will never allow them to be reached. Same as. 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.

2 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 matrixA payoff matrix or payoff function is a concept in game theory which shows what payoff each player will receive at the outcome of the game. The payoff for each player will of course depend on the combined actions of all players. Technically, matrix is use 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.

John von NeumannA separate article covers Saint John Neumann, the American priest. John von Neumann (Neumann Janos) ( December 28, 1903 February 8, 1957) was a Hungarian- American mathematician who made important contributions in quantum physics, set theory, computer sci proved the Minimax theorem in 1928Centuries: 19th century 20th century 21st century Decades: 1870s 1880s 1890s 1900s 1910s 1920s 1930s 1940s 1950s 1960s 1970s Years: 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 See also 1928 in aviation 1928 in film 1928 in literature 1928 in mu, stating that such strategies always exist in two-person zero-sum games and can be found by solving a set of simultaneous equations.

3 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 of 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 lawMurphy's law is a popular adage in Western culture, which broadly states that things will go wrong in any given situation. It is most commonly formulated as "if anything can go wrong, it will. The law was named after Edward A. Murphy, Jr. a development en, take an approach which minimizes the maximum expected loss, using the same techinques as in the two-person zero-sum games.

In addition, expectiminimax treeAn expectiminimax tree is a specialized variation of a minimax tree for use in artificial intelligence systems which play games of chance. In the traditional minimax method, the levels of the tree alternate from max to min until the depth limit of the tres have been developed, for two-player games in which chance (for example, dice) is a factor.

4 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. For example in the prisoner's dilemma, the minimax strategy for each prisioner is to confess even though they would each do better if both denied their guilt.

Home > Minimax

1 Minimax algorithm with alternate moves

2 Minimax theorem with simultaneous moves

3 Minimax in the face of uncertainty

4 Minimax in non-zero-sum games

Topics: Minimax Algorithm With Alternate Moves, Minimax Theorem With...