[Contents]

Copyright © 2007 jsd

Twenty Questions
John Denker

1  Overview of the Puzzle

Let’s analyze the well-known parlor game called “Twenty Questions”.

The rules are simple: One player (the oracle) picks a word, any word in the dictionary, and the other player (the analyst) tries to figure out what word it is. The analyst is allowed to ask 20 yes/no questions.

When children play the game, the analyst usually uses the information from previous questions to design the next question. Even so, the analyst often loses the game.

In contrast, an expert analyst never loses. What’s more, the analyst can write down all 20 questions in advance, which means none of the questions can be designed based on the answers to previous questions. This means we have a parallel algorithm, in the sense that the oracle can answer the questions in any order.

I’ll even tell you a set of questions sufficient to achieve this goal:

1) Is the word in the first half of the dictionary?
2) Is the word in the first or third quarter?
3) Is it in an odd-numbered eighth?
*) et cetera.

You can understand this as follows: There are only about 217 words in the largest English dictionaries. So if you use the questions suggested above, after about 17 questions, you know where the word sits on a particular page of the dictionary.

Note that if you ask only 15 questions about a dictionary with 217 entries, you will be able to narrow the search down to a smallish area on the page, but you won’t know which of the words in that area is the right one. You will have to guess, and your guess will be wrong most of the time. The situation is shown in figure 1.

20q
Figure 1: Correctness versus Information

You can see that it is important to choose the questions wisely. If you use non-incisive questions such as

1) Is the word “aardvark”?
2) Is the word “abacus”?
3) Is the word “abaft”?
*) et cetera.

it would require, on average, hundreds of millions of questions to find the right word.

This can be seen as an exercise in hypothesis testing, of the sort discussed in reference 1. We have hundreds of millions of hypotheses, and the point is that we cannot consider them one by one. We need a testing strategy that can rule out huge groups of hypotheses at one blow. Another example (on a smaller scale) can be found in reference 2. Additional examples can be found in reference 3 and reference 4.

2  References

1.
John Denker,
“How to Define Hypothesis”
www.av8n.com/physics/hypothesis.htm

2.
John Denker,
“The Twelve-Coins Puzzle”
www.av8n.com/physics/twelve-coins.htm

3.
John Denker,
“Learning, Remembering, and Thinking”
www.av8n.com/physics/thinking.htm

4.
For a general discussion of what entropy is, see:
www.av8n.com/physics/thermo/entropy.html
[Contents]

Copyright © 2007 jsd