Information Technology Reference
In-Depth Information
Figure 10.4.
A labeled game tree
Max to play =
Min to play =
W
move 1
move 2
Max can force a win
by making move 2.
W
means Max wins.
L
means Max loses.
L
W
W
L
W
W
W
W
WWWL
W
WW LL
L
L
W
W
L
W
L
W
L
L
L
L
, since by choosing the middle option, Min can guarantee a win. At one level up
(level 2), Max has two choices, which are now both labeled
L
. So Max has no winning
move, and this node is labeled
L
.
Continuing in this way from the bottom up leads to the labeling shown in
figure 10.4. Then two things become clear:
The initial state is a winning state for Max.
The best move for Max to make is move 2, which can lead to a win no matter
what Min does (and despite all the
L
labels on the leaves).
So as with planning, the game player can decide on a good first move if the search is
carried ahead all the way to the goal. But unlike with planning, it is not sufficient to
find a single path to the goal; all the possible responses and counterresponses must
be considered all the way to the end.
10.2.2 A general game player
This process on one example game tree can be generalized to deal with any game,
including games with ties. Here is how to label a node for state
S
in a game between
two players
P
and
Q
,
assuming it is
P
's turn to play, as being either a winning position
for
P
, a winning position for
Q
,or
neither
: