[50 points] Write a Java program that uses binary decision trees
to play the game of twenty questions.
For this assignment,
the game works as follows. The player (human)
thinks of something X at the beginning
of the game and answers the program's questions truthfully.
(Initially the decision tree is empty; the
program may state this and prompt for an item to place at the root
of the tree or it may have the initial item built in by you.)
Leaf nodes contain items; internal nodes contain questions that lead either
left (yes) or right (no) to the known items. At an internal node,
the program poses the question at that node and descends either left
or right depending on the player's input.
This process repeats until a leaf
node is encountered. The program then queries whether the item Y at
the leaf is the player's item X.
If Y matches the
player's item X, the game concludes and another should start.
Otherwise, the program prompts for a question that separates X from Y.
It then modifies the tree to make the leaf previously holding
Y an internal node with question
Q and new left and right children (leaves) holding items X and Y.
A new game should then start.
A transcript of sample play.
Note: it will take very many plays to accumulate a database capable
of correctly determining the thought-of item. You may wish to
restrict your input (items/questions) to a subject of interest to you.
To get you started, a class for reading string input and prompting
yes/no is available in ~lorenz/cs35-2/hw6/input.java
A skeleton for your program is available as
~lorenz/cs35-2/hw6/twenty-template.java