Information Technology Reference
In-Depth Information
is divisible by 3. In particular, at the start of the game, Max, who moves first, cannot
guarantee a win:
?- win_move(21,max,M).
No
Once Max moves, by taking either one or two chips, Min will be able to make a
winning move by leaving Max with eighteen chips, that number being divisible by 3:
?- win_move(20,min,M).
M=2
?- win_move(19,min,M).
M=1
So the behavior of
win_move
makes clear that if Min plays perfectly, Max will lose.
Observe that this strategy of keeping the number of chips available to the opponent
divisible by 3 is not programmed anywhere. It emerges out of looking at the entire
game tree and labeling each of the nodes.
10.2.4 A second example: Tic-tac-toe
In some way tic-tac-toe is simpler than Race to 21, and playing it well is a challenge
only for very young players. But there are some interesting complications, including
the possibility of a tie.
The first decision in writing a tic-tac-toe program is how to represent the states and
moves. A state of the
3
×
3
board in tic-tac-toe is determined by the markers in each of
the nine possible positions. So a state can be represented by a list with nine elements,
[
p
1
,
p
2
,
p
3
,
p
4
,
p
5
,
p
6
,
p
7
,
p
8
,
p
9
]
,
where each
p
i
is
x
or
o
or another character indicating
blank, here a hyphen
-
(not to be confused the Prolog underscore,
_
). So the initial
state of a tic-tac-toe game is represented by the list
[-,-,-,-,-,-,-,-,-]
, where all
the positions are vacant. The game is over in any state where one of the following
conditions holds:
There are three
x
marks making a straight line (
x
wins).
There are three
o
marks making a straight line (
o
wins).
Every
p
i
in the state is either
x
or
o
(the board is full).
A move in tic-tac-toe involves a player's putting a mark in one of the vacant positions.
So a move is represented by a number
m
such that
1
≤
≤
m
9
, with the proviso that
in the current state,
p
m
=
-
.
