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 :
 
Search WWH ::




Custom Search