Anti-Buzz: Twenty Questions

by Andrew Emmott on May 31, 2014

in Anti-Buzz

Andrew has been writing Anti Buzz for 4 years resulting in almost 200 articles. For the next several weeks we will revisit some of these just in case you missed it:

Computers generally run in a binary fashion, that is to say for any situation there are only two possible answers or next steps. How does that effect computing? Andrew gives us a good example using the old game of twenty questions:

 

newface-620x461Here and there I’m taken by the urge to impart some of the more abstract wisdom of computer science. I’ve made attempts in the past, perhaps with some success, but my approach has always been very direct: I try to explain a math or science topic in so-called layman’s terms, and I’m thinking I should do it the other way around. This article is the first of three parts, a sort of pilot program if you will, where I discuss three “normal” things and reveal their common computational elements. I’ll be moving in reverse chronological order. I hope to improve understanding of computation beyond just the gadgets you use everyday. The core ideas of computer science have been with humanity for a long time, independent of any screens and processors.

For this week, consider the game of Twenty Questions: One person thinks of something, and the other tries to guess what it is with a series of yes or no questions (limit 20). It is a straightforward enough parlor game, but if you play it enough times you might develop a sense of strategy, which is where the game stops being a free-flowing human endeavor and begins to look like a mathematical one.

What is the best question to ask?

We’ll get some obvious intuitions out of the way first. You typically want to avoid narrow questions. If you come out of the gate with “Is it a dog?” “Is it a cat?” “Is it a fish?” you are likely to burn through your questions too fast. “Is it an animal?” would have saved you a lot of trouble up front. Likewise, you need to respect the logical history of your questions. If you ask “Is it an animal?” and are met with “No” then it would be foolish to ask “Is it a dog?” Most people grasp these basic concepts, but suppose it has been put to you to figure out what the absolute best question to ask was, given any opponent or situation.

“Is it an animal?” is a good first question, but could it be better?

“Is it alive?” or even “Is it alive or made from living things?” seem better. Why? There is some risk versus reward at play: If you ask a narrow question, but the opponent answers “Yes” then you have it made it much easier for yourself, but if they answer “No” then you will have wished you asked a broader question. Conversely, if your question is too broad, then a “Yes” won’t help much either. What you want is a question that is equally helpful regardless of the “Yes” or “No” response. The optimal strategy is to always ask a question that cuts all the possibilities in half. In information theory, one might say you are trying to maximize binary entropy.

But how do you cut “all things a person might think about” in half? If there is an infinity of concepts, (debatable), then what might surprise you is that “cutting in half” is somewhat easy. To simplify the example, imagine that you were trying to guess a number. “Is it less than 60?” splits all the numbers in half; there are infinite numbers less than 60 and infinite numbers not less than 60. In geometry, this splitting of infinite space into two halves could be seen as finding a hyperplane. Of course, if you keep splitting infinity in half, you are still left with infinite possibilities, in which case it is a wonder that anybody ever wins this game.

newface-620x461Let’s jump ahead an say that you already have the solution; you have the perfect question that splits all human concepts in half. What’s the next question you should ask? It depends on the answer to the first doesn’t it? Every question you ask should try to split all remaining possibilities in half, but each answer is going to lead to a different half-of-everything. So for Round 2 you need to come up with two questions: one in case they answer “Yes” the first time, and another in case they answer “No.” Let’s say you accomplish this. To take stock of what we have, we have three questions included in our strategy, and four quarters-of-everything that we have reduced our problem to … and 18 questions left to ask. (Perfection is exhausting). I’ll run through one more round: four quarters-of-everything demand four new questions (seven total) and result in eight slices-of-everything. (Fans of Moore’s law should recognize that we are dealing with powers of two and that this is going to get exponentially complicated). Building up a solution in this way is called building a decision tree and specifically our approach is building a full and complete binary tree.

If you went to the trouble of planning out all 20 questions, (the goal being that you are asking ‘perfect’ questions and enacting a ‘perfect’ strategy), then you will need to prepare 1,048,575 questions which will lead you to 1,048,576 unique slices-of-everything, which is the upper limit on the number of “things someone might think about” that your strategy might account for. One can imagine defeating this ‘perfect’ strategy by simply choosing an item that is not on the list of 1,048,576, thus contradicting the very possibility of such a perfect strategy existing. (You probably didn’t realize that you were in the middle of reading a mathematical proof). However, in practice, covering over a million objects probably covers anything any reasonable opponent might choose, but even so, designing that near-perfect decision tree is significantly more work than you might have expected.

The impossibility of perfection, and the extreme complexity of coming close to perfection are precisely what made this game succeed as a parlor game and allow it to remain personal and fun while still offering a chance for enthusiastic players to “match wits” in a strategic sense. However, more modern incarnations of the game have called for a computer player, and computers are not good at ad-hoc guessing games in the same way humans are. To bring the point home, the careful formulation of over one million questions is not a matter of faster processors or a bigger 4G network – it’s an enormous amount of human work for very little pay-off. Needlessly to say, the electronic versions of twenty-questions require an amount of cleverness beyond the tedium of building a ‘perfect’ decision tree.

Twenty Questions is just one of many seemingly innocuous tasks that have large computational penalties associated with them. That complexity informs how we interact with it, even when we don’t realize it. (I argue that it makes Twenty Questions more fun as a parlor game because it can’t be aggressively solved). Next week we’ll go further back in time to observe this phenomenon.

by: at .

Share

Comments on this entry are closed.

Previous post:

Next post: