CompSci 100, Fall 2008, Animal/Twenty-questions


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


You'll be modifying code in a model using binary trees so that a game of twenty questions can be played.

Amusing Gilbert and Sullivan Twenty Questions Game
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 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.
In the game you'll write code for 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.

For infomation about an old TV show (logo above right) named 20 Questions see this Wikipedia article and this link for a technical article on playing twenty questions with a liar.

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.

Consult the howto pages for a sequence of screen shots and more information on playing the game.

Adding New Knowledge

The game is dynamic in supporting the addition of new knowledge and the use of this knowledge in subsequent games. The howto pages show a sequence of screen shots with a complete explanation of how your game should support the addition of new knowledge.

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 howto pages.

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. The model is described in the howto pages.


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 using the model's 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.

More details on the I/O and pre-order traversals can be found in the howto pages.

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 twentyq (not animal).