Information Technology Reference
In-Depth Information
10.2.3 Playing Race to 21
To see how the general game-playing program works with a specific game like Race
to 21, load both programs into Prolog. To understand how winning moves are found,
it is best to start by looking at states very near to the end of a game. For example, in
Race to 21, it is clear that if there are only one or two chips left, then the player whose
turn it is to play has a winning move:
?- win_move(1,_,M).
M=1
?- win_move(2,_,M).
M=2
Here the move leads directly to a final state where the player is the winner (because
there are no chips left). It is also evident that if there are three chips left, then there is
no winning move:
?- win_move(3,_,M).
No
This is because after any legal move, the game is in a state that is a winner for the
opponent. So 3 is a not winning position for the player who has to play. If there are
four or five chips left, then there
is
a winning move:
?- win_move(5,_,M).
M=2
?- win_move(4,_,M).
M=1
−
=
The reason that 2 is a winning move for a player with five chips left is that
5
3
is not a winning position for the opponent. The case with four chips is similar. What
about six chips?
?- win_move(6,max,M).
No
2
The reason Max does not win with six chips is the following. If he takes one chip,
then there are five left for Min, and this would be a winning position (for Min); if he
takes two chips, then there would be four chips left, and this, too, wins for Min. So
there is nothing Max can do with six chips to guarantee a win.
Similar reasoning would show that 9 is also not a winning position, nor is 12 or 15.
In general, for Race to 21, a player cannot guarantee a win if the number of chips left
