Question-answering with binary trees and recursion.
20 Questions is a guessing game in which the objective is to ask yes/no questions to determine an object. In our version, the human player begins a round by choosing some object, and the computer attempts to guess that object by asking a series of yes/no questions until it thinks it knows the answer. Then, the computer makes a guess. If the computer’s guess is correct, the computer wins. Otherwise, the player wins, and the computer will add the object to its knowledge base.
QuestionsGame class to represent the computer’s tree of yes/no questions and answers for playing 20 Questions using the provided private static inner class
QuestionsGame class keeps track of a binary tree whose
QuestionNode instances represent questions and answers. Every node contains a
String data field representing the question or answer.
- Even though the name of the game is “20 Questions”, the computer is not limited to only 20; the tree may have a larger height.
The leaves of the tree represent possible answers (guesses) that the computer might make. All the other nodes represent questions that the computer will ask to narrow the possibilities.
- Left branch
- Indicates the next question the computer asks if the answer is yes.
- Right branch
- Indicates the next question if the answer is no.
The game is played by starting at the root, asking questions for each of the branch nodes, and going down the the tree based on the player’s answer. Once a leaf node is reached, the computer will ask if that answer is the correct one.
- Initializes a new
QuestionsGameobject with a single leaf node representing the object “computer”.
public void write(PrintStream output)
- Stores the current tree to the given
output. This method can be used to later play another game with the computer using questions from this one.
public void read(Scanner input)
- Replaces the current tree by reading another tree from the
inputscanner. Assume the file is valid. Call
input.nextLine()to read entire lines of text.
public void askQuestions()
- Play a complete guessing game with the player using the current tree, asking yes/no questions until reaching an answer. A game begins with the root node of the tree and ends upon reaching an answer leaf node. If the computer wins the game, print a message saying so. Otherwise, ask the user for
- what object they were thinking of,
- a question to distinguish that object from the player’s guess, and
- whether the player’s object is the yes or no answer for that question.
public boolean yesTo(String prompt)
- Asks the given question
promptuntil the user types “y” or “n”. Returns true if “y”, false if “n”. Use this method whenever it’s necessary to ask yes/no questions to the player.
write will be interacting with files containing questions in a standard format.
QuestionNode should be represented as a non-empty sequence of line pairs. The first line of the pair should contain either “Q:” or “A:” to differentiate between questions (branches) and answers (leaves). The second line of the pair should contain the text for that node (the actual question or answer). The nodes of the tree should appear in pre-order. Refer to the
writeTree methods discussed in class for examples of formatting trees as flat files.
QuestionMain will always read and write to a file named
questions.txt. To start with the tree from
big-questions.txt, copy the contents of those files to a file named
questions.txt. Be careful since the program will write the tree to this file every time!
Before beginning, write the method header for each method (but not any of the body) so that
- Decide what fields belong in the
- Implement the constructor for
write, which writes the current question tree to the given
read, which reads in a question tree from the given
askQuestionsand then play the game! When playing the game, add questions one by one and check each behavior.
Q: Is it an animal? Q: Can it fly? A: bird Q: Does it have a tail? A: mouse A: spider Q: Does it have wheels? A: bicycle Q: Is it nice? A: TA A: teacher
The following output log shows one game being played on the above tree:
Welcome to the cse143 question program. Do you want to read in the previous tree? (y/n)? y Please think of an object for me to guess. Is it an animal? (y/n)? n Does it have wheels? (y/n)? y Would your object happen to be bicycle? (y/n)? y Great, I got it right! Do you want to go again? (y/n)? n
Initially, the computer is not very practiced at guessing objects, but it gains experience each time it loses a game. If the computer guesses incorrectly, it asks the player to give it a new question to help in future games. For example, suppose in the preceding log that the player was thinking of a car instead.
Welcome to the cse143 question program. Do you want to read in the previous tree? (y/n)? y Please think of an object for me to guess. Is it an animal? (y/n)? n Does it have wheels? (y/n)? y Would your object happen to be bicycle? (y/n)? n What is the name of your object? car Please give me a yes/no question that distinguishes between your object and mine--> Does it get stuck in traffic? And what is the answer for your object? (y/n)? y Do you want to go again? (y/n)? n
Using the new information from a lost game, the computer will replace the incorrect answer node with a new question node that has the old incorrect answer and a new correct answer as its children.
Example questions.txt after adding "car"
Q: Is it an animal? Q: Can it fly? A: bird Q: Does it have a tail? A: mouse A: spider Q: Does it have wheels? Q: Does it get stuck in traffic? A: car A: bicycle Q: Is it nice? A: TA A: teacher
Every method with complex behavior should be implemented with recursion rather than iteration. A full-credit solution should have zero loops. Avoid unnecessary logic such as extra base cases or recursive cases. Use the
x = change(x) pattern to simplify code and use the Output Comparison Tool to check the output format!
- At the end of a game lost by the computer, do not “morph” what used to be an answer node of the tree into a question node. This is considered bad style because question nodes and answer nodes are fundamentally different kinds of data.
- Class design errors
- Data structure errors
- Not using
x = change(x)when appropriate to simplify code.
- Poor choice of constructors when designing a node class. For example, including unused constructors, missing helpful constructors that eliminate redundancy, or not having a fitting constructor for a reoccuring type of node.
- Not using
- Miscellaneous errors
\nto produce more than one line of output with a single
Create a new file
reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):
- What did you learn this week?
- What did you enjoy in the course this week?
- What did you find challenging or frustrating this week?
- What did you find particularly helpful for your learning this week?
reflection.txt to Grade-It!