Comment puis-je implémenter un algorithme “ 20 questions ”?

Je ne sais pas comment 20Q la fait spécifiquement, mais il y a beaucoup dinformations sur la façon dimplémenter un jeu de 20 questions .

Il existe de nombreuses façons de résoudre ce problème, mais je vais en décrire une . Ces jeux peuvent implémenter une sorte darbre de décision . Pour un jeu électronique comme 20Q, cet arbre serait précalculé et assez facile à parcourir. Il existe des méthodes pour utiliser les arbres de décision pour apprendre où le jeu peut accepter de nouveaux objets à la fin de ses questions s’il est incapable de deviner ce que l’utilisateur est. demander.

Lorsque les questions sont une série de réponses par oui ou par non, vous vous retrouvez avec un arbre binaire. Chaque nœud est une question et les feuilles sont des réponses. Lorsque les réponses aux questions sont inconnues ou incertaines, les nœuds enfants peuvent être combinés et leurs questions posées en série pour extraire davantage les réponses possibles.

En gros, voici le processus:

1. Commencez par une liste complète des objets. Ceux-ci peuvent tous commencer à la même probabilité, ou ils peuvent être triés en fonction de la probabilité que lobjet soit choisi lors du test.
2. Commencez par la première question de larbre de décision. Poussez-la dans la file dattente des questions.
3. Posez la question en haut de la file dattente.
4. Réponse du processus:
   1. Oui / Non réponses supprime / ajoute une quantité prédéterminée de probabilité de chaque réponse en fonction de la question.
   2. La réponse « Peut-être » supprime / ajoute une fraction du montant prédéterminé dun « oui ».
   3. « Inconnu » ne change pas les probabilités
5. Une réponse « Inconnu » ou « Peut-être » pousse les deux questions des nœuds suivants dans la file dattente des questions. Une réponse « Oui » ou « Non » ajoute simplement le nœud respectif oui / non à la file dattente des questions.
6. Passez à létape 3 jusquà ce que le manque de questions ou la probabilité dune réponse unique dépasse une « certitude prédéfinie »  » au seuil.
7. Donnez la réponse la plus probable.

La génération de larbre est probablement le sujet dune autre question. Mais fondamentalement, il sagit de choisir des questions qui divisent les réponses autant que possible. Placez les questions qui divisent les questions le plus également près du début afin que le plus grand nombre de questions puisse être sélectionné le plus rapidement possible.

La réponse simple est que le jeu portable 20Q a été créé à partir de lintelligence artificielle qui vit à http://20Q.net . Sur 20Q.net, vous pouvez jouer à différentes versions du jeu de Twenty Questions, similaires au jouet, sauf que le jeu apprend de chaque jeu joué. Le jouet portable utilise le mêmes algorithmes de réseau de neurones. Le réseau de neurones choisit les questions à poser et fait des suppositions. Cette approche signifie que lIA devinera souvent correctement même si vous répondez à une question différemment de ce que lIA a appris. Un autre avantage est que le jeu posera des questions différemment à chaque jeu même si vous pensez à la même chose.

Les algorithmes et le réseau neuronal du jeu anglais classique (Animal, Vegetable, Mineral) a été créé en 1988 par Robin Burgener. . . moi.

Merci davoir posé la question.

Commentaires

• Bonjour Robin, bienvenue sur le site. Qui de mieux pour répondre à cette question que linventeur lui-même. Il est ‘ intéressant de savoir à quel point le 20Q est réellement complexe. Merci pour votre contribution au site et plus encore pour votre contribution à lintelligence artificielle. Jespère que vous ‘ visiterez le site de temps en temps et répondrez A.I. questions :).
• hehe, jadore quand ça arrive xD.

Jai recherché sur Google « 20q code » et jai trouvé ceci: http://mosaic.cnfolio.com/B142LCW2008A197

Cette version est uniquement pour les animaux, mais les 20 questions réelles ont probablement un algorithme similaire.

Voici un bref aperçu du code que jai lié:
Il y a plusieurs réponses différentes codées en dur dans le programme.Plusieurs attributs TRUE ou FALSE leur sont alors assignés:

#define ANIMALS_LIST "daddylonglegs bee penguin eagle giraffe octopus tiger elephant jellyfish bull \nparrot dolphin python crocodile cat leopard monkey zebra sheep rat \nowl spider frog polarbear snail tortoise rabbit salmon rhino fox" #define MAMMALS "0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1" #define FLYING_ANIMALS "1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0" #define WATER_ANIMALS "0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0" #define BEAK "0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0" ... 

Comme vous pouvez le voir, une abeille nest pas un mammifère mais elle vole, etc.

Il existe un tableau pour chaque groupe:

int mammals[ TOTAL_ANIMALS ] = { 0 }; int flying_animals[ TOTAL_ANIMALS ] = { 0 }; int water_animals[ TOTAL_ANIMALS ] = { 0 }; ... 

Lorsque chaque question est posée:

 askUserQuestion( guesses, "\nQuestion %d: Is your animal a mammal? \n", mammals ); 

Le programme examine la définition de la catégorie appropriée et suit quel animal est le plus probablement celui auquel vous pensez en fonction des valeurs VRAI ou FAUX et de votre réponse entrée Oui ou Non à la question.

Ceci est fait dans:

void askUserQuestion( int guessNumber, char* question, int* animalData ); 

Cest pas un arbre décisionnel massif ou un tas dénoncés if / else codés en dur. Robin Burgener, linventeur, a complètement documenté son algorithme dans son dépôt de brevet en 2005. Il « est ingénieusement simple.

Commentaires

• Au lieu de chercher les autres réponses, vous pouvez donner une brève description de lalgorithme au lieu de simplementposter un lien vers celui-ci.
• au cas où vous auriez manqué les autres réponses, il a fait un commentaire ci-dessus! peut-être que @ user22025 pourrait également donner une brève explication ici: D