Information Technology Reference
In-Depth Information
Figure 10.13.
A Prolog program for Boxes
boxes.pl
player(max). player(min).
% This is the Boxes game.
square_lines(sq1,[1,3,4,6]).
% Lines for square 1
square_lines(sq2,[2,4,5,7]).
% Lines for square 2
square_lines(sq3,[6,8,9,10]).
% Lines for square 3
initial_state([],max).
% Initially no lines are drawn.
game_over(St,_,W) :-
% Winner W owns two squares.
owns(W,Sq1,St), owns(W,Sq2,St), \+ Sq1 = Sq2.
% Player P owns Sq if just drew last line or owned Sq before.
owns(P,Sq,[draw(P,L)|St]) :- last_avail_line(L,Sq,St).
owns(P,Sq,[_|St]) :- owns(P,Sq,St).
% Line L is available and is the last of square not yet drawn.
last_avail_line(L,Sq,St) :-
avail_line(L,Sq,St), \+ avail_line(_,Sq,[draw(_,L)|St]).
% Line L is from Sq and not yet drawn in state St.
avail_line(L,Sq,St) :-
square_lines(Sq,Ls), member(L,Ls), \+ member(draw(_,L),St).
% The legal moves
legal_move(St,P,[L],[draw(P,L)|St]) :-
% Draw a line and stop.
avail_line(L,_,St).
legal_move(St,P,[L|Rest],New) :-
% Draw a line and go on.
last_avail_line(L,_,St), legal_move([draw(P,L)|St],P,Rest,New).
predicate
available_line
says that a line is available for a square in a situation if
it is one of the lines for that square, and there is no previous draw action involving
that line in the situation. Finally, the last two clauses of the program describe when a
move is legal: either a list with a single line, or a list with more than one line, when a
last available line for a square was just drawn.
Figure 10.14 shows the Boxes game in action:
The first query asks if Max has a winning move from the configuration drawn
on the right-hand side. The answer is that Max can win by drawing line 3
(completing a square) and then drawing line 8 in the same move.
The second query asks a similar question for the configuration drawn there. In
this case, Max can win by drawing line 7, but at this point, although he has the
option of continuing with another line, he must not do so. Furthermore, this is
the only winning move.
