CSC 210 Program #3

Twenty Questions

Logistics

Go...

  •  Worth 4 points, or 4% of your class grade
  •  Assigned Saturday April 22, 2006
  •  Due Saturday May 6, 2006 by the end of the day... 2 weeks!
  •  Covers trees, mostly

Description

Have you seen those little "20 questions" electronic games yet. You think of something, and the gizmo asks up to 20 yes/no questions trying to guess what your object is. It's fun.

They sell them at Walgreens, pretty cheap. But not cheap enough, so let's build one.

So, Twenty Questions is a game with two players. The "knower" thinks of something (person, place or thing) and keeps it to himself. The "guesser" tries to guess the knower's thing by asking a series of yes/no questions. If the guesser can identify the thing in 20 questions or less, then he wins.

I have attached one very simple example of how your program might play Twenty Questions. We'll discuss this example at length in class.

Playing

In this case, your program will be the guesser. Your program's guesses will be directed by a decision tree. Our trees will be binary trees. Each node in the tree will contain a String that will be either a question or a guess.

The root of your tree will contain the first question. If the user's response to this question is "yes", then you'll travel to the left child of the node. If the response is "no", then travel to the right child. You'll continue traversing nodes until you reach a leaf node. Leaf nodes in the tree will contain your final guesses, indicating the end of your program's questioning/search.

These question trees are pretty valuable, so we'll save ours in a file so that we can use them and even make them grow.

Learning

Once you "get it", playing is pretty straightforward. Now, building one of these question trees, that's the tough part. As a first step, you'll want to type in a question tree file, and play with it. Once your program knows how to play, you'll want to tell it to learn, so that it can expand its question tree.

When your program reaches a leaf, makes its guess, and is wrong, the program should ask the user:

  1. what he was really thinking of, and
  2. what question would differentiate that object from what your program guessed.

With that information, the new question should be added to that spot in the tree as a new node.

Experimenting

So your program's running. Excellent.

Now, since we have 2 weeks and not 2 years, pick a domain to focus on. You'll want a collection of related things where the number of possible choices is not too great... something like dog breeds or major U.S. cities or football teams or whatever. Then try and construct a "good" question tree and try it out on your family and friends.

We'll try your program in class too. I have no idea how large a tree you need to have before any kind of "wow" factor kicks in, but we'll see. It'll be interesting to see what you guys can come up with.

Implementation

My solution has 3 classes:

  •  public class MyNode<E> - a generic node with data and left and right children
  •  public class MyTree<E> - a generic binary tree
  •  public class TwentyQuestions - my game

The MyTree class is pretty standard stuff. I did not nest/hide my node class within the tree as our book does. Both ways are acceptable, and we'll talk about this in class. In any case, please create your own tree class. I'm not going to be dogmatic about generics or whatever, you just can't use the Java Collections code.

Of course, the TwentyQuestions class is the interesting stuff. I have 4 important public methods:

  •  load - loads a question tree from a file
  •  store - stores the current question tree to a file
  •  play - plays a twenty questions game using the current question tree
  •  learn - adds a question to the tree per the user's instructions

Your file format should be done using a preorder traversal. You'll find pages 413-415 in the text very interesting in this regard.

I don't know how much I/O you've done in 160/161. You'll only need very basic stuff for this program. There's a nice template on handling input/output streams on page 739 of our text. My load() method takes a BufferedReader as a parameter. My store() takes a PrintWriter. The console and files are our two favorite streams, and these classes can handle either. I'll add to the book's offering with these snippets:

// create a reader for console (keyboard) input
BufferedReader reader =
         new BufferedReader( new InputStreamReader( System.in));
 
// create a writer for console output
PrintWriter writer =
         new PrintWriter( new OutputStreamReader( System.out));

Here's some pseudo-code for the play() method:

load question tree
node = root
while node is not a leaf
   ask node's question
   if response is yes then node = left child
   else node = right child
end while
print node's guess
if correct then brashly proclaim victory
else call learn

Here's some pseudo-code for the learn() method:

Ask user what his item was
Ask user for a question to distinguish his item
   from the last node's guess
Ask if the correct response is yes or no
Attach a new tree node with the question
   and proper left/right nodes
store modified question tree

Grading

Same as it ever was...

By the due date, please place your work for Program #2 in your folder on the k: drive. I'll be looking for:

  •  A README file describing the state of your program... what works, what doesn't, etc.
  •  All your *.java Java source code files
  •  All your *.class files... please compile your Java
  •  A javadoc folder with the nifty auto-magic documentation of your classes

Of course, your code must be beautiful and follow the class coding guidelines. Code that does not meet this metric will be served a harsh brand of grading justice.

Etc

I'll post hints and such (like correcting instructor errata) here as the week goes by.

Here are some 20 questions web sites:

I'll bring my 20Q electronic gizmo with me as well.

thanks... yow, bill

...

william.krieger.faculty.noctrl.edu

wtkrieger@noctrl.edu