Assignment 5: Spamventure! and Knights/knaves...

Submission

For this assignment, you'll work within two files whose starting versions are linked here:

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

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. To do this, it should use the "succeed via fail" approach, noted in class on 2/27 and below.
   
   
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 not hold 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. In order to do this, you might want to use the setof predicate that creates a list of items - then you can use the built-in length predicate to test the length of that list.
   
   Here is an example listOfItemsInHand( L ) predicate you're welcome to use:

   % listOfItemsInHand( L ) binds L to the list
   %   of items X that satisfy the predicate thing_at( X, in_hand ).
   % base case - empty list
   listOfItemsInHand( [] ) :- \+setof( X, thing_at(X,in_hand), _ ).
   % general case - nonempty list
   listOfItemsInHand( L ) :- setof( X, thing_at(X,in_hand), L ).
     

   
   
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 the commands you implement (except Easter Eggs...) 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 required here.
    
    
12. Write a comment at the top of your spamventure.pl file that explains the context of your game (it's "twitch plays Spamventure!") 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.

How can fail help?    Here is an example we will cover (or have covered) in class. It shows how to use Prolog's backtracking in order to have a single predicate (such as inventory) describe multiple objects. To see how it works, include these predicates in a file and then try bad. and good.  :

% Three foo facts!
foo(chris).
foo(taylor).
foo(dave).

% The good and the bad:
bad :-
    foo(X), write('foo: '), write(X),
    nl.

good :-
    foo(X), write('foo: '), write(X),
    nl,
    fail.

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 have included a couple of errors in how objects are handled in the provided starter file - a good first step is to fix those...:

• As provided, 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 includes the walkthrough/"cheat sheet" and other notes on your game in a comment at the top. (For the spamventure problem, you do not need to write any tests... .)

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!

Helper predicates to write    The starter file has tests for these helper predicates - be sure to write an additional test -- and test it! -- for the predicates not already provided:

• 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 the provided definition for getVar - it's efficient, because it only checks right-hand sides if there are no variables on the left:

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

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

Examples    Look over these examples of id... They will help clarify the format of that final predicate:

• 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!)

Submit this problem as logic.pl. Start with the provided file (with tests) at the top of this page... .

Part 3:    Java and Eclipse!    (8 points)

[8 points; pair or individual]

This week's Java problems are not based on CodingBat.

Java is, arguably, one of the most popular software engineering languages (software engineering is only a facet of CS, admittedly...).

As such, Java is quite a different beast than Raket or Prolog. In particular, Java is partly defined by the huge set of tools that help people program, debug, and run it. This week's goal is to gather all of those tools and make sure they're running for you!

So your task is to download, install, and run this (pretty large) Java-support software:

• The Java SDK (software development kit) - the compiler and execution environment for Java:
  • Here is the link to download the Java SDK
  • You'll need to click the "Accept the Oracle agreement" radio button, and then you should be able to download it for your operating system.
  • Note that you do want the Java SDK (not the Java run-time environment, which you may already have). The "SDK" stands for Software Development Kit, the compiler for Java source code and associated tools.
• Eclipse - a popular and industry-strength IDE (integrated development environment) for many languages...
  • Here's the link to the Eclipse download page
  • We'll simply use the Eclipse Standard 4.3.2 edition, which the top link on that page.
• Third, try them out!
  • First, install the JDK. Then, install Eclipse.
  • Next, run Eclipse. It may take a moment to start up
  • It will ask where you want to store your projects -- you can use the default folder it provides - or another one. I chose Use this as the default and don't ask again.
  • You should see the "Welcome" screen. (If you've already used Eclipse, you can get back to the Welcome screen via the Help menu.)
  • Click on Tutorials... (Feel free to explore the other options, if you'd like!)
  • On the subsequent screen, under Java Development, click on Create a Hello World Application.
  • Work through the tutorial, which will appear on the right.
  • Write a small function... average:
    • Once you've gotten Eclipse's Hello World tutorial running, it's worth it to create a small piece of code of your own. This will be to write a Java function named average, that computes and returns the average of an array of numbers.
    • First, copy the code from this link so that it replaces the code in the HelloWorld.java file entirely.
    • Try running that new code -- read it over to get a sense of how it works. You'll see that the average function isn't computing the average (yet)... .
    Fix the average function so that it does compute - and return - the average correctly.
    • Try it out!
    • Congratulations -- you've gotten Java, Eclipse, and a slightly-customized Hello World application running. More Java next week!

Submitting...    As in previous weeks, submit a short sentence (such as "I'm Eclipsed!") to the submission system under hw5pr3.txt once you've gotten this working.

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!