Assignment: Twenty Questions¶

Back before ubiquitous electronic entertainment, people would play parlor games, including "20 questions". The idea of the game is simple. One person, let's call them the oracle, thinks of something: person, place, or thing. The other people can ask the oracle yes/no questions. If they can guess the target within 20 questions, the asker(s) win, otherwise the oracle does.

My daughter was recently playing this on my phone, using an app called Akinator the Genie. You can blame her for this assignment, since I think it would be fun to build a 20 questions game, where the computer plays the asker and the human is the oracle.

Since these are yes/no questions, the game play amounts to searching a binary tree. The nodes are questions, and the leaves are guesses (answers). With 20 questions, you can reach 2²⁰ or about a million possible answers.

Implementationally, the game will be represented as a literal tree, using JavaScript objects. (But no methods.)

We could build on this to create a "learning" version of the game, where when the computer fails, it can ask for the correct answer and a question to distinguish the failed guess from the correct answer, and update its tree.

Goals¶

This assignment will demonstrate your skill with:

1. Ajax (we'll fetch the tree from a server)
2. Recursive tree traversal (we'll print the tree)
3. Maintaining your place in a tree data structure (necessary for playing the game)
4. Dynamic element creation (you'll dynamically add questions and buttons to the page, and remove unneeded buttons). You did this in the quiz assignment, so this is not entirely new.
5. Event delegation (to answer the questions and update the display). Again, you did this in the quiz assignment.

Note: this is a pretty hard assignment. Start early and ask questions. It's not a huge amount of code, though. My implemenation, including blank lines and comments and such, is less than 200 lines of code.

Dependencies¶

This assignment is based only on the material up to and including Chapter 13 (Ajax) and very little on Ajax. It does, however, require you to brush up on your recursion skills, which are not covered by our book but which we will discuss in class.

Reference Solution¶

Here is a link to the obfuscated reference solution

Getting started¶

• your solution will be in a twenty subfolder in your cs204-assignments folder
• you can copy my HTML and CSS files. You'll write your own JS/JQ code in a separate file. I called mine 20-static.js; you can use whatever name you like.

cd ~/public_html/cs204-assignments
mkdir twenty
cd twenty
cp ~cs204/pub/assignments/twenty/solution/20-static.html .
cp -r ~cs204/pub/assignments/twenty/solution/css .

Take the time to read my HTML so you can see what you'll need to be dynamically creating and the containers for the dynamically created content. Play the game a few times to make sure you understand how it works.

Operation¶

There are three distinct aspects of the assignment:

1. Fetching the text from the server using Ajax and parsing it into a tree. I will give you this code.
2. Displaying and hiding the tree; this is a recursive algorithm
3. Playing the game; this is not a recursive algorithm.

The last two depend on the first, but not on each other, so you can attack them in either order.

For this semester, I will solve step 1 for you, in the reference solution. You should read the HTML and JS/JQ code in that file, particularly after you've read the chapter on Ajax. It's only a handful of lines of code. The tree that is loaded is put in a global variable, loaded_tree (formerly current_tree), so you can look at it in the JS console. Your code will also use the global variable in its functioning. note: your code will never change the value of this global variable. It gets set only when the Ajax callback does so.

When the page loads, it'll have buttons for the following:

1. Get a tree from the server
2. New Game
3. Show Tree

Initially, the first button is the only one that will work. It uses an Ajax request to load a tree from the server as a string of text and parse it into a JSON data structure. After the tree is loaded, both of the other two buttons will be useable. You will implement their behavior.

Tree Structure¶

Internally, the question tree will be a tree of JavaScript objects, but that's inconvenient for writing. [Actually, it's not so bad, which is one reason for the popularity of JSON, JavaScript Object Notation.] Nevertheless, I created a format that is a little easier to write.

Here's are examples of the file format:

• easy.text
• medium.text
• hard.text

The reference solution uses a function to parse that format and create the tree structure. Each tree node looks like this:

    {Q: "Is it bigger than a breadbox?",
     Y: ...,
     N: ...
    }

The two attributes, Y and N are either other tree nodes or strings. If it is a string, it is a guess (an answer). Here's a node with two guesses:

    {Q: "Is it bigger than a breadbox?",
     Y: "a car?",
     N: "a cellphone?"
    }

It's possible for either child to be a string and the other a node; they don't have to simultaneously be strings. Or they could both be nodes. Any node that is not a string is another question.

The tree that is loaded from the server is saved to a global variable called loaded_tree (formerly current_tree). Feel free to poke around in it.

Task 1: Tree Display¶

One task is to write a function that will take the current tree and print it on the page in a nicely indented way. You'll do this by creating nested DIVs, one DIV for each node in the tree. Here's a screen shot where I've changed the border to red to make the divs visible:

You are welcome to use the Chrome Inspector to poke around in the reference solution and see the DIVs that it builds, so you'll know what your code needs to build.

Your function will be a recursive function that takes a tree node as an argument and returns a DOM element. That DOM element is unattached, meaning it has not been attached to any part of the page.

The base case of the recursion is when the node is a string, meaning that it is a guess, like "Frodo Baggins?". There's a hint below on how to detect this base case.

If the node is not a string, then it is a question node, and you should:

• create an unattached DOM element for this subtree.
• attach the question text to the DOM element
• recursively create DOM elements for the Y and N children and attach them to the DOM element
• return the DOM element

Write a top-level recursive function to do this.

Testing Tree Display¶

You can test your recursive function like this:

domElt = myRecursiveFunction(current_tree);
$("body").append(domElt);

This should remind you of how we tested the question construction in the Quizzes assignment; the only difference is that this time the function is recursive.

Tree Display Event Handler¶

Add an event handler for the "show tree" button that renders the tree to some (empty) place on the page. The reference solution puts it in #treedisplay. The event handler should also update the button to say "hide" and have the opposite functionality. If you have trouble with that, just have two buttons.

(Note that in my screenshot above and in the reference solution, I had some extra features: the first question was marked as such, and questions were marked as being Yes versus No. It's not hard to do that, but it is a little tricky, so you do not have to implement this. Just establish a convention that the Yes continuation is always first. I marked them above for clarity, though I'm sure you could figure out which was the yes and which was the no.)

Task 2: Game Play¶

Remember, you don't have to do Task 1 before Task 2. You can do them in either order, since they are independent.

To play the game, you'll implement a number of buttons, each one handling a yes or no question. Actually, you'll delegate all the work to a few handler functions.

There are different ways to organize the code, from 1 powerful handler function that handles all 4 kinds of buttons, to 4 simpler handler functions that each handles one kind of button. Your choice. The different buttons are:

1. A Yes answer to a question
2. A No answer to a question
3. A "Yes, you win" answer to a guess (computer wins by guessing correctly)
4. A "No, I win" answer to a quess (computer loses by guessing incorrectly)

Note that the game traces a path through a tree, but playing the game is not recursive. Each step in the game just goes from a node to one of its two children. That single step is not recursive. (Furthermore, there are no loops here.)

Here are some aspects of the implementation:

Where am I?¶

An important part of the game is knowing where you are in the tree. If it's the beginning of the game, you are at the root of the tree (loaded_tree). If the user has answered one question with a "yes", then you are at the Y child of the root, or loaded_tree.Y.

Your code should keep track of where you are in the game, meaning which node is the current node. You should have a global variable to keep track of where your place is in the tree, and update this variable whenever a user answers a question. In the reference solution, this variable is called gameNode (formerly currentTreeNode).

Next Game Step (Ask the Next Question)¶

You should implement a function that takes one node as an argument and does the next step in the game: either asks the question or makes the guess associated with that node. This will involve:

• building some structure to hold the question/guess text and two buttons (for yes and no). I did mine with cloning, find(), and .text(), but you can also do it by building structure, like we did with the quiz assignment. Indeed, I'm expecting that. The structure is smaller and simpler than in the Quizzes assignment.
• appending that structure to the list of questions, which is also similar to Quizzes.

The game will start with that function being invoked with the root of the loaded tree. As the game proceeds, that function will be invoked with a child of the current game node.

Processing an Answer¶

You'll write an event handler for clicking on the "Yes" button that does the following:

• removes both buttons
• chooses the correct child, and
• asks the next question (see the previous function)

Write a nearly identical function for "No". These will not be lengthy functions. Or combine them. Recall that I said this task could be done with 1 big function, 4 little functions or maybe something else.

Processing a Guess response¶

Two more functions will be necessary to handle the final yes/no question: correct and incorrect guesses. (I implemented them as different buttons, but you could use the same pair as before; there are many ways to attack this problem.) They will:

• remove both buttons
• insert an appropriate response (Yay or Boo)

Delegate¶

Attach these as event handler(s) on an ancestor to all the questions, so that the clicks will bubble up and have the correct action applied. The reference solution adds the event handler(s) to #questions.

Starting the Game¶

Have a button that starts the game by asking the first question. It should clear out whatever is left from the previous game.

Hints¶

You should start by copying the reference solution files and replacing the 20-static.js file which contains obfuscated code with an empty file. Make sure the resulting page loads correctly and the Ajax feature works.

You can test whether a node is a question or a guess by checking to see if it's a string. Here's how:

if( typeof( node ) === 'string' ) ...

You can start with either the tree display or the game play. Neither depends on the other.

The loaded_tree variable should not change as a result of either the tree display or the game play. It should only change when we fetch a new tree from the back end.

When implementing the tree display, make the recursive function a global function. Remember that it will not attach any structure to the page, so to test it, you'll have to do something like this:

x = recursive_tree_display_function(some_node);
$("#tree_goes_here").one().append(x);

That's also a hint about what the event handler function will have to do.

Note that to delete the existing tree (when you want to hide it), you can use the jQuery empty method.

When attacking the game play feature, I suggest starting with code to build the questions and the guesses, and later implement the button handlers.

Finally, all the event handlers should be added when the page loads, not dynamically.

Modularity¶

This assignment is hard enough, so don't worry about packaging things up in modules and IIFEs.

How to turn this in¶

Do all your work in a new folder called twenty. Turn in a Gradescope item.

Tutors/Graders¶

You can use the password to view the solution

Time and Work

The following link has been updated for Fall 2023.

Finally, when you have completed the assignment, make sure you fill out the Time and Work Fall 2023 That report is required.