/* finin@Umbc.edu, 2001, 2006
 
   http://umbc.edu/~finin/

  a simple minimax algorithm for playing two person games.  To define
  the game, provide definitions for

   a state is like s(N,B) where N is the player number (e.g., 1,2) and
     B is the board position.
   player(N,Depth,Eval) -- Player N does lookahead to depth Depth and uses
     the static evaluation predicate Eval.  Eval/2 takes two arguments
     (+S,-V) and is true if state S has static value V.
   start(S) -- true if S is the initial game state.
   move(S1,S2) - true if there is a legal move from state S1 to S2.
   win(P,S) -- true if state S is a win for player P.
   draw(S) -- true of state S is a draw
   printBoard(S) -- prints the curent board

  We assume that a state is of the form s(P,B) where P is the player
  whose turn is next (1 or 2) and B represents the "board position".

*/


% mm(+N,+S1,-S2,-Value) does the minimax algorithm with a lookahead
% depth  of N and a static evaluation function Eval starting in state
% S1.  The best next move is the one which results in state S2 and the
% value backed up for this position is V.

% stop recursing if N=0, figure out which player is to move and get
% her static evaluation predicate

mm(0,Eval,S,S,Value) :- !, call(Eval,S,Value).

% stop recursing if if one of the players has won or if it's a draw.
mm(_,Eval,S,S,9999) :- win(1,S).
mm(_,Eval,S,S,-9999) :- win(2,S).
mm(_,_,S,S,0) :- draw(S).

mm(N,Eval,S1,S2,Value) :-
  N2 is N-1,
  % find all of the legal moves and their minimax values. 
  findall(V-S, (move(S1,S), mm(N2,Eval,S,_,V)), Moves),
  % sort them from lowest to highest.
  keysort(Moves,SortedMoves),
  % select which of SortedMoves is the best for this player
  selectMove(S,Eval,SortedMoves,S2,Value),
  !.		 

% selectMove(+State,+ListOfSortedMoves,-BestMove,-ValueOfBestMove) %
% selects the best move for the state, depending on which player's turn %
% it is (e.g., min or max).

% If there are no moves, just run the static evaluator on this state.
selectMove(S,Eval,[],S,Value) :- call(Eval,S,Value).

% If it's player 1's turn, choose the max (last value).
selectMove(s(1,_),_,SortedMoves,S2,Value) :- last(SortedMoves,Value-S2).

% If it's player 2's turn, choose the min (first value).
selectMove(s(2,_),_,[S2-Value | _],S2,Value).