Snarf the code via Eclipse/Ambient using twentyq, or
browse
the code directory online. The snarf URL is
http://www.cs.duke.edu/courses/cps100/fall08/snarf
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 20q.net. 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.
Initially the program is
run from the main method
in the GameMain.java
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.
Input/Output
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).
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'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.
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
README
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.
