¿Cómo puedo implementar un algoritmo de “ 20 preguntas ”?

No sé cómo lo hizo 20Q específicamente, pero hay mucha información sobre cómo implementar un juego de 20 preguntas .

Hay muchas formas de resolver esto, pero describiré una . Estos juegos pueden implementar algún tipo de árbol de decisiones . Para un juego electrónico como 20Q, este árbol estaría calculado previamente y sería bastante fácil de recorrer. Hay métodos para usar árboles de decisión de aprendizaje donde el juego puede aceptar nuevos objetos al final de sus preguntas si no puede adivinar qué es el usuario. preguntando.

Cuando las preguntas son una serie de respuestas de sí o no, terminas con un árbol binario. Cada nodo es una pregunta y las hojas son respuestas. Cuando las preguntas se responden con desconocido o no seguro, los nodos secundarios se pueden combinar y sus preguntas se pueden hacer en serie para seleccionar más las posibles respuestas.

Básicamente, este es el proceso:

1. Comience con una lista completa de los objetos. Todos estos pueden comenzar con la misma probabilidad, o pueden ordenarse según la probabilidad de que se eligiera el objeto en la prueba.
2. Comience con la primera pregunta en el árbol de decisiones. Empújela en la cola de preguntas.
3. Haga la pregunta en la parte superior de la cola.
4. Procese la respuesta:
   1. Las respuestas Sí / No eliminan / agregan una cantidad predeterminada de probabilidad de cada respuesta en función de la pregunta.
   2. La respuesta «Quizás» elimina / agrega una fracción de la cantidad predeterminada de un «sí».
   3. «Desconocido» no cambia las probabilidades
5. Una respuesta «Desconocido» o «Quizás» empuja las dos preguntas de los siguientes nodos a la cola de preguntas. Una respuesta «Sí» o «No» simplemente agrega el nodo correspondiente sí / no a la cola de preguntas.
6. Vaya al paso 3 hasta que no haya preguntas o la probabilidad de una sola respuesta esté más allá de una «certeza predefinida». » umbral.
7. Proporcione la respuesta más probable.

La generación del árbol es probablemente el tema de otra pregunta. Pero básicamente se trata de elegir preguntas que dividan las respuestas tanto como sea posible. Coloque las preguntas que dividen las preguntas de la manera más equitativa cerca del principio para que la mayor cantidad de preguntas se pueda seleccionar con mayor rapidez.

La respuesta simple es que el juego portátil 20Q se creó a partir de la inteligencia artificial que vive en http://20Q.net . En 20Q.net puedes jugar a diferentes versiones del juego de Veinte preguntas, similar al juguete, excepto que el juego aprende de cada juego jugado. El juguete de mano usa el los mismos algoritmos de red neuronal. La red neuronal elige las preguntas que se deben hacer y también hace conjeturas. Este enfoque significa que la IA a menudo adivinará correctamente incluso si respondes una pregunta de manera diferente a lo que se le enseñó a la IA. Otra ventaja es que hará preguntas de manera diferente en cada juego, incluso si estás pensando en lo mismo.

Los algoritmos y la red neuronal del clásico juego inglés (Animal, Vegetable, Mineral) fue creada en 1988 por Robin Burgener. . . yo.

Gracias por preguntar.

Comentarios

• Hola Robin, bienvenido al sitio. Quién mejor para responder a esta pregunta que el propio inventor. Es ‘ interesante saber qué tan complejo es realmente el 20Q. Gracias por su contribución al sitio y más aún su contribución a la inteligencia artificial. Con suerte, ‘ visitarás el sitio de vez en cuando y responderás A.I. preguntas :).
• jeje, me encanta cuando esto sucede xD.

Busqué en Google «código 20q» y encontré esto: http://mosaic.cnfolio.com/B142LCW2008A197

Esta versión es solo para animales, pero las 20 preguntas reales probablemente tengan un algoritmo similar.

Aquí hay una descripción general rápida del código que vinculé:
Hay varias respuestas diferentes codificadas en el programa.Luego se les asignan varios atributos VERDADERO o FALSO:

#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" ... 

Como puede ver, una abeja no es un mamífero pero vuela, etc.

Hay una matriz para cada grupo:

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

Cuando se hace cada pregunta:

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

El programa mira la definición de la categoría apropiada y rastrea qué animal es más probable en el que está pensando en base a los valores VERDADERO o FALSO y su respuesta Sí o No a la pregunta.

Esto se hace en:

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

It «s no es un árbol de decisiones masivo o un montón de declaraciones if / else codificadas. Robin Burgener, el inventor, documentó completamente su algoritmo en su solicitud de patente de 2005. «es ingeniosamente simple.

Comentarios

• En lugar de hurgar en las otras respuestas, es posible que desee dar una breve descripción del algoritmo en lugar de solopublicando un enlace a él.
• en caso de que se haya perdido las otras respuestas, ¡comentó arriba! tal vez @ user22025 también podría dar una breve explicación aquí: D