GAIA: Ejemplos de Vida. Tres en Raya

http://www.redcientifica.com/gaia/ejv3_c.htm

Ejemplos de Vida. Tres en Raya

Manuel de la Herrán Gascón

Tres en Raya
Pulse Aprender para comenzar el proceso de aprendizaje. Cuando considere que se ha aprendido lo suficiente, pulse Terminar y después Jugar Contra el Ordenador para comprobar el nivel de aprendizaje al que se ha llegado.
Los procesos de aprendizaje son lentos, y para el programa no es apropiado detener el aprendizaje en cualquier punto de la ejecución. Por esta razón, después de haber pulsado Terminar, probablemente será necesario esperar un tiempo (varios segundos o algunos minutos), hasta que el proceso de aprendizaje se detiene realmente en un punto estable.
El tres en raya es un juego muy simple y no es difícil programar un ordenador para que lo haga con cierta habilidad. Lo que hace interesante a este 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 no va a ser necesario introducir al programa conocimiento sobre cómo jugar, y mucho menos sobre cómo ganar. Este programa aplica una variedad de Algoritmos Genéticos para aprender jugar al tres en raya, clasificando ciertas reglas generadas mediante pseudoazar según su utilidad.

Aprendiendo a jugar al tres en raya
En este programa las entidades que nacen, se reproducen y mueren son "jugadores", y están formados por "reglas" (genes) que definen cómo actuar (jugar) ante determinadas circunstancias. El programa maneja reglas del tipo "Si observo tal situación, realizo tal acción". 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. Por ejemplo, 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á, 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. Las últimas versiones del programa admiten distintas distribuciones de premios, por ejemplo, obtiene más puntos un jugador que gana sin haber sido el que comenzó la partida, ya que esto último siempre supone una ventaja adicional.
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.
Las reglas también poseen "prioridades" de forma que ante una misma situación, pudiendo dispararse más de una regla, se dispara la de más prioridad. Por tanto, el procedimiento completo de elección de la regla a disparar es:
1.- Selecciónar del conjunto A de todas las reglas del agente, un subconjunto B de todas las reglas que pueden ser disparadas en este momento, es decir, aquellas en cuya parte izquierda se representa un estado de tablero que coincide con el actual.
2.- Si el subconjunto B es vacío, se ejecuta un movimiento lícito cualquiera, elegido mediante una función de pseudoazar. Si el subconjunto B posee un único elemento, se ejecuta dicha regla. Si el subconjunto B no es vacío y poseee mas de un elemento, se selecciona, del conjunto B, un subconjunto C de aquellas reglas cuya prioridad es máxima (los valores numéricos más altos).
3.- Si el subconjunto C posee un único elemento, se ejecuta dicha regla. Si el subconjunto C poseee mas de un elemento, se selecciona, del conjunto C, un subconjunto D de aquellas reglas cuyo peso es máximo (los valores numéricos más altos).
4.- Si el subconjunto D posee un único elemento, se ejecuta dicha regla. Si el subconjunto D poseee mas de un elemento, se selecciona, del conjunto D, un elemento cualquiera, elegido mediante una función de pseudoazar.
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.
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.

Pseudocódigo
Un ejemplo simplificado del funcionamiento general de este programa sería:
1.- Creamos 40 agentes compuestos cada uno de 100 reglas; estas reglas están generadas al azar. Cada regla dice que acción realizar ante cierto estado del tablero. Cada regla posee asociado un valor de prioridad de 0 a 3, generado también al azar.
2.- Ponemos a los agentes a jugar partidas por parejas. Es decir, tomamos agentes de dos en dos y hacemos que cada pareja juegue 5 partidas seguidas al tres en raya.
3.- Asígnamos puntuaciones a los agentes: cada vez que un agente gana una partida, gana un punto, y si la pierde, pierde un punto.
4.- Ordenamos a los agentes en función de sus puntos (a esto lo llamamos "peso" del agente")
5.- Ahora vamos a hacer que los mejores agentes sigan "viviendo" y en cambio mueran los otros, cuyo lugar será ocupado por nuevos agentes. Selecciónamos los 20 mejores agentes, y los combinamos por parejas, creando por cada pareja dos nuevos descendientes que tienen las reglas de uno y otro progenitor intercaladas, y los copiamos en al zona de memoria de los 20 agentes peores.
6.- Volvemos al paso 2

Algunos aspectos a tener en cuenta
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 implícitamente 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 si 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.

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

Opciones del programa
El funcionamiento básico puede ser modificado con distintas opciones. El programa permite elegir las siguientes:

Número de agentes que jugarán al tres en raya, que será constante durante todo el aprendizaje.
Número de reglas que posee cada agente, también constante.
Probabilidad de mutación, es decir, la probabilidad de que al crearse una regla de un nuevo agente, en vez de tomar la regla de uno de sus dos progenitores, se genere una regla al azar.
El tipo de selección, permitiéndose cuatro casos: Se selecciona para la reproducción el 50% mejor del conjunto de todas las entidades, que genera el 50% restante Se reproduce el 10% mejor sobre el 90% restante Se reproduce el 20% mejor sobre el 80% restante Se selecciona el 40% mejor y el 10% peor, y se reproduce sobre el 50% restante
Frecuencia de mutaciones acumulada, de forma que la probabilidad de que exista una mutación en una regla no es independiente para cada regla, sino que es más probable que se produzca una mutación en una regla si en su vecina ya se ha producido.
Los padres pueden tomarse por parejas elegidas al azar o en orden de pesos.
Los jugadores pueden unirse igualmente al azar o en orden de pesos.
En el caso de detectar que dos progenitores son iguales, es posible hacer que los hijos sean mutaciones en todos sus elementos.
El peso de una entidad se puede calcular de forma independiente, tal como se ha explicado, en función del número de partidas ganadas, o se puede modificar este valor, disminuyendo el peso si existe otra entidad muy parecida, asegurando así la variedad en la población.
Las entidades pueden comunicar a otras su conocimiento, de manera que cuando una entidad ha ganado una partida, se aumenta el peso de las reglas utilizadas en esa partida, pero no solo en la entidad ganadora, sino en toda la población, actuando de forma similar para las reglas usadas en las partidas perdidas.
La generación de reglas se puede hacer totalmente al azar o con una función de azar "trucada" que genera con mayor probabilidad reglas que se presuponen útiles, dando así un "empujoncito" a la evolución. Como es lógico, los algoritmos que más éxito tienen en problemas prácticos son aquellos que además de ser capaces de aprender por sí mismos, parten de un estado inicial en el que las entidades poseen gran cantidad de conocimiento útil acerca del problema a resolver. Aunque los resultados podrían ser mucho más espectaculares, no se hace mucho énfasis en esta cuestión, ya que lo que se está estudiando es el proceso de aprendizaje autónomo, y no la representación del conocimiento humano en un programa.
En principio, en la reproducción se toma una regla de uno u otro progenitor de forma alternativa: primero de la madre, después del padre, el siguiente de la madre, etc., pero existe la opción de heredar siempre la regla de mas peso de los dos.
Sustituir por mutaciones las reglas repetidas en un mismo agente.
Sustituir por mutaciones las reglas con un peso menor o igual que uno dado (en todos los ciclos).
Sustituir por mutaciones y cada cierto número de ciclos, las reglas con un peso menor o igual que uno dado.

Pruebas de ejecución del programa
Manteniendo el ejemplo 2 durante mas de un día (500 ciclos) se han conseguido los siguientes resultados. Se consigue llegar a una (y en ciertos momentos dos) de las reglas buscadas en su forma más optimizada. Transucurrido un tiempo desde su primera aparición, esta regla se mantiene en la población. El número de otro tipo de reglas buenas pero no optimizadas, es decir, con valores de P o C donde debería haber *, permanece mas o menos constante. El número de movimientos realizados con reglas crece de una forma lenta pero identificable.

Conclusiones
Este programa no trata de aprender a jugar al tres en línea sin más. Hay muchos métodos mejores para hacer aprender a un programa, como hacerlo jugar contra jugadores humanos, de forma que intente formalizar el conocimiento humano aplicado en cada caso e lo imite.
Lo interesante de este programa es que no requiere ningún conocimiento previo sobre el juego. Se intenta que el programa aprenda por sí mismo, como si se tratase de un problema por completo desconocido para los humanos.
La primera versión de este programa se distibuyó en Octubre de 1997. Ya entonces el aprendizaje (partiendo de un absoluto desconocimiento inicial, es decir, partiendo de reglas al azar) era muy lento, aunque se podía percibir levemente en ejecuciones muy largas (de varios días) como se muestra en las gráficas. Al principio atribuí esta situación a algún error de programación que estuve buscando infructuosamente. Suponía que había algún error (de programación, no de diseño, es decir, no conceptual), probablemente alguna opción que, aunque no impedía totalmente el aprendizaje, lo perjudicaba, en vez de favorecerlo.
Hasta la fecha (noviembre 1999), más de dos años después, no he podido encontrar dicho error de programación, si bien es cierto que tras un tiempo, perdí el interés por seguir investigando porqué este programa no funcionaba como yo esperaba.
Algunos experimentos recientes siguen apuntando en la dirección de problemas de diseño: por ejemplo, una tarde de domingo inspirada, definimos (Ender, Txipi y yo, o más bien creo recordar que lo hizo casi todo Txipi) un "super-jugador" imbatible que después programé para que pudiera ser introducido en la población en cualquier momento de la ejecución (haciendo una pausa, y continuando después). La introducción de este agente tiene un gran efecto sobre la población, como es de esperar. En poco tiempo, todos los jugadores vivos tienen características de éste agente y todos se convierten en buenos jugadores. Más adelante, el parecido con este "super-jugador" es cada vez más grande...asi que el "super-jugador" cada vez tiene más dificultades para ganar a sus adversarios...¡hasta que desaparece! No solo esto, sino que la población comienza a degenerar y si se mantiene el programa en ejecución durante mucho tiempo, y después jugamos contra el "mejor" de los agentes, descubriremos que a pesar de contar todavía con algunas reglas interesantes (todas heredadas de aquel "super"), tiene otras completamente absurdas, pero que sin embargo es posible que le hayan sido de utilidad en su población. De hecho, si un agente utiliza una regla absurda y gana esa partida, incrementará el peso de esa regla absurda. Se deberían poder generar por azar nuevas reglas útiles que ayuden a apartar las reglas absurdas, pero también es cierto que el espacio de estados de una regla es muy grande, y que es difícil (lento) que por azar se generen reglas buenas, como demuestran las gráficas.
Algunas razones que se avuenturan como posibles causas de este comportamiento son:

El método de asignación de puntuaciones no es del todo correcto
La población es pequeña. Los agentes aprenden a ganar en el "juego" representado por su coyuntura (las reglas de los otros agentes) y no al "tres en línea" que todos conocemos
El número de reglas por agente es pequeño.
El espacio de estados de las reglas es demasiado grande para tratar las reglas como unidades, asi que habría que realizar búsquedas a nivel de regla, por ejemplo, aplicando mutaciones a nivel de elementos componentes de una regla y no a la regla completa.

[Volver al Indice]

Bajar código fuente
Este programa y sus ficheros fuente son gratis y de libre distribución. El código fuente está disponible y puede ser modificado, distribuido, o utilizado en otros programas citando al autor o autores.
Para obtener la última versión del programa, para sugerir posibles ampliaciones, si se detectara algún error en la programación o si desea comunicar que se va a ampliar o utilizar una parte o todo este programa, no dude en ponerse en contacto con el autor en la dirección: E-mail

Pulse aquí para bajar el código fuente.
[Volver al Indice]

[ Home Page Castellano | Home Page English ]