Assignment 10: Prolog for Fun and Profit:
Due Sunday, April 12 by 11:59 pm

Submission

For this assignment, you'll work within two files, both linked from the top-level assignments page with starter comments/code:

• spamventure.pl for the Prolog text adventure
• logic.pl for the Knights/Knaves problem

Part 1: Spamventure! (50 Points)

[50 points, pair or individual]

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

In class on Monday and 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 spamventure.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 spamventure.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)

[50 points, pair or individual]

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. Your file should be named logic.pl.

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 true 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 following items:

• 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.

       id( t, Who ).
       Who = human ;
       Who = knight   % need not wait for all repetitions of this - hit Enter
       Yes 
       
       id( [ifthen, f, 1], Who ).
       Who = human ;
       Who = knight   % need not wait for all repetitions of this - hit Enter
       Yes 
       
       id( [ifthen, 1, [ifthen, 2, 1]], Who ).
       Who = human ;
       Who = knight   % need not wait for all repetitions of this - hit Enter
       Yes 
       
       id( [iff, [ifthen, [and, 1, 2], 3], [ifthen, 1, [ifthen, 2, 3]]], Who ).
       Who = human ;
       Who = knight   % need not wait for all repetitions of this - hit Enter
       Yes 
       
       id( [iff, 1, [not, 1]], Who ).
       Who = human ;
       Who = knave    % need not wait for all repetitions of this - hit Enter
       Yes 
       
       id( [and, 1, 2], Who ).
       Who = human ;
       No
       

  It's not a good idea to use setof to test your knight/knave identifier. This is because it's possible to write the id in such a way that there are many repeats of a single result, and setof will try to generate them all. This can take too long!

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

• noVars( Expr ) true if Expr has no logical variables, i.e., literal integers
  
  Here is the code we wrote in class, which you may want to adapt:

       noVars( t ).
       noVars( f ).
       noVars( [_, L, R] ) :- noVars( L ), noVars( R ).
       

  Note that you'll need to handle not, as well.
  
  
• getVar( Expr, N ) true if N is an integer representing a variable that is currently contained in Expr. Here is a slight variant (that adds speed/efficiency!!) to the code we wrote in class:

       getVar( N, N ) :- number( N ).
       getVar( [_, L, R], N ) :- getVar( L, N ); (noVars(L), getVar( R, N )). 
       

  Notice that this variant only descends the second branch if there are no variables in the first branch! This will make the expansion much more succinct and, thus, faster and memory-efficient. Be sure to use this (the code may not complete in the time/memory available otherwise!)
  
  That said, it's worth mentioning that the above code for getVar will not bind to more than one variable in a single invokation. For example,

       ?- getVar([ifthen, 1, 2], X).
       X = 1 ;
       No
       

  Although this may seem like a problem, once you substitute a truth value for 1, the next call to getVar will happily return the 2. And did we mention it's much faster?
  
  
• taut( Expr ) would be true if Expr is a tautology (check for no logical variables first...)
• unsat( Expr ) would be true if Expr is unsatisfiable (check for no logical variables first...)
• subst( N, TorF, OldExpr, NewExpr ) would be 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 instances of N have been replaced with the literal value of TorF.
  
  Here is an example of how subst might work:

       subst( 1, t, [and, [not, 1], 1], NewExpr ).
  
       NewExpr = [and, [not, t], t]
       

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

Optional Extra Credit

This week the extra credit is open-ended: to go above-and-beyond the Spamventure requirements with additional features in your text-adventure (up to +10 points are available).

If you choose to do this, please make a note of it on the top of your file -- and mention the ways in which you pushed beyond the problem's requirements!