CIT 597 Assignment 7: The Animals Game
Fall 2005, David Matuszek

Purposes of this assignment:

General idea of the assignment:

The Animals Game is a form of Twenty Questions (although there is no limit on the number of questions). Traditionally, the text-based version goes something like this:

Computer: Think of an animal. Hit Return when you're ready.
Human: (hits return)
Computer: Does your animal live in the water?
Human: No
Computer: Does it have stripes?
Human: No
Computer: I know! Is your animal a horse?
Human: No
Computer: OK, what is your animal?
Human: A turtle
Computer: What question would distinguish your animal from a horse?
Human: Does it have a shell?
Computer: What is the answer for a turtle?
Human: Yes
Computer: Thanks, I'll remember that! Would you like to play again?

And the computer does remember that. If the human (or any other human) plays again, the program will know that a turtle is one of the possible answers.

(By the way: If the computer gets the right answer, the traditional response is: "See? Humans should work, computers should think!")


Your task is to write a web application to play this game.

Your HttpServlet should act as a controller.

A game is played within one session. Session information can consist mainly of the list of yes/no responses given so far by the user (an ArrayList is probably a good data structure to use for this). When the game ends, this information should be reset (that is, no information is kept about the series of responses to old games).

Use a separate Java class for the model. The best and most obvious way to keep knowledge about animals is as a binary tree, where each non-leaf contains a question, and each leaf contains the name of an animal. To play the game, the computer walks down the tree and, at each node, asks the question contained in that node. Yes and no answers cause the computer to move to the left child or the right child.

Use JSP for the view. Each web page (after the first) should display a list of the questions asked so far, along with the user's responses, and the current question or final guess. Buttons should be provided for the user's yes/no responses. When the computer's final guess is wrong, the resultant page should also have text fields or text areas for the user to type in the name of the animal and a question to ask.

When there is more than one user (say, from different browsers), you need to keep information about game state for each individual user. However, when a user adds an animal (and a corresponding question), that information should be made available immediately to all users.That is, if John adds a "lion" while Mary is in the middle of a game, Mary should be able to get to the answer "lion" at the end of her game (assuming that her sequence of answers leads her there, of course).

Computer (to Mary): Does your animal live in the water?
Mary: No
Computer (to John): OK, what is your animal?
John: Lion
Computer (to John): Thanks, I'll remember that!
...some time later...
Computer (to Mary): I know! Is your animal a lion?

This requires that information about an individual game be kept as session information, but the binary tree used to represent what the computer knows has to be available to all users. Since this is shared information, synchronization is necessary.

Nice but not required: You can make sure that the animal names are all in lowercase, and you can do something to make sure that the words "a" and "an" are used appropriately. This is fairly simple string manipulation (but not really what the assignment is all about), so do it only if you want your program to look nice.

I have a class which you are welcome to use if you wish. Here is a brief description; for more detail you can look at the Javadoc, the code, or the test class..

Method Description
BinaryTree(Object value, BinaryTree leftChild, BinaryTree rightChild) <<constructor>> Creates a node containing the given value, with the given left and right children.
BinaryTree(Object value) <<constructor>> Creates a leaf node containing the given value. (Children may be added later.)
void setValue(Object value) Puts the given value into this node.
Object getValue() Returns the value contained in this node.
void setLeftChild(BinaryTree subtree) Adds the given binary tree as a left child of this tree.
BinaryTree getLeftChild() Returns the left child (null if none).
void setRightChild(BinaryTree subtree) Adds the given binary tree as a right child of this tree.
BinaryTree getRightChild() Returns the right child (null if none).
boolean isLeaf() Returns true if this node has no children.
String toString() Returns a String representation of this tree.
void print() Prints this tree (on System.out).
boolean equals(Object o) Returns true if this tree is equal to the tree given as a parameter. This method assumes that an appropriate equals method is defined for every value in the tree nodes.
int hashCode() Returns a hash code for the entire binary tree rooted at this node. This method assumes that an appropriate hashCode method is defined for every value in the tree nodes.

Due date:

Tuesday, November 8, before midnight. Please just zip up your entire directory under webapps and submit it via Blackboard.