Designing a twenty questions algorithm

Question

I am interested in writing a twenty questions algorithm similar to what akinator and, to a lesser extent, 20q.net uses. The latter seems to focus more on objects, explicitly telling you not to think of persons or places. One could say that akinator is more general, allowing you to think of literally anything, including abstractions such as "my brother".

The problem with this is that I don't know what algorithm these sites use, but from what I read they seem to be using a probabilistic approach in which questions are given a certain fitness based on how many times they have to lead to correct guesses. This SO question presents several techniques, but rather vaguely, and I would be interested in more details.

So, what could be an accurate and efficient algorithm for playing twenty questions?

I am interested in details regarding:

What question to ask next.

How to make the best guess at the end of the 20 questions.

How to insert a new object and a new question into the database.

How to query (1, 2) and update (3) the database efficiently.

I realize this may not be easy and I'm not asking for code or a 2000 words presentation. Just a few sentences about each operation and the underlying data structures should be enough to get me started.

Answer 1

The 20 questions game can be implemented on some sort of decision tree. For an electronic game like 20 questions, this tree would be precomputed and fairly easy to traverse. There are methods for implementing learning decision trees where the game can accept new objects at the end of its 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.

Following are the steps for 20 questions:

• Start with a full list of the objects. These can all start at once or they can be sorted by how likely the object was to be chosen in testing.

• Start with the first question in the decision tree. Push it onto the question queue.

• Ask the question on top of the queue.

• 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. "Unknown" does not change probabilities

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

• Go to step 3 until out of questions or probability of a single answer is beyond a predefined "certainty" threshold.

• Provide the most probable answer.

Are you planning to step into the world of AI jobs? Go through Top artificial intelligence interview questions and crack all AI-related interviews easily!