Game Development Reference
In-Depth Information
With the heuristic for the fox it becomes:
...(1 8) (1 8) (1 8) . . .
Instead of needing 32,768 combinations to search three turns, we now only need
to search 512.
Complexity with Depth-Limit Heuristics
We will allow the fox to look ahead at most five turns and the hounds to look
ahead at most six. These numbers come from experience tuning the AI; the fox
can always find a way to break the line in five fox moves or fewer if one exists.
Six hounds' moves are enough for them to reform their line if it is possible. These
make the complexity computations completely different. When the fox is looking
ahead, it is trying to break the line. This implies that the line is there, so the
hounds know their best move. So we get four fox moves times one hound's move
per turn, for five turns.
(4 1) (4 1) (4 1) (4 1) (4 1) = 1024
This is 1,024 moves, and it can be evaluated in a few seconds even with the
debugging output scrolling by. The hounds' computation is similar: eight moves
for six turns.
(1 8) (1 8) (1 8) (1 8) (1 8) (1 8) = 262,144
A quarter million moves might seem troubling, but without the heuristic, the
number would be 4,096 times larger—at just over a billion. Heuristics make
otherwise impossible look-ahead tasks possible.
Drawbacks to Heuristics
The danger with heuristics is when they fail. ''Usually right'' is not the same as
''always right.'' One of the heuristics that we will use in Fox and Hounds was not
always correct for all the given evaluation functions tested. That heuristic is that
the best move for the fox when the line is broken is to take the shortest path
toward freedom. We use that heuristic to prevent the fox from looking ahead
when the hounds are looking ahead; this improves performance considerably.
The hounds look ahead when the line is broken, as they look to pin the fox
behind a reformed line. The hounds, in their look-ahead, predict the fox's move
using the heuristic. The hounds are predicting their opponent's move, but the
prediction might not come true. As long as any move the fox might take puts
Search Nedrilad ::

Custom Search