% ida_plan.pl -- Iterative deepening with heuristic pruning (ala A*)
%    by: John Zelle
%  additions by: 

:- use_module(sets).

% input problem: legal_move/3, goal_state/1, hpred/2.

max_depth(100).     % Max depth to search to.

% ida_search(HeuristicPred, InitialState, Plan) --
%     perform an idastar search using HPred as the heuristic function.
% example: ?- start(5, I), ida_plan(h0, I, Plan).
ida_plan(HPred, Start, Plan) :-
	max_depth(MaxD),
	call(HPred, Start, StartH),     % use HPred as a goal
	gen_bound(StartH, MaxD, Depth),
	write(Depth),nl,
	reachable(HPred, Start, StartH, Depth, Plan, Goal),
	goal_state(Goal).

% reachable(HPred, CurrState, H(CurrState), StepsLeftUntilBound, Plan, Goal)
reachable(_, S, _, _, [] ,S).
reachable(HPred, S0, H0, StepsLeft, [Op|Ops], S) :-
	StepsLeft >= H0,
	StepsLeft1 is StepsLeft - 1,
	legal_move(S0, Op, S1),
	call(HPred, S1, H1),
	reachable(HPred, S1, H1, StepsLeft1, Ops, S).
reachable(_, _, H, StepsLeft, _, _) :-   % pruned. update bound increment, then fail.
	StepsLeft < H,
	Needed is H-StepsLeft,
	update_bound_increment(Needed),
	fail.

% non-logical predicates to handle generating/updating next bound.

/* gen_bound(+Start, +Max, -Bound) -- generate successive depth bounds
       between Start and Max via backtracking. The increase on a redo
       is determined by the value of the dynamic predicate bound_increment/1.
       bound_increment is reset to Max each time the next bound is generated.
*/

gen_bound(Start, Max, Start):-
    retractall(bound_increment(_)),
    assert(bound_increment(Max)).  % set increment to "infinity"
gen_bound(Bound, Max, Bound1) :-
    bound_increment(Inc),
    NewBound is Bound + Inc,
    NewBound =< Max,
    gen_bound(NewBound, Max, Bound1).

% Save the smallest increment necessary to usefully expand search
update_bound_increment(ThisInc) :-
    bound_increment(Inc),
    NewInc is min(ThisInc, Inc),
    retractall(bound_increment(_)),
    assert(bound_increment(NewInc)).

h0(_, 0). % generic heuristic for uninformed (iterative deepening) search

% idag_plan(HPred, InitialState, Plan) --
%     perform an ida search using HPred as a heuristic function and cycle checking


