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

1 // Original import directives plus:
2 import java.util.Map;
3 import java.util.HashMap;
4
5 class TicTacToe
6 {
7 private Map<Position,Integer> transpositions
8 = new HashMap<Position,Integer>( );
9
10 public Best chooseMove( int side )
11 { return chooseMove( side, HUMAN_WIN, COMPUTER_WIN, 0 ); }
12
13 // Find optimal move
14 private Best chooseMove( int side, int alpha, int beta, int depth )
15 { /* Figures 10.15 and 10.16 */ }
16
17 ...
18 }

figure 10.14
Changes to the TicTacToe class to incorporate transposition table and alpha-beta pruning

the extra cost of maintaining the larger transposition table was not offset by
the fewer examined positions.

Lines 17 to 24 are new. If we are in the first call to chooseMove , we initial-
ize the transposition table. Otherwise, if we are at an appropriate depth, we
determine whether the current position has been evaluated; if it has, we return
its value. The code has two tricks. First, we can transpose only at depth 3 or
higher, as Figure 10.12 suggests. The only other difference is the addition of
lines 57 and 58. Immediately before the return, we store the value of the posi-
tion in the transposition table.
The use of the transposition table in this Tic-Tac-Toe algorithm removes
about half the positions from consideration, with only a slight cost for the
transposition table operations. The program's speed is almost doubled.

The code has a few
little tricks but
nothing major.

10.2.3 computer chess

In a complex game such as Chess or Go, it is infeasible to search all the way
to the terminal nodes: Some estimates claim that there are roughly 10 100 legal
chess positions, and all the tricks in the world will not bring it down to a man-
ageable level. In this case, we have to stop the search after a certain depth of
recursion is reached. The nodes at which the recursion is stopped become
terminal nodes. These terminal nodes are evaluated with a function that esti-
mates the value of the position. For instance, in a chess program, the

Terminal positions
cannot be searched
in computer chess.
In the best pro-
grams, consider-
able knowledge is
built into the evalu-
ation function.