20 Questions

Question-answering with binary trees and recursion.

ed Workspace

Table of contents

1. QuestionsGame
   1. Method summary
   2. File format
   3. Development strategy
2. Full example
3. Grading
4. Reflection
5. Submission

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

Implement a 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 QuestionNode. The 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.

Note

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.

Method summary

public QuestionsGame()

Initializes a new QuestionsGame object 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 input scanner. 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 prompt until 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.

File format

read and write will be interacting with files containing questions in a standard format.

Each 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 readTree and writeTree methods discussed in class for examples of formatting trees as flat files.

Note that QuestionMain will always read and write to a file named questions.txt. To start with the tree from spec-questions.txt or 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!

Development strategy

Before beginning, write the method header for each method (but not any of the body) so that QuestionMain compiles.

1. Decide what fields belong in the QuestionNode and QuestionsGame classes.
2. Implement the constructor for QuestionsGame.
3. Implement write, which writes the current question tree to the given output.
4. Implement read, which reads in a question tree from the given input.
5. Implement askQuestions and then play the game! When playing the game, add questions one by one and check each behavior.

Full example

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.

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

Grading

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!

Anti-pattern

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

• Not using calls on this(…) to eliminate redundancy by having one constructor call another.

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.

Miscellaneous errors

• Using \n to produce more than one line of output with a single print, println, or printf call.

Reflection

Create a new file reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):

1. What did you learn this week?
2. What did you enjoy in the course this week?
3. What did you find challenging or frustrating this week?
4. What did you find particularly helpful for your learning this week?

Submission

Submit QuestionsGame.java and reflection.txt to Grade-It!