Recursion - Data Structures and Problem Solving Using Java - page 337

1 // Find optimal move
2 public Best chooseMove( int side )
3 {
4 int opp; // The other side
5 Best reply; // Opponent's best reply
6 int dc; // Placeholder
7 int simpleEval; // Result of an immediate evaluation
8 int bestRow = 0;
9 int bestColumn = 0;
10 int value;
11
12 if( ( simpleEval = positionValue( ) ) != UNCLEAR )
13 return new Best( simpleEval );
14
15 if( side == COMPUTER )
16 {
17 opp = HUMAN; value = HUMAN_WIN;
18 }
19 else
20 {
21 opp = COMPUTER; value = COMPUTER_WIN;
22 }
23
24 for( int row = 0; row < 3; row++ )
25 for( int column = 0; column < 3; column++ )
26 if( squareIsEmpty( row, column ) )
27 {
28 place( row, column, side );
29 reply = chooseMove( opp );
30 place( row, column, EMPTY );
31
32 // Update if side gets better position
33 if( side == COMPUTER && reply.val > value
34 || side == HUMAN && reply.val < value )
35 {
36 value = reply.val;
37 bestRow = row; bestColumn = column;
38 }
39 }
40
41 return new Best( value, bestRow, bestColumn );
42 }

figure 7.29
A recursive routine for
finding an optimal Tic-
Tac-Toe move

3. “You gotta believe”: Always assume that the recursive call works.

4. Compound interest rule: Never duplicate work by solving the same

instance of a problem in separate recursive calls.