Fun and games - Data Structures and Problem Solving Using Java - page 428

1 /**
2 * Routine to solve the word search puzzle.
3 * Performs checks in all eight directions.
4 * @return number of matches
5 */
6 public int solvePuzzle( )
7 {
8 int matches = 0;
9
10 for( int r = 0; r < rows; r++ )
11 for( int c = 0; c < columns; c++ )
12 for( int rd = -1; rd <= 1; rd++ )
13 for( int cd = -1; cd <= 1; cd++ )
14 if( rd != 0 || cd != 0 )
15 matches += solveDirection( r, c, rd, cd );
16
17 return matches;
18 }

figure 10.7
The solvePuzzle
routine for searching
in all directions from
all starting points

1. A terminal position can immediately be evaluated, so if the position is

terminal, return its value.

2. Otherwise, if it is the computer's turn to move, return the maximum

value of all positions reachable by making one move. The reachable
values are calculated recursively.

3. Otherwise, it is the human player's turn to move. Return the mini-

mum value of all positions reachable by making one move. The
reachable values are calculated recursively.

A refutation is a
countermove that
proves that a pro-
posed move is not
an improvement
over moves previ-
ously considered. If
we find a refutation,
we do not have to
examine any more
moves and the
recursive call can
return.

10.2.1 alpha-beta pruning

Although the minimax strategy gives an optimal Tic-Tac-Toe move, it per-
forms a lot of searching. Specifically, to choose the first move, it makes
roughly a half-million recursive calls. One reason for this large number of
calls is that the algorithm does more searching than necessary. Suppose that
the computer is considering five moves: C 1 , C 2 , C 3 , C 4 , and C 5 . Suppose also
that the recursive evaluation of C 1 reveals that C 1 forces a draw. Now C 2 is
evaluated. At this stage, we have a position from which it would be the human
player's turn to move. Suppose that in response to C 2 , the human player can
consider H 2 a , H 2 b , H 2 c , and H 2 d . Further, suppose that an evaluation of H 2 a
shows a forced draw. Automatically, C 2 is at best a draw and possibly even a
loss for the computer (because the human player is assumed to play opti-
mally). Because we need to improve on C 1 , we do not have to evaluate any of
H 2 b , H 2 c , and H 2 d . We say that H 2 a is a refutation, meaning that it proves that