Information Technology Reference
In-Depth Information
Figure 10.17.
A minimax procedure in Prolog
minimax.pl
% Computing the values of moves for two players, Max and Min.
% The game-dependent predicate estval estimates values of states.
% The search of the game tree is limited to a depth given by D.
% can_get(S,P,D,V): P can get a value of V or better in state S.
can_get(S,max,_,V) :- game_over(S,max,W), winval(W,V1), V1 >= V.
can_get(S,min,_,V) :- game_over(S,min,W), winval(W,V1), V1 =< V.
can_get(S,max,0,V) :- \+ game_over(S,_,_), estval(S,max,E), E >= V.
can_get(S,min,0,V) :- \+ game_over(S,_,_), estval(S,min,E), E =< V.
can_get(S,P,D,V) :- \+ game_over(S,_,_), val_move(S,P,D,_,V).
% val_move(S,P,D,M,V): P can get a value of V or better with move M.
val_move(S,max,D,M,V) :- D>0, D1 is D-1, V1 is V-1,
legal_move(S,max,M,S1), \+ can_get(S1,min,D1,V1).
val_move(S,min,D,M,V) :- D>0, D1 is D-1, V1 is V+1,
legal_move(S,min,M,S1), \+ can_get(S1,max,D1,V1).
winval(max,999).
% The value of a state where Max has won
winval(min,-999).
% The value of a state where Max has lost
winval(neither,0).
% The value of a state with a tie
These ideas lead to the Prolog program shown in figure 10.17. The labeling predi-
cate is called
can_get
. What
can_get
says for Max (and analogously for Min) is that
Max can get a value of
v
or better if one of the following conditions holds:
The game is over, and the final value
v
according to the winner (as specified by
the predicate
winval
) satisfies
v
≥
v
.
0, and the estimated value of the state
v
according to the game-
specific predicate
estval
satisfies
v
≥
The depth
d
=
v
.
The game is not over, and Max can get a value of
v
or better by making a move
(as specified by the predicate
val_move
).
The predicate
val_move
is used for choosing a move. What it says for Max (and
analogously for Min) is that assuming a depth
d
0
, Max can guarantee a value of
v
or better if there is a legal move to a state where Min cannot get a value of
v
>
−
1
or
−
better (for her) at depth
d
1
.
The predicate
val_move
replaces
win_move
and
tie_move
as a general game-playing
program. If the depth is very large, one will never hit the estimates, and so the
values will be completely determined by the winner at the end of the game. So the
query
val_move(S,max,10000,M,999)
asks for a move
M
for player Max in state
S
that will guarantee a win for Max, as
win_move(S,max,M)
did before. The query
