Lab Project #3 – Binary Tree Guessing Game
In a guessing game, you think of something and have to guess what it is by asking you
questions that have. yes or no answer. Write : program that asks the questions for me.
This program uses a binary decision tree that grows as the game progresses. Instead of
creating the tree before it is used, the program acquires facts from the user and adds them to
the decision tree. Thus, the program learns by playing the game and becomes more proficient
over time.
To simplify the problem, let’s restrict your choice of things. For example, suppose that you
think of a country. The program could begin with the simple three-node tree pictured here:
[Graph]
With this tree, the program asks the question in the root and makes one of two guesses,
depending on the answer to the question. Here is one possible exchange between the
program and the user (user replies are bold):
Is it in North America?
> yes
My guess is U.
S.A. Am I right?
> yes
I win.
Play again?
The program has guessed correctly; the tree remains unchanged.
Now, suppose the user is thinking of something else. The exchange might go like this:
Is it in North America?
> no
My guess is Brazil. Am I right?
> nо
I give up; what are you thinking of?
> England
Give me a question whose answer is yes for England and no for Brazil.
› Is it in Europe?
Play again?
With this new information, we augment the tree, as in the picture below:
[Graph]
We replace the contents of the leaf that contained the wrong answer -Brazil in this case-
with the new question provided by the user.
We then give the leaf two children. One child
contains the guess that was in the former leaf (Brazil), and the other contains the user’s
answer (England) as a new guess. The program now can distinguish between Brazil and
England.
You will need to use the provided zipped folders, StackAndQueuePackage and TreePackage,
to compile your finished program. Both Package folders need to be in the same folder as
GuessingGame.java
[Picture]
Finish the code in the file GuessingGame.java and submit in Canvas. You may keep the same
file name. You do not need to submit the Package folders – they are for your use when
developing your program.
public class GuessingGame
{
public static void main ( String I args )
{
String response;
DecisionTree <String > gameTree = new Decision Tree <> ( “Is it in North America?” “Brazil” “U.S.A.” ):
do
System . out . printin (“Think of a country and I will guess it.
game Tree = play (gameTree);
System. out . print (“Play again? ” );
response = getUserResponse();
} while ( response . toLowerCase (). equals (“yes” )):
System . out. printin ( “Bye!” );
} // end main
public static String getUserResponse ()
{
Scanner stdin = new Scanner ( System . in );
return stdin . nextLine ();
} // end getUserResponse
public static boolean isUserResponse Yes ()
String answer = getUserResponse ()
if ( answer. toLowerCase 0. equals ( “yes” ))
return true;
else
return false;
} // end isUserResponse Yes
public static DecisionTree <String > play (DecisionTree String > gameTree )
{
// Initialize current node to root
gameTree. resetCurrentNode ():
while (! game Tree. isAnswer ()
// Ask current question
System. out . printin ( gameTree getCurrentData());
if ( isUserResponseYes ())
gameTree. advance ToYes();
else
gameTree. advanceToNo ();
// end while
assert game Tree. isAnswer (): // Assertion: Leaf is reached
// Make guess
System . out. printin (“My guess is + gameTree. getCurrentData () +”. Am I right?” );
if ( isUserResponse Yes ())
System. out. printin (” I win.” );
else
learn (gameTree);
return gameTree;
} // end play
// Responds to the user when this program makes a wrong guess and
// extends the decision tree so that this guess is not made again.
public static void learn (DecisionTree <String > gameTree )
{
System. out. printin (*I give up: what are you thinking of? ”
//TODO set correct answer string
//TODO set current answer string
String correctAnswer = getUserResponse ();
String currentAnswer = gameTree . getCurrentData ()
System . out. printin (“Give me a question whose answer is yes for “
correctAnswer+ ” but no for ” + currentAnswer):
String newQuestion = getUserResponse ();
// TODO create new question with current data
// TODO set responses based on current answer and correct answer
gameTree. setCurrentData (newQuestion);
gameTree. setResponses (currentAnswer, correctAnswer);
} // end learn
} // end GuessingGame
/*Sample output:
Think of a country and I will guess it.
it in North America?
res
Ay guess is U.S…. Am I right?
res
win.
Play again? yes
Think of a country and I will guess it.
S it in North America?
no
I guess is Brazil. Am I right?
no
I give up; what are you thinking of?
England
Give me a question whose answer is yes for England but no for Brazil
Is it in Europe?
Play again? yes
Think of a country and I will guess it.
Is it in North America?
no
Is it in Europe?
ves
My guess is England. Am I right?
yes
I win.
Play again? no
Bye!
*/
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
