Project 4: A Game About Animals

Release Date

November 27, 2000

(Note: Any changes to this project description since the release date will be posted in this color (green) and italicized.)

This document was last modified on

Due Date

Midnight Monday, December 11, 2000. Note that this means before 23:59:59 on Monday evening. The standard late policy applies.

Objectives

The objectives of this project are:

The Problem

You must write a program to play a simple game of questions with the computer. The rules of this game are simple:

  1. The player thinks of an animal.
  2. Until the computer has either (a) given up, (b) guessed the right animal, or (c) guessed the wrong animal,
    1. the computer asks a yes or no question, and
    2. the player answers yes or no based on the animal that he/she is thinking of.
  3. If the computer gives up or guesses the wrong animal, the computer
    1. asks for the answer, and
    2. asks a yes/no question that can help it identify this animal in the future.
Computers are not reknowned for their intelligence, so the computer starts out with no idea what animal you're talking about. However, as it plays the game and guesses wrong, it "learns" new information each time and organizes it into a collection of facts and relationships that it has learned. This collection of facts and relationships is sometimes called a "knowledge base". Designing the computer's knowledge base for this game is the core of this project.

A Sample of the Game

The best way to try to understand this game is to watch it being played.

[irix1]% proj4 Ok. Think of an animal. Ready? ('y' to continue): y I give up. What is it? dog What question would tell me that it's a dog? Does it have a tail? Would you like to play again? ('y' or 'n'): y Ok. Think of an animal. Ready? ('y' to continue): y Does it have a tail? ('y' or 'n') y Is it a dog? ('y' or 'n'): n I give up. What is it? fish What question would tell me that it's a fish? Does it swim under water? Would you like to play again? ('y' or 'n'): y Ok. Think of an animal. Ready? ('y' to continue): y Does it have a tail? ('y' or 'n') y Does it swim under water? ('y' or 'n') n Is it a dog? ('y' or 'n'): n I give up. What is it? cat What question would tell me that it's a cat? Does it meow? Would you like to play again? ('y' or 'n'): y Ok. Think of an animal. Ready? ('y' to continue): y Does it have a tail? ('y' or 'n') y Does it swim under water? ('y' or 'n') n Does it meow? ('y' or 'n') y Is it a cat? ('y' or 'n'): y I win! Would you like to play again? ('y' or 'n'): n Note that the computer starts out by giving up. This is because the computer doesn't "know" anything when the program starts; it's knowledge base is empty. The program gets one guess at an animal, so your program should narrow down its choices as much as possible before it guesses. Remember, if the computer guesses the wrong animal, it loses the game, but it learns from its loss.

Sample Program

A sample executable is available in the directory

/afs/umbc.edu/users/j/k/jkukla1/pub/cs202/fall00/Project4/

on the irix.gl.umbc.edu systems. Please use it to help understand how the program should behave under certain conditions before coming to your instructor. And when in doubt, make it behave like the sample program!

Note: The program is an executable file compiled for irix, so the odds are fairly high that it won't run as is on your home machine.

Requirements

Your program must:
  1. Play the game outlined above.
  2. Use correct articles ("a" vs. "an") when talking about animals (note that the user should only enter the animal's name (see sample))
    1. Animal names starting with vowels (a,e,i,o,u) should be preceeded by the article "an".
    2. All other animal names should be preceeded by the article "a". Follow this rule strictly, even though there may be exceptions. For example, "unicorn" will be "an unicorn" for this program, even though it is really "a unicorn" according to English language rules.
    3. Prompt the user at the end of each game to find out if they'd like to play again.
    4. Use a binary tree to store the knowledge that the program has acquired.
    5. Ask as many questions as it can before guessing to increase its odds of winning.
    6. Contain a knowledge base class. Note that this class must be a template class. The class must contain a constructor, copy constructor, destructor, and an overloaded assignment operator.
    7. Contain a binary tree class. Note that this class must be a template class. The class must contain a constructor, copy constructor, destructor, and an overloaded assignment operator.
    8. Contain a node class. Note that this class must be a template class. The class must contain a constructor, copy constructor, destructor, and an overloaded assignment operator. You may make the binary tree class a friend of the node class.
    9. Use only the knowledge base class in the main and/or auxiliary functions. That is, main and auxiliary functions cannot use either the binary tree or node classes.

    Assumptions

    You may make the following assumptions.

    Extra Credit

    For a total of 10 points of extra credit (5 points each), implement the ability to load a knowledge base in from a file and the ability to save the current knowledge base to a file. To receive all 10 points your program must read in its own output (that is, the grader must be able to play a game, save it, quit, restart, load, and resume the game without error). The choice of file format is up to you.

    Add a file called README explaining your new features to the graders. If they can't figure out how to make it work, you won't get extra credit.

    Coding Standards

    You MUST follow the CMSC 202 coding standards. Read them thoroughly and carefully.

    Using Code You Didn't Write

    Claiming authorship of code that you didn't write is plagiarism and will be dealt with as academic dishonesty. You should avoid using code that you did not write; it defeats the learning experience of the project. If you do use outside code in your project, you must cite the source. If a significant portion of the project comes from an outside source, your grade may be reduced.

    Testing Your Program

    Remember, your program must compile and run using the CC compiler on the IRIX machines (irix1.gl.umbc.edu or irix2.gl.umbc.edu). If your program does not compile or does not generate the correct output, you will not receive full credit for this project.

    Your Makefile

    Many systems come with a utility called "make", which helps simplify project compilation. For this class you are required to use make for each project. The way this is done is by using a "makefile" that tells the make utility what to do when compiling your program.

    You may use this sample makefile as a starting point for this project. You should make sure that you have a makefile named either makefile or Makefile and that when you type make your program compiles to an executable called proj4. Failure to follow these simple directions will result in a reduced grade.

    Grading

    The grade for this project will be broken down as follows: 50% Correctness This tests that your program behaves the same way that the sample does. 30% Design and Style You should follow the coding standards and make sure your coding style is consistent. 20% Documentation Commenting source code inline as well as header files. A breadown that the graders will receive when they go to grade your project is provided here.

    What to Turn In

    You should submit your Makefile and all files needed to build your program.

    Submitting Your Project

    When you have finished and tested your project, you can submit it electronically using submit. The project name for this assignment is proj4. As an example, to submit your files, you would type: submit cs202 proj4 Makefile file.1 file.2 ... file.n More complete documentation for submit and related commands can be found here. You should replace all of the file.x's above with your real file names.