Information Technology Reference
In-Depth Information
Figure 10.18.
Cutoffs in a game tree
...
...
A
A
...
E
B
C
...
...
C
4
B
E
5
D
...
D
...
3
...
8
cutoff
cutoff
...
val_move(S,max,10000,M,0)
asks for a move
M
for player Max in state
S
that will
guarantee at least a tie. When the depth is smaller, and estimates of values have to be
used (as provided by the
estval
predicate), then the guarantees are only relative to
those estimated values.
10.3.2 Alpha and beta cutoffs
Minimax with estimates allows making decisions about how to move in a game with-
out searching all the way to the end of the game. But because the search should be
as deep as possible for the sake of accuracy, there may still be a very large number of
nodes to consider in a game tree. However, sometimes it is not necessary to look at
all those nodes to make the final decision.
Consider the portion of a game tree depicted on the left side in figure 10.18. The
goal is to assign a value to the node labeled
A
, where it is Max's turn to play. To do
this, values must be assigned to the nodes below
A
, where it is Min's turn to play. (Max
will eventually chose the maximum of the values for
B
,
C
,
E
, and any other children
of
A
.) Proceeding from left to right as usual, it has already been determined that the
value of the node labeled
B
is 5. To get a value for the next node,
C
, the values of its
children must be found. (Min will eventually chose the minimum of these values.) As
part of this process, it has just been determined that the value of node
D
is 3.
Before continuing with the remaining children of
C
, observe the following. The
value assigned to node
C
cannot be larger than 3, since Min chooses a minimum.
However, whatever the value of
C
is, it will not change the value for
A
, since Max
chooses a maximum, and the value of
B
is already larger than 3. The conclusion is
