How can I implement a "20 Questions" algorithm?

Question

Ever since childhood, I've wondered how the 20Q electronic game worked. You think of an object, thing, or animal (e.g. potato or donkey). The device then asks you a series of questions such as:

• Is it larger than a loaf of bread?
• Is it found outdoors?
• Is it used for recreation?

For each question, you can answer yes, no, maybe, or unknown. I always imagined it work with immense, nested conditionals (if-statements). However, I think that's an unlikely explanation because of its complexity for the programmer.

How would I implement such a system?

Answer 1

I don't know how 20Q did it specifically, but there is plenty of information on how to implement a game of 20 questions.

There are lots of ways of solving this, but I'll describe one way. These games can implement some sort of decision tree. For an electronic game like 20Q, this tree would be precomputed and fairly easy to traverse. There are methods for using learning decision trees where the game can accept new objects at the end of it's questions if it's unable to guess what the user is asking.

When the questions are a series of yes or no answers, you end up with a binary tree. Each node is a question and the leaves are answers. When questions are answered with unknown or not sure, the child nodes can be combined and their questions asked in series to further cull the possible answers.

Basically this is the process:

1. Start with a full list of the objects. These can all start at equally likely, or they can be sorted by how likely the object was to be chosen in testing.
2. Start with the first question in the decision tree. Push it onto the question queue.
3. Ask the question on top of the queue.
4. Process response:
   1. Yes/No answers removes/adds a predetermined amount of probability from each answer based on the question.
   2. "Maybe" answer removes/adds a fraction of the predetermined amount of a "yes".
   3. "Unknow" does not change probabilities
5. An "Unknown" or "Maybe" response pushes both of the next nodes questions onto the question queue. A "Yes" or "No" response just adds the one respective yes/no node onto the question queue.
6. Go to step 3 until out of questions or probability of a single answer is beyond a predefined "certainty" threshold.
7. Provide most probable answer.

Generating the tree is probably the topic of another question. But basically it's choosing questions that split the answers as much as possible. Put the questions that divide the questions most equally near the beginning so that the most number of questions can be culled the fastest.

Answer 2

The simple answer is that the handheld game 20Q was created from the artificial intelligence that lives at http://20Q.net. At 20Q.net you can play different versions of the game of Twenty Questions, similar to the toy except that the game learns from every game played. The handheld toy uses the same neural network algorithms. The neural network picks the questions to ask as well as making guesses. This approach means that the A.I. will often guess correctly even if you answer a question differently from what the A.I. has been taught. Another advantage is that the game will ask questions differently every game even if you are thinking of the same thing.

The algorithms and the neural network of the classic english game (Animal, Vegetable, Mineral) was created in 1988 by Robin Burgener . . . me.

Thanks for asking.

Answer 3

I googled "20q code" and found this: http://mosaic.cnfolio.com/B142LCW2008A197

This version is only for animals but the actual 20 Questions probably has a similar algoritm.

Here is a quick overview of the code I linked:
There are several different answers hard coded into the program. Several TRUE or FALSE attributes are then assigned to them:

#define ANIMALS_LIST      "daddylonglegs bee penguin eagle giraffe octopus tiger elephant jellyfish bull \nparrot dolphin python crocodile cat leopard monkey zebra sheep rat \nowl spider frog polarbear snail tortoise rabbit salmon rhino fox"
#define MAMMALS                    "0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1"
#define FLYING_ANIMALS             "1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
#define WATER_ANIMALS              "0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0"
#define BEAK                       "0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0"
...

As you can see a bee is not mammal but it does fly, etc.

There is an array for each group:

int   mammals[ TOTAL_ANIMALS ] = { 0 };
int   flying_animals[ TOTAL_ANIMALS ] = { 0 };
int   water_animals[ TOTAL_ANIMALS ] = { 0 };
...

When each question is asked:

  askUserQuestion( guesses, "\nQuestion %d: Is your animal a mammal? \n", mammals );

The program looks at the definition of the appropriate category and tracks which animal is most likely the one you are thinking of based on the TRUE or FALSE values and your inputed Yes or No answer to the question.

This is done in:

void askUserQuestion( int guessNumber, char* question, int* animalData );

Answer 4

It's not a massive decision tree or a bunch of hard-coded if/else statements. Robin Burgener, the inventor, completely documented his algorithm in his 2005 patent filing. It's ingeniously simple.