Game Development Reference

In-Depth Information

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,