Compsci 100, Fall 2009, Animal/Twenty Questions Howto

TwentyQ Version 2.0

*
One key feature of web 2.0 sites is interactivity and generative or user-generated content. To make this possible in this program you should submit a file that allows a game to be played to this website to which you can upload a file which will be identified with your net-id and a category you choose. This site is hardwired into the program when the user chooses URL as shown on the left, but the user can change the URL. Once loaded the user can choose a category and one game in this category to be played -- the game is loaded from the web into the program. As more students add content the game should be more fun to play. We'll give bonus points to the game that is judged the best by the class.

Starting a Game

In the screen shots below the user is selecting a quiz about buildings by clicking on the folders which represent quiz categories and then on a file within a folder which represents a quiz/game of twenty questions. The folders shown on the left come from choosing to load via the web using the specificied URL. On the right the game has been started and the first question appears in the game info panel of the GUI.

* *

Playing the Game

Here's the progression of a series of questions from the animal.txt file. The file is shown and visualized at the bottom of this web page. The sequence of screen-shots and explanations should be read left-to-right and top-to-bottom, so the first two shots are below, then the game progresses. The view changes in each case because the model's processYesNo method makes a call to the view to update appropriately depending on the user's response. This sequence of calls between the model and the view is explained in more detail below.

Answering the first question in a game where the user is thinking of a chicken.   So it has feathers and lives in a barnyard, what's next?
start   start
Wow, the computer guessed my animal!   The computer wins! (by guessing your animal)
start   start

Adding New Knowledge

Here's a different sequence of user-responses, where the user is thinking of a lion. These responses show how the user is prompted for a new animal and a question to differentiate the new animal from the incorrect one guessed/chosen by the computer. This sequence also represents a series of calls between the mdoel and the view that is explained below.

Answering the second question in a game where the user is thinking of a lion (and already said "no" to having feathers).       So it is a mammal, but doesn't have stripes
start   start
No stripes, and now it doesn't hop     Nope, not an elephant.
start   start

Now the GUI/View is called by the model to prompt the user to enter what information was being thought of (it was lion, not elephant, the user indicates this by typing the answer into a dialog box as shown below. Note that the model has displayed the path from the beginning by calling the view appropriately -- the model must keep the path or information that allows the path to be recreated to make this possible. The user then enters the new information, in this case that the user was thinking of a lion.

When the model realizes it has guessed wrong, which happens when the user responds "NO" and the current node of the binary tree representing the game is a leaf node, the model notifies the view of the path that the user chose by calling myView.update with a string representing the path. Then the model calls the view's getNewInfoLeaf method to display the dialog labeled New Information Needed which can be dragged/moved so that the user can see the responses in the main game window. This method in the GUI/view will get information from the user then call the model's addNewQuestion method which you will implement. Before calling myView.getNewInfoLeaf() you may need to store state in the model since the view will call the model's addNewQuestion method

start

In the code you write in addNewQuestion you'll prompt the user appropriately by calling myView.update with a string displayed to the user. You then call myView.getDifferentiator which causes the GUi/View to prompt the user to enter a question differentiating a lion from an elephant to grow the tree of knowledge used in the game. The GUI/View than passes the user's question to the model's addNewKnowledge method.

Again, the user can drag/move the New Question Needed dialog to make the main game window more visible.

start

At this point if we play a new game the question "Does it have tusks" will be incorporated into the tree -- it is the differentiator leading to the leaves elephant and lion. The user can play more, and ultimately decide to save the game/tree to a file for playing again. Saving a file is a menu-option which the view relays to the model's method write which takes a FileWriter parameter and writes a tree to this file so that the game can be played again by reading from the file. The user chooses to save a game from the File menu as shown below.

The Model for the Twenty Questions Game

Model communicates with View

To display messages to the user the model can call myView.showMessage to display one string at the bottom of the view, e.g., the number of nodes in the tree as shown in the screen shots above, or myView.update to display a string. THe String passed to update can have newline characters in it which cause linebreaks in the display. For example the lines below generate part of the prompt shown in the screen shot above. StringBuffer sb = new StringBuffer(); sb.append("To add new knowledge to this game\n"); sb.append("you must create a question that differentiates\n"); sb.append("from my guess and what you were thinking of.\n\n"); sb.append("What has a YES answer for:\n"); ... myView.update(sb.toString()); As shown in the screen shots above, the user selects a file in which the tree/game will be saved. The default dialog box for choosing a filename specifies the name of the file the user originally entered, but you'll probably want to user a different name at first to avoid overwriting the file until you know your code works.

The AnimalGameModel Class

Your model class will need to implement IAnimalModel to play the game. You can use the model you're given which has stub methods with no code for all the methods specified in the interface.

Recall that in the MVC architecture we used previously communication from the View came to the model via the process method. In this program, however, the view communicates with the model using three methods. Some of the calls are initiated directly by the user, e.g., loading a new file or playing a new game. Other calls are started by the model itself, e.g., the model calls an appropriate method in the view which in turn calls a method in the model, e.g., when adding new information and questions to a game.

See the javadoc in IAnimalModel for details but the idea is you'll write these methods which are called by the view.

The model class communicates back-and-forth with the view to update the state of the game, e.g., to move down the tree and then restart from the root of the tree for a new game. The model should maintain as an object invariant a reference/pointer to the current node in the tree whose question the user answers using the view. For example, this current node is initially the root. Depending on the user's response to the first question (and to subsequent questions) the current node is updated to be the left- or right-child according to the user anwering 'yes' or 'no'.

You'll need a myCurrentNode and a myRoot to help traverse the tree. You'll need other state as well, you'll need to determine what the appropriate satte is.

In the process of playing a game, myCurrent will eventually reach a leaf node. Then you'll need to call the appropriate view methods to start the process of adding new information to a tree/game.

You'll want to implement private helper methods in your AnimalGameModel class to help with the methods you must implement as part of the interface.

You'll need to implement a method to write information to a file. To write the file you'll need to read the API for java.io.FileWriter, in particular you'll only need to use the the write method that accepts a String parameter -- be sure to terminate each string with a newline character, e.g., something like the following:

writer.write(root.info + "\n"); // write root info to file

The newline character, "\n", writes a "new line" and is read as 'slash-n' or 'backslash-n'.

Input/Output, Preorder Traversals

For the run above, the sample file animal.txt is reproduced below. 



    #Q:Does it have feathers
    #Q:Does it live in a barnyard
    Is it a chicken
    #Q:is it wise
    Is it an owl
    #Q:does it gobble
    Is it a turkey
    #Q:does it say "Nevermore!"
    Is it a raven
    Is it an eagle
    #Q:Is it a mammal
    #Q:does it have stripes
    Is it a tiger
    #Q:does it hop
    Is it a kangaroo
    Is it an elephant
    Is it a gila monster

The tree that corresponds to this file is shown below. You'll need to construct a tree like this in the program you write. Note that yes answers in the tree are shown as left/blue arrows, no answers are right/red arrows. The leaf nodes are shown only with the animal information rather than the entire question, e.g., Is it an elephant

Reading the Tree

By far the easiest way to read the tree is to leverage the power of recursion. When you read a file via the scanner, read one line at a time. The code below reads every line in the file, you'll need to do this, but not use a loop --- rather you'll use recursion instead. For example, the code below reads an entire file one line at-a-time. public void initialize(Scanner s){ while (s.hasNextLine()){ String line = s.nextLine(); // process line } } Alternatively, you could read every line recursively. In your code you'll make more than one recursive call, e.g., to read both left and right subtrees. Furthermore, the recursive method might return a value, e.g., a TreeNode rather than the vague use of process in the comment in the code snippets immediately above and below. public void readAll(Scanner s){ if (s.hasNextLine()){ String line = s.nextLine(); // process line readAll(s); // read the rest, recursively } }

When reading a tree, every internal node has two children. So when you read a line representing an internal node, which can be identified by the beginning #Q: as seen in animal.txt, you'll make two recursive calls to read the yes/left and no/right subtrees.

If the line read represents a leaf node, simply return a leaf node without making any recursive calls.

In either case you'll create one new AnimalNode and return it. 

  Question
  Yes Answer (left subtree)
  No  Answer (right subtree)

Questions are identified by the three-character string #Q: at the beginning of a line, lines that do not begin with the string #Q: represent answers/animals. Some lines may begin with comments, the characters // at the beginning of a line mean that line should be skipped. You'll need to write a recursive method that reads each line of the file and processes one line in building a tree.

The key in the recursion is to recognize that no recursion is necessary when reading a leaf -- and a leaf is any line that doesn't begin with #Q:. If an internal node of the tree is read, then two recursive calls are needed: one for the "yes" branch and one for the "no" branch.