Binary Trees Lab 20 Questions
Submission
o Submit all code and other materials in a single zip file to the appropriate assignment folder on Kodiak.
Goal: Build a system that learns to play a "20 Questions"-like game.
Files
• tree.py - (Do not modify.) Base class for all trees. . binary_tree.py - (Do not modify.) Base class for all binary trees. • linked_binary_tree.py - (Do not modify.) Implementation of a binary tree using linked nodes. • main.py - (Do not modify) Calls play_game() in twenty.py to play the game. • twenty.py - (Modify) Implements the 20 questions game. • training.txt - (Modify) A trace of you training your system. gametree.dat - (Modify) The saved tree generated by your training. Introduction Prior to doing any design, make sure to thoroughly review each of the modules which were distributed with this lab. If anything is unclear about these dasses, ask! Your textbook describes these classes in further detail in Sections 8.1-8.3. Problem You may have seen online games that purport to be "psychic," with the ability to correctly guess any item or character that you may be thinking of by asking yes/no questions of the player. Your goal is to write a program that can play this game, in part by learning about a universe of your choice as it plays by asking yes/no questions. For example, your program might learn about animals by having the following dialogue with its user. (For readability, user responses are shown here in red. The responses also use capital letters, which is not a requirement for this assignment.) Think of an animal, and I will guess it. Does it have legs? yes Is it a cat? yes I win! Continue? yes Think of an animal, and I will guess it. Does it have legs? no Is it a snake? yes I win! Continue? yes Think of an animal, and I will guess it. Does it have legs? no Is it a snake? no I give up. What is it? earthworm Please type a question whose answer is yes for earthworm and no for enake: Does it live underground? Continue? yes Think of an animal, and I will guess it. Does it have legs? no Does it live underground? no Is it a snake? no I give up. What is it? fish Please type a question whose answer is yes for fish and no for snake: Does it live in water? Continue? no The program begins with minimal knowledge about animals: It knows that cats have legs and snakes do not. When the program incorrectly guesses "snake" the next time, it asks for the answer and also asks for a way to distinguish between snakes and earthworms. The program builds a binary tree of questions and animals. A "yes" response to a question is stored in the question's left child; a "no" response to a question is stored in the question's right child Task Extend make a child class of) the Linkedinaryfree class to create a data structure that supports this game. Make use of the protected methods in LinkedBinaryTree to modify the tree structure. You may name your class anything you wish, though your module must be named twenty.py. Additionally, you must have a play_game () function in the module (not your class) that allows the user to play when it is called. We want to avoid having to retrain the system from scratch every time we play the game. So we'll save and load the tree to and from a file. BinaryTree (which you are extending) already has methods for saving and loading the tree: save_tree() and load_tree(). The examples below demonstrate how to use them. Save a tree to gametree.dat mytree.save_tres('gametree.dat') Load a tree from gametree.dat mytree = BinaryTree.load_tree 'gametree.dat's These methods read and write binary files. So you will not be able to read them in a plain text editor When the game first begins, ask if they want to load a file, and if so ask for the filename. Would you like to load a game? yes What file should I load? gametree.dat When the game ends, ask if the user would like to save the file, and if so ask for the filename to save the tree to. Would you like to save the game? yes What Eile should I save to (I will overwrite it)? gametree. dat import linked_binary_tree # Define your class here. Give it a better name than A, # and make sure it extends LinkedBinary Tree. class A: def play_game): # Game logic here. # Feel free to create other methods, modules and classes. | Provide a session log of you training your system from scratch. Just copy and paste your interaction with your program.