% minimax search 
  % INPUT:\ \  Tree:\  Game tree
  % OUPUT:  Val: Backpropagated value of root\ \ \ */

  minimax(Tree,Val) :- mnmx(max, Tree, -99999, Val). 

  mnmx(max, [ _  ,X | Y], Vmax, Val) :- !,
	  mnmx(min, X, 99999, Val1),
	  max(Vmax, Val1, NewVmax),
	  mnmx(max, [ _   | Y], NewVmax, Val).
  mnmx(min, [ _  ,X | Y], Vmin, Val) :- !,
	  mnmx(max, X, -99999, Val1),
	  min(Vmin, Val1, NewVmin),
	  mnmx(min, [ _   | Y], NewVmin, Val).
  mnmx( _  , [ _  ], NewVal, Val) :- !,
	   NewVal=Val.
  mnmx( _  ,  Leaf,  _  , Val) :- leaf_value(Leaf, Val).




  % alpha-beta search 
  % INPUT:\ \  Tree:\  Game tree
  % OUPUT:  Val: Backpropagated value of root\ \ \ */

  alphabeta(Tree, Val) :- ab(max, Tree, (-99999,99999), _  , -99999, Val). 

  ab(max, [N, X | Y], (A,B), Vmax, Val) :- !,
	  ab(min, X, (A,B),  99999, Val1),
	  str_max([N | Y], (A,B), Vmax,  Val1, Val).
  ab(min, [N, X | Y], (A,B), Vmin, Val) :- !,
	  ab(max, X, (A,B), -99999, Val1),
	  str_min([N | Y], (A,B), Vmin, Val1, Val).
  % here leaf values are determined: 
  ab( _  ,  Leaf, _  , _  , Val) :- leaf_value(Leaf, Val).

  %here alpha pruning takes place: 
  str_min( _  ,(A, _  ), _  , Val1, A1):- 
	  Val1 < A, !,
	   A=A1. 
  %otherwise, the value of min-nodes is determined here: 
  str_min([ _  ], _  ,Vmin, Val1, Val) :- min(Vmin, Val1, Val).
  str_min(N, (A,B), Vmin, Val1, Val):-
	  min(Vmin, Val1, NVmin),
	  %here beta is updated:
	  min(NVmin, B, BB), 
	  ab(min, N, (A,BB), NVmin, Val).

  % here beta pruning takes place:
  str_max( _  , ( _  ,B), _  , Val1, B1):- 
	  Val1 > B, !, 
	  B=B1.  
  %otherwise, the value of max-nodes is determined here: 
  str_max([ _  ], _  , Vmax, Val1, Val) :-  max(Vmax, Val1, Val).
  str_max(N, (A,B),  Vmax, Val1, Val):-
	  max(Vmax, Val1, NVmax),
	  % here alpha is updated:
	  max(NVmax, A, AA),
	  ab(max, N, (AA,B),  NVmax, Val).




% Library file.

goal(Node) :- Node == i.
arc(a, b).
arc(a,m).
arc(m,i).
arc(a, c).
arc(b, d).
arc(b, e).
arc(c, b).
arc(c, f).
arc(c, g).
arc(d, h).
arc(d, i).
arc(e, d).
arc(e, j).
arc(f, b).
arc(f, j).
arc(g, k).
arc(g, l).
h.
arc(i, a).
j.
arc(k, f).
arc(k, c).
arc(l, k).






% Huristic function

hfun(L,N) :- length(L,N).

lmember(_,[ ]) :-!,fail.
lmember(X, [X | _]).
lmember(X, [ _ | L]) :- lmember(X,L).

%not(X) :- X, !, fail.
%not(_).

move_smallest_to_top([ ], [ ]).
move_smallest_to_top([Val-X|L], [S|R]) :-
	find_smallest(L, Val-X, S, R).

find_smallest([ ], T, T, [ ]).
find_smallest([Val1-X | L], Val-T, S, [Val-T | R]) :-
	Val1 < Val, !,
	find_smallest(L, Val1-X, S, R).

find_smallest([Val1-X | L], Val-T, S, [Val1-X| R]) :-
	% Val <= Val1
	find_smallest(L, Val-T, S, R).


% Tree structure.
tree_arc(a, b).
tree_arc(a, c).
tree_arc(b, d).
tree_arc(b, e).
tree_arc(c, f).
tree_arc(c, g).
tree_arc(d, h).
tree_arc(d, i).
tree_arc(e, j).
tree_arc(g, k).
tree_arc(g, l).

tree_value(a,1).
tree_value(b,2).
tree_value(c,3).
tree_value(d,4).
tree_value(e,5).
tree_value(f,6).
tree_value(g,7).
tree_value(h,8).
tree_value(i,9).
tree_value(j,10).
tree_value(h,11).
tree_value(l,12).

htree([Node|_], Val) :- tree_value(Node, Val).