The Game Tree

A game tree is a model of all possible moves in a game, organized as a tree. For example, consider the tic tac toe board in Figure 10.8.

Figure 10.8: A tic tac toe board is played halfway. X has made two moves, and O has made one.

Now imagine that you are playing X and the computer is trying to play O. You have just made your second move. For the computer to decide where to play next, it must analyze each possible move. (There are nine possible moves for O right now.) If we draw every possible next move for O, we get something like Figure 10.9.

Figure 10.9: The tic tac toe boards are organized in a tree structure, with the given board as the root and each possible move as a child of the root.

Now let's take it one step further. For each of those nine possible moves, let's construct every possible next move of X. If we add each of these under the nine possible moves for O, our tree will be one level deeper and look like Figure 10.10.

Figure 10.10: Every possible next move for X is added to the tree. Note that only two lower branches are shown in this figure for space considerations.

At this point, you can see that some of the possible moves O can make next allow X to win the game. Those are obviously moves that O would not want to make. Some of the moves do not yet win for X, so those are worth considering further. We can continue to do this until all possible conclusions to the game have been reached.

In this way, all possible moves are considered and each is put into a node of the tree. The result is that we can use our tree to decide where O should play next. That's the general idea behind turn -based game AI.

As an example, I want to implement tic tac toe so that you can see a simple recursive solution to a turn-based game AI. However, before we break right into the example, we need to discuss one final topic: the minimax search.