Game Development Reference

In-Depth Information

numbers are multiplied together. Both show unacceptable growth rates; in

Tic-Tac-Toe
, it is managed by keeping the game small, where in
Fox and Hounds

we will manage it with heuristics.

Our project will prove just how much heuristics help. For example, when the

hounds have the fox behind an unbroken line and they have moves that keep the

line unbroken, the hounds have no need for look-ahead. In the aforementioned

calculations, each time this happens, the eight hounds' moves to explore in depth

become just one. In terms of a tree, only one of the eight branches will need to be

followed. Our heuristic allows us to prune away
˚
of the work
at each level in the

tree that the heuristic can be applied
. After the first move, when the fox is looking

to break the wall but is too far away to make contact with the hounds, the

complexity computation of three moves of na
¨
ve look-ahead without this

heuristic gives a sequence resembling the following:

...(4
8)
(4
8)
(4
8) . . .

The na
¨
ve method requires 32,768 combinations to be searched. With the heuristic,

the hounds know right away that their best move is the one that keeps the wall

intact. The three-move sequence becomes this:

...(4
1)
(4
1)
(4
1) . . .

With the heuristic applied, there are 64 combinations to be searched.

Careful examination of the board shows that in this part of the game, the hounds

have only seven moves available instead of eight. One hound in the line is either

against an edge or has another hound in front of it blocking one of its two moves.

Using seven instead of eight yields 21,952 combinations to be searched. This is

lower than 32,768, but pales when compared to the 64 combinations that the

heuristic yields. Good heuristics like this one can be applied at multiple levels in

the tree. There are other heuristics that can be applied to the game.

We can do something similar when the line is broken. The heuristic is that the fox

takes the shortest path to freedom. This reduces the number of moves evaluated

by the fox from four to just one. This allows us to eliminate
¯
˘
of the work at every

level of the tree while the hounds are looking ahead to reform their line. We

started with our na¨ve look-ahead sequence:

...(4
8)
(4
8)
(4
8) . . .