Project due date - May 6, 1996

For this project, you will write an interactive game-playing program. The program will ask a human user yes/no questions until it either guesses the object of which the user is thinking, or gives up. If it has to give up, the system will ask the user to teach it something that it could use in future games. Your main program will consist (essentially) of a loop that plays a game and asks if the user wants to play again, until the user says no. When a program run first begins, the system should offer the user information about the game, but only give explanations if requested. If the user doesn't need info, go straight to the play of the game.

The main data structure your program will need is a binary decision tree. Each node (except for leaves) should contain a question to ask the user, and the leaves should contain names/descriptions of objects that the system will offer as guesses. Play will consist of following the path from the root to the leaf indicated by the users responses. Once at a leaf, the system will have reached the best candidate for a match of which it knows. If it is wrong, it will "learn" by modifying its decision tree. For example, given the following tree at the start of a game:

				Is it an animal?


                Does it have a mane?       	broccoli


              a horse       a spider

and a user who was thinking of a spider, the program would correctly guess "spider". If, on the other hand, the user was thinking of a dog, the system should ask for a question distinguishing spiders from dogs. Suppose the user suggested web-spinning. Then the system should change its tree to reflect the new info:

                           Is it an animal?
                            /            \
                           /              \
             Does it have a mane?       broccoli
                         /                  \
                        /                    \
                    a horse            Does it spin webs?
                                             /      \
                                            /        \
                                        spider       dog

Your program should start each gaming session with a tree that is 2 to 4 levels deep (your choice exactly how many levels, and what objects/questions to include.) You should show at least 3 sample runs, and at least one of them should loop at least 6 times.

WHAT TO HAND IN: Documented code, sample runs, user's manual (describing expected input format & error routines, and output format), maintenance manual describing your data structure, and your algorithm (including (consisting of?) how the structure is updated) in fairly abstract, high-level terms.