Information Technology Reference
In-Depth Information
10.1.1 How a game can be defined
It is the fact that one player does not control the moves of the other player that makes
games different from planning. Nonetheless, there are some clear similarities. A game
(whether very complex like chess or very simple like tic-tac-toe) can be characterized
by the following:
There are two
players
. One of them moves first.
There is a space of
states
in the game. One of them is the
initial state
of the game.
There is also a
final state
of the game, where the game is over and one of the two
players is the winner (or there is a tie).
In any state that is not a final state of the game, there is a set of
legal moves
, that
go from one game state to another. Throughout the game, players take turns
choosing a move that is legal in the current state.
For any given game, the
rules of the game
characterize it in these terms. Note that the
rules of the game always tell how to play the game, but they do not tell how to play
it
well
(see section 10.2).
In the previous chapter, three predicates were used to characterize any planning
problem in Prolog:
initial_state
,
goal_state
, and
legal_move
. It will be similar
for games except that there are four predicates:
player(
player
)
. This says that
player
is one of the two players in the game.
initial_state(
state
,
player
)
.
This says that the game starts in
state
and that
player
moves first.
game_over(
state
,
player
,
winner
)
. This says that when it is the turn of
player
in
state
, then the game is over and
winner
wins. The
winner
is either one of the two
players, or the special constant
neither
when there is a tie.
legal_move(
state
1
,
player
,
move
,
state
2
)
. This says that when it is the turn of
player
in
state
1
, then
move
is legal and the game goes to
state
2
, where it will be the turn
of the other player.
These four predicates are used to define each of the games considered in this chapter.
10.1.2 A first example: Race to 21
Race to 21 is an even simpler game than tic-tac-toe:
There are 21 chips on a table. Players take turns removing either one or two
chips. The player removing the last chip wins.
