Comment fonctionnent 20 questions?

Question

Jeux en ligne simples de 20 questions alimentés par une intelligence artificielle extrêmement précise.

Comment devinent-ils si bien?

Answer 1

Vous pouvez le considérer comme l'algorithme de recherche binaire. À chaque itération, nous posons une question qui devrait éliminer environ la moitié des choix de mots possibles. S'il y a un total de N mots, alors nous pouvons nous attendre à recevoir une réponse après les questions log2 (N). Avec une question de 20, nous devrions trouver de façon optimale un mot parmi 2^20 = 1 million de mots.

Un moyen facile d'éliminer les valeurs aberrantes (mauvaises réponses) serait probablement d'utiliser quelque chose comme RANSAC. Cela signifie qu'au lieu de prendre en compte toutes les questions auxquelles vous avez répondu, vous choisissez au hasard un plus petit sous-ensemble, ce qui est suffisant pour vous donner une réponse unique. Maintenant, vous répétez cela à quelques reprises avec différents sous-ensembles aléatoires de questions, jusqu'à ce que vous voyez que la plupart du temps, vous obtenez le même résultat. vous savez alors que vous avez la bonne réponse.

Bien sûr, ce n'est qu'une façon de résoudre ce problème.

Answer 2

Il utilise un algorithme d'apprentissage.

k-NN est un bon exemple de l'un d'entre eux.

Wikipedia: k-Nearest Neighbor Algorithm

Answer 3

Je recommande la lecture sur le jeu ici: http://en.wikipedia.org/wiki/Twenty_Questions

En particulier la section Ordinateurs:

Le jeu indique que les informations (telle que mesurée par l'entropie de Shannon statistique) requis pour identifier un objet arbitraire est d'environ 20 bits. Le jeu est souvent utilisé comme un exemple lorsque enseigner aux gens sur l'information théorie. Mathématiquement, si chaque question est structurée pour éliminer la moitié des objets, 20 questions permettront au questionneur de distinguer entre 2 ou 1 048 576 sujets. En conséquence, la stratégie la plus efficace pour Twenty Questions est de poser des questions qui diviseront le champ des possibilités restantes environ en deux à chaque fois. Le processus est analogue à un algorithme de recherche binaire en informatique.

Answer 4

Un arbre de décision prend directement en charge ce type d'application. Les arbres de décision sont couramment utilisés dans l'intelligence artificielle. Un arbre de décision est un arbre binaire qui demande «la meilleure» question à chaque branche de distinguer entre les collections représentées par ses enfants gauche et droit. La meilleure question est déterminée par un algorithme d'apprentissage que les créateurs de l'application 20 questions utilisent pour construire l'arbre. Puis, comme le soulignent d'autres affiches, un arbre de 20 niveaux profonds vous donne un million de choses.

Une manière simple de définir la «meilleure» question à chaque point consiste à rechercher une propriété qui divise le plus uniformément la collection en deux. De cette façon, quand vous obtenez une réponse oui/non à cette question, vous vous débarrassez de la moitié de la collection à chaque étape. De cette façon, vous pouvez approximer la recherche binaire.

Wikipédia donne un exemple plus complet:

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

Et certains arrière-plan général:

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

Answer 5

Il se présente comme "le réseau neuronal sur Internet", et y sont des mensonges la clé. Il stocke probablement les probabilités de question/réponse dans une matrice de rechange. En utilisant ces probabilités, il est capable d'utiliser un algorithme d'arbre de décision pour déduire la question à poser qui permettrait de mieux affiner la question suivante. Une fois que le nombre de réponses possibles est réduit à quelques dizaines, ou s'il a déjà atteint 20 questions, alors il commence à lire le plus probable. L'aspect vraiment intriguant de 20q.net est que, contrairement à la plupart des algorithmes d'arbre de décision et de réseau de neurones que je connais, 20q supporte une matrice éparse et des mises à jour incrémentielles.

Editer: Il s'avère que la réponse a été sur le net tout ce temps. Robin Burgener, l'inventeur, a décrit son algorithme en détail dans son 2005 patent filing.