% Изкуствен интелект, Факултет по математика и информатика, СУ "св. Кл. Охридски"
%--------------------------------------------------------------%

%   Searching game trees (Sicstus Prolog)                      %

%   (adaptation from the 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                %

%--------------------------------------------------------------%



% Illustrative game tree (from the Bratko's book):



moves(a,[b,c]).

moves(b,[d,e]).

moves(c,[f,g]).

moves(d,[h,i]).

moves(e,[j,k]).

moves(f,[l,m]).

moves(g,[n,o]).



utility(P,V) :- 

    utility1(P,V), 

    write(utility-P=V), nl.



utility1(h,1).

utility1(i,4).

utility1(j,5).

utility1(k,6).

utility1(l,2).

utility1(m,1).

utility1(n,1).

utility1(o,1).



max(a).

max(d).

max(e).

max(f).

max(g).



min(b).

min(c).

min(h).

min(i).

min(j).

min(k).

min(l).

min(m).

min(n).

min(o).



%--------------------------------------------------------------%

%   Minimax search                                             %

%   call: minimax(+Pos,-BestSuccessor,-Utility).               %

%--------------------------------------------------------------%

minimax(Pos,Succ,Utility) :-

    moves(Pos,SuccList), !,           % not a terminal position

    best_move(SuccList,Succ,Utility,Pos).

minimax(Pos,_,Utility) :-             % a terminal position

    utility(Pos,Utility).             % an explicit utility



best_move([P],P,V,_) :-

    minimax(P,_,V), !.

best_move([P1|Ps],Succ,Val,Pos) :-

    minimax(P1,_,V1),

    best_move(Ps,P2,V2,Pos),

    better(P1,V1,P2,V2,Succ,Val,Pos).



better(P1,V1,_,V2,P1,V1,Pos) :-

    max(Pos),

    V1>V2, !.

better(P1,V1,_,V2,P1,V1,Pos) :-

    min(Pos),

    V1<V2, !.

better(_,_,P2,V2,P2,V2,_).



%--------------------------------------------------------------%

%   Alpha-Beta search                                          %

%   call: alphabeta(+Pos,+Alpha,+Beta,-BestSuccessor,-Util).   %

%--------------------------------------------------------------%

alphabeta(Pos,Alpha,Beta,Succ,Util) :-

    moves(Pos,SuccList), !,

    next_move(SuccList,Alpha,Beta,Succ,Util,Pos).

alphabeta(Pos,_,_,_,Util) :-

    utility(Pos,Util).



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



good_move([],Alpha,Beta,P,V,P,V,_) :-  !.

good_move(_,Alpha,Beta,P,V,P,V,_) :-
    min(P),

    V>Beta, !.

good_move(_,Alpha,Beta,P,V,P,V,_) :-
    
    max(P),

    V<Alpha, !.

good_move(Ps,Alpha,Beta,P,V,GoodP,GoodV,Pos) :-
    newbounds(Alpha,Beta,P,V,NewAlpha,NewBeta,Pos),
    
    next_move(Ps,NewAlpha,NewBeta,P1,V1,Pos),

    better(P,V,P1,V1,GoodP,GoodV,Pos).



newbounds(Alpha,Beta,P,V,V,Beta,Pos) :-

    max(Pos),

    V>Alpha, !.

newbounds(Alpha,Beta,P,V,Alpha,V,Pos) :-

    min(Pos),

    V<Beta, !.

newbounds(Alpha,Beta,_,_,Alpha,Beta,_).