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

We do not need to evaluate each node completely; for some nodes, a refu-
tation suffices and some loops can terminate early. Specifically, when the
human player evaluates a position, such as C 2 , a refutation, if found, is just as
good as the absolute best move. The same logic applies to the computer. At
any point in the search, alpha is the value that the human player has to refute,
and beta is the value that the computer has to refute. When a search is done on
the human player's side, any move less than alpha is equivalent to alpha ; when
a search is done on the computer side, any move greater than beta is equiva-
lent to beta . This strategy of reducing the number of positions evaluated in a
minimax search is commonly called alpha-beta pruning.
As Figure 10.11 shows, alpha-beta pruning requires only a few changes
to chooseMove . Both alpha and beta are passed as additional parameters. Ini-
tially, chooseMove is started with alpha and beta representing HUMAN_WIN and
COMPUTER_WIN , respectively. Lines 17 and 21 reflect a change in the initializa-
tion of value . The move evaluation is only slightly more complex than origi-
nally shown in Figure 7.29. The recursive call at line 30 includes the
parameters alpha and beta , which are adjusted at line 37 or 39 if needed. The
only other change is at line 42, which provides for an immediate return when
a refutation is found.

Alpha-beta prun-
ing is used to
reduce the number
of positions evalu-
ated in a minimax
search. Alpha is the
value that the
human player has
to refute, and beta
is the value that the
computer has to
refute.

To take full advantage of alpha-beta pruning, game programs usually try
to apply heuristics to place the best moves early in the search. This approach
results in even more pruning than we would expect from a random search of
positions. In practice, alpha-beta pruning limits the searching to
nodes, where N is the number of nodes that would be examined without
alpha-beta pruning, resulting in a huge savings. The Tic-Tac-Toe example is
not ideal because there are so many identical values. Even so, the initial
search is reduced to roughly 18,000 positions.

Alpha-beta pruning
works best when it
finds refutations
early.

ON ( )

10.2.2 transposition tables

Another commonly employed practice is to use a table to keep track of all
positions that have been evaluated. For instance, in the course of searching for
the first move, the program will examine the positions shown in Figure 10.12.
If the values of the positions are saved, the second occurrence of a position
need not be recomputed; it essentially becomes a terminal position. The data
structure that records and stores previously evaluated positions is called a
transposition table; it is implemented as a map of positions to values. 1

A transposition
table stores previ-
ously evaluated
positions.

1. We discussed this generic technique, which avoids repeated recursive calls by storing values
in a table, in a different context in Section 7.6. This technique is also known as memoizing .
The term transposition table is slightly misleading because fancier implementations of this
technique recognize and avoid searching not only exactly identical positions, but also sym-
metrically identical positions.