[Haskell-cafe] Wumpus World

[Richard A. O'Keefe]

On 27 Mar 2008, at 4:23 pm, Benjamin L. Russell wrote:

> After briefly searching the Internet and coming up
> with a page entitled "CIS587: The Wumpus World"
> (http://www.cis.temple.edu/~ingargio/cis587/readings/wumpus.shtml),
>
> I think that since the statement of this problem
> there, involving the Situation Calculus, chiefly
> involves a sequence of logical statements with truth
> values and the relations between the statements, the
> statements there could perhaps initially be more
> directly applied with Prolog than with Haskell.

A solution to the problem is a sequence of actions.
In Prolog,
     action(right).
     action(left).
     action(forward).
     action(shoot).
     action(grab).
     action(release).
     action(climb).

     solution(Actions) :-
         initial_state(State0),
         length(Actions, _),
         fill_in(Actions, State0).

     fill_in([], State) :-
         final_state(State).
     fill_in([Action|Actions], State0) :-
         action(Action),
         effect(Action, State0, State1),
         fill_in(Actions, State1).

Now all that's left is to implement effect(Action, State0, State1),
which means "(known) action Action can be carried out in
(known) state State0 and results in state State1".

By inspection, we can see that
	[forward,left,forward,forward,grab,left,shoot,
          left,forward,forward,right,forward,climb]
will solve the problem, so we must search to a depth of 13,
and have 7 actions to choose from, so a blind iterative-deepening
search like this must check on the order of 1.1x10**11 states.

> Also, you may wish to keep in mind the following
> differences between Haskell and Prolog:
[snip]
>
>
> * Haskell code tends to be more succinct (as Paul
> Johnson mentioned)

Not really an issue for this problem.
>
>
> * Haskell code tends to run faster, and can often be
> optimized to run at a speed on par with OCaml
>
> * Prolog tends to be one of the slowest-running
> programming languages

That largely depends on which compiler you use and what coding style
you follow.  I've known Prolog code outperform published Fortran for
the same problem, thanks to using a better algorithm that was easy to
express in Prolog and practically impossible in Fortran 77.

The Prolog results at http://shootout.alioth.debian.org/
are only for the open source system SWI Prolog, which is basically
a one-man effort.  The commercial SICStus Prolog is substantially
faster.  Some of the Prolog benchmark versions look distinctly odd.

It is certainly true that Prolog can be slow *if* you try to write
conventional imperative code in it, which many people do.  But then,
conventional imperative code isn't the best way to use Haskell either.

Prolog's strongly-typed-and-moded brother, Mercury, gives you a
combination of
	- logic programming
	- strict functional programming
	- Haskell-like typeclasses
which makes it a candidate.

However, checking 1.1x10**11 states is going to take a while no matter
*what* language you use.  Looking at the problem again, we see that
if you can get the gold and shoot the wumpus, then you can certainly
get out again by retracing your steps, because the pits do not move
around.  So in the solution
	[forward,left,forward,forward,grab,left,shoot,
          left,forward,forward,right,forward,climb]
the second line consists of steps that are entirely predictable
from the first.  So we *really* only have to search to a depth of 7,
checking 9.5x10**5 states.  That's a speedup of 117649, which is much
more than you are going to get from ANY programming language.

I should point out that Prolog is not well suited to *directly*
expressing rules like
	Smelly(l1) = > (EXISTS l2 At(Wumpus,l2,s) & (l2=l1 OR Adjacent(l1,l2)))
This is going to require some programming.

Something that might be rather fun would be feeding the Wumpus World
axioms to the free theorem prover OTTER, which is quite impressive.