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.

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.

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