Information Technology Reference
In-Depth Information
Figure 10.1.
A problem in tic-tac-toe
XO
Player
X
to play and win
after at most three moves
Zero-sum. This means that the players in the game are always in complete oppo-
sition: what is good for one player is bad for the other, and vice versa. This is
total war!
Chess and checkers both fit this description, and so do much simpler games like
Othello (Reversi) and tic-tac-toe.
This chapter has three sections. The first section explores how game problems of
this sort are similar to, and different from, the planning problems of chapter 9, and
how the rules of a game can be encoded in Prolog. The second section develops a gen-
eral game player in Prolog, analogous to the general planning program of chapter 9.
The third section considers how the thinking has to adapt for more complex games
like chess.
10.1 Games as problems
To see how playing a game is related to planning, consider the problem posed in
figure 10.1 for the well-known game of tic-tac-toe.
Here is an example of
faulty
reasoning
applied to this problem:
Player
X
can move to position 9 (bottom left). At this point, player
O
can move
to position 3 (top right), after which player
X
can move to position 5 (center),
thereby winning the game.
The reason this is faulty is clear. After player
X
moves to position 9, player
O
is free
to make any legal move. If instead of going to position 3, player
O
chooses to move
to position 5, then player
X
is no longer guaranteed a win. Instead, the game would
probably end in a tie. (Section 10.2.4 looks at the thinking behind tic-tac-toe in detail.)
