Information Technology Reference
In-Depth Information
Figure 10.21.
A numeric game tree
4.
One of the reasons the Prolog general game player presented in the file
gameplayer.pl
may be hard to follow is because of the possibility of a tie. Write
a simpler version of
label
and
win_move
(and any other predicate you need) for
games where there is always a winner. Show that your program works properly
on Race to 21.
5.
Consider the numeric game tree to depth 4 in figure 10.21.
a.
Determine the numeric values for all the nodes in the tree.
b.
Indicate on the tree where alpha and beta cutoffs would occur, assuming
that the tree is explored in the usual way, from left to right. Of the entire
tree, how many leaf nodes do not need to be examined by using alpha-beta
cutoffs?
6.
Consider the following game, called Wythoff's Nim, a variant of Race to 21:
When the game begins, there is a pile of green chips and a pile of red chips
on the table. Each player takes turns removing at least one chip from the
table, and the last player to take a chip wins. In a move, a player may take
any number of green chips, or any number of red chips, or exactly the same
number of green and red chips.
To encode this game in Prolog, a game state can be represented using a list of
two numbers
0
is
the number of red chips. The moves of the game can then be represented by one
of the following terms:
green
(
[
p
1
,
p
2
]
, where
p
1
≥
0
is the number of green chips, and
p
2
≥
m
)
, where 1
≤
m
≤
p
1
, when
m
green chips are to be removed
red
(
m
)
, where 1
≤
m
≤
p
2
, when
m
red chips are to be removed
