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.
Complexity with the Line 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) . . .
Search Nedrilad ::

Custom Search