07.363 Assignment n+3: Prolog Project

This assignment is worth 10% of your final mark.

Hunt the Wumpus

To run the game, login to cs26 and make a copy of wump.nw from the G363 directory. Then run the command noweb wump.nw. This will produce a file wump.pl (and a file wump.tex; ignore the latter for now). You can now load wump.pl into SICStus Prolog. To play the game, type the query

  ?- enter_maze(maze_1).

   ?- enter_maze(random).

1. Draw an artistic impression of maze_1, indicating the entrance and which rooms contain pits, bats, and the Wumpus. You should not attempt to draw a picture of the Wumpus, as the dreaded beast has never been seen by a human eye! Feel free to elaborate the picture with drawings or bats, pits, trapdoors, etc. [5 Marks]

2. Give the minimum sequence of commands needed to slay the Wumpus in this maze (note that you can give a list of rooms to move through to the move command). Your sequence of commands must avoid encountering any bats (include commands to shoot them if necessary!) [5 Marks]

3. Modify the predicate smell_the_air/3 to detect when the Wumpus is two corridors away. The status message should report ``I smell a faint odour of Wumpus''. [5 Marks]

4. Design a new maze, maze_2, that cannot be won without a lucky bat ride; i.e. there must be too many bats to shoot, and bats block all paths to the Wumpus. Draw a picture of your maze. [5 Marks]

5. Extend the game so that some rooms may contain vacuum cleaners (the hand-held ``dust buster'' variety). When the explorer enters a room with a vacuum cleaner, she picks it up (i.e. assumes a ``has vacuum cleaner'' state) and is henceforth immune from bat rides---the noise of the vacuum cleaner interferes with the bat's echo-location, and they flop harmlessly to the floor. [20 Marks]

   You will need to:

   1. define EDCG accumulators for vacuums (a list of rooms containing vacuum cleaners) and has_vacuum (the number of vacuum cleaners in the explorer's possession);
   2. add these accumulators to the appropriate pred_info/3 clauses;
   3. add an extra field to the maze/6 predicate to record the locations of the vacuum cleaners (a list of rooms);
   4. modify the move_explorer//1 predicate to check has_vacuum before making a bat ride, and to pick up a vacuum if there is one on the room. Each of these actions should have a corresponding status message; e.g. ``A bat flops to the floor'', and ``A vacuum cleaner? How interesting!''.
   5. update the peek action to include the locations of any vacuum cleaners in the report;
   6. for completeness, add a drop command that lets the explorer drop a vacuum cleaner (if she has one).
6. Add a new ``special'' command strategy that reports the minimum pit-free path from the explorer's current location to the room containing the Wumpus, along with the locations of any bats on that path. [10 Marks]

   The status message should look like this:

       You can win by moving along the path [2,20,40,15]
       Be careful to kill the bat in room [20]
   

   If there is no pit-free path to the Wumpus, the status message should report ``Victory is unlikely''.

   I recommend you use the SICStus Prolog ugraphs library predicates del_vertices/3 and min_path/5, and the ordsets library predicate ord_intersection/3; i.e. include the following chunk in your program:

   <>=
   :- use_module(library(ordsets), [ord_intersection/3] ).
   :- use_module(library(ugraphs), [del_vertices/3, min_path/5]).
   @ 
   

   Literate Programming with and ``noweb''

   The Wumpus handout is written in noweb, a literate programming tool. That is, there is a single document wump.nw that contains both Prolog source code and documentation for the program. The source code is distributed throughout the document in ``chunks''. These chunks are extracted by the noweb processor to produce a file wump.pl. The noweb processor also produces a file wump.tex that contains instructions for producing a typeset document with cross-references and indices. In this case, , a high-quality document preparation system, has been used as the typesetter.

   All changes you make to Hunt the Wumpus should be made to your copy of wump.nw, which you can obtain from the G363 directory. Although there are a large number of typesetter instructions, you should only need to be aware of the following:

   \section

   start a new section

   \subsection

   start a new sub-section

   [[code]]

   within the documentation, typeset code as program code

   $ % & ^ \ _ # { }

   these characters have a special meaning to LaTeX; avoid them if possible. If you must include one, try preceeding it with a backslash, as in \$, or write it like \verb|$|

   <>=

   start a new code chunk

   @ %def ide ...

   signal the end of a code chunk that defines ide. The %def ide ... can be omitted if chunk doesn't define a new predicate.

   To extract the Prolog source, type

      % noweb wump.nw
   

   or, in Emacs, use M-x compile RET noweb wump.nw RET. There may be a NCSA-Telnet key set up to do this; check the NCSA-Telnet HELP screen.

   Oh, and sorry---there is no way you can do this assignment using the Macintosh Prolog. Please let me know if you would like an additional tutorial on using Unix.

   What to hand in

   Hand in the written part of the assignment at the resource center in the usual way. This will include the maze drawings, minimum command sequence, and listings summarising your code changes. Do not give a printed listing of the entire program. I want a written summary of your changes (with appropriate commentary) only.

   The program part (i.e. your final version of wump.pl) is to be submitted electronically, using the submit-ass-3 utility. You should find this utility in the G363 directory. To submit your program, type

   A key will be set up to automate this task for Emacs users; check the HELP screen for details.