Lab 18: Putting together some pieces

This lab gives you a chance to practice program design using several concepts from the semester.

1. Introduction

In class yesterday we wrote most of a program to play one side of the game Twenty Questions. The program is even designed to “learn” as it plays, collecting additional questions and guesses into a decision tree. In today's lab, you will be extending that program in a variety of ways, giving you a chance to work with ideas from earlier in the semester.

To get started, clone the repository:

hg clone /cslab/class/csci235/labs/lab18
cd lab18

This code is descended from what we had at the end of class; the biggest changes are that I have filled in the documentation and more fully separated the user-interface code.

As you work today, take advantage of the fact that you have a Mercurial repository. Be sure to commit as you complete various features--and especially before you try something that might make a mess.

2. Provide ways for the human player to quit

There is presently no good way to quit the game. It should be pretty easy to ask the user before starting a new game; so add that. Also, come up with a way that the user could quit at any of the yes-no questions while playing the game. Hint: You need to exit from a potentially deep series of calls to the ask() methods. Can you think of a good way to do that? A further hint.

Note that, for the next step, you'll want to quit the program in a way that makes it possible to save what the program has collected.

3. Saving and restoring questions

Add appropriate methods to save the decision tree in a file and to load a decision tree from a file. As we discussed at the end of class, you can do the saving by adding a write() method to Node and its subclasses; those can recursively walk the tree.

I recommend that you write each node as a single line, and that you label each with something like "A:" or "Q:" so that you can easily tell what class you have when you read it.

Recall that there are three usual orders for traversing a tree: preorder, in which you do a node before its children; postorder, in which you do a node after its children; and inorder, in which you do a node between its children. Writing in any of these orders is straightforward; the question you need to think about is which order will be easiest to read. Add a comment near the beginning of Questions.java that describes the format in which files of questions are written.

A sensible way to start would be to read from and write to a fixed filename. You can finesse the problem of getting started by using the editor to make a file that has a first guess in it. Be sure that you catch all reasonable exceptions and at least print an appropriate message before you give up and quit.

3. Command-line argument

Fix the program so that if it is started with an argument, the argument will be used as the filename, but use a default filename if there is no argument.

If reading the file fails, come up with some way to prime the tree. (At present, the program starts by guessing "dog". You might come up with a mechanism that would make more sense.)

When the user quits, write the tree to the same filename from which it was read.

4. More improvements

As time permits, come up with additional ways to improve your program. Here are some suggestions:

• Consider having the program work with a "topic" for its questions (instead of always being animals). Come up with a way to add that to your file format, but make the program work if the file doesn't specify a topic. Give a chance to specify a topic when priming the tree if the file can't be read.
• Have the program print out how many different animals it knows about when it reads from a file.
• Make the handling of yes/no questions work better, by ignoring case, by allowing abbreviation, and by asking again if the answer is not clearly 'yes' or 'no'.
• Print the number of questions that were required when the program guesses correctly.
• Keep score across multiple games, with how many times it is successful, how many times it failed, and the average number of questions required when successful.

Feel free to come up with your own ideas. Describe them at the end of the header comment in the file Questions.java.

5. Turn in

Turn in your source files with the command

/cslab/class/csci235/bin/handin lab18 *.java