%--------------------------------------------------------------
% Searching game trees (minimax and alpha-beta pruning)        
%# (C) 1998 Zdravko Markov (adaptation from Ivan Bratko's book) 
% The game tree is represented by the following predicates:    
%   moves(Pos,ListOfSuccessorPositions) - possible moves       
%   utility(Pos,Utility) - utility function value of terminals 
%   min(Position) - MIN is to move at Positions                
%   max(Position) - MAX is to move at Positions                
%--------------------------------------------------------------
%--------------------------------------------------------------
% Minimax search                                               
%   call: minimax(+Pos,-BestSuccessor,-Utility).               
%--------------------------------------------------------------

new_player(V,N) :-
    N is -1*V.

minimax(Pos,Succ,Utility,V,Limit) :-
    Limit \= 0, !, 
    Limit1 is Limit-1,
    new_player(V,N),
    moves(Pos,SuccList,N), !,           % not a terminal position
    best_move(SuccList,Succ,Utility,N,Limit1).
minimax(Pos,_,Utility,_,_) :-             % a terminal position
    utility(Pos,Utility).             % an explicit utility

best_move([P],P,V,N,Limit) :-
    minimax(P,_,V,N,Limit), !.
best_move([P1|Ps],Succ,Val,N,Limit) :-
    minimax(P1,_,V1,N,Limit),
    best_move(Ps,P2,V2,N,Limit),
    better(P1,V1,P2,V2,Succ,Val,N).

better(P1,V1,_,V2,P1,V1,N) :-
    max(N),
    V1>V2, !.
better(P1,V1,_,V2,P1,V1,N) :-
    min(N),
    V1<V2, !.
better(_,_,P2,V2,P2,V2,_).

%--------------------------------------------------------------
%   Alpha-Beta search                                          
%   call: alphabeta(+Pos,+Alpha,+Beta,-BestSuccessor,-Util).   
%--------------------------------------------------------------
alphabeta(Pos,Alpha,Beta,Succ,Util,V) :-
    new_player(V,N),
    moves(Pos,SuccList,N), !,
    next_move(SuccList,Alpha,Beta,Succ,Util,N).
alphabeta(Pos,_,_,_,Util,_) :- 
    utility(Pos,Util).

next_move([P|Ps],Alpha,Beta,Next,Eval,N) :- 
    alphabeta(P,Alpha,Beta,_,V,N),
    good_move(Ps,Alpha,Beta,P,V,Next,Eval,N).

good_move([],_,_,P,V,P,V,_) :- !.
good_move(_,_,Beta,P,V,P,V,N) :-
    min(N),
    V>Beta, !.
good_move(_,Alpha,_,P,V,P,V,N) :-
    max(N),
    V<Alpha, !.
good_move(Ps,Alpha,Beta,P,V,GoodP,GoodV,N) :-
    newbounds(Alpha,Beta,P,V,NewAlpha,NewBeta,N),
    next_move(Ps,NewAlpha,NewBeta,P1,V1,N),
    better(P,V,P1,V1,GoodP,GoodV,N).

newbounds(Alpha,Beta,P,V,V,Beta,_) :- 
    min(P),
    V>Alpha, !.
newbounds(Alpha,Beta,P,V,Alpha,V,_) :-
    max(P),
    V<Beta, !.
newbounds(Alpha,Beta,_,_,Alpha,Beta,_).