Game Development Reference

In-Depth Information

black squares'' and the more complex ''fewer moves for the fox'' bites them, so we

will fix it.

This last evolutionary step is to change how the black squares were counted. If the

fox cannot get to an open black square, that square should not count in

the computation. Otherwise, the hounds could be distracted into making a move

that reduces the number of black squares but does not reduce the moves available

for the fox. Late in the game, most moves for the hounds reduce the total number

of black squares by one. All such moves are equally good, and if the line is intact,

the hounds do not look ahead. Look back at the sequence of boards shown in

Figure 6.6. After the fox has taken move 41, there are two moves for the hounds

that do not break their line. The first is to move the hound near the center of the

board down and to the left, directly toward the fox. The second is the one shown

as move 42 in Figure 6.6: The right-most hound moves down and to the right,

placing it on the last row. Using the na¨ve method of counting black squares, each

of these hounds' moves reduces the number of black squares by one, giving them

identical evaluation scores. The hounds do not have any moves that reduce the

number of black squares more than one; in fact all of their other moves break the

line. The two moves we are considering do not give identical results! The first

move we considered will bring victory to the hounds on their next move when

the fox retreats to one of three squares, each of which allows the hounds to trap it.

The second move, shown as move 42 in Figure 6.6, leads the fox to make move

43 as shown, which dooms the hounds.

A more sophisticated way of counting black squares prevents this from hap-

pening. We count a black square in the board evaluation score only if it has a

hound on it or if the fox can get to it. In Figure 6.6, there is a black square after

move 41 in the bottom row that becomes a white square with the number 2 after

move 42. In the na¨ve counting method, this square counted as a black square for

the evaluation score. It is the square that lead the hounds to make the ill-fated

move shown. Under the better method for counting black squares, this black

square does not count in the evaluation score because the fox cannot get to it.

The coloring algorithm colors it black after move 41, but it no longer counts in

the score. The two moves that do not break the line no longer have identical

scores; the hounds will now prefer the winning move of pushing the center

hound directly at the fox.

We will implement both ways of counting the number of black squares. The code

for this will be described in the next section when we deal with game state. The

ColorMe
routine will call either
NaiveBlackCount
or
BetterBlackCount
to get