Ever since I was a kid, I've wondered how they made the 20Q electronic game. In this game, which is it's on device, you think of an object, thing, or animal (e.g. a potato or a donkey), once you mentally choose your thing, the device goes through 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 of the questions you can answer yes, no, maybe, or unknown. The way I've always thought of it to work was with immense, nested conditionals (if statements). But, I don't think that would be very likely as it would be terribly difficult to understand while coding it.

I'm not looking for a discussion as SE doesn't allow it; I'm looking for concrete knowledge or solutions.

-

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:
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.

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.

-
+1 Great answer. Very helpful. –  Dan the Man Oct 18 '12 at 18:35

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.

-
Hello Robin, welcome to the site. Who better to answer this question than the inventor himself. It's interesting to know how complex the 20Q actually is. Thanks for your contribution to the site and more so your contribution to artificial intelligence. Hopefully you'll visit the site occasionally and answer A.I. questions :). –  Byte56 Oct 18 '12 at 22:01
hehe, love it when this happens xD . –  joxnas Oct 20 '12 at 17:26

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 };
...
``````

``````  askUserQuestion( guesses, "\nQuestion %d: Is your animal a mammal? \n", mammals );
``````void askUserQuestion( int guessNumber, char* question, int* animalData );