Spammy looking site, but amazing technology. Can anyone explain the algorithm? | Hacker News Reader

Spammy looking site, but amazing technology. Can anyone explain the algorithm?

us.akinator.com

6 pointsElite10 comments

If you can find 20 questions so that each question roughly halves the sample size depending on the answer, you can halve a big set of people 20 times, thus yielding a set of size 2^20 = 1 048 576 times smaller than the original.

So if you take a set of people of size 1 million and ask the right 20 yes/no questions you can almost always figure out the right person. Of course, the more questions you ask, the finer the result (with 30 questions it's 1 billion). Also, these questions don't have to be binary, thus they can cut a set in e.g. 1/5, not half.

Of course with real world questions this is much harder to do, but with a clever question selecting algorithm it could be done this way, I suspect.

I suspect it's implemented using decision trees.

http://en.wikipedia.org/wiki/Decision_tree

This "Guess the Dictator" game was a hit years ago, http://www.smalltime.com/Dictator. It's pretty much the same thing and they're lots of fun. http://hunch.com is leveraging this type of decision tree learning nicely today.

Something similar to Twenty Questions? http://en.wikipedia.org/wiki/Twenty_Questions

I know it is old, but no-one has hit on exactly what is happening. It is decision trees, and it does make use of the winnowing effect of true-false questions. The last ingredient is user feedback. If it cannot correctly guess your character, it asks you to enter them. It then saves your person and the decision tree that got you to them for future use: croudsourcing.

I got it confused on Gorodish -- it offered Jean Valjean, which is a good approximation, and afterwards Quasimodo, which isn't really. But afterwards it got all correct.

Not so amazing to me. I tried for 10 minutes to lead it to Kevin Bacon, no luck.

Character to find : Kevin Bacon

Question Answer given Answer expected

Does your character really exist? Yes Yes

Is your character an adult man? Yes Yes

Is your character a citizen of the United-States? Yes Yes

Does your character play in movies? Yes Yes

Is your character currently more than 50 years old? Yes Yes

Is your character dead ? No No

Does your character use intense violence in his movies? Probably not No

Is your character white? Yes Yes

Has your character ever been nominated for an Oscar? No Don't know

Does your character have a moustache? No No

Is your character from a TV series? No No

Is your character a singer? No No

Does your character mostly play in comedies? No No

Does your character often play in action movies? No No

Is your character a porn actor? No No

Has your character ever retired? No No

Is your character an actor? Yes Yes

Does your character appear in a dance movie? Yes Yes

Is your character a disciple of Muten Roshi/Turtle Hermit in Dragon Ball? No No

Is your character silver-haired? No No

You have to answer the questions accurately. He guessed correctly on the first attempt and in 20 questions. Even though I don't know how a someone can really exist and be a character in Dragon Ball and it asks if he is an actor even though earlier he asked if they play in movies.

Odd, I answered every query identically but did not get the violence question and then my line diverged from there. An element of randomness?

Pretty good. I was thinking Faramir, and it guessed Boromir.

Reply on news.ycombinator.com