Hey, i've been thinking: how does the akinator work? (en.akinator.com) I tought about some answers and i even did a simulation (took me four days), but i wish to know what do you people think about it.

(cause my simulation doesnt work very well, especially the part about the question select, where the intelligent agent has to select a question to ask to the client)

Sorry by the bad english, but i think my text is understandable

asked 15 Oct '11, 17:03

Macmod's gravatar image

Macmod
31113


The best question to ask would be the one that brings it closest to the goal. The goal would be to have only a single remaining possible candidate, and so a good heuristic would be the number of possible remaining candidates. Therefore, your best bet for approaching the goal directly would be to reduce the number of remaining candidates as much as possible with each question.

Since the problem is stochastic (he doesn't know whether you will answer yes or no), the way to ensure the remaining group is as low as possible is to split the group down the middle as closely as possible. The more uneven the split, the more chance that your answer will be in the 'larger' half, and the greater the list of remaining candidates, on average. (Although even ignoring the fact that your answer is probably more likely to be in the 'larger' half, this method of splitting ensures reliability.)

Thus if half the people in his database were men, and half were women, then that would be the best candidate for the first question.

By this reckoning, he would be accurately able to guess 2^20 people, under optimal conditions.

link

answered 16 Oct '11, 05:52

Fishy's gravatar image

Fishy ♦
2.8k825

edited 16 Oct '11, 06:04

1
An excellent description: partitioning the knowledge base in such a way it can minimize the number of questions. I expect that a system like this, which has been online and used by a wide variety of people, also has statistics on the most common choices. Partitioning the space so common choices are focused on for elimination or confirmation would accelerate the rate of convergence.
(17 Oct '11, 17:43) Godeke ♦ Godeke's gravatar image

The Akinator is a smart phone and web based game that can determine which character a player is thinking of by asking him/her a series of twenty, or less, questions.

You can think of it as the Binary Search Algorithm. In each iteration, we ask a question, which should eliminate roughly half of the possible word choices. If there are total of N words, then we can expect to get an answer after log2(N) questions.

With 20 question, we should optimally be able to find a word among 2^20 = 1 million words.

One easy way to eliminate outliers (wrong answers) would be to probably use something like RANSAC. This would mean, instead of takinging into account all questions which hae been answered, you randomly pick a smaller subset, which is enough to give you a single answer. Now you repeat that a few times with different random subset of questions, till you see that most of the time, you are getting the same result. you then know you have the right answer.

Ofcourse this is just one way of many ways of solving this problem.

link

answered 16 Oct '11, 06:54

aarvy_ravi's gravatar image

aarvy_ravi
761

Wikipedia has an article about RANSAC: http://en.wikipedia.org/wiki/RANSAC
(17 Oct '11, 17:27) EllenL EllenL's gravatar image

What fun, thanks for the link. I stumped it with Alexander von Humboldt, then I replayed with the same character in mind but the akinator still gave up. It asked twice if my character had Spanish origins, so either it is a stupid algorithm or it is clever enough to work around human errors. But it's offline now so I can't test further.

I'll bet if a German player thought of Alexander von Humboldt the akinator would have figured it out, but I'm American.

link

answered 16 Oct '11, 04:41

EllenL's gravatar image

EllenL
3.1k418

I tried akinator again -- it only asked my age and gender, so didn't know that I'm American. But I used the English version so that was a clue. Is there a German version? If so, would someone please test akinator in German with "Alexander von Humboldt" and let us know if it's right on the first try? Today's play led to a third failure for Alexander v.H. but then akinator got it right on the fourth try. As before, akinator asked some questions that it already knew the answer to. But those occurred in the continuation questions, not in the original twenty. I played around with uncertain answers (maybe yes, I don't know, maybe no) but didn't figure out anything about the program that way.
(17 Oct '11, 17:46) EllenL EllenL's gravatar image
The reason for the repeated questions is that it considers them distinct. Users can submit their own questions, which it can probably learn about by using them with characters it has already identified. But it can't tell if two questions are equivalent. Playing with the German version, I found quite a few questions that were simple reformulations, e.g. "is your character dead" vs. "is your character deceased", more so than in the English one. As for Alexander von Humboldt, the German version guessed correctly after the second round of questions, drilling down Real? -> Alive? -> Nazi? -> Actor? -> Scientist? -> Travels a lot? -> What he looks like (with several irrelevant questions interspersed).
(18 Oct '11, 06:29) DataWraith DataWraith's gravatar image

When i was learning about AI before, we implemented something called Expert System, it is used to make medical system or for techinal support. It is something that learns from new information and it is usually used as a classificator. I think Akinator uses that.

link

answered 16 Oct '11, 06:32

juansev's gravatar image

juansev
143

When i was learning about AI before, we implemented something called Expert System, it is used to make medical system or for techinal support. It is something that learns from new information and it is usually used as a classificator. I think Akinator uses that.

link

answered 16 Oct '11, 06:33

juansev's gravatar image

juansev
143

It's simply an Expert System.

The system compares your input with a database of facts, and infer based on predefined rules.

You can easily implement something similar to akinator with CLIPS. It's relatively easy to implement the system and the rules, the problem resides in the database of facts, because for your system to be accurate and efficient you need a huge database of facts.

link

answered 16 Oct '11, 09:28

lrq3000's gravatar image

lrq3000
2.0k419

edited 16 Oct '11, 09:29

Your answer
toggle preview

Follow this Question via Email

Once you sign in you will be able to subscribe for any updates here

Q&A Editor Basics

  • to upload an image into your question or answer hit
  • to create bulleted or numbered lists hit or
  • to add a title or header hit
  • to section your text hit
  • to make a link clickable, surround it with <a> and </a> (for example, <a>www.google.com</a>)
  • basic HTML tags are also supported (for those who know a bit of HTML)
  • To insert an EQUATION you can use LaTeX. (backslash \ has to be escaped, so in your LaTeX code you have to replace \ with \\). You can see more examples and info here

powered by OSQA