🚀 go-pugleaf

In article <41581@linus.UUCP> bwk@mbunix (Kort) writes:
>A tip of the hat to Richard for his well-penned remarks.
>I am amazed at the power of Prolog to solve a problem in
>combinatorial logic without being given an explicit method.
>But I am also disheartened by the difficulty of untangling
>the effects of reordering the clauses.

Purr purr...

>When a bright student solves a brain-teaser, the order in which
>the clues are stated does not strongly affect the method of
>solution.  In Prolog, resequencing the clues can have dramatic
>effects on the search order.  I find this phenomenon bewildering.

Well, I'm not a student any more, but even when I was, the order of the
clues had a pretty strong effect on me.  (...rrup rrup) Why should it be
bewildering that an intelligent-but-slow organism which spends some time
thinking about the problem and a totally-stupid-but-fast programming
language interpreter should act differently?

Let's look at the monkey-and-bananas program which started this
discussion.  It's just a depth-first search, where states have the
form	state(MonkeyHoriz,MonkeyVert,BoxVert,HasBananas).

initial_state(state(atdoor,onfloor,atwindow,hasnot)).

move(	state(middle,onbox,middle,hasnot),
	grasp,
	state(middle,onbox,middle,has)).
move(	state(P,onfloor,P,H),
	climb,
	state(P,onbox,P,H)).
move(	state(P1,onfloor,P1,H),
	push(P1,P2),
	state(P2,onfloor,P2,H)).
move(	state(P1,onfloor,Q,H),
	walk(P1,P2),
	state(P2,onfloor,Q,H)).

depth_first_monkey(Moves) :-
	initial_state(State),
	depth_first_monkey(State, Moves).

depth_first_monkey(state(_,_,_,has), []).
depth_first_monkey(State1, [Move|Moves]) :-
	move(State1, Move, State2),
	depth_first_monkey(State2, Moves).

Note that this state space is just about as bad for depth-first search
as it can possibly be:  for any P,H,  push(P,P) is a possible
action which transforms state(P,onfloor,P,H) to itself, and similarly
for any P,Q,H,  walk(P,P) is a possible action which transforms
state(P,onfloor,Q,H) to itself.  Or if you're smart enough to avoid
trivial loops, push(P,Q);push(Q,P) and walk(P,Q);walk(Q,P) are loops.
Loops are BAD NEWS for depth-first search.

There is an easy way of fixing this, and while it looks like a hack it
is actually a principled strategy which competes well with breadth-first
search.  That is ITERATIVE DEEPENING.  To keep this message short:

iterative_deepening_monkey(Moves) :-
	list(Moves),
	depth_first_monkey(Moves).

list([]).
list([_|L]) :-
	list(L).

I suggest that you consult a good AI text to find out when iterative
deepening is appropriate.  In this particular case, the iterative
deepening version works well no matter how you shuffle the rules.

This is actually a problem where working backwards is a good idea:
there is only one move which can possibly yield the final state, only
one move which can yield that state, and not too many before that.

What one really wants is a "smart" program which notes for example that
any sequence Walk*{Push;Walk*}* can be collapsed to either Walk or
Walk?Push;Walk?, that no action can follow a 'grasp', and that no
other action than 'grasp' can follow 'climb', so that the only
"interesting" sequences are
	{Walk | Walk? Push Walk?} {Climb Grasp?}?

-- This is why I have never really got interested in things like the Zebra
puzzle:  by the time you have figured out a cunning way to represent the
search space and the rules there is nothing left to write in Prolog.