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

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 Position thisPosition = new Position( board );
9 int tableDepth = 5; // Max depth placed in Trans. table
10 int bestRow = 0;
11 int bestColumn = 0;
12 int value;
13
14 if( ( simpleEval = positionValue( ) ) != UNCLEAR )
15 return new Best( simpleEval );
16
17 if( depth == 0 )
18 transpositions.clear( );
19 else if( depth >= 3 && depth <= tableDepth )
20 {
21 Integer lookupVal = transpositions.get( thisPosition );
22 if( lookupVal != null )
23 return new Best( lookupVal );
24 }
25
26 if( side == COMPUTER )
27 {
28 opp = HUMAN; value = alpha;
29 }
30 else
31 {
32 opp = COMPUTER; value = beta;
33 }

figure 10.15
The Tic-Tac-Toe algorithm with alpha-beta pruning and transposition table (part 1)

evaluation function measures such variables as the relative amount and
strength of pieces and other positional factors.

Computers are especially adept at playing moves involving deep combi-
nations that result in exchanges of material. The reason is that the strength of
pieces is easily evaluated. However, extending the search depth merely one
level requires an increase in processing speed by a factor of about 6 (because
the number of positions increases by about a factor of 36). Each extra level of
search greatly enhances the ability of the program, up to a certain limit
(which appears to have been reached by the best programs). On the other

The best computer
chess programs
play at grandmaster
level.