Assignment 5: Spamventure! and Knights/Knaves
Due Tuesday, October 14th by 11:59 pm

Submission

For this assignment, you'll work within four files, whose starting versions are linked here in hw5.zip. The four files are

• spamventure.pl for the Prolog text adventure
• logic.pl for the Knights/Knaves problem
• Hw5pr3.java - Starting code for your Java assignment
• Hw5pr3Test.java - Starting code for your Java JUnit tests

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!

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. Again, this will use the "succeed via fail" approach...
   
   
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. Or something else entirely!
   
   
10. Document all commands in the instructions function.
    
    
11. You need not go gonzo with this. It's possible to add tons of features but this isn't required. That said, if you'd like to make your game more elaborate, up to 10 bonus points will be awarded for features beyond what are requested here.
    
    
12. Write a comment at the top of your spamventure.pl file that explains the context of your game and documents the sequence of moves required to win the game, the objects you have included, and the additional feature (or "twist") you've added.
    The grutors will try out these instructions on your game (that is, if they can't solve it by themselves!)
    If you do implement other additional features, be sure to mention them in this top-of-file comment, as well, so we're sure to know about them!

Your code should use dynamic assertion and retraction of facts -- and the Prolog fail mechanism for binding to and/or displaying more than one thing through a single predicate call.

Getting started    One concrete thing we'd suggest that will help get started with the dynamic predicates and assert and retract that will be needed for your adventure is the following. We included a couple of errors in how objects are handled in the provided starter file:

• When the player is at jacobs, there is a key there -- you see this via the thing_at(key, jacobs) predicate. However, the description does not include a key! Change the way places are described so that each item is described when its location is described. This will use fail in order to bind to each item, print it, and then continue for more... . Test it by adding lots more objects (even if you remove them later) and making sure they're listed!
• When the player is at west_dorm, the spam is described, but in the overall description, not as part of checking what's present and listing that. Fix this problem, too, so that items are described when present and not described when they're somewhere else (such as in_hand)!

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

You should write tests for spamventure. Here is a simple example that checks that when you go north and then south you end up in jacobs.

% run this test by typing run_tests(play)
:- begin_tests(play).
test(play1) :- start,
	      go(north),
	      go(south),
	      player_at(jacobs), !.

:- end_tests(play).

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

[42 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. You will need to write your own test cases for this problem, but we give you some sample calls to get you started.

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, you'll 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    Look over these examples! They 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
  
       
       id( [ifthen, f, 1], Who ).
       Who = human ;
       Who = knight   % need not wait for all repetitions of this - hit Enter
  
       
       id( [ifthen, 1, [ifthen, 2, 1]], Who ).
       Who = human ;
       Who = knight   % need not wait for all repetitions of this - hit Enter
  
       
       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
  
  
       id( [not, [iff, [ifthen, [and, 1, 2], 3], [ifthen, 1, [ifthen, 2, 3]]] ], Who ).
       Who = human ;
       Who = knave    % need not wait for all repetitions of this - hit Enter
       
       id( [iff, 1, [not, 1]], Who ).
       Who = human ;
       Who = knave    % need not wait for all repetitions of this - hit Enter
  
       
       id( [and, 1, 2], Who ).
       Who = human ;
       false
       

  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! You SHOULD write tests for all of your helper predicates used to solve the knight/knave problem (and again - you should write these before writing code!)

Hints: possible helper predicates    One possible decomposition uses these helpers:

• noVars( Expr ), succeeding if Expr has no variables, i.e., no integers.
• getVar( Expr, N ), succeeding if Expr has a variable, i.e., an integer, and N then gets bound to it. Use this start of a definition for getVar - it's efficient, because it only checks right-hand sides if there are no variables on the left:

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

  Note that you'll need a third rule here - for the case when there's only one subexpression, not two! This is the not case!
• subst( N, TorF, OldExpr, NewExpr ), where N is an integer, TorF is either t or f, and then it binds NewExpr to the same structure as OldExpr, with all of the instances of N replaced by TorF. This is the key step of the algorithm, as discussed in class!
• eval( NoVarExpr, TorF ), where TorF is either t or f. This predicate would only need to handle expressions NoVarExpr with no variables - and it should bind TorF to the appropriate truth value for that expression. Recursion is key here! If you'd like to use this, here is an example rule that may help get you started:

   
  eval( [not, SubExpr], t ) :- eval( SubExpr, f ).
  

• taut( Expr ) would succeed if Expr is a tautology. If Expr has no variables, the task would be delegated to eval; if it does have variables, then subst would be used -- twice -- to replace one of them with t and then f, and then checking further... .
• unsat( Expr ) could work in an identical manner to taut, succeeding only where Expr is unsatisfiable.

More elaborate hints... if you'd like...    This page has a fuller description of the above set of helper predicates that decompose this satifiability challenge.. These hints are not the only way to handle things, butif you're feeling stuck -- or if you're unclear about what the pieces of this problem might be, that link will provide one possible strting point... .

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

Part 3:    Java!    (8 points)

[8 points; pair or individual]

• This week's problems are not based upon CodingBat. The problems will provide more practice with arrays and these methods will be used as helper methods in some sorting algorithms we will see later this semester.
• If you didn't look over loops last week, you may want to do that here: by reading more on the CodingBat array 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!