Akinator

Akinator is a web game akin to 20 questions. The game starts with the user chosing some person, either ficticious or not. Then, the users is prompted with a series of questions that they must answer. After some number of questions, the program produces a guess of the person the user had chosen. Thanks to an intelligent use of data structures, and some clever learning mechanisms, the program is usually able to pick the correct person.

Setup

Create a directory assignment12 under assignments in your cs170 directory. All code for the assignment should be stored in this directory.

  cd ~/cs170/assignments
  mkdir assignment12 
  cd assignment12

Details

You are going to write a simplified Akinator clone for this assignment. You will be provided with a question database, which lists all of the questions necessary for the program, as well as all of the potential answers. Your job is to read this text file into your program, and construct a decision tree based on that information.

A decision tree is simply a binary tree where all of the internal nodes (Nodes with children) are questions. The meaning of the children of these internal nodes are different: An answer of yes to the question in the node leads down the left sub-tree, while an answer of no leads down the right sub-tree. That means that all of the answers in the left sub-tree are people that the question is True for, and all the answers in the right sub-tree are people that the question is False for. The leaves of the tree are answers, people that the user could have been thinking of.

The provided database of questions and answers is formatted for easy insertion into the database. The order of the questions follows a breadth-first search from the actual root of the tree. This means the first question in the file is the root, the second question is the left child of the root, etc. To facilitate ease of insertion into the tree, the full path from the root is also included on these lines. After all of the questions are provided, all of the answers are provided. These also follow a breadth-first traversal, and include the full path from the root as well.

Your program should read in the provided database of questions, and build a decision tree. You will ask the user to think of a person (In this case faculty at Roanoke College), and you will ask the question at the root. You will prompt the user to answer the question, and then proceed to the next question in the tree. You will continue this, until you arrive at a leaf. In which case, this is the answer that was expected.

Your program, at this point, will be very restricted on what it can guess. It can only correctly identify MCSP faculty members. The problem is that there is no way for a non-MCSP faculty member to appear in the list. What if someone was thinking of Dr. Zorn? Or Dr. Steelher? What would be better is if your program could learn. Which is fairly easy to do with a decision tree like this.

when the user "fools" your program, it should ask for the question that should have been asked to differentiate between your program's answer and the correct answer. You will also need to get the correct answer: the person they were thinking of. You should replace your program's answer in the tree with a node representing this new question. Your program's answer becomes the negative response to the users question, and the users correct answer becomes the positive response.

Program Outline

Write down an outline of your program on paper. You should define what classes you need, what the attributes of those classes are, and what methods each class will have. For each attribute, define the datatype being stored within and their purpose. For each method, define their Pre and Post conditions.

This is due Monday, Apr. 6^th. All of what you define here can (and probably will) change by the time your final program is written. Consider this an "rough draft" for your program. This will help you get started thinking about the problem before Monday. The key things to think about are:

• What do you need to store, and how will you store them?
• What are the operations you need to be able to perform on the data?
• If you have classes, what data needs to be in attributes, and which data can stay as local variables, etc.

Submission

You are required to submit a tar file to http://inquire.roanoke.edu/. On inquire, there is a link for Assignment 12. You can create a tar file by issuing the following commands:

cd ~/cs170/assignments
tar czvf assignment12.tgz assignment12/

"Hacker" Prompt

1. Database Generation The provided database is not that interesting. It's simply all of the MCSP faculty. Your program should work on any database file that is formatted the correct way. Come up with your own database file: It could be Disney characters, sport teams, etc. Include this database file with your submitted tar file. You must have at least as many questions and answers as the default database file provided!

2. Vague Answers If you have ever used Akinator before, you know it doesn't only ask yes or no questions. And it shouldn't, since such a dichotomy is pretty rare. Instead, it asks for a level of confidence: Yes, No, probably yes, probably no, and I don't know. Akinator uses this to "prune" the tree. It removes branches from the tree based on the confidence level of the answer. Akinator operates more like Evil Hangman than a decision tree.

   I'm not asking you to do anything as complicated as the full Akinator. Instead, I want your tree to no longer be a binary tree. It should be a 5-ary tree. Instead of having only 2 branches, you will have 5! You will need to modify your tree structure, as well as how your program parses the users data. Make sure you build an appropriate test database!