how2examples.com
Home - Introduction to Artificial Intelligence

Minimax

Game theory is a branch of applied mathematics that studies situations where participants, with different goals, make decisions that impact the other participants. Minimax is a decision making strategy that can be applied to two-player zero-sum games. A zero-sum game is a game where a positive outcome for one player will be equally negative for the other. This is typical of many two player games - for one player to win the other player must lose, while a draw is considered neither a positive or negative outcome for either player.

The minimax strategy attempts to minimise the negative cost for a worst case scenario. The basis for the minimax strategy is the assumption that the opposition will always choose the move that gives them the best chance of a positive outcome (i.e. maximises their chances of winning). The minimax strategy is effective because, in a zero-sum game, it is advantageous to minimise the opportunities an opponent has to maximise their chances of winning.

Minimax Algorithm

Minimax can be implemented using a recursive algorithm which traverses a game tree consisting of possible moves and their outcomes. The root node of the tree represents the current game state. Each branch from a node represents a possible move a player could make. Each child node represents the resulting game state of a possible move. The layers of the tree alternate between moves made by one player and moves made by their opponent.

Game states that represent completed games are called terminal states. A utility function is used to assign a numerical value to terminal states based on the rules of the game. If the terminal state represents a winning outcome for the player performing the search then it will be assigned a high value. If the terminal state represents a losing outcome for the player performing the search then it will be assigned a low value.

Starting with the terminal states, the values are propagated up the tree one level at a time. A node where the player performing the search would move next is assigned the highest possible value of its child nodes. A node where the opponent would move next is assigned the lowest possible value of its child nodes. Once the values have been propagated up the tree, the child nodes of the root node are evaluated and the node with the highest value is selected as the best move to make.

Minimax Tree for Noughts and Crosses (Tic-tac-toe)
Minimax Tree for Noughts and Crosses (Tic-tac-toe)
'X' to move next. Needs to take the bottom-left square to avoid defeat.
Assuming 'O' also plays optimally, the expected outcome is a draw.

For many games the large number of possible combinations of moves means it is not always feasible to search from an initial game state to every possible terminal state. Due to time and memory constraints an implementation may only be able to search to a maximum of a given depth. An evaluation function is required to judge the game states represented by the remaining unsearched nodes (the leaves of the game tree). Like the utility function used to judge terminal states, the evaluation function is specific to the rules of the game being played. While it is often straightforward to judge terminal states (as they normally represent clear winning or drawn outcomes), judging game states for uncompleted games can be more subjective.

Alpha-beta Pruning

As minimax progresses down each level of the search tree the number of nodes it needs to search can increase rapidly. As the number of nodes required to be searched increases so does the time and memory requirements. Alpha-beta pruning is a technique that reduces the number of nodes that need to be searched by ignoring branches that cannot affect the final decision. Alpha-beta pruning immediately stops evaluating a move when a possible outcome has been found that is worse than a previously evaluated move.

Interactive Example Of Minimax

Below is an example of how a computer can use the minimax algorithm to decide which moves to make in a two-player game. The game is noughts and crosses (also known as tic-tac-toe). Click in any of the free squares of the grid to place an 'X', the computer will respond by placing a 'O' in a remaining free square. Continue until either player wins or it is a draw. Below the grid is a representation of a minimax tree showing possible moves and their expected outcomes. Click on the 'Expand...' links to view the child nodes.

Click here to reset board

The implementation of the minimax algorithm used to implement the noughts and crosses logic contains a few game-specific features to improve efficiency. When evaluating each node in the game tree the following rules are used (in the order listed) to limit the number of child nodes that need to be searched:

  1. If the player has an option to complete a winning line then they will take it (so no other moves need to be considered).
  2. If the player has an option to block a winning move of their opponent then they will take it (so no other moves need to be considered).
  3. When a child node has been searched and been found to return a winning result for the player there is no need to evaluate the other child nodes (as none of the other child nodes could cause a better possible result).
  4. Where a child node results in a board that can be rotated to match the result of an already searched child node then there is no need for it to be searched. i.e. When determining the first move of the game there is no need to separately consider each of the four corners rather than just one.