Game Development Reference
In-Depth Information
When the hounds are forced to break their line, they use the simple heuristic of
picking the move that results in the longest path to freedom for the fox. This gives
the hounds the time they need to reform their line and close the hole before the
fox escapes. It is clear that having more time to correct a worrisome situation is
better than having less time.
Once the line is broken, good hounds' moves are ones that force the fox behind a
newly reformed line. They must do this in order to win. As we will see later, the
sooner they reform the line the better.
A reasonable heuristic for the fox is to head directly for the nearest hole in the line
when the line is broken. We will see later that this heuristic is imperfect. It is clear
circumstances the fox should wait and not head directly for the nearest gap.
Collectively, we can call these the line heuristics . A related heuristic is that when
the hounds have more than one move that keeps their line unbroken, the move
that hems the fox in the most is the best. A less obvious heuristic is that if the fox
ever makes it to any square that no hound can make it to, the fox has gotten past
the hounds and wins. A final pair of heuristics is that we can safely limit the look-
ahead depth to five fox moves or six hounds' moves. The project will use all of
these heuristics. We will examine the impact they have on complexity.
Heuristics greatly help the evaluation function. Figure 6.3 shows the fox forcing
the hounds to break their line. That move is not sufficient to win, but it is better
than any other possible move the fox can make that does not break the line. The
heuristics can also help prune the search space. The hounds have at most eight
moves to pick from. If any of those moves keeps the fox behind an intact wall,
then there is no need for the hounds to do any look-ahead. They still might need
to decide between two such moves, but no look-ahead is called for.
In the very first paragraph of this chapter we posed the simple question, ''If I
move here, and then each of us takes our best moves in turn, will I win in the
end?'' Now we look at the complexity of '' . . . takes our best moves in turn.'' The
hounds cannot take more than 28 total moves because each of the four hounds
can only move seven times each before it hits the back wall. That yields 28 moves
by the hounds. Since the fox moves first, such a game would require a matching
28 more moves from the fox. A fox in the middle of the board with nothing