Information Technology Reference
In-Depth Information
Figure 10.5.
A general game player
gameplayer.pl
% This general game player needs these predicates to be defined:
% - player(Player)
% - game_over(State,Player,Winner)
% - legal_move(BeforeState,Player,Move,AfterState)
% label(S,P,W): state S with player P to move is labeled winner W.
label(S,P,W) :- game_over(S,P,W).
label(S,P,P) :- win_move(S,P,_).
label(S,P,neither) :- \+ win_move(S,P,_), tie_move(S,P,_).
label(S,P,Q) :- opp(P,Q), \+ tie_move(S,P,_), \+ game_over(S,P,_).
% win_move(S,P,M): P can win by making move M.
win_move(S,P,M) :- \+ game_over(S,P,_), opp(P,Q),
legal_move(S,P,M,New), label(New,Q,P).
% tie_move(S,P,M): P can avoid losing by making move M.
tie_move(S,P,M) :- \+ game_over(S,P,_), opp(P,Q),
legal_move(S,P,M,New), \+ label(New,Q,Q).
opp(P,Q) :- player(P), player(Q), \+ P=Q.
1.
If the game is over in state
S
, then label the node with the winner (
P
,
Q
,or
neither
) according to the rules of the game.
2.
Otherwise, label the node with
P
as the winner if there is a legal move from
S
to
a state
S
where
S
is labeled with
P
as the winner. This move is called a
winning
move
for
P
in game state
S
.
3.
Otherwise, label the node with
neither
as the winner if there is a legal move
from
S
to a state
S
where
S
is not labeled with
Q
as the winner. This move is
called a
nonlosing move
for
P
in game state
S
.
4.
Otherwise, label the node with
Q
as the winner.
Except for condition 3 (having to do with ties), this summarizes what was done
in the tree for Max and Min in figure 10.4. Regarding a tie, a node is labeled with
neither
when a player has no winning move but has a move to a state that is not
labeled with the opponent's winning.
These principles can be encoded in a Prolog program, shown in figure 10.5. This
defines a
general
game player. As with planning, for each specific game, a program-
mer will need to provide clauses that define the
player
,
game_over
, and
legal_move
predicates for that game. (The
initial_state
predicate is not used here.) Once these
are provided, the predicate
win_move
can be used to see if there is a winning move
from a state; and
tie_move
, to see if there is a move that avoids losing.