12
$\begingroup$

The title speaks for itself. Here are Akinator and 20Q.

The principle of these games is to ask a user a number of questions relating to some entity chosen by the user. And then find out what is this entity. The core of the algorithm is to find the "most useful question" at each round, while dealing with a user who might not answer all questions correctly.

"most useful question" being defined as the question that give the most information, in the optimal case splitting the audience (or number?) of candidate entities into two equal halves.

I found a paper that described some algorithms (well the word "algorithm" was not used, but the proofs could be turned into algorithms). Unfortunately I cannot find this paper again :( . The paper described the problem with game theory concepts, with some levels of lying allowed to the user (it discussed 3 levels of lying). Please post if you think you know the paper.

$\endgroup$
1

1 Answer 1

14
$\begingroup$

I think you are probably looking for "On playing “Twenty Questions” with a liar", Dhagat, Gacs, and Winkler, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409

The many other papers that cite this one probably include additional relevant hits.

$\endgroup$
2
  • $\begingroup$ Does anyone have a source for the 2nd link? It is not available anymore. $\endgroup$ Commented Feb 16, 2015 at 23:05
  • $\begingroup$ The second link was obtained by going to Google scholar, finding the first paper, and then clicking on the "cited by NN" link that it shows for its results (where NN is the number of papers that cite this one). Presumably that procedure still works, even if Google has changed their URL format. $\endgroup$ Commented Feb 17, 2015 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.