20 Questions

20 Questions

More information about the details of the assignment can be found in the how to.

As mentioned in the bizarrely exhaustive Wikipedia article, Twenty Questions is an example of a binary tree: each node represents a question, and each child an answer, either “yes” or “no”. 20q.net and other variations on the game are more-than-binary trees: they permit “maybe”, “Don’t know”, and other kinds of answers. We’ll be sticking to the simple yes-or-no version of the game.

In this assignment, you will implement a learning version of twenty questions: one that not only plays the game, but learns new objects when it loses. You’ll be able to save your learned tree to disk, so that you can exchange it with a friend, or start up again where you left off.

Check out this page for information on how to play 20 questions.

Twenty Questions is all about working with trees: building them, manipulating them, writing them to disk, reading them from disk, and everything else.

The Assignment

Like Markov, Twenty Questions uses a Model-View architecture; this means we provide the graphical interface (“GUI”), and you write the logic. Note that the interaction between the model and view is more complicated than you’ve seen before; understanding how they communicate is an important part of this assignment.

You’ll be writing code to do four main things:

  1. Read a file that stores a Twenty Questions game tree. The tree represents what questions and nouns the game currently knows about.
  2. Keep track of the state of the game (that is, where you are in the tree) as the player responds “yes” or “no” to various questions. This will let you add a new node to the tree (with an appropriate question) in the event that the program loses.
  3. Keep track of what you need for working communication with the view. This can be tricky: see the how to for details.
  4. Write a file containing a game tree to disk. In combination with item 1, this let you read an existing tree, play the game for a while (adding new things to the tree), and then save the new-and-improved tree. Snazzy!

 

Read and Write
Part of what you’ll be doing is implementing reading trees from disk, and writing them to disk. This will be done using recursion: in particular, the pre-order traversal, which was discussed in class. The code, once finished, is remarkably short: such is the power of recursion.

History
For historical reasons, the code calls the game “Animal” instead of Twenty Questions. You aren’t limited to animals! It’ll do whatever you want.

Grading

  • Correct implementation of tree input and output – 5 points
  • Correct implementation of twenty questions including adding nodes to the tree – 8 points
  • Code style – 2 points. (See below)

Submission
Submit your code and README using Ambient or websubmit. Please make sure you submit the entireassignment each time you submit, including any code we provided, even if you haven’t changed it. You can submit as many times as you’d like; we’ll take the last one.

Code Style
Fact: code is hard to read.
How you lay out your code, and your program, make a big difference in how easy it is to understand. There are (at least!) four people who need to understand your code: you (while writing it), anybody you ask for help, your grader, and you (six months from now, when you look at it to figure out how you did something). While the following rules are not set in stone, they provide a good place to start:

  • Think about how your code is going to be organized before you’ve written it. Good design matters!
  • Give your classes, variables, and methods descriptive names. Naming your variables foo andbar doesn’t say much; xPosition and yPosition are much better.
  • Use Java’s conventions on naming. ClassesAreNamedLikeThis: words are run together, and each word is capitalized. Similarly, methodsAreNamedLikeThis: words run together, and all but the first word are capitalized. Variables are named like methods.
  • Indent your code properly. Roughly speaking, this means “everything inside a curly brace gets indented one extra level.” See the code we provide for how this should look. To make this easy, Eclipse can do it for you: select your code with the mouse, and then do Source -> Correct Indentation.
  • Don’t let your lines get too long. Although Java doesn’t care how long your lines are, long lines are much harder to read. The closest thing there is to a universal standard is 80 characters. Eclipse makes this easy, too: in Preferences -> Text Editors, turn on “Print Margin” and set it to 80. That will add a vertical line at the 80-character mark.

 

Remember: easy-to-understand code makes your grader happy. Happy graders are friendly graders!