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

1 // Find optimal move
2 private Best chooseMove( int side, int alpha, int beta, int depth )
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 = alpha;
18 }
19 else
20 {
21 opp = COMPUTER; value = beta;
22 }
23
24 Outer:
25 for( int row = 0; row < 3; row++ )
26 for( int column = 0; column < 3; column++ )
27 if( squareIsEmpty( row, column ) )
28 {
29 place( row, column, side );
30 reply = chooseMove( opp, alpha, beta, depth + 1 );
31 place( row, column, EMPTY );
32
33 if( side == COMPUTER && reply.val > value ||
34 side == HUMAN && reply.val < value )
35 {
36 if( side == COMPUTER )
37 alpha = value = reply.val;
38 else
39 beta = value = reply.val;
40
41 bestRow = row; bestColumn = column;
42 if( alpha >= beta )
43 break Outer; // Refutation
44 }
45 }
46
47 return new Best( value, bestRow, bestColumn );
48 }
figure 10.11
The chooseMove routine for computing an optimal Tic-Tac-Toe move, using alpha-beta pruning