Assignment 10: Prolog for Fun and Profit:
Due Sunday, November 16 by 11:59 pm

Part 1: Spamventure! (50 Points)

In this part of the assignment you will be writing an interactive text-adventure game in Prolog!

In class on Tuesday we saw a simple adventure game written in Prolog. A preliminary skeleton file is available at the top-level assignment page. You can use this code as a starting point for your own adventure game... Another example is available from David Matusek of Villanova University at this link.

Your adventure game should have the following features:

1. As in the code provided for you, the game should be invoked by typing start. You should update the instructions to describe your adventure game and any special commands it uses and the overall objective the player is working towards. In addition, it should display the information on your current location. (See below for more on what kind of information is displayed for each location.)
   
   
2. Your game should have an objective (e.g. finding the spam, slaying the evil Spamerwonk, or some other goal of your own devising). This goal should be stated when the game is started. The game should end when the objective has been met. (You can use the command halt. in your code to end the Prolog session.)
   
   
3. Expand the game "map" beyond the four locations in the existing file. You can build a totally new game map if you like. You should have at least 6 different locations.
   
   
4. Upon arriving at a new location, the game should give a brief description of that location (e.g. "You see a grove of Spam trees swaying gently in the wind."), a list of all of the objects at that location which can be picked up (e.g. "You see a spam", "You see a key"), and a list of new locations which can be reached (in one move) and their direction (e.g. "You see a cave to the north. You see a lake to the south."). Note that the provided file does not correctly implement the descriptions of objects, because the spam is described as part of west_dorm. As a result, even if you take the spam there, it will remain in the description. Your game should only describe the objects still remaining at a location.
   
   
5. Implement a drop(X) rule analogous to the take(X) rule. If the user attempts to drop an object that she isn't holding, the program should say something like "You aren't holding that!"
   
   
6. The player may hold no more than two objects at a time. If the user attempts to take an object which would exceed this limit, she is told that this is not permitted.
   
   
7. Implement an inventory predicate which lists all of the objects currently held by the player. That is, when the player types inventory., she sees a list of all the items in her hand.
   
   
8. The current file has only two objects defined (spam and key). Add some more objects and make sure that each object is required for some task. (E.g. The spam might be required to "power up" for a particularly harrowing task, etc.) Make sure your game uses at least 4 objects.
   
   
9. Add at least one additional feature of your own choosing. For example, you might introduce an animate creature that is adversarial or cooperative.
   
   
10. Document all commands in the instructions function.
    
    
11. You need not go gonzo with this. It's easy to add tons of features but this isn't required. Up to 10 bonus points will be awarded for features beyond what is requested here.
    
    
12. Write a comment at the top of your part1.pl file that documents the sequence of moves required to win the game. The grutors will try out these instructions on your game (if they can't solve it by themselves!) If you do implement additional features, be sure to mention them in this top-of-file comment, as well.

Your code will need to use dynamic assertion and retraction of facts as well as the Prolog fail mechanism described in class for binding to and/or displaying more than one thing through a single predicate call.

Please submit your code in a file called part1.pl, which will include the "cheat sheet" and other notes on your game in a comment at the top.

Part 2: The Island of Knights and Knaves! (50 Points)

For this problem, your task is to create a prolog program that can identify (id) the possible speakers of statements you overhear on the Island of Knights and Knaves.

On that island, there are three kinds of inhabitants:

• knights, who speak only true statements.
• knaves, who speak only false statements.
• and humans, who can speak both treu and false statements (and may not know which one!)

For this problem, write a Prolog predicate

id( Expr, Speaker )

knight
knave
human

Possible Expressions:

Although the Expr input to your id rule will always be a fully-instantiated list as far as Prolog is concerned, it will represent an arbitrary parse tree for a logical expression that may contain compositions of

• The literal truth values t (meaning true) and f (meaning false)



• The logical operators and, or, not, iff, ifthen. You are familiar with and, or, not. As for the other two:
  • [iff, L, R] is true when the truth values of L and R are the same.
  • [ifthen, L, R] is true when "L implies R," that is, when L is false or R is true.
  Of these five logical operators, not is unary and forms logical parse trees via
  • [not, T], where T is a logical parse tree or literal or literal integer (see below).
  The other four operators, and, or, iff, ifthen are binary and form logical parse trees via
  • [and, L, R]
  • [or, L, R]
  • [iff, L, R]
  • [ifthen, L, R]



• Also, literal integers 1, 2, 3, ... may be present in Expr. If such a literal integer is present, it represents a logical variable that may take on either the value t or f. If the same integer appears in more than one place in an Expr, any substitution of t or f for one instance of that integer must also be substituted identically for all other instances of that integer. There are some examples of subst rule below that will help clarify this.
  
  Warning! These integers represent logical variables in the parse tree, represented by a fully-instantiated Prolog list. They are not Prolog variables in that list. Although it might seem tempting to use Prolog variables as logical variables, mixing the implementation language with the logical language leads to trouble, rather than to efficiency!

Examples    The examples will help clarify the format of

• the logical parse trees
• the way in which literal integers can represent logical (but not Prolog) variables within those logical parse trees
• the way id works (and a few examples of moderate-sized tautologies)
• one way that subst might be written -- you are free to decompose this problem as you see fit, but a few possiblities are listed after these examples.

setof( Who, id( t, Who ), Set ).
Set = [knight,human]

setof( Who, id( [ifthen, f, 1], Who ), Set ).
Set = [knight,human]

setof( Who, id( [ifthen, 1, [ifthen, 2, 1]], Who ), Set ).
Set = [knight,human]

setof( Who, id( [iff, [ifthen, [and, 1, 2], 3], [ifthen, 1, [ifthen, 2, 3]]], Who ), Set ).
Set = [knight,human]

setof( Who, id( [iff, 1, [not, 1]], Who ), Set ).
Set = [knave,human]

setof( Who, id( [and, 1, 2], Who ), Set ).
Set = [human]

% You might consider using a helper rule subst( N, Val, Expr, NewExpr ):
subst( 1, t, [and, [not, 1], 1], NewExpr ).
NewExpr = [and, [not, t], t]

Possible helper rules:

This problem does not require a lot of code, but it does require some careful thinking about

• how to check whether an expression Expr contains a literal integer representing a logical variable
• how to determine whether an expression, even containing only leaves of t and f, is a tautology or unsatisfiable or neither
• how to substitute t or f into such an expression, yielding a new expression -- there are a couple examples of this above
• how to avoid having Prolog head off infinitely searching for bindings that will not be helpful

• noVar( Expr ) true if Expr has no logical variables, i.e., literal integers
• taut( Expr ) true if Expr is a tautology (check for no logical variables first...)
• unsat( Expr ) true if Expr is unsatisfiable (check for no logical variables first...)
• getVar( Expr, N ) true if N is an integer representing a variable that is currently contained in Expr.
• subst( N, TorF, OldExpr, NewExpr ) true if N is an integer representing a variable that is currently contained in OldExpr, and TorF is t or f, and NewExpr is identical to OldExpr, except that all instnces of N have been replaced with the literal value of TorF.

Too many repetitions of the same answer?

It's possible to write id in such a way that it is correct, but that it gives so many repetitions of the same answer that it runs out of stack space, as if it contained an infinite loop. One way to help you avoid this is to use the "cut" operator, which is simply the exclamation point ! . Inserted in a sequence of predicates, the ! operator disallows backtracking across itself.

For example, suppose that in the process of defining taut, you substitute t for a variable in your logical expression. You might then call taut recursively to be sure the result is a tautology. If it is a tautology, you don't want or need to return to see if there are "other ways" in which it can be checked to be a tautology. Simply insert the cut operator, and prolog will not backtrack past it:

taut( E ) :-
  ... do some set-up work ...
  subst( V, t, E, NewE ),
  taut( NewE ), 
  !,
  ... do some more work ...
  ... but it will never backtrack back past the !

Submit this problem as part2.pl. There is a very short skeleton file from which to start on the top-level assignments page.

Optional Extra Credit

There are two possibilities for extra credit this week: the first is going above and beyond the Spamventure requirements with additional features in your text-adventure (up to +10 points are available).

phrasebook( Speaker, Phrase ).

You might consider using a helper rule which contains an additional argument in the spirit of tail-recursive functions. Then, generate all logical parse-trees whose Prolog lists are of length 1, culling out (with your id rule, perhaps) those that could not be spoken by Speaker. Afterwards, generate all logical parse-trees whose Prolog lists are of length 2, then 3, and so on... .