At the forefront of Artificial Intelligence

Minimax Trees

This essay is a little advancement over the Simple Board Game AI essay. In that essay, we looked at immediate moves - how the computer would deal with the current situation and make a move accordingly. Now, what happens if we would like the computer to strategize a little a look ahead. This is where minimax trees come in handy.

Max

Imagine a simple game that only has three moves, one move results in a win, another a draw, and finally a loss. Therefore, we want to assess each node and figure what the outcome will be. Let us extend our game to one that allows you to make three moves per go, and only takes two goes to win. Therefore, we will want to look ahead to find out which move combination works for us. We can generate a game tree of all the possible moves:

You can see how there are 9 final possible moves. Imagine that N11 is the winning situation, therefore our first move will have to be N4. How can we figure this out algorithmically? Let us assign values to a win, draw and loss. A win will be 1, a draw 0 and a loss -1. Say that N11 is the only winner, and the rest are drawing situations. So, what we'll want to do is evaluate the tree from the bottom-up propagating the maximum value for the nodes upwards. Therefore, for the N5-N7 group, 0 is the highest so this is applied to N2. N8-N10 also has 0 as the highest, which is taken on by N3. The N11-N13 group has 1 as the highest. The program knows to choose N4.

In our example, since the tree is only two layers deep this seems rather trivial. But imagine a tree 10 layers keep, this method would allow you to simply calculate which moves would lead to a winning situation. Most of you will already notice a large fault in this - trees this large are incredibly expensive in both memory and computational terms. A 10-layer tree that branches three times for each node would have 59,049 nodes. This is relatively simple - a Tictactoe tree would have 362,880 (9!) nodes.

Therefore, we have to cut down the depth of our tree. This gives us a problem, though - if we limit the depth we are not guarenteed a winning scenario as one of the nodes. This is where the clever programming has to come in. You must create some sort of evaluation function that can assess how close to a winning situation the board is. Since the nodes are not so clear-cut (win, draw, loss) a more complicated numbering system has to be used. The system is completely dependent on the programmer and the board game in question.

This is only half the problem, though, because we have not yet factored in an opponent player.

Min and Max

Very few board games are one player, so how can we add this into our tree? Think about it, when we are playing for ourselves we are attempting to maximize our score, so our opponent will want to minimize our score. Let us look at a game tree - this one though is limited to a depth of 2. Here is our game tree with evaluations assigned to the final nodes:

Now, the assigned values are for boards representing our opponents choice of boards. N1 stands for the current board, N2-N4 are our three possible moves and N5-N13 are the opponents possible follow-up moves. Since our opponent will try to minimize our winning possibility^*, therefore will calculate the minimum value for each node and assign it to the parent. N2 will equal 0, N3 will equal 3, N4 will equal 2. In making a choice for our best possible move, we look at the maximum of these values - which is 3 (N3).

Minimax Conclusion

In conclusion, let me put the algorithm into a stepped form:

Generate the game tree to depth d.
The final nodes should have a value assigned to them, denoting how close to a winning scenario they are. The higher the value, the closer to a winning scenario.
Then minimize the scores if calculating for the opponent, and maximize them for the player. Propogate the scores upward through the tree until the computer can make a decision as to the best "branch" of gameplay to explore.

The minimax algorithm is surprisingly simple, but its downfall lies in the huge amount of memory and computation it can take to achieve decent results. There is a lot of research into minimizing the expansion of the game tree. The most popular pruning method is alpha-beta pruning which will be covered at a later date. The bottom line is, try to minimize the number of branches for each node and keep the depth at a reasonable level. Remember the number of nodes requires is equal to b^d, where b is the number of branches per node and d is the depth of the tree.

^* This is one of the pitfalls of the minimax algorithm. It assumes that our opponent is completely defensive.

Submitted: 23/08/2001

Article Toolbar

BibTeX entry