7: The Animals Game
Fall 2005, David Matuszek
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?
Computer: Does it have stripes?
Computer: I know! Is your animal a horse?
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?
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.
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
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?
Computer (to John): OK, what is your animal?
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 BinaryTree.java 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..
BinaryTree(Object value, BinaryTree leftChild, BinaryTree rightChild)
<<constructor>> Creates a node containing the given value, with the given left and right children.
<<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.
Returns the value contained in this node.
void setLeftChild(BinaryTree subtree)
Adds the given binary tree as a left child of this tree.
Returns the left child (
void setRightChild(BinaryTree subtree)
Adds the given binary tree as a right child of this tree.
Returns the right child (
trueif this node has no children.
Stringrepresentation of this tree.
Prints this tree (on
boolean equals(Object o)
trueif this tree is equal to the tree given as a parameter. This method assumes that an appropriate
equalsmethod is defined for every value in the tree nodes.
Returns a hash code for the entire binary tree rooted at this node. This method assumes that an appropriate
hashCodemethod is defined for every value in the tree nodes.
webappsand submit it via Blackboard.