/* BEST-FIRST AND/OR SEARCH
(from Prolog Programming for AI, Ivan Bratko, Addison-Wesley, 1986)
This program only generates one solution.  This solution is guaranteed
to be a cheapest on if the heuristic function used is a lower
bound of the actual costs of solution trees.

Search tree is either:
tree(Node, F, C, Subtrees)	Tree of candidate solutions
leaf(Node, F, C)		Leaf of a search tree
solvedtree(Node, F, SubTrees)	Solution tree
solvedleaf(Node, F)		Leaf of a solution tree
C is the cost of the arc point to Node
F=C+H where H is the heuristic estimate of an optimal solution subtree
   rooted in Node

SubTrees are always ordered so that:
(1) all solved subtrees are at the end of a list
(2) other (unsolved subtrees) are ordered according to ascending F-values
*/

:- op(500, xfx, :).
:- op(600, xfx, --->).

andor(Node, SolutionTree) :-
  expand(leaf(Node, 0,0),999999999,SolutionTree,yes). /*Assuming 999999999
     is less than any solution value*/

/*Case 1: bound exceeded */
expand(Tree,Bound, Tree, no) :-
  f(Tree,F), F>Bound, !.

/*Case 2: goal encountered */
expand(leaf(Node,F,_C),_,solvedleaf(Node,F),yes) :-
  goal(Node), !.

/*Case 3: expanding a leaf */
expand(leaf(Node,_F,C), Bound, NewTree, Solved) :-
  expandnode(Node,C, Tree1), !,
  expand(Tree1,Bound,NewTree, Solved).

expand(leaf(_,_,_),_,_,never) :- !.

/*Case 4: expanding a tree */
expand(tree(Node,_F,C,SubTrees),Bound,NewTree,Solved) :-
  Bound1 is Bound-C,
  expandlist(SubTrees, Bound1,NewSubs,Solved1),
  continue(Solved1,Node,C,NewSubs,Bound,NewTree,Solved).

expandlist(Trees,Bound,NewTrees,Solved) :-
  selecttree(Trees,Tree,OtherTrees,Bound,Bound1),
  expand(Tree,Bound1,NewTree,Solved1),
  combine(OtherTrees,NewTree,Solved1,NewTrees,Solved).

continue(yes,Node,C,SubTrees,_,solvedtree(Node,F,SubTrees),yes) :-
  backup(SubTrees,H),F is C+H,!.

continue(never,_,-,_,_,_,never) :- !.

continue(no, Node, C,SubTrees,Bound,NewTree,Solved) :-
  backup(SubTrees,H), F is C+H, !,
  expand(tree(Node,F,C,SubTrees), Bound,NewTree,Solved).

combine(or: _, Tree, yes, Tree, yes) :- !.

combine(or:Trees, Tree, no, or:NewTrees,no) :-
  insert(Tree,Trees, NewTrees), !.  /*OR list still unsolved */

combine(or:[],_,never,_,never) :- !.  /*No more candidates*/

combine(or:Trees,_,never,or:Trees,no) :- !.  /*Ther are more candidates*/

combine(and:Trees,Tree,yes,and:[Tree|Trees],yes) :- allsolved(Trees),!.  
           /*AND list solved */

combine(and:_, _,never,_,never) :- !.
          /*AND list unsolvable*/

combine(and:Trees,Tree,_YesNo,and:NewTrees,no) :-
  insert(Tree,Trees,NewTrees), !.   /*AND list still unsolved*/

/*Expandnode makes a tree of a node and its successors */
expandnode(Node,C,tree(Node,F,C,Op:SubTrees)) :-
  Node ---> Op:Successors,
  evaluate(Successors,SubTrees),
  backup(Op:SubTrees,H),  F is C+H.

evaluate([],[]).
evaluate([Node/C | NodesCosts],Trees) :-
  h(Node,H), F is C+H,
  evaluate(NodesCosts,Trees1),
  insert(leaf(Node,F,C), Trees1, Trees).

/* Allsolved checks whethere all trees in a list are solved*/

allsolved([]).
allsolved([Tree|Trees]) :-
  solved(Tree),
  allsolved(Trees).

solved(solvedtree(_,_,_)).
solved(solvedleaf(_,_)).

f(Tree,F) :- arg(2,Tree,F), !.

insert(T,[],[T]) :- !.
insert(T,[T1|Ts],[T,T1|Ts]) :- solved(T1), !.
insert(T,[T1|Ts],[T1|Ts1]) :-
  solved(T),
  insert(T,Ts,Ts1), !.

insert(T,[T1|Ts],[T,T1|Ts]) :- 
  f(T,F), f(T1,F1), F=<F1, !.

insert(T,[T1|Ts],[T1|Ts1]) :-
  insert(T,Ts,Ts1).

backup(or:[Tree|_],F) :-  f(Tree,F), !.

backup(and:[],0):- !.
backup(and:[Tree1|Trees],F) :-
  f(Tree1,F1),
  backup(and:Trees,F2),
  F is F1+F2, !.
backup(Tree,F) :- f(Tree,F).

selecttree(Op:[Tree],Tree,Op:[],Bound,Bound) :- !.
selecttree(Op:[Tree|Trees],Tree,Op:Trees,Bound,Bound1) :-
  backup(Op:Trees,F),
  (Op=or,!,min(Bound,F,Bound1); 
   Op=and, Bound1 is Bound-F).

min(A,B,A) :- A<B, !.
min(_A,B,B).