152 Project
Goals for this project
- Practice with data representation
- Practice using linked structs
- Practice the whole software development process - design, implementation, testing, repeat.
You are expected to complete this assignment individually. If you need help, you are invited to come to office hours and/or ask questions on piazza. Clarification questions about the assignments may be asked publicly. Once you have specific bugs related to your code, make the posts private.
Twenty Questions
In this project, you are going to implement a 20 questions game that can learn from its mistakes. For a complete description of the game, see Wikipedia. The "Computers, scientific method, and situation puzzles" are especially intriguing if you enjoy looking at life through a computer science / algorithmic lens. On the department linux machiens is a working version of the game. You can play it by logging into a department computer (ssh cnetid@linux.cs.uchicago.edu) and typing: "/home/dmfranklin/bin/qgame". Before reading the rest of the description, you need to either already know the game or read about it. Please make sure you understand the game before moving on.
Twenty questions uses a decision tree. This is a very common data structure. It stores decision points as a binary tree. Each node involves a decision, and the two children are where you go depending on the result of the decision. Twenty questions is especially well-suited to this structure because the answer to every question can only be "yes" or "no", providing two possible directions.
For example, the decision tree below shows a very, very, very simple game of 20 questions that involves only two questions before a guess.
You can see that for this game, the computer would first ask if what you are thinking of ("it") is alive. If it is alive, it will ask if it lives in the ocean. If not, then it will guess a kangaroo. If so, then it will guess a platypus. Quick question - if the computer has a chance to ask 20 questions before guessing, how many different items can it guess?
This project has four parts.
In order to play your game, you need to have completed two of the parts - game play and either building a tree from a file or learning from playing the game.Ground rules: You may use an online C or tutorial on trees or binary trees and code given in lab or class, or textbooks, but you may not receive help from any individual except the TA's or instructor. You also may not look up anything about code related to decision trees, twenty questions games, or any other programming assignment of this nature.
Set Up
Create a twentyqs directory for this assignment.
We have provided some starting files. You will notice that a lot less is specified in the .h files than you are used to. This is intentional so that you can practice not only your implementation skills, but also your design skills. We are providing enough so that we can make sure the output is consistent. Make sure you include all of the functions that we specify, plus more that you define. Do NOT change the interface on any function we provide. You may add extra functions if you want some other functionality.
Here are some files to start you out.
- qinfo.h - this stores info for a single question. This is structured as a tagged union not because it is strictly necessary, but because the test revealed that a significant number of students in the course do not understand how to use this syntax.
- qinfo.c - implementation of qinfo struct. I've given you the print function so that the output is consistent.
- qtree.h - a very partial definition of a qtree structure. In fact, the struct definition is not there. All there is are three functions that you'll need to implement. You need to decide on the struct, whether you need other structs to support it, and the functions you will need.
- qgame.h - declarations of two functions - one to create a tree from a file and the main gameplay function.
- qgame.c - This is where the two functions from qgame.h belong. There are printfs in the gameplay function so that the interface is consistent for everyone.
- qtree.c - implementation of qtree.
- test_qgame.c - code with main function. It calls gameplay.
- Makefile - makes executable named qgame.
- qtree.txt - answers specific questions about your tree design.
Part 1: Game Play
Game play begins either with an empty tree or a tree from a file. Your main file, test_qgame.c, contains the main function. If no command-line argument is given (beyond the executable name), then it passes gameplay a NULL pointer. If a command-line argument is provided, then it passes that argument to gameplay to use as the filename for the file to read to create a starting tree. When starting from nothing, ask a single question: "Is it a crocodile?"
Below is the transcript of a session beginning with an empty tree. This also shows the questions it would ask for tree learning, which is in part 3. However, for this part, you just ask the questions and ignore the answers. The basic game play (without learning) occurs when the computer is correct.
./qgame Now, wait, don't tell me - Is it a crocodile? (yes or no): yes Great! I got it! Score: You 0, Me 1 Would you like to play again (yes or no)? yes Now, wait, don't tell me - Is it a crocodile? (yes or no): yes Great! I got it! Score: You 0, Me 2 Would you like to play again (yes or no)? yes Now, wait, don't tell me - Is it a crocodile? (yes or no): no Oh, no, I was so sure... What was it? bumblebee What extra question could I have asked that would have identified bumblebee? Does it fly? Score: You 1, Me 2 Would you like to play again (yes or no)? no Bye!
Part 2: Building Tree from File
In the second step, you will look at the command-line argument and see if it contains a second argument - a file to read in. If so, read it in. The format of the file is here. Each line contains three questions. The first question belongs in the parent node, followed by the left child then the right child. The first two numbers tell whether the left child and right child each is a question node or a guess node.
You are guaranteed that, with the exception of the first line, the parent node has already been inserted into the tree. In the first line, you need to insert three nodes - the root and its left and right child. From then on, the first string is already in the tree. You need to find that one and then add the two children.
You need to add code in test_qgame.c that checks for the command-line argument, pass it to gameplay, and then add code to gameplay to call create_qtree_from_file. Then you need to implement create_qtree_from_file. This will require some qtree functions.
Below is the transcript of a session beginning with the tree specified in gameinfo.txt. This also shows the questions it would ask for tree learning, which is in part 3. However, for this part, you just ask the questions and ignore the answers. The basic game play (without learning) occurs when the computer is correct.
./qgame gameinfo.txt Is it alive? (yes or no): yes Does it live in the ocean? (yes or no): no Now, wait, don't tell me - Is it a kangaroo? (yes or no): yes Great! I got it! Score: You 0, Me 1 Would you like to play again (yes or no)? yes Is it alive? (yes or no): no Is it smaller than a breadbox? (yes or no): yes Now, wait, don't tell me - Is it a thimble? (yes or no): yes Great! I got it! Score: You 0, Me 2 Would you like to play again (yes or no)? yes Is it alive? (yes or no): yes Does it live in the ocean? (yes or no): yes Now, wait, don't tell me - Is it a platypus? (yes or no): yes Great! I got it! Score: You 0, Me 3 Would you like to play again (yes or no)? yes Is it alive? (yes or no): no Is it smaller than a breadbox? (yes or no): no Now, wait, don't tell me - Is it a kitchen table? (yes or no): no Oh, no, I was so sure... What was it? chair What extra question could I have asked that would have identified chair? Do people sit on it? Score: You 1, Me 3 Would you like to play again (yes or no)? no Bye!
You need to create a file named qtree.txt that describes the overall design of your
qtree structure. This is where you describe your data structure and the role the different
functions play. Answer three questions:
1. What struct(s) did you choose to implement the qtree?
2. What functions did you define in the qtree to facilitate building the
tree from the file? Describe the interfaces.
3. When playing the game, how do you iterate through the tree? How do you know when you're on the last question?
Part 3: Building Tree from Play: Learning
If the game gets the question wrong, then it needs to learn from its mistake. The last question asked was in the form "Is it an (object)?" It first asks what the correct item was (i.e. giraffe), then what question would have distinguished the right answer from the wrong answer (i.e. Does it have a long neck?).Below is the trascription of a session utilizing learning. It begins with an empty tree and builds it as it plays.
./qgame Now, wait, don't tell me - Is it a crocodile? (yes or no): no Oh, no, I was so sure... What was it? giraffe What extra question could I have asked that would have identified giraffe? Does it have a long neck? Score: You 1, Me 0 Would you like to play again (yes or no)? yes Does it have a long neck? (yes or no): yes Now, wait, don't tell me - Is it a giraffe (yes or no): no Oh, no, I was so sure... What was it? dinosaur What extra question could I have asked that would have identified dinosaur? Is it extinct? Score: You 2, Me 0 Would you like to play again (yes or no)? yes Does it have a long neck? (yes or no): yes Is it extinct? (yes or no): no Now, wait, don't tell me - Is it a giraffe (yes or no): yes Great! I got it! Score: You 2, Me 1 Would you like to play again (yes or no)? yes Does it have a long neck? (yes or no): no Now, wait, don't tell me - Is it a crocodile? (yes or no): no Oh, no, I was so sure... What was it? tree What extra question could I have asked that would have identified tree? Is it vegetation? Score: You 3, Me 1 Would you like to play again (yes or no)? yes Does it have a long neck? (yes or no): no Is it vegetation? (yes or no): yes Now, wait, don't tell me - Is it a tree (yes or no): no Oh, no, I was so sure... What was it? carrot What extra question could I have asked that would have identified carrot? Is it edible? Score: You 4, Me 1 Would you like to play again (yes or no)? yes Does it have a long neck? (yes or no): yes Is it extinct? (yes or no): yes Now, wait, don't tell me - Is it a dinosaur (yes or no): yes Great! I got it! Score: You 4, Me 2 Would you like to play again (yes or no)? no Bye!
Testing part 3 can get very tedious. Playing once is fun. Debugging by playing the same thing over and over is
tedious. Instead of doing it manually, you should make a file like gameinput.txt.
This records all of the answers you give for a session. This is part of the session displayed above. To run
your code using this input, do the following:
./qgame < ./gameinfo.txt
Answer the following questions in your qtree.txt file:
4. What functions did you define to facilitate learning? Describe the interfaces.
Part 4: Storing Result
The final job is to store the results. You have already seen the format of the file when you completed reading from a file. If an input file is given, reopen that file again (for writing) and write out the result of your tree.Answer the following questions in your qtree.txt file:
5. What functions did you define to facilitate storing the tree? Were you able to keep the tree, items, and gameplay separate, or did some need knowledge of the others? Why or why not?
Submit
At this point, you should have the following files: Makefile, qinfo.h, qinfo.c, qtree.h, qtree.c, qgame.h, qgame.c, test_qgame.c, qtree.txt. Also, to illustrate that you tested your program thoroughly, you need at least one, and possibly more than one, gameinfo.txt file and gameinput.txt file. These should exercise different aspects of the program.
Don't forget to add and commit all of your files.