For a look at the finished application, see http://www.backstopmedia.com/examples/e4x.html. These articles assume that you are familiar with XML and JavaScript concepts. See the Resources if you need to polish up your skills. You will also need to have access to an E4X-capable browser such as Firefox 1.5 or above.

What you will accomplish

In this article you'll learn to create a simple "Twenty Questions" application that can guess the object that the user is thinking of, such as "a house cat" or "breakfast cereal." You might think that interpreting human thoughts requires a pretty sophisticated application. In fact, you can find a sophisticated, well-trained neural network at http://www.20q.net. This www.20q.net system has been "learning" for twenty-odd years, allows multiple shades of certainty—yes, no, unknown, irrelevant, sometimes, probably and doubtful—and (one would assume) all sorts of statistical analysis to interpret its database and seemingly read your mind.

In this article series, the sample application will be less sophisticated. Instead, you will implement a simple binary search, an algorithm that works on the theory that if you continue to eliminate as many non-suitable items in a set as possible that you'll eventually get to the one that you want. In fact, the name "twenty questions" stems from the theory that a set of everything in the universe can be narrowed down to just one item using about 20 different yes-or-no questions to narrow things down.

In Part 1, you'll build a self-contained system that starts with a fixed knowledge base and asks the user questions to determine the item he or she is thinking of. In Part 2, you'll start to train the system for new items. If it guesses wrong, the system asks what the correct item was and how to distinguish it from the rest of the knowledge base. It then adds that item to the knowledge base and starts again. Finally, you'll integrate that functionality with an external database so that everybody benefits from what the system learns from others.

Back to top

The algorithm

Now, all of this is easy to say, but how do you implement Twenty Questions in a browser? After all, a human can use intuition to determine the next question; how can you get the computer to decide?

It turns out that it's actually pretty straightforward. The binary search algorithm—or more generally, divide and conquer algorithms—involve eliminating roughly half of the possible choices with each question. So for example, if you started with 1024 possible choices, after the first question you'd be down to only 512, after the second only 128, after the third, 64, and so on. For 1024 possible choices, you'd need only 10 questions to get to the target. In fact, 20 questions let you distinguish between 1,048,576 different options!

In fact, it's not really that complicated an algorithm. It goes like this:

1. Load all items in the knowledge base.
2. Ask the user whether the item is "animal, vegetable, or mineral?"
   The rest of the application uses just "yes or no" answers, but this is a traditional "first question" and serves to eliminate roughly 2/3 of the possible choices right off the bat.
3. Eliminate all of the items that don't satisfy the answer to the question.
4. If you're down to just one item, ask the user if it's correct.
   If it's correct, reload the knowledge base and start again. If it's not correct, find out what the correct response is and ask the user for a question that would have distinguished the right answer from the wrong one. Add this information to the knowledge base. (You'll do this in Part 2.)
5. If you still have more than one item, determine the question that applies to the greatest number of the remaining items. (This is key; it enables you to eliminate the greatest number of potential items.)
6. Ask that question.
7. Return to step 3.

As it turns out, E4X is well suited to this kind of algorithm.

Note: Unfortunately, you can't force people to add correct information to the knowledge base, but people who don't are essentially making their own items unfindable.

Back to top

Introducing E4X

When you think of working with XML in a programmatic environment, what's the first thing that comes to mind? DOM? XPath? Or maybe the first thing that comes to mind is "OUCH, what a pain!" Yes, it's true; XML is a great data storage format, and a pain in the neck to manipulate. But what if you could easily create XML objects, easily access and even filter XML nodes, and easily serialize the data to a string for display or storage? That'd be less painful wouldn't it?

Well, welcome to E4X.

E4X uses a data-binding-like structure to make it possible to easily access parts of an XML document. For example consider this snippet (see Listing 1).

                
<script type="text/javascript;e4x=1">

myquestion = <question>
          <display>Is it animal, vegetable, or mineral?</display>
          <answerOption>Animal</answerOption>
          <answerOption>Vegetable</answerOption>
          <answerOption>Mineral</answerOption>
     </question>;
             
alert("The question is '" + myquestion.display + "'");             

</script>

Note: Please notice the script's type declaration. The addition of ";e4x=1" to the end of the type is necessary to turn off certain backwards compatible features in early Mozilla implementations of E4X.

First off that is NOT a typo; there are no quotation marks around the XML that you declare. You really can just drop it right into the code, which comes in handy, as you'll see later. (Fortunately, you also have the option to create the object from a string, as you'll also see later.) Second, notice that by using simple object syntax you can retrieve the value of the display element, giving a result like Figure 1.

In fact, retrieving information is simple even for non-text data. Consider Listing 2.

                
...
          </question>;

alert("The question is \n" + myquestion);   

Here you're referencing the whole XML document, and that's what you get, as you can see in Figure 2.

Wasn't that easy? No arcane serializers or transformations, just the data right where you need it.

E4X provides two basic classes you'll need: XML(), which approximates a document or an element, and XMLList(), which approximates a Nodelist. You'll see both in action in this article.

Now let's build the application.

Back to top

Create the knowledge base

The first step is to create the actual knowledge base. To do that, you'll use a single XML document that contains both the questions to ask and the targets to which they refer, as in Listing 3.

                
kdata = 
<knowledgebase>
   <questions>
       <question id="1">
          <display>Is it animal, vegetable, or mineral?</display>
          <answerOption>Animal</answerOption>
          <answerOption>Vegetable</answerOption>
          <answerOption>Mineral</answerOption>
       </question>
       <question id="2">
          <display>Does it bark?</display>
          <answerOption>Yes</answerOption>
          <answerOption>No</answerOption>
       </question>    
   </questions>
   <targets>
      <target id="1">
         <display>a house cat</display>
         <answer questionid="1"><answerValue1>Animal</
		                               answerValue1></answer>
         <answer questionid="2"><answerValue2>No</
		                               answerValue2></answer>
      </target>
       <target id="4">
         <display>a dog</display>
         <answer questionid="1"><answerValue1>Animal</
		                              answerValue1></answer>
         <answer questionid="2"><answerValue2>Yes</
		                              answerValue2></answer>
      </target>       
      <target id="2">
         <display>a carrot</display>
         <answer questionid="1"><answerValue1>Vegetable</
		                                 answerValue1></answer>
      </target>
      <target id="3">
         <display>a ruby</display>
         <answer questionid="1"><answerValue1>Mineral</
		                              answerValue1></answer>
      </target>
   </targets>
</knowledgebase>;

knowledgeBase = new XML(kdata);    

Look at this structure before you move on, because it contains the crux of the algorithm. First, you have questions and you have targets. The questions are easy; each one contains the actual question, and the possible answers. Except for the first question, you'll use only "yes" or "no." This structure gives the flexibility to add other possible answers later.

The targets include a target identifier (the id), the display name of the target, and an answer for each question the system knows about. For example it knows that a dog is an animal, and that it barks, whereas all it knows about a carrot is that it's a vegetable. Of course, that's all it needs to know; you wouldn't expect a vegetable to bark!

As the system learns new questions and answers, it will add them to the existing targets as appropriate.

Tip: If you want to start with a smarter system, you can download the current knowledge base at http://backstop.nicholaschase.com/knowledgebase.php?getkb=YES.

Back to top

Display the question

The next step is to actually ask the first question. To do that, you'll need to display it. One way to make this easy is to create customizable HTML, as in Listing 4.

                
<html>
<head>
<title>E4X mindreader</title>
<script type="text/javascript; e4x=1" src="e4x.js"></script>
<style type="text/css">
.answerLink {color: blue; text-decoration: underline}
</style>
</head>
<body style="background-color:#abdfe7;" onload="ask_question()">

<div id="questionFormDiv" 
   style="position: absolute;top: 50px;visibility: hidden; width: 100%;">

   <span id="displayQuestion"></span><br />

</div>

</body>
</html>

The idea here is that you have a div that you can turn on and off— off is the initial value—with a span for you to insert text. To do that, you need to be able to select a specific XML element.

Back to top

Filtering nodes

With E4X, you can select a node or nodes using filters, as in Listing 5.

                
...
knowledgeBase = new XML(kdata);    

var currentQuestion = 1;


//******************************
//   BEGIN FUNCTIONS HERE
//******************************
function ask_question(){

   var questionElement = knowledgeBase.questions.question.(@id == currentQuestion)
   
   var questionDisplay = questionElement.display;
   document.getElementById("displayQuestion").innerHTML = questionDisplay ;
     
   show_form("questionFormDiv");

}

function hide_form(divName){
    document.getElementById(divName).style.visibility = "hidden" ;
}
function show_form(divName){
    document.getElementById(divName).style.visibility = "visible" ;
}

When the HTML page loads, it calls the answer_question() function, so you'll create that first. The first step is to create a variable, questionElement, that holds the XML representing the first question. (Because you need to know what question you're on throughout, just make that a global. While not an ideal programming practice, this isn't meant as a production application.)

Notice the syntax at the start of the ask_question() function. It's very much like XPath predicates, and functions the same way. In this case, you select the knowledge base, then move down to the questions child of the root element, and then to all question children of the questions element. From there, you filter out any question elements that don't satisfy the filter—in other words, any elements but the question that you want.

The result is a single element, and you can easily pull out the display child of that element and, with standard DOM operations, display it on the page as in Figure 3.

Now you need to add the potential answers.

Back to top

Working with XMLLists

You can choose different ways to create a page that enables users to enter information. In this case, you'll use spans to simulate links, as in Listing 6.

                
   <span id="displayQuestion"></span><br />
   <span class="answerLink" 
            onclick="answer_question(this)" id="answer1Text"></span>
   <span class="answerLink" 
            onclick="answer_question(this)" id="answer2Text"></span>
   <span class="answerLink" 
            onclick="answer_question(this)" id="answer3Text"></span>

These links are constructed to refer to the answer_question() function you'll write in a moment. But first, you'll need to populate the answers, as in Listing 7.

                
...
   document.getElementById("displayQuestion").innerHTML = questionDisplay ;
        
   var answerOptions = new XMLList();
   answerOptions = questionElement.answerOption;

   var answerCounter = 0;
   document.getElementById("answer3Text").innerHTML = "";
   for each( var answerText in answerOptions) {
       answerCounter++;
       document.getElementById("answer"+answerCounter+"Text").innerHTML =
                                                               answerText;
   }
}
...

The answerOptions variable consists of an XMLList, which is similar to a DOM Nodelist. In this case, it consists of all of the answerOption elements that are part of the current questionElement. You can then use that list in a for each loop, referencing each one in turn and adding it to the appropriate span. (Clear the third span first because after the first question, it won't be used again.)

The result is a page that includes a link for each answerOption element, as you can see in Figure 4.

So what happens when the user answers the question?

Back to top

Answering the question

Remember, when the user answers a question, you want to filter out all of the items that no longer qualify based on the answer to that question. First, you need to get a set of the targets currently being considered, as in Listing 8.

                
...
var currentQuestion = 1;
var currentTargetSet = knowledgeBase.targets;

//******************************
//   BEGIN FUNCTIONS HERE
//******************************
function ask_question(){
...
}

function answer_question(answerSpan){
  hide_form("questionFormDiv");  

  var theAnswer = answerSpan.innerHTML;
  var remainingTargets = 
    currentTargetSet..target.(answer["answerValue"+currentQuestion]==theAnswer);

  alert("There are "+remainingTargets.length()+" targets remaining: \n" + 
                     remainingTargets);  

}
...

Notice that at the top of the listing, you create a new object, currentTargetSet, which initially holds the entire targets element. Once you get down to answer_question(), however, you'll start to thin that out.

After you retrieve the answer the user gave—remember, the function receives the actual span as an argument—you can filter currentTargetSet to create a new XMLList, remainingTargets.

Notice that I used two periods in this expression. Just as XPath uses the double slash (//) notation to represent descendants, E4X uses double periods (..). Here you first retrieve all target descendants of the root element, and then filter them down.

Take a good look at that filter. When you saw the brackets, you probably thought about XPath predicates, but that's not what you're doing here. Instead, the answer variable is a hash. Similar to the traditional way to reference form elements from JavaScript, the expression answer["answerValue1"] is identical to answer.answerValue1.

The advantage here is that you can dynamically name the element that you seek. In this case, the filter looks for target elements that have an answer.answerValue1 descendant with a value that matches the answer given by the user.

As before, the filtering process produces an XMLList, so you can retrieve the length of the list to see how many targets are left. For example, if the user chooses "Animal", you will see that two targets still remain, as in Figure 5.

With two targets left, you need to figure out the next question to ask, in order to distinguish between them.

Back to top

Selecting the next question to ask

According to the algorithm, the next question should be the most common question among the remaining targets, so you'll have to make an assumption. In a production system, you will probably store each question that is asked or find another way to make sure that you eliminate questions previously asked. In this case, you make the assumption that questions will be more specific as time passes and the knowledge base contains more items. I raise this because you'll make the assumption that questionid values get larger as you go along, making it possible to easily eliminate questions that were already asked, as in Listing 9.

                
...
  var remainingTargets = 
         currentTargetSet..target.(answer["answerValue"+currentQuestion] == theAnswer);
  alert("There are "+remainingTargets.length()+" targets remaining: \n" + 
             remainingTargets);            
      
  var targetContainer = <targets/>;
  currentTargetSet = new XML(targetContainer);
  currentTargetSet.targets = remainingTargets; 
    
  if (remainingTargets.length() == 1){
       // Make a guess
  } else {
   
      
    var remainingAnswers = currentTargetSet..answer.(@questionid > currentQuestion);

    mostPopularQuestionCount = 0;
    mostPopularQuestionId = 0;
    
    get_most_popular_question(remainingAnswers);
    currentQuestion = mostPopularQuestionId;
    ask_question();
  }
}

var mostPopularQuestionId = 0;
var mostPopularQuestionCount = 0;

function get_most_popular_question(answersToCheck){
    
    var answersToCheckElement  = <answersToCheckRoot/>;
    var checkElement = new XML(answersToCheckElement);
    checkElement.appendChild(answersToCheck);
    var firstId = checkElement..answer[0].@questionid;
    
    var thisQuestionCount = checkElement.answer.(@questionid == firstId).length();
    if (thisQuestionCount > mostPopularQuestionCount){
        mostPopularQuestionCount = thisQuestionCount;
        mostPopularQuestionId = firstId;
    }
    answersToCheck = checkElement..answer.(@questionid != firstId);
    
    if (answersToCheck.length() > 0){
        get_most_popular_question(answersToCheck);
    } else {
     //   alert("Most popular question is "+mostPopularQuestionId+", 
	 with "+mostPopularQuestionCount+" answers.")
    }
}
...

If you eliminate all targets that don't satisfy the user's answers and only one item remains, it's time to guess, which you'll see in a moment.

If, on the other hand, more than one item remains, you first need to reconstruct the currentTargetSet; remember, remainingTargets is just a list of target elements, so the first step is to create a new document, with a root element, and add those target elements to it.

Once you do that, you can get an XMLList of all of the remaining answers that have a questionid greater than the current question. It is from these answers that you need to choose the most popular question.

To do that, you'll create a recursive function, get_most_popular_question(). Each time it runs, it selects the first questionid value it finds, then figures out how many answers to that question are in the current set. It checks to see whether that's the highest question count so far, and if any other questions are in the current set, it sends them to run through the routine again.

Finally, set the currentQuestion to the most popular question and go back and ask again.

In this case, if you choose Animal to start with, you find you have two remaining targets, "a house cat" and "a dog". If you eliminate question 1, the most common question is 2, "Does it bark?"

Back to top

Making a guess

Once the user answers the question "Does it bark", you'll only have one target left. No matter what the answer is, it's time to make a guess, as in Listing 10.

                
...
  var targetContainer = <targets/>;
  currentTargetSet = new XML(targetContainer);
  currentTargetSet.targets = remainingTargets;    

  if (remainingTargets.length() == 1){
    currentGuessText = currentTargetSet.target.display;
    currentGuessId = currentTargetSet.target.@id;
    guess();
  } else {
    var remainingAnswers = 
          currentTargetSet..answer.(@questionid > currentQuestion);
    get_most_popular_question(remainingAnswers);
    currentQuestion = mostPopularQuestionId;
    ask_question();
  }
}

var currentGuessText = "";
var currentGuessId = "";

function guess(){
    document.getElementById("guessSpan").innerHTML = currentGuessText;
    show_form("guessDiv");    
}
...

If you're ready to guess, it means that the currentTargetSet includes just the guess, so you can create globals for currentGuessText and currentGuessId and display the guess div, as shown in Listing 11.

                
<div id="guessDiv" style="position: absolute; top: 50px;visibility: hidden;  
                          width: 100%;">

     It's <span id="guessSpan"></span>, right?<br />
     <a href="#" onclick="start_over()">YES!  You're right!  
                                         Let me try again.</a><br />
     <a href="#" onclick="get_new_target()">No, sorry!</a><br />

</div>

</body>
</html>

So if you choose Animal, Yes, the application should guess "a dog", as in Figure 6.

You'll deal with what happens if it guesses wrong in Part 2, but first look at what to do if the application guesses correctly.

Back to top

Guessing right

The start_over() function is pretty straightforward, as you can see in Listing 12.

                
function start_over(){
    hide_form("guessDiv"); 
    currentQuestion = 1;
    currentTargetSet = knowledgeBase.targets;
    ask_question();
}

To start over, you want to hide the guess div, then reset both the currentQuestion and the currentTargetSet, and go back to ask_question() to display the first question again.

But what if it guesses wrong? If it guesses wrong, you need to teach it about the correct item, and you'll see how to do that in Part 2.

Back to top

Next steps

In this article, you learned how to use E4X to implement a bubble sorting routine in the form of a game of Twenty Questions. You learned how to create and manipulate both E4X XML() objects and XMLList() objects, and how to use object syntax to access the data within them. You also learned how to use filters to limit the nodes in a given set.

But the application is still pretty simple. In a production application you might want to increase the range of possible answers to include "sometimes" or "I don't know" but at that point you'll also have to increase the complexity of your algorithm to accept multiple possible answers for an item. You won't do that in this series—you can license the 20Q.net algorithm if you really need that (see Resources)—but in Part 2 you will integrate your system with a backend database so the system learns about new items as people play it.

Back to top

Download

Information about download methods

Resources

Learn

• Live sample application: See and try the finished Twenty Questions application for this article.
  
  
• E4X specification (PDF file, 1.81 MB): Read the official syntax and semantics for ECMAScript for XML, a set of programming language extensions that add native XML support to ECMAScript.
  
  
• Ajax and scripting Web Services with E4X (Paul Fremantle and Anthony Elder, developerWorks, April 2005): In this article, find a more complex example of E4X and JavaScript combined to initiate Web services requests.
  
  
• Sample knowledge base: Download the latest version of the knowledge base the Twenty Questions application.
  
  
• 20q.net: Try a real implementation of Twenty Questions using a neural net.
  
  
• The Game of Twenty Questions: Learn strategies for playing Twenty Questions with humans.
  
  
• Binary search algorithm: On Wikipedia, learn more about this technique to find a particular value in a sorted list.
  
  
• Tutorial: Build apps using Asynchronous JavaScript with XML (Naveen Balani and Rajeev Hathi, developerWorks, November 2005): Learn to develop and design Web applications based on Asynchronous JavaScript with XML, or Ajax.
  
  
• Ajax and XML: Five Ajax anti-patterns (Jack Herrington, developerWorks, March 2007): Learn which common practices of Ajax coding to avoid in this article.
  
  
• Ajax and XML: Five common Ajax patterns (Jack Herrington, developerWorks, March 2007): Look at five common Ajax design patterns that you can use as a basis for your own work.
  
  
• Ajax for Java developers: Build dynamic Java applications (Philip McArthy, developerWorks, September 2005): Dig into this five-part series that introduces a groundbreaking approach to creating dynamic Web application experiences using Ajax.
  
  
• IBM XML certification: Find out how you can become an IBM-Certified Developer in XML and related technologies.
  
  
• XML technical library: See the developerWorks XML Zone for a wide range of technical articles and tips, tutorials, standards, and IBM Redbooks.
  
  
• developerWorks technical events and webcasts: Stay current with technology in these sessions.
  
  
• The technology bookstore: Browse for books on these and other technical topics.
  
  

Get products and technologies

• IBM trial software: Build your next development project with trial software available for download directly from developerWorks.
  
  

Discuss

• Participate in the discussion forum.
  
  
• XML zone discussion forums: Participate in any of several XML-related discussions.
  
  
• developerWorks XML zone: Share your thoughts: After you read this article, post your comments and thoughts in this forum. The XML zone editors moderate the forum and welcome your input.
  
  
• developerWorks blogs: Check out these blogs and get involved in the developerWorks community.
  
  

About the author

Rate this article

Comments

Back to top

Table of contents

• What you will accomplish
• The algorithm
• Introducing E4X
• Create the knowledge base
• Display the question
• Filtering nodes
• Working with XMLLists
• Answering the question
• Selecting the next question to ask
• Making a guess
• Guessing right
• Next steps
• Download
• Resources
• About the author
• Comments

Next steps from IBM

Create rich Internet applications using WebSphere Portal Express Web 2.0 technologies.

---

• Try: WebSphere Portal Express
• Article: Get started using Ajax and WebSphere Portal Express
• Tutorial: Quickly build a an Ajax-enabled WebSphere Portal Express Web application
• Demo: Architecture, design, and construction using the IBM Rational Software Delivery Platform: AJAX
• Buy: WebSphere Portal Express

Dig deeper into XML on developerWorks

IBM SmartCloud trial. No charge.

Unleash the power of hybrid cloud computing today!

---

Public and private solutions in one trial.

Special offers