Java Reference
In-Depth Information
23.24
Example: Guessing game. In a guessing game, you think of something and I have to guess what it
is by asking you questions that have a yes or no answer. Suppose that a program asks the questions
for me. This program uses a binary decision tree that grows as the game progresses. Instead of cre-
ating the tree before it is used, the program acquires facts from the user and adds them to the deci-
sion 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 in Figure 23-16. 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 blue):
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.
FIGURE 23-16
An initial decision tree for a guessing game
Is it in North America?
No
Ye s
U.S.A.
Brazil
23.25
Augmenting the tree in the guessing game. 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?
No
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 Figure 23-17. 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.
23.26
A class for the guessing game. We demonstrate some of the methods declared in the interface
DecisionTreeInterface by implementing part of a class GuessingGame . This class, as shown in
Listing 23-5, begins with a decision tree as a data field and a constructor that creates an initial tree.
The tree has one yes-or-no question as its root and two guesses as children, one guess for each
possible answer to the question. We assume that DecisionTree will have the constructors that we
used here.
Search WWH ::




Custom Search