Information Technology Reference
In-Depth Information
both
(
)
≤
≤
≤
≤
m
, where
1
m
p
1
and
1
m
p
2
, indicating that
m
green chips
and
m
red chips are to be removed
For example, starting in state
[
4, 2
]
, here are all of the states that can be reached
in one move:
[
3, 2
]
,
[
2, 2
]
,
[
1, 2
]
,
[
0, 2
]
,
[
4, 1
]
,
[
4, 0
]
,
[
3, 1
]
, and
[
2, 0
]
.
To generate legal moves for this game in Prolog,
it is useful to be able to
generate numbers between two bounds.
You may use the built-in predicate
(
)
≤
≤
between
x
,
y
,
z
, which holds when
x
z
y
, and which can generate a
z
given an
x
and
y
.
a.
Write Prolog clauses defining this game for two players, Max and Min.
The initial state is unspecified, so you need to write clauses for
player
,
game_over
, and
legal_move
(using
between
).
b.
Suppose the game is in state
, where it is Max's turn to play. Draw the
full game tree (with
W
and
L
at the leaves) starting at this state. Use the tree
to determine the best next move for Max. Explain your reasoning. Show that
your program selects this move.
[
]
3, 1
c.
Show by running your program that the best move, starting in state
[
4, 6
]
,is
to take one chip from each pile.
d.
Consider a sequence of game states defined by the following rule:
The
0
th element of the sequence is the state
[
]
0, 0
;
[
p
1
,
p
2
]
For any
i
, where
p
1
is the smallest number that does not appear in an earlier state of the
sequence, and where
p
2
=
>
0
, the
i
th element of the sequence is the state
p
1
+
i
.
Use your program to explore what happens if the initial state of a game is
one of the states in this sequence.
7.
Use exercise 6d to describe a winning strategy for Wythoff's Nim. Given an
arbitrary state of the game
[
p
1
,
p
2
]
, what is the best move to make?
8.
Look on the Internet to discover the strange connection bet
w
een winning strate-
gies for Wythoff's Nim and the
golden mean
, that is,
+
√
5
(
−
)
/2, the remarkable
1
number studied since the time of the ancient Greeks.
9.
The game player presented in the file
minimax.pl
can find a move to guarantee a
given numeric value, if one exists. However, it cannot find the
best
move to make,
since it does not compare the values produced by all possible moves. Write a
game player that does this.
Hint:
Use the built-in Prolog predicate
findall
to
produce a list of
all
the legal moves from some state.
