Quel algorithme se cache derrière akinator ou 20q?

12

Le titre parle de lui-même. Voici Akinator et 20Q .

Le principe de ces jeux est de poser à un utilisateur un certain nombre de questions relatives à une entité choisie par l'utilisateur. Et puis découvrez ce qu'est cette entité. Le cœur de l'algorithme est de trouver la "question la plus utile" à chaque tour, tout en traitant avec un utilisateur qui pourrait ne pas répondre correctement à toutes les questions.

la "question la plus utile" étant définie comme la question qui donne le plus d'informations, dans le cas optimal en divisant l'audience (ou le nombre?) des entités candidates en deux moitiés égales.

J'ai trouvé un article qui décrivait certains algorithmes (enfin le mot "algorithme" n'était pas utilisé, mais les preuves pouvaient être transformées en algorithmes). Malheureusement, je ne retrouve pas ce document :(. Le document décrit le problème avec les concepts de la théorie des jeux, avec certains niveaux de mensonge autorisés pour l'utilisateur (il a discuté de 3 niveaux de mensonge). Veuillez poster si vous pensez connaître le document.

ds.algorithms BenoitParis
la source
1
stats.stackexchange.com/questions/6074/… Voici une discussion sur stats.SE
Tomek Tarczynski

Réponses:

14

Je pense que vous cherchez probablement "A jouer" Vingt questions "avec un menteur", Dhagat, Gacs et Winkler, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409

Les nombreux autres articles qui citent celui-ci incluent probablement des hits pertinents supplémentaires.

David Eppstein
la source
Quelqu'un at-il une source pour le 2ème lien? Il n'est plus disponible.
Ryan
Le deuxième lien a été obtenu en allant sur Google scholar, en trouvant le premier article, puis en cliquant sur le lien "cité par NN" qu'il montre pour ses résultats (où NN est le nombre d'articles qui citent celui-ci). Vraisemblablement, cette procédure fonctionne toujours, même si Google a changé son format d'URL.
David Eppstein