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 assignment11 under assignments in your cs170 directory. All code for the assignment should be stored in this directory. 

cd ~/cs170/assignments
mkdir assignment11
cd assignment11

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 MCSP faculty), 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.

Program Outline

Write down an outline of your program on paper. You should define what classes you need, what the attributes of thos 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. 7th. 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.

Submission

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

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

"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. Learning: Your current program is very restricted on what it can guess. If the user picks something that is not a known answer, your program will never try to guess it. A better solution would be for the program to learn: When the users picks something that wasn't in the tree, it should be added into the tree somehow.

    Modify your program so that when the user "fools" your program, it asks for a question that should have been asked, as well as the correct answer: the person they were thinking of. You simply need to replace your guessed answer in the tree with a node representing this new question. Your guessed answer becomes the negative response to the users question, and their answer becomes the positive response.

    You also need to update your database file. Add a function that writes your decision tree out to a file in the same format as the one you read in.

  3. 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!

Last modified: Fri Apr 4 14:49:39 EDT 2014