Information Technology Reference
In-Depth Information
Figure 10.3.
An example game tree
Max to play =
Min to play =
level 0
move 1
move 2
W
means Max wins.
L
means Max loses.
level 1
level 2
WWWL
W
WW LL
W
W
L
level 3
W
L
W
L
L
L
level 4
Starting from the very bottom of the tree, the labeling proceeds as follows:
If it is Max's turn to play at a node,
-
the node is labeled
W
(Max wins) if there is at least one move from there to a
state labeled
W
;
-
the node is labeled
L
(Min wins) if every move is to a state labeled
L
.
If it is Min's turn to play at a node,
-
the node is labeled
L
(Min wins) if there is at least one move from there to a
state labeled
L
;
-
the node is labeled
W
(Max wins) if every move is to a state labeled
W
.
The intuition here is that if it is Max's turn to play, and he has a move that takes
him to a state where he wins, then this is a
winning state
even if there are many other
moves that would take him to a loss.
For example, consider the rightmost node at level 2 in figure 10.3, where it is Max's
turn to play. In this state, Max has three legal moves available to him: one leading to
a win and two leading to a loss. Max can therefore win from this state by choosing
the leftmost node, and so this state (at level 2) is labeled
W
.
The reasoning for Min is analogous. Consider the left node at level 3 in figure 10.3,
where it is Min's turn to play. She has three legal moves available, two leading to
Max's winning and the middle one leading to her winning. This node is labeled
