Game Development Reference
Fox and Hounds , the game we will use for our project, does provide insights into
more complex evaluation functions. We will return in depth to evaluation
functions when we take up the project.
Our reasonably simple question started out, ''If I move here.'' Think of Tic-Tac-
Toe as a tree. From the root of the tree, there are nine branches, one for each
possible first move. Each of those branches has eight sub-branches, corre-
sponding to the possible second moves that could follow a first move. This is the
top of the search space that our AI will look through in search of victory.
If we count the number of possible game boards in the first three levels, there is one
empty game board, nine game boards with one move, and 72 boards with two
moves on them. As it turns out, while there are nine squares available for a first
move, there are only three different kinds of first moves: the center, any corner,
and the middle of an outer row or column. You can make your favorite corner into
any other corner simply by viewing the game from another angle—you do not
need tomove any marks! From those three first moves, there are 12 kinds of second
move. This is shown in Figure 6.1, from Wikimedia Commons [Wikimedia04].
From the figure, we see that there are 12 kinds of boards after two moves, while
our na¨ve method of look-ahead calls for 72 boards. We can get rid of ˙ ¨ of the
expected workload if our code is smart enough to realize that most opening
moves are the same as some other opening moves, and only the unique ones need
to be evaluated. This is called pruning , and the numbers show how effective it can
be at fighting computational complexity. The idea with pruning is that the
numbers that we multiply together to measure complexity are all smaller
numbers than before. Our computational ''grenade'' either takes longer to
explode or becomes a less problematic firecracker.
In the Tic-Tac-Toe example, there was no loss of information after pruning.
There are other kinds of pruning that may cause loss of information, however.
One of the most common kinds of pruning is to limit the depth of the look-
ahead. Tic-Tac-Toe has barely any middle ground where setting a depth limit
makes sense. It takes five moves of look-ahead at the opening move to see the first
possible victory. After four or more moves have been made, there are five or
fewer moves left in the game. In other games, the AI programmer sets the look-
ahead ''high enough to stay out of trouble, low enough to run quickly.'' If that
limit is too low, the player will observe something like, ''Now he sees it coming,