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

34 Outer:
35 for( int row = 0; row < 3; row++ )
36 for( int column = 0; column < 3; column++ )
37 if( squareIsEmpty( row, column ) )
38 {
39 place( row, column, side );
40 reply = chooseMove( opp, alpha, beta, depth + 1 );
41 place( row, column, EMPTY );
42
43 if( side == COMPUTER && reply.val > value ||
44 side == HUMAN && reply.val < value )
45 {
46 if( side == COMPUTER )
47 alpha = value = reply.val;
48 else
49 beta = value = reply.val;
50
51 bestRow = row; bestColumn = column;
52 if( alpha >= beta )
53 break Outer; // Refutation
54 }
55 }
56
57 if( depth <= tableDepth )
58 transpositions.put( thisPosition, value );
59
60 return new Best( value, bestRow, bestColumn );
61 }
figure 10.16
The Tic-Tac-Toe algorithm with alpha-beta pruning and transposition table (part 2)
hand, computers generally are not as good at playing quiet positional games
in which more subtle evaluations and knowledge of the game is required.
However, this shortcoming is apparent only when the computer is playing
very strong opposition. The mass-marketed computer chess programs are
better than all but a small fraction of today's players.
In 1997, the computer program Deep Blue, using an enormous amount of
computational power (evaluating as many as 200 million moves per second),
was able to defeat the reigning world chess champion in a six-game match. Its
evaluation function, although top secret, is known to contain a large number
of factors, was aided by several chess grandmasters, and was the result of
years of experimentation. Writing the top computer chess program is certainly
not a trivial task.