CompSci 100, Spring 2008, Animal/Twenty-questions


The game of Twenty Questions is sometimes amusing, especially if the domain of questions is one you find interesting. You can play an AI/hybrid version of the game online at, but for this assignment you'll write a program that permits the user to play a dynamic version of twenty questions --- dynamic in the sense that the user can add new questions, save the game, then replay the game with the new questions --- but only yes/no answers are possible when playing the game.

You can see a video of someone playing a final version of the game to see how the GUI works. You're given the GUI for the game and you'll have to complete the model by writing code using binary trees.

Snarf the code via Eclipse/Ambient using animal, or browse the code directory online. The snarf URL is

Playing the Game

Initially the program is run from the main method in the class. Until you complete the model, however, the game won't be complete. When it is, the screenshots below illustrate how the game will be played. Before you can play, you'll need to load a file representing a game. Use the File menu for this and navigate to something like animal.txt or football.txt for playing two different kinds of game. You won't be able to use the yes/no buttons or the newgame menu until you've loaded file since these will be grayed-out or disabled until then.

Here's the progression of a series of questions. 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.

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.

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 tells the computer this is the case.) Note that the model has displayed the path from the beginning by calling the view appropriately -- the model must keep the path to make this possible. The user then enters the new information, in this case that the user was thinking of a lion.

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 view will get information from the user then call the model's addNewQuestion method which you will write.


Now the user is prompted (the model calls the appropriate method in the GUi/View) to enter a question differentiating a lion from an elephant to grow the tree of knowledge used in the game. The model calls the view's getDifferentiator method which, after getting a differentiating question from the user will call the model's addNewKnowledge method.

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


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 Program You Write

You must write a program that allows the user to play a game of twenty questions as described. The user can add new information to the tree as the game is played. The user should be able to play more than once during a run of the program. The user should be able to save the tree to a file specified by the user. You can do this entire assignment by completing the class AnimalGameModel as described in the section below.

Most of the control aspects of the program are already incorporated into the class AnimalGameViewer that is similar to previous view (e.g., Markov) implementations we've seen in other programs. You'll need to implement the AnimalGameModel class so that it works together with the view similarly to the other MVC programs you've worked on this previously.

Model communicates with View

To display messages to the user the model can call myView.showMessage to display one string or myView.update to display all the strings in an ArrayList of strings (or, in general, all the objects in some collection). The model's method addNewQuestion, which has been started for you, shows some of this in action.

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 in the run above a different name is used. It's a good idea to use a different name for the file until you know your program works.

The AnimalGameModel Class

Your model class will need to implement IAnimalModel to play the game, in particular you should start with the AnimalGameModel class given to you and add/modify it as needed.

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 started 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 appropriate methods in the view which in turn call a method in the model, e.g., when adding new information and questions to a game.

See the javadoc for details but the idea is you'll write these methods:

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.

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, 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

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


The input to the program will be any file in the schema below which is the pre-order traversal of a tree representing the guessing game. Note that in every such tree all non-leaf/internal nodes have two children.

You'll do the input from a nested/inner class AnimalReader. This class uses a separate thread for reading to ensure the GUI is responsive even when a big file is read (or a file is read over the Internet via a URL).

  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're given code in the nested-inner class AnimalReader in the method build that reads an entire file line by line. You'll need to replace this method with 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.

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

What to Submit

This assignment is worth 35 points, the breakdown is as follows:

functionality points
read file into tree 6
play game/add info to tree 10
save file properly 4
show path to user 5
coding style/classes 4
data file created 3

You must also submit a README file in which you list all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimated of how long you spent on the program and what your thoughts are about the assignment.

You must create a sample data file whose name indicates something about its contents. The questions should be yes/no questions about any topic, e.g., animals, elements from the periodic table, courses at Duke, and so on.

Submit via eclipse using animal