Aprendizaje Automático y Vida Artificial
Manuel de la Herrán Gascón
Publicado en octubre de 1997 en la revista "Solo Programadores" (nº 38)
Indice:
Seguimos intentando crear vida. Esta vez, vida inteligente. Este artículo describe cómo utilizar los conceptos de Vida Artificial y Algoritmos Genéticos para crear programas capaces de aprender por sí mismos a resolver todo tipo de problemas. Como ejemplo se ofrece en el CD-ROM el código fuente de un programa capaz de aprender a jugar al tres en raya.
En anteriores números de la revista se ha estudiado el tema de la Vida Artificial (Solo Programadores, nº 36) con un programa que permitía observar fenómenos emergentes como la evolución y la cooperación en un mundo virtual habitado por hormigas y plantas. También se han descrito los Algoritmos Genéticos (Solo Programadores, nº 37): qué son, cómo programarlos y cómo mejorarlos. Su funcionamiento se puso a prueba en un programa que trataba de descubrir una frase introducida por el usuario. Se va a recordar brevemente este Algoritmo Genético (AG). En primer lugar se genera una lista de frases combinando palabras tomadas al azar de un diccionario. Las frases que más se parecen a la frase buscada se seleccionan como "buenas" y se "reproducen" por parejas, creando nuevas frases por combinación de palabras tomadas de uno y otro progenitor. Repitiendo el proceso de selección y reproducción, y permitiendo de vez en cuando la modificación de una palabra al azar (mutación), se llega a obtener la frase buscada.
En un AG, los elementos que se reproducen (en este ejemplo, frases) son llamados entidades, agentes, cadenas, patrones, soluciones o simplemente "bichos". Uno de los problemas que surgen a la hora de utilizar algoritmos genéticos, y que se discute en el número nº 37 de la revista, es saber cuáles son las entidades que deben ser seleccionadas. En el caso de las palabras y las frases, se usa la propia solución (la frase buscada) para saber hasta que punto una frase es correcta, por lo que se puede decir que el programa, en realidad no adivina nada, ya que sabe por anticipado exactamente qué es lo que está buscando. Sin embargo, el ejemplo fue muy útil para experimentar mejoras en el rendimiento del algoritmo.
Esta vez tenemos la oportunidad de comprobar cómo este método se puede aplicar a un problema en el cual no tenemos por qué conocer los elementos que componen el agente buscado, aunque sí sabemos que es lo que queremos que haga: jugar y ganar al tres en raya. Se trata de un juego muy simple y no es difícil programar un ordenador para que lo haga con cierta habilidad. Lo que hace interesante este programa es que no requiere ningún conocimiento previo sobre el juego. Es decir, el programa será capaz de jugar contra sí mismo y contra nosotros, y aprender a partir de la propia experimentación, y poco importa que se trate del tres en raya o del ajedrez, ya que no va a ser necesario introducir al programa conocimiento sobre cómo jugar, y mucho menos sobre cómo ganar.
En el CD-ROM que acompaña a esta revista se encuentra el programa de instalación para Windows 3.x, 95 y NT, y el código fuente en Visual Basic 4.0 para 16 bits de Ejemplos de Vida 3.0, que incluye el mundo artificial de hormigas y plantas, el algoritmo genético capaz de adivinar frases y el programa que aprende a jugar al tres en raya.
[ Volver al Indice ]
En el programa que adivina frases, los bichos son frases, y están compuestos de palabras que se combinan en la reproducción. En el tres en raya, los bichos son "jugadores", y están formados por "reglas" que definen cómo actuar (jugar) ante determinadas circunstancias. El programa maneja reglas del tipo "Si observo tal situación, realizo tal acción" (Ver fig. 1). Al jugar una partida, la entidad observa el estado del tablero. Si posee alguna regla que aplicar, la aplica. En caso contrario, juega al azar. Esta regla evita que el contrario ponga tres fichas en línea.
Todos los jugadores poseen un indicador llamado peso que representa la habilidad de dicho agente en el juego del tres en raya. Cuando finaliza una partida entre dos jugadores virtuales, el peso del ganador se incrementará en una unidad, al contrario que el del perdedor. En el caso de que la partida finalice en tablas, sin ganadores, los pesos no se verán afectados.
Si en un momento dado de la partida la entidad puede aplicar más de una regla, el agente seleccionará la regla que más victorias haya proporcionado. Para ello, al igual que los agentes, las reglas también tendrán asignado un peso, que aumentará cada vez que la regla haya sido usada en una partida ganada y disminuirá en las perdidas.
Estas reglas son el material genético que maneja el programa. Cuando dos jugadores se reproducen, generan una nueva entidad formada por las reglas de ambos tomadas de forma alternativa, y creando de vez en cuando una nueva regla al azar en vez de tomarla de uno de los padres.
Básicamente, el proceso de aprendizaje consiste en evaluar las entidades, ordenarlas en función de su utilidad y reproducir los mejores individuos, que ocuparán el lugar de los perdedores. Evaluar las entidades en este caso es agruparlas por parejas y hacer que jueguen partidas.
Sub bucle_general()
While hay_que_detener = False
evaluar_agentes
ordenar_agentes
reproducir_agentes
Wend
End Sub
Cuando consideremos que el proceso de aprendizaje ha durado lo suficiente (y esto puede ser mucho tiempo), pulsaremos el botón de "Terminar" y después el de "Jugar contra el Ordenador" para comprobar cuánto se ha aprendido. Pulsando "Ver Agentes" veremos una lista de las reglas de cada agente, con los pesos finales de cada regla y de cada agente.
Al jugar contra el programa, en realidad estamos jugando contra el primer agente de la lista, es decir, el que más veces ha ganado, aunque el programa permite también jugar contra cualquiera de los otros que ha quedado "vivos". En el tablero de juego se informa, entre otras cosas, del número de partidas que han finalizado en tablas y del número de fichas totales que se han colocado utilizando una regla (en vez de al azar), por cada ciclo.
[ Volver al Indice ]
La premisa que se ha seguido en todo el proceso de programación ha sido la de no incluir en el programa ningún conocimiento acerca del problema a resolver, ya que lo que se está estudiando es el aprendizaje en general, y no la representación del conocimiento humano para un problema en particular. Sin embargo, en algunos aspectos es inevitable incluir cierto conocimiento, y en otros se ha hecho "trampa". Los aspectos inevitables son por ejemplo, los que se refieren al juego en sí mismo, como el formato de las reglas. Cada regla posee en la parte izquierda nueve valores que corresponden con los nueve sentidos del agente, y en la parte derecha un valor que representa una de las nueve acciones posibles. Evidentemente las entidades deben ser capaces de ver el tablero y de colocar fichas, y esto también hay que programarlo. Otro aspecto inevitable es la función que detecta cual de los jugadores ha ganado la partida, o si el juego ha quedado en tablas. Es decir, el juego, el problema a resolver o el entorno donde habita el agente (como se quiera llamar), hay que programarlo: no podemos resolver un problema si no definimos los términos de ese problema.
Por otra parte, el programa produce un aprendizaje muy lento. Recordemos que el programa no selecciona jugadores buenos al tres en raya (ya que no sabe lo que es un jugador bueno, precisamente eso es lo que tratamos de descubrir), sino que se seleccionan jugadores mejores que los demás. El mejor individuo de todos estará muy preparado para jugar y ganar en su mundo. Bueno, pero un niño descubre casi inmediatamente como no perder en el juego. ¿Por qué nuestro programa es tan torpe? No hay que olvidar que los agentes ven el tablero como una secuencia de datos, es decir, tal como aparece en la figura 3.
Hay que reconocer que incluso para nosotros resultaría muy incómodo jugar con un tablero así. Si además no supiésemos que esta fila de casillas representa en realidad una rejilla de 3x3, podríamos volvernos locos intentando averiguar cómo ganar una partida.
Estas razones animan a cometer algunas excepciones en la generación de reglas para acelerar el proceso del aprendizaje. En primer lugar, siempre se generan reglas válidas. Esto no tendría por qué ser así, podría por ejemplo generarse la regla C********1 que no es válida ya que coloca la ficha en una casilla ocupada. Los agentes que aplicasen una regla de este tipo perderían la partida inmediatamente, y así sólo se conseguiría retardar aún más el aprendizaje. El programa también permite dar mayor probabilidad de aparición a cierto tipo de reglas que se sabe de antemano que pueden ser muy interesantes, concretamente reglas con dos P ó dos C y una V, que en muchos casos podrán corresponder con: "Si tengo dos fichas en línea pongo la tercera y gano" o "Si el contrario tiene dos fichas en línea, le impido ganar poniendo la tercera".
[ Volver al Indice ]
Este programa se ha realizado, por comodidad, desde el punto de vista del proceso. Existen unos operadores (como el cruce y la mutación) que son aplicados en serie a todas las entidades. Es decir, primero se evalúan todas las entidades, después se seleccionan las mejores, más tarde se reproducen, etc. Cada agente decide cómo jugar al tres en raya, pero no puede decidir con quién jugar, con quién reproducirse, o cuándo compartir su conocimiento.
Para dotar a los agentes de mayor autonomía, a la vez que se logra una aproximación más cercana al mundo real, es preferible programar estas simulaciones desde el punto de vista de las entidades (los datos), siendo la propia entidad la que decide en cada momento cómo actuar.
Los dos estilos de programación pretenden simular un paralelismo: el primero es un paralelismo de procesos, el segundo es un paralelismo de entidades. El ideal sería disponer un procesador para cada entidad (paralelismo de entidades real). A falta de ello, el programa podría repartir el tiempo de ejecución entre todas las entidades, y el bucle general quedaría de la forma:
Sub bucle_general()
While hay_que_detener = False
for i = 1 to numero_de_seres_vivos
ejecutar_ser_vivo
next i
Wend
End Sub
Esto recuerda mucho más al bucle general del programa de hormigas y plantas que al de las palabras y frases. Es más complejo de programar por el hecho de tener que mantener el estado en que se ha quedado cada entidad antes de pasar a la ejecución de la siguiente, pero tiene la ventaja de que gran parte del código sería independiente del problema que se está resolviendo.
¿Cómo se consigue el mismo resultado dejando la iniciativa a las entidades? Bueno, en realidad los agentes no van a tener demasiada libertad, aunque tal vez ellos piensen lo contrario. En primer lugar es recomendable añadir a las entidades unas coordenadas que hagan referencia a su ubicación física, permitiendo que se muevan al azar por su mundo virtual. A partir de ahora, dos entidades deberán estar juntas para poder reproducirse o jugar una partida. Esto sería lo equivalente a la función de desordenar que ya posee el programa. Por otro lado, llamemos al peso "energía". La energía aumenta al ganar partidas y disminuye al perderlas. Hagamos que sólo se puedan reproducir los agentes con un determinado nivel de energía, y que fallezcan aquellos en los que ésta ha llegado por debajo de cierto valor. Acciones como reproducirse, moverse o la simple inactividad pueden restar energía al agente. Como se puede suponer, los agentes no van a tener más remedio que jugar y ganar si quieren seguir estando "vivos" o tener descendencia. La energía global del sistema debería permanecer constante (o al menos no variar demasiado) por coherencia, y para evitar extinciones o superpoblación, que de todas formas podrían suceder, y que en general se han de evitar.
Este modelo tiene muchas ventajas. Por una parte, una vez construido el esquema general, nos damos cuenta de que resulta mucho más fácil y rápido programar algunas funciones. La reproducción se simplifica mucho, al ser las propias entidades las que eligen pareja. Además este modelo nos permite ampliar y enriquecer el concepto de agente proporcionándole mayor potencia, convirtiéndolo en un pequeño resolutor de problemas. Y no sólo eso: para solucionar un problema distinto, bastará con definir unos nuevos agentes; el resto del programa permanecerá igual.
Vamos a ver poco a poco todas las cosas que nuestros agentes son capaces de hacer. Cada entidad posee una serie de acciones que es capaz de realizar, pero ahora no solo coloca fichas: ahora también puede, por sí misma, compartir su conocimiento, buscar pareja, reproducirse, o comenzar una partida. Podemos hacer que en cada ciclo, cada entidad sólo pueda realizar un número determinado de acciones, elegidas del conjunto de acciones posibles, antes de pasar a la ejecución de la siguiente (recordemos que hay que simular un paralelismo). Otra posibilidad es asignar un intervalo de tiempo a cada entidad y que cada una ejecute todas las acciones que le sea posible. También podremos limitar el tiempo de ejecución (o el número de acciones) a algunas de las entidades peores, en vez de eliminarlas.
En el programa de las hormigas, cada entidad realizaba una acción por ciclo, que dependía del estado en que se encontraba, calculado en función de los vecinos que tuviera en ese momento. En el caso de que un mismo estado pudiera disparar más de una acción, la acción se decidía según una cierta probabilidad. Ahora estamos hablando de algo mucho más completo, más sencillo de entender (ya que se parece más a la vida real), aunque más tedioso de programar. La entidad poseerá básicamente cuatro atributos: objetivo, creencias, sentidos y acciones. El agente (autómata) se dedicará a una u otra tarea (acción, salida) en función de un proceso de decisión interno (inteligencia), más o menos complejo, basado en sus creencias (memoria, reglas) y sentidos (entradas).
La entidad va a tener un objetivo que cumplir y sus sentidos le informarán, entre otras cosas, de cuándo ese objetivo se cumple y en qué grado. Utilizando sus creencias, el agente realiza en cada caso la acción que cree que más le acercará a su meta. En el caso del tres en raya, el objetivo es ganar el juego. Los sentidos informan en cada momento del estado del tablero, que se almacenará en la memoria. Las acciones son no sólo las que actúan directamente sobre el problema que se está resolviendo, como colocar una ficha, sino también las que afectan a cualquier otro componente del entorno (como compartir el conocimiento con otro agente), o aquellas que consisten en manejar de alguna forma el conocimiento almacenado en la memoria, y que posteriormente determinarán la secuencia de acciones a realizar sobre el entorno, como predecir el comportamiento del contrario.
La información que recibe el programa acerca del entorno se almacenará en variables. Un estado será un conjunto de valores para esas variables. Por ejemplo, nuestro agente podrá ver el contenido de cada una de las 9 casillas del tres en raya, con lo que dispondrá de 9 variables, y las posibles combinaciones de esos valores formarán el conjunto de estados posibles.
[ Volver al Indice ]
Aquello en lo que la que la entidad cree lo podemos agrupar en tres categorías. En primer lugar, existirá una memoria de los sucesos que han ocurrido. Por otro lado es posible que unas variables dependan del valor de otras, por lo que existirán reglas que definan esta descomposición. Finalmente tenemos las reglas que predicen el comportamiento del entorno. Las reglas usadas por el juego del tres en raya son del tipo "si observo tal situación, realizo tal acción". Estas reglas sirven para decidir qué hacer, pero no explican el porqué. Un formato más general debería permitir reglas capaces de describir un estado inicial, un estado final, y la acción necesaria para pasar de uno a otro (Ver fig. 4). Reglas como (1) "Si es el turno de X, yo juego con X, y en las casillas 1 y 2 hay una ficha X, estando vacía la casilla 3, y realizo la acción de poner una ficha en la posición 3, entonces el ganador será X con una probabilidad del 100%, y esta regla tiene una importancia máxima". Podrían existir reglas sin acción y/o reglas donde el estado final se deba calcular en función de otras variables: "Si en las casillas 1 y 2 hay una ficha X, en las casillas 4 y 5 hay una ficha O, estando vacías las casillas 3 y 6, entonces el ganador será el del turno actual, con una probabilidad del 40%, y esta regla tiene una importancia de 0,7".
Un formato que admite estas posibilidades es:
Estado, Acción --> Conclusión, Probabilidad, Importancia
Estado es un conjunto de pares "variable = valor", Acción es una acción simple o compleja, Conclusión es un conjunto de pares "variable = formula", que una vez resueltas las fórmulas produce pares "variable = formula". Probabilidad es la confianza que el agente tiene en la regla, e Importancia es un indicador del grado en que la regla puede afectar al objetivo.
[ Volver al Indice ]
¿Cómo decide la entidad que acción ejecutar con este tipo de reglas? La entidad posee una variable especial, llamada objetivo, que representa el grado en el que la entidad se comporta según la forma deseada por quien la creó. La variable objetivo dependerá de los valores de otras variables, según una fórmula determinada, en este caso, la colocación de tres fichas propias en línea. La evaluación de la entidad, o lo que es lo mismo, la comprobación de hasta dónde se cumple el objetivo, está encapsulado dentro de la propia entidad. No es necesario que otro agente lo evalúe, la propia entidad no puede evitar perder "energía" si no lo consigue.
El agente intentará realizar aquellas acciones que más le acerquen a su objetivo. Para ello, deberá predecir la respuesta del entorno ante sus acciones. Pero recordemos que el agente parte de un completo desconocimiento del problema particular. ¿Qué hacer? En primer lugar, observa la situación actual (inicialmente, el tablero vacío)-, y comprueba si el objetivo buscado se cumple. Como todavía nadie ha sido declarado ganador, y a falta de otra opción mejor, el agente ejecuta acciones al azar. Después de una acción observa sus consecuencias y su "mente" produce una asociación causa-efecto que almacena en forma de regla. Las posteriores acciones estarán condicionadas por el conocimiento almacenado en la memoria, evitándose en lo posible recurrir al azar.
Si se realiza una acción y se pasa a un estado desconocido, se almacenará información que represente ese nuevo estado y se creará una regla que represente las condiciones necesarias para pasar a ese nuevo estado. El problema consiste en cómo identificar qué acción ha sido la responsable de una transición. Por ejemplo, colocar una ficha en un determinado lugar puede ser la causa inmediata de ganar la partida, pero tiene poca utilidad suponer que únicamente esa acción es la responsable de vencer en el juego. Es más apropiado decir que la causa es la sucesión completa de acciones desde el comienzo de la partida. Para poder utilizar este tipo de reglas, las acciones se podrán organizar en una estructura jerárquica. Así, una sucesión de acciones interesante formará una acción de nivel superior, y esta acción podrá formar parte de una regla.
Sin embargo esto no explica la mayoría de los comportamientos inteligentes conocidos. Una partida no se gana por realizar una determinada serie de acciones, sino más bien por una estrategia, por un conocimiento del juego en general, por un conocimiento de experto obtenido a través de múltiples experiencias. A este nivel de análisis, la causa de haber ganado es el haber realizado una serie de acciones -tomar una decisión es realizar una acción-, que además de actuar sobre el entorno o problema a resolver, manejan símbolos referentes a él y manipulan o indican cómo manipular la información adquirida, determinando en última instancia cuál será la sucesión de acciones a realizar sobre el juego.
Aunque en cada instante sólo se pueda ejecutar una acción básica, las acciones de nivel superior se pueden solapar en el tiempo. La toma de una decisión cuya influencia se manifiesta en el desarrollo de otras acciones puede entenderse también como una acción. Por ejemplo, el hecho de decidir utilizar, bajo ciertas condiciones, únicamente un subconjunto del conjunto total de reglas posibles, puede considerarse una acción (de nivel superior). Esta acción se solapará con las acciones básicas que se ejecuten en cada momento. Este ejemplo además ilustra como permitir una cierta jerarquía dentro de las reglas, ya que es posible incluir esta acción, que hace referencia a las reglas, dentro de otra regla.
En las variables también existe una jerarquía. El número de variables que forman un estado normalmente será muy grande, y muchas veces ocurrirá que varios estados distintos se comportan como uno sólo. Esta última situación se da en el tres en raya por la simetría que posee el tablero. Por estas razones es interesante representar algunas combinaciones de valores de variables como un único valor para una variable de nivel superior.
Así, dispondremos de un mecanismo que nos permitirá algo parecido a crear conceptos. Por ejemplo, se podría crear el concepto de "dos fichas en línea", que será una nueva variable, con un nombre o identificador cualquiera, que adoptará el valor verdadero en el caso de que se produzca esta situación. En las variables es posible aplicar la lógica difusa. Existen conceptos de naturaleza continua, que se definen mediante la referencia a una propiedad y el grado en que se manifiesta dicha propiedad. Por ejemplo, nosotros podemos decir que el cielo es azul. Sin embargo, no existe una frontera numérica que marque la diferencia entre un cielo azul y un cielo blanco en función del número de puntos de luz de cada color. Ambos conceptos pueden ser ciertos simultáneamente en cierta medida. Así, podríamos expresar: el cielo posee un tono azulado en un 70%. Por otra parte no siempre se dará un grado de confianza total a la información manejada. Es posible que un concepto se cumpla en un cierto grado y que a esta información se le asigne una cierta confianza, y de esta forma, podríamos decir: el cielo posee un tono azulado en un 70% y esta información posee una probabilidad del 90% de ser cierta. Estos valores pueden ser incluidos en cada variable.
¿Cómo reconocer que conceptos son importantes? Cuando un agente llegue a su límite de almacenamiento, deberá seleccionar algunas creencias para que sean borradas. Para ello, intentaremos relacionar los estados con el objetivo, de manera que se tengan más en cuenta aquellos que más influyen en él, ya sea favoreciendo o perjudicando su consecución.
La creación de variables de nivel superior también hace que las necesidades de espacio a la hora de almacenar una regla sean menores. Con un número suficiente de reglas describiendo el comportamiento del entorno, y conociendo el estado actual y el estado al que se desea llegar, se puede buscar la sucesión de acciones que nos llevan de un estado a otro, hasta la meta. La creación de variables superiores no ha de estar limitada a un solo instante de tiempo, a una sola lectura del entorno. En realidad, el tiempo se puede considerar como una variable más, y crear así conceptos que describan un comportamiento que posea continuidad.
[ Volver al Indice ]
En este artículo se han descrito las posibilidades de razonamiento dentro de un agente. Las entidades que hemos estudiado recuerdan a los procesos Unix (que nacen, mueren, tienen procesos hijos, se comunican enviándose mensajes), y también tienen un aire de instancias de Programación Orientada a Objetos (POO), ya que si en POO tenemos objetos que encapsulan datos y procedimientos, aquí tenemos agentes que encapsulan un objetivo, unos sentidos, unas creencias y unas acciones.
En cualquier caso, lo que es evidente es que si el método de búsqueda es independiente del problema a resolver, se echa terriblemente en falta la existencia de unas librerías de entidades y de un compilador de un lenguaje de definición de agentes y de entornos de problema. En teoría, con algo así, nos quedaría poco por programar. En la práctica, y dada la lentitud inherente del aprendizaje evolutivo, cuyo ejemplo más cercano somos nosotros mismos (que hemos tardado 3.800 millones de años en evolucionar desde los primeros microorganismos vivos), será más útil combinar estas técnicas con la representación humana del conocimiento. De todo ello puede resultar un Resolutor General de Problemas de gran potencia. Las posibilidades de este nuevo paradigma son sin duda, muy excitantes.
En el próximo número veremos los agentes desde una perspectiva mucho más elevada: nos centraremos en los mundos donde viven los agentes y en como crear mundos o universos paralelos llenos de agentes y sacar provecho de todo esto.
[ Volver al Indice ]
[ Home Page Castellano | Home Page English ]
