Arboles Binarios & Inteligencia Artificial

POR: Byron Rosero (4525) - Jairo Cabezas (5855) Arboles Binarios e Inteligencia Artificial 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 C++ Vamos a crear este tipo de dato en lenguaje python: class cArbol { private: Nodo valor, izq, der; }; 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. arbol = Arbol(5) Esto nos crearía el siguiente esquema. Podríamos añadirle dos nodos hijos: arbol = Arbol(5) arbol.izq = Arbol(4) arbol.der = Arbol(3) Lo anterior se puede resumir en una sola línea de código. arbol = Arbol(5, Arbol(4), Arbol(3)) El resultado es el mismo. Como vemos cada llamada a la clase Arbol() solo nos genera un nodo del árbol. 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. class cArbol { private: Nodo valor, izq, der; public: int suma(cArbol Arbol){ if (Arbol == NULL) return 0 return (suma(Arbol.izq) + suma(Arbol.der) + Arbol.valor arbol = Arbol(5, Arbol(4), Arbol(3)) }; Nuestra función suma recibe el nodo padre como parámetro. Tiene la condición base de que si el árbol vale NULL (está 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 NULL 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 cómo crear estructura de árboles con C++ 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? N 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 cuernos 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 cuernos? s Es un Rinoceronte? n Qué animal era? Elefante Qué diferencia a un Rinoceronte de un Elefante? tienen trompa larga Si el animal fuera un Rinoceronte cual seria la respuesta? n Estas pensando en un animal? s vuela? n Ladra? n tiene cuernos? n tienen trompa larga? n Es un Raton? n Qué animal era? Jabali Qué diferencia a un Raton de un Jabali? tiene colmillos largos Si el animal fuera un Raton cual seria la respuesta? n Estas pensando en un animal? s vuela? n Ladra? n tiene cuernos? n tienen trompa larga? n tiene colmillos largos? 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 cuernos? s tienen trompa larga? n parece un colmillos largos? n 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í a 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 pájaro de un perro? 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 en Python. #!/usr/bin/env python # -*- coding: utf-8 -*- # Clases # ----------------------------------------------------------- class Arbol: def __init__(self, carga=None, izq=None, der=None): self.carga = carga self.izquierda = izq self.derecha = der def __str__(self): return str(self.carga) # ----------------------------------------------------------- # Funciones # ----------------------------------------------------------- def si(preg): from string import lower resp = lower(raw_input(preg)) return (resp[0] == 's') # ----------------------------------------------------------- def main(): bucle = True raiz = Arbol("pajaro") while bucle: if not si("Estas pensando en un animal? "): break arbol = raiz while arbol.izquierda != None: if si(arbol.carga + "? "): arbol = arbol.izquierda else: arbol = arbol.derecha #adivinar animal = arbol.carga if si("Es un " + animal + "? "): print "Soy el más grande!" continue #obtener informacion nuevo = raw_input("Qué animal era? ") info = raw_input("Qué diferencia a un " + animal + " de un " + nuevo + "? ") indicador = "Si el animal fuera un " + animal + " cual seria la respuesta? " arbol.carga = info if si(indicador): arbol.izquierda = Arbol(animal) arbol.derecha = Arbol(nuevo) else: arbol.derecha = Arbol(animal) arbol.izquierda = Arbol(nuevo) return 0 if __name__ == '__main__': main() 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 solucionar 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.