Seguro que todos hemos vistos muchas aplicaciones y juegos de adivinación las típicas que te dicen que pienses en un objeto o en una persona y en pocas preguntas te adivinan en qué estás pensando y se nos queda una cara de tontos que no es normal. En este artículo vamos a ver por encima como crear un adivinador simple.
Estos juegos se basan en una gran base de datos de la que mediante preguntas que se hacen al jugador se van eliminando opciones hasta que queda una. Suelen tener grandes algoritmos heurísticos para poder acertar incluso con datos erróneos por parte del usuario.
Nosotros vamos a crear un sistema adivinador de animales al que hay que "enseñarle" en un principio nuestro adivinador solo conocerá un animal y preguntará si ese es el animal que estás pensando, si no es así te preguntará en que animal pensabas y en que lo diferencia del que nos ha propuesto, así irá creando un árbol de animales que al cabo de unos cuantos miles de partidas podrá adivinar cualquier animal.
Usaremos el lenguaje de programación Python por su sencillez y usaremos una estructura de árboles para almacenar nuestro adivinador. Empecemos.
Árboles
Un árbol es una estructura de datos compuesta de nodos. Cada nodo está compuesto por una carga y enlaces a sus nodos hijos.
Como vemos en este árbol las cargas son números enteros como 65, 58, 79, etc. Los nodos tienen hijos a los que apuntan, por ejemplo, el nodo 65 tiene 2 nodos hijos 58 y 79. 58 a su vez tiene 3 nodos hijos 25, 96 y 12.
Los árboles se componen de un nodo que no tienen padre en nuestro caso es 65 que se llama tronco (por el símil con el árbol). Los nodos hijos que van saliendo de él se llaman ramas hasta llegar a nodos que no tienen nodos hijos que se llaman nodos hojas.
Arboles binarios
Es este artículo vamos a centrarnos en los árboles binarios. Son árboles que tienen solo dos nodos hijos. Se va bifurcando de dos en dos, por los que se les llama binario.
Como podemos ver en el árbol superior hay dos nodos hijos en cada rama, por tanto es un árbol binario.
Árboles binarios en Python
Vamos a crear este tipo de dato en en lenguaje python:
Podemos ver que recibe tres valores, la carga y dos referencias a sus nodos hijos, en un principio todo definido con None. Para crear un arbol podríamos hacer lo siguiente.
Esto nos crearía el siguiente esquema.
Podríamos añadirle dos nodos hijos:
Lo anterior se puede resumir en una sola línea de código.
El resultado es el mismo. Como vemos cada llamada a la clase Arbol() solo nos genera un nodo del árbol. Hemos redefinido el método __str__ que sustituye el valor de la sentencia print aplicado al objeto, mostrandonos solo la carga.
Lo más importante para un tipo de dato es tener alguna manera de poder recorrerlo, vamos a implementar una función que recorra todos los nodos del árbol y nos devuelva la suma de las cargas de cada nodo.
Nuestra función suma recibe el nodo padre como parámetro. Tiene la condición base de que si el árbol vale None (esta vacío) pues su valor es 0 si no se cumple se llama recursivamente para calcular el valor de sus hijos más la carga cuando alcanza un nodo que vale None retornará 0 y saldrá de la recursividad.
Los árboles binarios sirven para ir eligiendo entre opciones que se van ramificando. Es útil para comportamientos y toma decisiones de una posible I.A.
Adivinador de animales
Ahora que sabemos como crear estructura de árboles con Python vamos a crear una Inteligencia Artificial que tratará de adivinar en que animal estamos pensando. El programa irá aprendiendo a medida que jugamos e irá conociendo más animales. Lo que vamos a hacer es crear una estructura árbol que se vaya ramificando poco a poco.
Veamos un ejemplo ejecución del programa para que veáis como funciona.
Estas pensando en un animal? s Es un pajaro? n Qué animal era? Raton Qué diferencia a un pajaro de un Raton? vuela Si el animal fuera un pajaro cual seria la respuesta? s Estas pensando en un animal? s vuela? s Es un pajaro? n Qué animal era? Aguila Qué diferencia a un pajaro de un Aguila? caza Si el animal fuera un pajaro cual seria la respuesta? n Estas pensando en un animal? s vuela? n Es un Raton? n Qué animal era? Perro Qué diferencia a un Raton de un Perro? Ladra Si el animal fuera un Raton cual seria la respuesta? n Estas pensando en un animal? s vuela? n Ladra? n Es un Raton? n Qué animal era? Rinoceronte Qué diferencia a un Raton de un Rinoceronte? tiene colmillos Si el animal fuera un Raton cual seria la respuesta? n Estas pensando en un animal? s vuela? s caza? n Es un pajaro? n Qué animal era? Buitre Qué diferencia a un pajaro de un Buitre? come carroña Si el animal fuera un pajaro cual seria la respuesta? n Estas pensando en un animal? s vuela? n Ladra? n tiene colmillos? s Es un Rinoceronte? n Qué animal era? Elefante Qué diferencia a un Rinoceronte de un Elefante? tienen trompa Si el animal fuera un Rinoceronte cual seria la respuesta? n Estas pensando en un animal? s vuela? n Ladra? n tiene colmillos? s tienen trompa? n Es un Rinoceronte? n Qué animal era? Jabali Qué diferencia a un Rinoceronte de un Jabali? vive en el agua Si el animal fuera un Rinoceronte cual seria la respuesta? s Estas pensando en un animal? s vuela? n Ladra? n tiene colmillos? n Es un Raton? n Qué animal era? Jirafa Qué diferencia a un Raton de un Jirafa? tiene el cuello largo Si el animal fuera un Raton cual seria la respuesta? n Estas pensando en un animal? s vuela? s caza? n come carroña? n Es un pajaro? n Qué animal era? Mosca Qué diferencia a un pajaro de un Mosca? es un insecto Si el animal fuera un pajaro cual seria la respuesta? n Estas pensando en un animal? s vuela? n Ladra? n tiene colmillos? s tienen trompa? n vive en el agua? s Es un Rinoceronte? s Soy el más grande!
Como se puede ver inicialmente el programa no “sabe” nada, solo sabe el nodo inicial que aleatoriamente hemos puesto que sea pájaro y pregunta si el animas es un pájaro. Si se le dice que no preguntará en que animal se estaba pensando y te pedirá una diferencia con el que te ha sugerido él para almacenarlo en su árbol. Así ha medida que se va jugando e introduciendo animales el programa va conociendo más ya que su árbol se va ramificando y creciendo en animales.
Veamos otra ejecución del programa más corta para poder analizarla.
Está pensando en un animal? s Es un pájaro? n Cómo se llama el animal? perro Qué pregunta distinguiría a un perro de un pájaro? Puede volar Si el animal fuera un perro, cuál sería la respuesta? n Estás pensando en un animal? s Puede volar? n Es un perro? n Cómo se llama el animal? gato Qué pregunta distinguiría a un gato de un perro? Ladra Si el animal fuera un gato, cuál sería la respuesta? n Estás pensando en un animal? s Puede volar? n Ladra? s Es un perro? s Soy el más grande!
Generaría el siguiente árbol binario.
Como podermos ver según la información que le damos va generando un árbol. Al principio de cada juego se empieza en lo más alto del árbol (tronco) y se hace la pregunta que contiene el nodo, cuando llega a un nodo hoja trata de adivinar. Hay que darse cuenta que todos los animales son nodos hojas y todas las preguntas son nodos ramas obvio porque solo las preguntas tienen o una respuesta u otra pregunta y los animales son estados finales. Si falla pide el a usuario el nombre del nuevo animal y una diferencia con el intento fallido, entonces añade el nuevo animal y la nueva pregunta al árbol.
Aquí está el código completo del programa.
La función si() devuelve verdadero si se ha escrito S o s y falso si se ha escrito otra cosa. Es esta función la que interactúa con el usuario.
La condición del bucle externo es 1, por lo que seguirá hasta que se encuentre la sentencia break cuando el usuario decida que ya ni piensa en ningún animal. El bucle while interno recorre el árbol guiado por las respuestas que va dando el usuario. Cuando se añade un nuevo nodo al árbol, la pregunta sustituye a la carga y los dos hijos son el nuevo animal y la carga original del nodo que ahora es la pregunta.
Una carencia de esta implementación es que, al salir, ¡olvida todo lo que le habías enseñado con tanto cuidado! Esto se podría soluciona almacenando la estructura del árbol en algún archivo o base de datos.
Este código tan simple si se le implementa una base de datos online que vaya haciendo crecer el árbol en cada juego de los usuarios. Al cabo de un tiempo, después de muchos juegos sería capaz de adivinar cualquier animal. Sería necesario añadir algo de heurística para evitar animales repetidos y demás, pero se sale de la intención del artículo.
Artículo basado en el capítulo de Árboles del libro Aprende a Pensar como un Programador con Python [pdf].
