The lab for this week is to write a basic "twenty questions" game where the user thinks of some animal and the computer tries to guess what the user is thinking of, by asking a series of yes/no questions. The program will use a binary tree to store the questions that the computer will ask, and to represent the action that the computer takes in response to the user's yes or no answer. The computer can also "learn." When the computer does not guess the user's animal, the computer can get a new question from the user that it can add to the tree.
Start a new Eclipse project named lab5. Add the file TwentyQuestions.java to your project. Since the program uses TextIO, you will also need to add a copy of TextIO.java to your project. Finally, copy the file TwentyQuestionsDataCS225.txt into your home directory. You can find all these files in /classes/s10/cs225.
In addition to the programming exercise, there is written exercise for this lab that asks you to write up some thoughts about what you might work on for a final project in this course.
This lab is due next Thursday. But because of the test next Wednesday, I will be willing to accept this lab a day or two late.
The file TwentyQuestionsDatCS225.txt is a data file for the program. The program looks for this file in the user's home directory. The name is chosen so that it is not likely to conflict with any other file in the home directory. This data file contains a representation of the binary tree that is used by the program. The program reads the tree from this file when it starts up. When the user quits the program, the tree is written back to the file, including any changes that have been made. This allows the program to "remember" the changes and "learn" new questions over time. The starting version of TwentyQuestions.java already reads in the file. To make it write the file, you have to implement the writeTree() method. The binary tree must be written in exactly the right format so that it can be read back in by the readTree() method.
The binary tree is implemented using the following class to represent nodes in the tree. Please read the comment to learn how it is used.
/**
* A class to represent nodes in the binary tree that
* holds the questions. There are actually two types
* of nodes, depending on the value of the finalAnswer
* field.
*
* If finalAnswer is true, then the node represents a guess
* by the computer, and the question field should contain only
* the name of the item that is being guessed, such as "a dog"
* or "a tube worm". In this case, the node is a leaf, and the
* yes and no fields are ignored.
*
* If finalAnswer is false, then the node represents a
* question that the computer will ask. The question field
* contains the complete question, such as "Is it a mammal?"
* or "Are you thinking of a mammal?". The yes and no fields
* point to the subtrees that correspond to the answers "yes"
* and "no" to the question.
*/
private static class TreeNode {
boolean finalAnswer;
String question;
TreeNode yes;
TreeNode no;
}
Note that this class uses yes and no as pointers to the left and right subtrees. Also, note that only nodes in which finalAnswer is false have subtrees; nodes in which finalAnswer is true are leaves on the tree.
The data in the original TwentyQuestionsDatCS225.txt file create a tree that looks like the following illustration:
To use this tree, the computer starts at the root and asks the question that is stored in the root, "Is it a mammal?" If the user answers "yes", the computer moves on to the left (or yes) subtree; if the user answers "no", the computer moves on the right (or no) subtree. It then asks the question in that node, and it continues down the tree in this way until it gets to a node for which finalAnswer is true, such as the "an elephant" node in the illustration. At that point, the computer makes its guess, and the user has to say whether or not the computer is correct. If the computer is wrong, then the program will want to extend the tree by adding a new question that the computer could have asked. Here is the complete dialog from one run of a completed version of the program, to show you what the interaction should look like. The user's responses are shown in bold:
Welcome to the game of Twenty Questions! Think of any item in the category "animal"... OK, let's begin. Is it a mammal? yes Do people commonly keep it as a pet? no Is it a farm animal? no Are you thinking of a an elephant? no OK, you got me. What were you thinking of? a tiger Please help me to improve my knowledge! What question could I have asked to distinguish between "an elephant" and "a tiger"? Does it eat meat? For "a tiger", is the answer to the question "Does it eat meat?" YES or NO? yes Do you want to play again? no OK. Bye for now!
At the end of the game, the "an elephant" node has been replaced by a question node containing the question entered by the user, "Does it eat meat?" If node is the pointer to the node, then the transformation that is made to the tree looks like this, with the original node on the left and the new branch of the tree on the right:
It is important to note that node is still pointing to the same node after the change. Only the contents of that node have been changed.
You should implement the play() method in TwentyQuestions.java. It should play one game against the user, and should modify the tree, as in the example, if the computer's final guess is incorrect.
Your programming assignment for this lab consists of implementing the play() method and the writeTree() method. I suggest that you test your program at several points along the way as you develop it. Start by making the computer play a game based on the data in the tree, without trying to make modifications to the tree. Once that works, you can add the code for adding a new question to the tree. The writeTree() method is a separate problem that you can work on and test separately.
It might seem early to be thinking about a final project. But you should already be looking for ideas. For this lab, I am asking you two write short descriptions of two possible projects that you might be interested in working on. At most one of the two proposals can be a game. Note that you will not be required to actually use either idea for your final project. You should write a paragraph about each possible project. Describe what problem the program will address and how it will be used. If you can, say something about the things that you would need to learn in order to complete the program.
At this point, you should not worry about whether your idea is feasible. You do not have to pick a program that you already know how to write -- in fact, that would be kind of pointless. Don't pick something that you could have done at the end of CPSC 124! A good project will use more complex algorithms or data structures. It might use more advanced GUI and event-handling techniques. It might use networking, files, or multi-threaded processing. Your project ideas might help in planning the rest of the course.
And you do not necessarily have to be very original. If there is some program that you like using, you can propose developing a similar program.
As for project ideas, games can make good projects. Tetris is a fairly ambitious choice. Other arcade games are possible. You might implement a classic board game, such as snakes and ladders. How about a poker game for several players, in which the computer just runs the game? (If you wanted to try to get the computer to play poker, that would be quixotic but interesting.)
Maybe some kind of useful GUI tool. How about something to help the department chair make up a schedule of which professors will teach which courses in the Math/CS department. That's my idea. What would you find useful? (One student made a program to grab and display information about current stock prices from the web.)
Painting and drawing programs are always popular. There are some sample programs in Chapter 12. You might extend or improve one of those. Or work on something different, like a program for making modifications to photographs (such as color adjustment, blur, changing to black-and-white).
For students who have taken linear algebra, a program to do some matrix and vector operations might be nice. Other math programs, such as a function grapher or a differential equation solver, are possible. For computer science, if you've taken CS 229, an NFA to DFA converter would be nice. Or a more full-featured Turing machine simulator, with better ways to design the machine. The basic idea is, something to help students learn about or understand "X". Maybe there is some program that would be useful in some other major?