What algorithm is behind the game Akinator?

Question

I was always surprised how the Akinator app could guess the character by asking several questions at once. So I wonder, what algorithm or method allows this to be done? Is there a name for this class of algorithms and where can I find out more about them?

Answer 1

Yes, there is a name for this class of algorithms - it is called classification algorithms in the field of machine learning . Decision trees are one example of a classification algorithm.

In this problem classification function of the algorithm are the answers to the question.

The solution of the question of which question should be asked can be carried out in various ways - for example, by maximizing the predicted (or average) entropy from the following question.

Answer 2

This game is sometimes known as 20 questions. There are some questions on SO on SO, for example:

• How does 20 AI algorithm work?
• Development of an algorithm of 20 questions
• does akinator work with the database?

Answer 3

Key characteristics of the algorithm:

• Self-enlightenment
• Errors Indulgence
• Intelligent system next question selects

The model of the game algorithm of Akinator is called "Expert system based on fuzzy logic."

And these are NOT decision trees, because he has no mistakes - indulgence.

I wrote once in C #, you can find it at the link: https://github.com/ukushu/AkinatorEngine

Answer 4

I think it looks like an expert system with a B-Tree structure.

Answer 5

I don’t know which algorithm Akinator uses, but here I put in an open-source algorithm that provides the same effect: https://github.com/srogatch/ProbQA.

Usually we use a cube from N(Questions) times N(Answer Options) times N(Targets) , see https://github.com/srogatch/ProbQA/blob/master/ProbQA/PqaCore/CpuEngine.decl.h .

We train the cube using the Bayesian formula with the assumption of independence, see https://github.com/srogatch/ProbQA/blob/master/ProbQA/PqaCore/CEEvalQsSubtaskConsider.cpp

Since the code is highly optimized for AVX2 and multithreading, it can be difficult to read. It may be easier to read the CUDA code for the same: https://github.com/srogatch/ProbQA/blob/master/ProbQA/PqaCore/CudaEngineGpu.cu

An application of this algorithm is also available as a website to recommend the game .