Description
In this assignment, you’ll implement a 20 Questions game. (It’s called “20 Questions”, but there can be as many questions as you like!) Your program will play 20 Questions with a user. It’ll be up to the human playing the game to come up with a secret object, and then the program will try to guess what the human is thinking of. If the program guesses wrong, then it will ask the human for help learning about the secret object. That means your program will actually get smarter as you play more games!
Your program will store all of the questions (and answers) it knows about as a tree.
There are two possible types of “nodes” in these trees:
Question (also called “internal”) nodes consist of tuples of three things: A question to ask; what to do if the answer to the question is “yes”; and what to do if the answer to the question is “no”. The “what to do” part is simply another, smaller, tree.
Answer (also called “leaf”) nodes also consist of a 3-tuple (also called a “triple”),
but the last parts of the triple are . There is a string representing the answer,
followed by two Nones.
None
A tree is made up of a set of tuples (of tuples (of tuples … )). For example:
(“Is it bigger than a breadbox?”, (“an elephant”, None, None), (“a mouse”, None, None))
represents a tree with one question and two answers.
(“Is it bigger than a breadbox?”, (“Is it gray?”,
(“an elephant”, None, None),
(“a tiger”, None, None)),
(“a mouse”, None, None))
represents a tree with two questions and three answers.
Getting familiar with the trees
The two trees above are already present in the starter file. Begin by experimenting with them a bit in iPython:
In [1]: run proj2.py
In [2]: smallTree
Out[2]:
(‘Is it bigger than a breadbox?’, (‘an elephant’, None, None), (‘a mouse’, None, None))
In [3]: printTree(smallTree)
Is it bigger than a breadbox?
+-Yes: It is an elephant
`-No: It is a mouse
In [4]: mediumTree
Out[4]:
(‘Is it bigger than a breadbox?’,
(‘Is it gray?’, (‘an elephant’, None, None), (‘a tiger’, Non e, None)),
(‘a mouse’, None, None))
In [5]: printTree(mediumTree)
Is it bigger than a breadbox?
+-Yes: Is it gray?
• +-Yes: It is an elephant
• `-No: It is a tiger `-No: It is a mouse
In [6]: mediumTree[1]
Out[6]: (‘Is it gray?’, (‘an elephant’, None, None), (‘a tige r’, None, None))
In [7]: printTree(mediumTree[1])
Is it gray?
+-Yes: It is an elephant
`-No: It is a tiger
Note several things about the above interaction:
The way Python prints trees isn’t especially easy to read. We’ve provided a
function that formats things in a nicer fashion. You’ll find
printTree
printTree
to be highly useful when you’re debugging your program.
Trees are “nested”; the “Is it gray?” question is a subtree has exactly the same
“shape” as
.
smallTree
.
You can access a subtree with subscripting notation, such as
mediumTree[1]
When a human (or a computer!) plays 20 Questions, they will follow a “path” through the tree. For example, if the object is not bigger than a breadbox, there is no point in asking whether it is gray.
What to write
Here are the functions that your program should have. You’re welcome to introduce other helper functions as needed.
[15 points]
simplePlay(tree)
This function accepts a single argument, which is a tree (or a sub-part of a tree), and
plays the game once by using the tree to guide its questions. It returns
if the
computer guessed the answer. Here’s an outline:
True
. If the tree is a leaf, ask whether the object is the object named in the leaf. Return
or appropriately.
True False
. If the tree is not a leaf, ask the question in the tree.
If the user answers “yes”, call yourself recursively on the subtree that is the second element in the triple.
If the user answers “no”, recur on the subtree that is the third element in the triple.
Try
out on
and
. Make sure that it returns
or
simplePlay
smallTree
mediumTree
True
depending on whether the computer guessed correctly. (For example, try it
False
out while thinking of an elephant, and again while thinking of a car.)
Hint 1
[40 points]
play(tree)
, this function accepts a single argument, which is a tree, and
Just like
simplePlay
plays the game once by using the tree to guide its questions. However, instead of
returning just or , returns a new tree that is the result of playing the
True False play
game on the original tree and learning from the answers.
If the computer guessed an object correctly, the “new” tree that is returned will be an identical copy of the original tree.
BUT, if the computer doesn’t guess the object correctly, it will ask the user for the name of the object and a question that will distinguish it (see below for an example). In that case the new tree that is returned will be similar to the old one, but with the new object and an additional question inserted. This means that the computer will learn as you play!
Here’s an example of this function in action (user-typed input is shown in blue:
In [2]: newTree = play(smallTree)
Is it bigger than a breadbox? yes
Is it an elephant? yes
I got it!
In [3]: newTree
Out[3]: (‘Is it bigger than a breadbox?’, (‘an elephant’, Non e, None), (‘a mouse’, None, None))
In [4]: newTree = play(tree)
Is it bigger than a breadbox? yes
Is it an elephant? no
Drats! What was it? a car
What’s a question that distinguishes between a car and an elep hant? Does it have wheels?
And what’s the answer for a car? yes In [5]: newTree
Out[5]: (‘Is it bigger than a breadbox?’, (‘Does it have wheel s?’, (‘a car’, None, None), (‘an elephant’, None, None)), (‘a mouse’, None, None))
The
function should be recursive. Again, test it first with
and then
with
play
smallTree
. But this time, also be sure to think of an object that isn’t in the tree
mediumTree
in
, you can print the
and add it to the tree. If you saved the output of
result nicely like this:
play
newTree
In [6]: printTree(newTree)
Is it bigger than a breadbox?
+-Yes: Does it have wheels?
• +-Yes: It is a car
• `-No: It is an elephant
`-No: It is a mouse
Hint 2
Hint 3
Hint 4
Saving and restoring trees
As it stands, 20 Questions is a somewhat boring game because it always starts with the same tree. An improvement would be be able to save game trees so that we can share our games and reload them later. To do that, we’ll need to create (write) and read files. A file is a place on your computer’s hard drive or SSD that can hold arbitrary information and keep it pretty much forever; every document (and every program and every picture) on your computer lives inside a file. We keep track of files
by giving them names like , and organize them by collecting them into proj2.py
folders (also called “directories”).
Opening and closing files
If you want to work with a file in a Python program, you must first open it. That’s like double-clicking it in VScode—or like opening a notebook. When you open a Python file, you have to tell Python whether you’re planning to read it or write it. You do so like this:
document = open(” myfile.txt”, “w “)
indicates that
Here,
is the name you want to give to the file, and
“myfile.txt”
“w”
you intend to write it (as you might guess,
is used for reading). Unlike opening a
“r ”
notebook, opening a file for writing will throw away anything that’s currently there
(and will create the file if it doesn’t already exist). The
function returns a file
open
handle, which is a way to refer to the file in the rest of your program. In this case
we’ve used
as a mnemonic name for the file handle.
document
When you’re done with the file, you must close it so that Python knows you’re done with it:
document.close()
Reading and writing files
If you have opened a file for writing, there are several ways to put data into it. The
simplest, which we’ll use for this assignment, is our old friend
:
print(“Here is some text”, file = document)
print
The additional “file =” argument tells Python that you want the information to be
saved in the given file (via its handle) rather than being displayed on the screen.
To read one line of data from a file, you can use
:
readline
line = document. readline()
As it happens, the line you read from the file will normally contain a “newline”
character at the end; you can get rid of that with
:
line = line.strip()
strip
Here’s a full example, at the ipython prompt, of creating and writing a file:
In [1]: document = open(“test.txt”, “w”)
In [2]: print(“Spish is spiced fish.”, file = document)
In [3]: print(“Penguins hate spam but they love spish.”, file
= document)
In [4]: document.close()
in Visual Studio, you should see two lines of text
At this point, if you open
about the penguin diet. test.txt
Now, let’s read the file back and print it out—again, just working at the ipython prompt:
In [5]: document = open(“test.txt”, “r”)
# Note that we can
re-use “document”
In [6]: while True:
…: line = document.readline()
…: if line == “”:
…:
break
…:
line = line.strip()
…:
print(line)
…:
Spish is spiced fish.
Penguins hate spam but they love spish.
In [7]: document.close()
Note a few things about reading files:
Each call to
gives you a new line from the file.
readline
You don’t need to know how many lines are in the file, and so you can read and
process an arbitrarily large file, one line at a time.
When there are no more lines, returns an empty string. (It turns out
readline
that we won’t need that feature in this assignment, though.)
Take a look at the IOdemo.py file for a few more examples of how to read and write files.
Saving the tree with [30 points]
saveTree(tree, treeFile)
With that background, it’s time to save our tree to a file so that the game will
remember what it has learned!
Write a function called that accepts a tree and a the
saveTree(tree, treeFile)
handle of a file that is open for writing, and saves the tree in that file. The examples below demonstrate the format for the file using the two trees that we constructed
above.
Why does
expect a file handle?
saveTree
will want to be recursive. If
opened the file
It turns out that
saveTree
saveTree
itself, then the recursion would re-open the file and clobber it. So instead
will append to an already-open file.
saveTree
An example
First, we open a file in “w” (for “write”) mode; then we save the tree to that file, and
finally we close the file. The
is necessary or your data might not appear, or
might be corrupted!
close
In [6]: treeFile = open(“tree1.txt”, “w”)
In [7]: saveTree(smallTree, treeFile)
In [8]: treeFile.close()
# Absolutely n
ecessary!
(for example, by opening it in Visual
When we look at the contents of
Studio), we see this:
tree1.txt
Internal node
Is it bigger than a breadbox?
Leaf
an elephant
Leaf
a mouse
example:
Now, let’s try it with the
newTree
In
[9]: treeFile = open(“tree2.txt”, “w”)
# We can re-us
e treeFile here
In
[10]: saveTree(newTree, “tree2.txt”)
In
[11]: treeFile.close()
# Absolutely n
ecessary!
file looks like:
The
tree2.txt
Internal node
Is it bigger than a breadbox?
Internal node
Does it have wheels?
Leaf
a car
Leaf
an elephant
Leaf
a mouse
Notice that the saved file is in the following format:
An internal node (a question) starts with the line
.
After the
Internal Node
line is a line with the question itself.
Internal Node
Following the question, there are two groups of lines that represent the left and right children of the internal node.
Note that these groups of lines can be arbitrarily large!
As a result, figuring out what the original tree looked like is a bit tricky for humans—but it’s exactly what the computer needs!.
A leaf node (the answer) starts with the line
and is followed by a line with
the answer.
Leaf
Here’s an annotated version of the file above, showing how the various components are grouped:
treenodes.png
Here’s the secret to making
(and you) happy: it’s recursive!
Hint 5
saveTree
Optional but highly recommended: Loading the tree with (10 extra-credit points)
loadTree(treeFile)
This next part of the problem is optional, but very highly recommended if you have time. It’s only about 10-15 lines of code, it will help you achieve a higher level of mastery of this material, and you’ll get 10 more points for it! BUT, if you’re running out of time and don’t do this, we’ll understand! In that case, move on to the last part
of the problem, which is the
function below.
The
main()
function accepts a file that has already been opened for
loadTree(treeFile)
to read one line at a time from the file, builds the tree
reading. It uses
readline()
described by that file, and returns it so that we can play that tree! Here are two examples, following on the running examples above.
In [12]: treeFile = open(“tree1.txt”, “r”)
# open up the fil
e for reading
In [13]: tree1 = loadTree(treeFile)
# read the file in
to a list
In [14]: treeFile.close()
# always close yo
ur file afterwards
In [15]: tree1
Out[15]: ((‘Is it bigger than a breadbox?’, (‘an elephant’, No ne, None), (‘a mouse’, None, None))
In [16]: treeFile = open(“tree2.txt”, “r”)
# open up the fil
e for reading
In [17]: tree2 = loadTree(treeFile)
# read the file in
to a list
In [18]: treeFile.close()
# always close yo
ur file afterwards
In [19]: tree2
Out[19]: (‘Is it bigger than a breadbox?’, (‘Does it have whee
ls?’, (‘a car’, None, None), (‘an elephant’, None, None)), (‘a
mouse’, None , None))
Again,
is recursive.
Hint 6 loadTree
Hint 7
Putting it together with the
function [15 points]
Finally, write a
main()
function that has the following behavior:
main()
Prints a welcome message
Asks the user if they would like to load a tree from a file (optional, but bonus points as indicated above)
If the user didn’t want to load from a file, the initial tree should be:
(“Is it
bigger than a breadbox?”, (“an elephant”, None, None), (“a mouse”,
None, None))
Plays the game
Asks the user if they would like to play again, in which case we play again with the new tree
When the user is done playing, asks the user if they would like to save the file, in which case the user is queried for a file name and the file is saved
Here’s an example, with the user input in blue:
Welcome to 20 Questions!
Would you like to load a tree from a file? yes What’s the name of the file? tree2.txt
Is it bigger than a breadbox? yes
Does it have wheels? no
Is it an elephant? yes
I got it!
Would you like to play again? yes
Is it bigger than a breadbox? yes
Does it have wheels? no
Is it an elephant? no
Drats! What was it? a hippo
What’s a question that distinguishes between a hippo and an el ephant? Does it have tusks?
And what’s the answer for a hippo? no Would you like to play again? yes
Is it bigger than a breadbox? yes
Does it have wheels? no
Does it have tusks? no
Is it a hippo? yes
I got it!
Would you like to play again? no
Would you like to save this tree for later? yes
Please enter a file name: tree3.txt
Thank you! The file has been saved.
Bye!
Finishing and Submitting
First, starting from the initial tree with just one question (“Is it bigger than a breadbox”) and two animals (“an elephant” and “a mouse”), play several times to build up a game that has a more interesting game tree.
Then, save that tree to a file called .
proj2_ tree.txt
If you implemented the “load” feature, you can play the game using your classmates’
trees! Have fun!
Then, submit your code, proj2.py and your
file in the submission
system.
proj2_tree.txt
