Information Technology Reference
In-Depth Information
Figure 10.15.
An example numeric game tree
move 1
move 2
5
-5
8
7
-1
-2
9
1
-12
-10
2
3
−
number (say,
999
) indicates that Min wins the game. The number
0
is used when the
game ends in a tie. (So big numbers are good for Max, and small numbers are good
for Min.)
It is then a simple process to assign a numeric value to
every node
on the tree.
Starting from the bottom of the tree, proceed as follows:
If it is Max's turn to play, label the node with the
maximum
of the labels of the
children of the node.
If it is Min's turn to play, label the node with the
minimum
of the labels of the
children of the node.
This labeling duplicates what was done previously with
W
and
L
(and also handles
ties properly): a node labeled
999
is a winning position for Max; a node labeled
−
999
is a winning position for Min; and a
0
is neither. Overall because of the minimums
and maximums, this numeric process is called
minimax
. (This finally also explains
why Max and Min have the names they do.)
What makes this process interesting is that a numeric game tree need not go all the
way to the end of the game but can stop at a certain depth, after which an
estimate
is
made about the value of the state. A bigger number means that the state is estimated
to be better for Max; a smaller number means that the state is estimated to be better
for Min. (How to arrive at these estimates is discussed later.)
A tree of this type is shown in figure 10.15. The tree stops at depth 3, and estimated
values are provided for all the leaf nodes. For example, according to this estimate, the
leftmost state at level 3 (with a value of 8) is estimated to be slightly better for Max
