guessing games 1

One of the first programs I ever wrote was a number guessing game:

I'M THINKING OF A NUMBER BETWEEN 1 AND 20
> 7
HIGHER
> 15
HIGHER
> 18
LOWER
> 17
YOU WIN

(The Commodore 64's green was brighter of course, but I wouldn't do that to you). The best strategy for beating the game, of course, is to pick the middle number of the range first in order to break the range in half. If that didn't happen to be the right number, you have a new possible range that's half the size, and you repeat the process. This is binary search at its purest. It's the best strategy in two ways: it always finishes in at most 5 guesses (worst-case performance), and the average number of guesses needed if you pick randomly is 3.7 (average-case performance).

I tried to write a program to do the guessing, but I couldn't work out how to let the user type "higher" or "lower" instead of numbers, and I gave up.

twenty questions

It's the same game, except instead of a number you can pick anything, and the guesser is allowed twenty yes-or-no questions to try to work out what it is.

I'M THINKING OF A SOMETHING
> IS IT ORGANIC?
YES
> IS IT ALIVE?
YES
> IS IT A PLANT OR AN ANIMAL?
YES
> LOL, IS IT A PLANT XOR AN ANIMAL?
NO
> IS IT ROBERT PLANT?
YOU WIN

Obviously it wouldn't be an easy program to write, but in theory it's possible if we formalise the game. First we need a dictionary, a list of all the possible objects the computer can be thinking about. There can only be a finite number if we want the game to be winnable.

Next we need a set of questions. Every yes-or-no question breaks the dictionary up into two sets: things that answer 'yes' and things that answer 'no'. We can characterise all questions by the sets of things that answer 'yes' (the objects they accept). Two questions that accept the same objects are really the same question.

Suppose our dictionary is {barrel, cat, dog, ball, fish, box, building}. The question "is it an animal?" accepts the objects {cat, dog, fish}. It's the same question, for our purposes, as "is it a cat or a dog or a fish" or "does it not begin with b".

If we allow any question (that is, any set of objects) to be asked, then the game becomes trivial: we can reduce it to the number guessing game. Just number all the objects, break them into ranges, and ask questions like: "Is it barrel or cat or dog". This is the optimal strategy, which implies that you can't always win at twenty questions if there are more than a million possible answers. But it makes for long and boring questions, so in the informal game we might say you're only allowed twenty words per question. In the formal game we'll say you're provided with a list of questions you're allowed to ask.

So our dictionary might be: {barrel, cat, dog, ball, fish, box, building}. And our questions might be:

• {cat, dog, fish} ("is it an animal?")
• {cat, dog, ball, box} ("can you play with it?")
• {barrel, ball, box, building} ("does it begin with b?")
• {barrel} ("is it a barrel?")
• {cat} ("is it a cat?)
• etc...

The "is it a X" questions aren't strictly required, you could say you 'win' as soon as you know exactly what the object is. They do guarantee it's possible to win though.

A strategy for 20 questions is a tree flowchart like the one for the guess-the-numbers game. Here's one for a poor strategy: just guessing.

The height of the tree is 6 which indicates it may take us six guesses to work out the object in the worst case. This next one is better (height 3). In fact it's optimal: since it is as good as binary search we know there is no better strategy. Usually the optimal strategy won't be as good as binary search.

The question is: how do we efficiently calculate the optimal strategy? Either on the fly - i.e. given the information we have so far, determine the next question to ask - or by pre-computing the entire flowchart.

More formally: given a set S and a collection of subsets T ⊆ ℘(S), construct a binary tree with leaves S and internal vertices T of minimal height, such that every left-descendant of t is in t, and no right-descendant is.

An obvious heuristic, reminiscent of binary search, is to always ask a question that splits the remaining possibilities as close to evenly as possible. While we might expect that this 'greedy algorithm' is optimal, it isn't due to interactions between questions. In the diagram below, question A divides the space of objects neatly in half, but whatever question we ask next we can be left with around a third of the objects afterward. Starting with questions B and C guarantees only a little more than a quarter of the possibilities remain after two questions.

A naive but approach is to recursively find the best left and right subtrees for the subsets induced by each first question, and choose the question that gives minimal max-height. Ultimately this runs takes exponential time since we find the tree for all 2ⁿ subsets of the dictionary. It has the feel of a hard problem, I wonder if exponential time is the best possible.