Artificial Intelligence/Search/Adversarial search/Minimax Search

The minimax search is especially known for its usefulness in calculating the best move in two player games where all the information is available, such as chess or tic tac toe (Muller, 2001). It consists of navigating through a tree which captures all the possible moves in the game, where each move is represented in terms of loss and gain for one of the players. It follows that this can only be used to make decisions in zero-sum games, where one player’s loss is the other player’s gain. Theoretically, this search algorithm is based on von Neumann’s minimax theorem which states that in these types of games there is always a set of strategies which leads to both players gaining the same value and that seeing as this is the best possible value one can expect to gain, one should employ this set of strategies (Kulenovic, 2008).

Description

The first step is to give each node a value in terms of utility for player 1. These values are derived from the values of the terminal nodes, which each represent an end of the game. Each level of the tree alternates between player 1’s move, who is trying to maximize her score, and player 2’s move, who is trying to minimize player 1's score in order to undermine her success. If the level above the terminal nodes represents player 2’s possible moves, then the value of the nodes will be the lowest value among those of their children, the minimum. On the other hand, if this level represents the possible moves for player 1, the value of its nodes will be the highest value among those of their children. Finally, once all the nodes have been assigned values, it is decision time for player 1 who just picks the move which will lead to the highest value (Russell & Norvig, 1995). Figure 1 illustrates this process.

,

Figure 1 : Assigning a value to the nodes and deciding the best move.

Pseudocode

This pseudocode is adapted from a version presented by Russell and Norvig (1995).

function minimaxDecision (game)
	for each possible move in game
		moveValue = minimaxValue(state, game)

	return move with highest value

function minimaxValue (state, game)
	if terminal node
		return utility

	if player 1's turn
		return highest value of children

	if player 2's turn
		return lowest value of children

Complications, Shortcomings and Future Directions

One shortcoming of this search is that it assumes that the opponent will act in such a way that he will effectively minimize your gains and maximize his own. However, this will not hold if your opponent is irrational, a beginner or a human who can be mistaken. In some cases, it may be best to gamble and hope that your opponent will not notice a subtle countermove (Moore & Knuth, 1975).

Moreover, representing all the possible moves for simple games like tic tac toe is not so difficult but with games like chess, it becomes computationally expensive to represent them all. Therefore, programmers often rely on further algorithms to narrow the search, such as alpha-beta pruning (Moore & Knuth, 1975). This consists of the stopping the calculation of the utility of one node when it is determined that there is no way its value could be higher than that of an adjacent node. For an alternative method called min/max approximation, see Rivest (1988).

Another way of cutting down the search space is to only go to a certain depth, treat the moves at that level as makeshift terminal nodes and determine their values using heuristics. Still, this is problematic in cases where long term planning is necessary (Sadikov & Bratko, 2006). However, this approach can be made more viable by looking for stable stages within a game and using these as intermediate terminal nodes (Scheucher & Kaindl, 1989). Despite these techniques, there is a debate as to whether using a minimax search is actually effective in such complex cases (Sadikov et al., 2005).

Finally, this section only discusses games in which the next state is solely determined by the moves of the players involved. The final frontier of the minimax search are games which involve chance, such as backgammon and poker (Hauk et al., 2006).

References

• Hauk, T., Buro, M., & Schaeffer, J. (2006). Rediscovering *-Minimax Search. In Computers and Games (pp. 35-50). Berlin: Springer-Verlag.
• Knuth, D. E., & Moore, R. W. (1975). An Analysis of Alpha-Beta Priming. Artificial Intelligence , 6 (4), 293-326.
• Kulenovic, M. R. (2008). Game Theory . Retrieved March 8, 2009, from University of Rhode Island Department of Mathematics: http://hypatia.math.uri.edu/~kulenm/mth381pr/GAMETH/gametheory.html
• Muller, M. (2001). Global and Local Game Tree Search. Information Sciences , 135, 187-206.
• Rivest, R. L. (1988). Game Tree Searching by Min/Max Approximation. Artificial Intelligence , 34, 77-96.
• Russell, S. J., & Norvig, P. (1995). Artificial Intelligence: A modern approach . Upper Saddle River, New Jersey: Prentice-Hall.
• Sadikov, A., & Bratko, I. (2006). Learning long-term chess strategies from databases. Machine Learning , 63, 329–340.
• Sadikov, A., Bratko, I., & Kononenko, I. (2005). Bias and pathology in minimax search. Theoretical Computer Science , 349, 268 – 281.
• Scheucher, A., & Kaindl, H. (1989). The reason for the benefits of minimax search. Proceedings IJCAI-89 , 322–327.