Assignment 3, Animal Crossing Out

Datalog (and Prolog) are excellent at describing queries over databases. Let’s use a database of animal facts to play 20 questions!

In the game of 20 questions, we have the user think of an animal and then we ask yes-or-no questions to try to guess what the animal is. Technically, we only have 20 questions to try to guess right, but we’ll give our program as many questions as it needs. Just for fun, our program also learns when it guesses wrong by adding knowledge to its own database.

Briefly, for this assignment, you’ll submit Prolog code that defines:

• response/2 and negate_response/2
• make_win_text/2, loss_text/1, and make_prop_text/3
• ask/2
• guess/2
• both_animal/1
• filled_script/1
• ancestor/2
• hole/2 and hole/3

Here is a code.pl starter file. You can find each TODO item in the starter file by searching for todo in that file.

1 The animal and script Tables

In a relational database, a “table” has a name (a predicate symbol, in Prolog terms) and a collection of rows, where each row has the same width (the same number of arguments, in Prolog terms). Not entirely coincidentally, these are exactly the key pieces we use to define a predicate to Prolog. So, for example animal/3 is a table named animal with three arguments.

Our 20 Questions game will work from knowledge about animals collected in two forms.

First, we’ll know basic attributes about some animals in our animal table. For example, if the information we needed to know were:

We might store that in Prolog like this:

% animal(Name, Property, YesOrNo) indicates that the animal named Name
% either has the property Property (if YesOrNo == yes) or does not
% (if YesOrNo == no).
animal("an elephant","larger than a breadbox",yes).
animal("an elephant","a mammal",yes).
animal("a sengi","larger than a breadbox",no).
animal("a komodo dragon","larger than a breadbox",yes).
animal("a komodo dragon","a mammal",no).

We’ll also track the “script” our program will follow when asking yes-or-no questions. It always starts with the same question and, on a “yes”, proceeds to the same subsequent question. On a “no” it might ask a different question from the “yes” one.

The script is defined by the table script/4:

% script(ThisNode, Property, YesNode, NoNode) means that when we're at
% the node with the identifier ThisNode, we ask about Property. On a
% yes answer, we move to YesNode. On a no answer, we move to NoNode.
script(start,"larger than a breadbox",bbyes,bbno).
script(bbyes,"a mammal",mmyes,mmno).

Except for the special start node in the script (which is where our program starts playing), node identifiers are completely arbitrary. They just need to be different from each other.

2 Game Play

Once it’s complete, the interface to our game is through two propositional atoms: play starts a game and dump_all writes out the contents of the database (the animal and script tables) in case you want to use that as your new database for your next run!

Our program will keep asking questions until it gets to the end of its script. At that point, if our script and animal tables were constructed correctly, it should have just one animal left that meets all the properties determined. It guesses that animal.

If it’s right, then it wins! If it’s wrong, it asks the user what animal they were thinking of, asks them for help telling the difference between that animal and its guess, inserts new knowledge about the new animal (about which it may know a lot, depending on what it asked up to this point), and finishes the game.

You can see what a couple of rounds of the game look like in this trace of play.

3 Your Job for the Game

The game requires a lot of input/output. The “learning” part where we expand the knowledge base requires using assert/1, which dynamically inserts new clauses into the knowledge base. We’ve provided almost all the I/O and all the uses of assert for you.

Your TODO items to make the game run are:

• Parsing and manipulating yes-or-no responses: response/2 and negate_response/2. These are both quite short.
• Setting up text for the program: make_win_text/2, loss_text/1, and make_prop_text/3. The last is harder than the others, but all should be quite short.
• asking the user for a yes-or-no answer: ask/2. This is the only input/output we ask you to do. Play around with it! Note that it relies on response/2 above. See the trace of play for examples of how it works.
• Making a final guess in the game: guess/2 requires understanding a bit about lists and Prolog “functions” (which are not functions in the normal sense at all but compound terms). You can finish it with some reading in the file and a bit of playing around before we even get to lists.

4 Your Job Beyond the Game

We would also like you to design some extra predicates that aren’t needed for the game but help you learn Prolog. Your TODO items for this part are:

• both_animal/1: true for any animal in animal/3 that has a property whose “Holds?” value is yes and a property whose “Holds?” value is no. (Not necessarily the same property.. and presumably not the same property in any well-designed database!)
• filled_script/1: true for any node in the script for which some animal has its property as a yes and some animal has its property as a no. (Again, not neccesarily the same animal.. and presumably not the same animal in any well-designed database!)
• ancestor/2: ancestor(Node, Ancestor) is true if Ancestor is reachable by working our way “back” through the script. Unusually, we require you to produce results in a particular order, which is also not the usual order that “good” Prolog code would produce them: produce the furthest-back ancestor first, working your way forward to Node itself. Significant partial credit is available if you ignore this ordering constraint, and it’s very easy to take correct code that gets the ordering wrong and turn it into correct code that gets it right.
• hole/2 and hole/3: These are more complex predicates designed to locate a particular problem in the KB. Read the documentation in the file for more information, and rely on the helpers we provide.

5 Bonuses (Boni?)

There are mulitple bonuses available here.

Complete the main code and submit it before working on any bonus. Do NOT submit bonus code to the main assignment, as it may lose marks.

This is hand-graded; so, you need to very very clearly guide us to what you added, why, how it works, and how to test it, or you don’t get any bonus points. Have comments at the top explaining this to us.

You can ONLY earn BP marks if you have already earned all available marks on the main submission. (That is, you’ve passed all the tests in the main submission.) Even if you submit great work, if you haven’t earned all available marks on the main submission, we won’t grade the bonus. So do the main submission first before any bonus work.

5.1 Yeah or Nah (+1BP)

Make awesome extensions to response/2 so that users can answer in many different ways when we ask yes-or-no questions. How significantly do you need to extend to get a bonus point? Enough for it to be cool. If you’re worried you might not get that far.. it’s a bonus point! It’s barely worth anything! Just don’t do it!

5.2 Shi or Bu (+1BP)

Internationalize the game into the language of your choice. Note that only two sections need to be modified for this (unless your language doesn’t fit with some grammatical assumptions we made in the structure of the game): the text section and the dabatase for animal and script. Be sure to internationalize everything consistently!

(Oops: we left a comment about dump_all and an error message elsewhere. Neither of these is part of the core game; you can ignore them if you want!)

5.3 Ask Back Better (+2BP)

Handle a couple of special cases we ignored. This is worth +2BP because it is hard.

First, our game can land at a final node (one with no script) where there are multiple animals that all match the properties discovered so far. Do something sensible in that case! That could mean asking about each possible animal in turn and only giving up when they’re all gone (but in that case, it should learn appropriately when it gives up). Or, that could mean giving up right away and asking the user for a question that helps it distinguish among the remaining animals. Or maybe there’s some other strategy we’ve missed. It’s up to you! However, if you ask the user for more information, be sure to update the KB appropriately.

Second, our game can land at a final node (one with no script) where there are no animals that match the properties discovered so far. Again, do something reasonable… probably asking for help from the user! Be sure to give them all the information they need to proceed and to update the KB based on what they tell you.

(The improved game should be able to start with an animal table that doesn’t fit well with the script table and use the learning step to gradually fix up the mismatch.)