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.

	Created by Eduardo Villa over 9 years ago

Texto pequeño que describe la aplicacion de un Arbol Binario de busqueda en Inteligencia Artificial, para realizar un pequeño juego de "Adivina que animal es". Con codigo en Python y C++