Computación evolutiva: Ejemplo II

Abstract

Siguiendo con la serie de ejemplos prácticos -pulsa aquí para ver el ejemplo I- y disponibles con licencia GPL, de algoritmos evolutivos, voy a mostrar ahora algo que, bien entendido; se comprende es un logro importante, que debemos a dos fundamentales ramas de la IA; como son la computación evolutiva y las redes neuronales.

Estoy hablando de la posibilidad de crear programas que adquieran “conocimiento” estratégico automáticamente sin necesidad de que un programador humano implemente ninguna regla heurística de aprendizaje.

La idea de este ejemplo parte de Blondie24; un juego de damas, implementado por David B. Fogel, que; haciendo uso de Estrategias Evolutivas y una red neuronal, consiguió que el programa aprendiera, tras 8 meses de entrenamiento, a jugar bien a las damas. Y tan bien aprendió, que consiguió un rating de 2048 –un 99,6% mejor que cualquier jugador humano-.

Lo increíble de Blondie24, era que el programador, en ningún momento implementó reglas heurísticas para el correcto funcionamiento del programa. No se escribió qué jugadas son mejores que otras, ni se propuso ningún mecanismo de recompensa por buenas jugadas, ni hizo falta la intervención humana en el aprendizaje en modo alguno. El programador sólo implementó de forma prestablecida las reglas básicas del juego: qué movimientos están permitidos hacer y cuándo alguien ha ganado el juego, y fue Blondie24 la que “aprendió” a jugar, como lo hace cualquier jugador humano –al que nadie le enseñe estrategias sino que aprenda por si mismo-: progresivamente mediante ensayo y error.

Ejemplo práctico II: Proyecto Noelia

Utilizando la teoría tras Blondie24, y algunos de los detalles geniales que David B. Fogel introdujo en su proyecto, me propuse hacer algo similar, pero a menor escala; para poder afrontarlo en poco tiempo, aunque sin perder su esencia.

Para conseguirlo, opté por implementar un programa que “aprenda” por si sólo buenas estrategias de un juego, mucho más elemental que las damas, y bastante utilizado en los ejemplos teóricos de IA: el juego del tres en raya, también conocido como tic-tac-toe. Aunque; tengo que reconocer, finalmente, me propuse algo un poco más ambisioso que eso, consguir no sólo que juegue buenas estrategias, sino que alcance estrategias con las que nunca pierda (no-loss-strategy).

El programa que os presento a continuación; programado en un applet de Java para que podáis probarlo de primera mano, consigue precisamente eso: aprender a jugar al tres en raya, sin enseñarle a priori ninguna técnica estratégica mediante heurística, sólo usando una red neuronal cuyos pesos se ajustarán mediante una estrategia evolutiva.

El programa, al ejecutarse inicialmente el applet, sólo "conoce" las reglas básicas del juego, cuándo termina la partida y el resultado de la misma, y sólo sabe prever si tu próximo movimiento la hará perder. Pero no entiende de estrategias, ni es capaz de jugar bien. Al comienzo, el programa tiene el nivel de una persona muy novata en el juego.

Si pulsamos en el botón Estadísticas, podremos ver cuántas partidas empata o pierde en este momento el programa tras jugar 50 veces contra un jugador experto -simulado mediante heurística, con un árbol min-max y profundidad (ply) de 9 movimientos-. De media, antes de entrenar, el programa perderá un 50% de sus partidas contra dicho jugador experto.

Si pulsamos sobre el botón Jugar, veremos que, en cuanto pensamos un poco y aplicamos una estrategia correcta, comenzamos a ganar partidas.

Para conseguir, de manera on-line; que el programa aprenda a jugar, debemos pulsar sobre el botón Entrenar. En ese momento, el programa comenzará a competir consigo mismo una y otra vez, mejorando con el paso de tiempo –de las generaciones- de manera automática su juego. Irá aprendiendo buenas estrategias de juego.

En cualquier momento del entrenamiento, podemos pulsar en el botón Cancelar, y comprobar cómo va mejorando el juego del programa. Si jugamos contra él, veremos que estrategias con las que antes le ganábamos, ahora ya no son efectivas, o que, si pulsamos sobre el botón Estadísticas, el porcentaje de partidas perdidas va disminuyendo.

Pasadas las generaciones –si se le permite entrenar bastante tiempo-, el programa será igual de efectivo que un jugador humano. Lo que significa que; lo mejor que podrás conseguir contra él serán tablas. El aprendizaje ocurrirá poco a poco, lo que significa que verás una mejora gradual en su calidad de juego. Por poner un ejemplo; es de notar que, tras pasar algunas generaciones de entrenamiento; el programa "comprende" que la mejor estrategia de juego consiste en mover a la casilla central siempre que esté libre.

Hay de tener en cuenta, que sólo notarás una mejora realmente significativa en la calidad de juego a partir de trascurridas algunas generaciones, y que un juego de estrategia no-loss suele llegar aproximadamente en 150 generaciones.

Debajo del siguiente applet con el ejemplo II, explicaré más en profundidad la teoría que sigue el proyecto de aprendizaje automático, y encontrarás un enlace con el código fuente del ejemplo:

No puede ejecutar applets de Java. Instale la JVM, y vuelva a recargar la página, por favor.

Podéis descargar el código fuente del ejemplo II desde este enlace.


Explicación técnica del ejemplo

El proyecto de ejemplo II, tiene las siguientes características técnicas:

Toda la estrategia de juego, corre a cuenta de una red neuronal; con conexión hacia delante y dos capas ocultas (hidden layer).

La capa de entrada contiene nueve nodos; uno por cada posible contenido dentro del array que forma el tablero de juego –con un 1 si la ficha de una casilla es propia, un -1 si la ficha es del adversario, y un 0 si la casilla está vacía-, y un nodo de salida, responsable de devolver el resultado del proceso neuronal: expresando lo bueno o malo que un movimiento concreto es.

Tenemos así una red neuronal compuesta de 9 nodos de entrada xi, 21 nodos en las capas ocultas, y un nodo de salida. Más otros 9 nodos de activación (nodos bias).

Inicialmente, los pesos wij de la red neuronal son marcados aleatoriamente, por lo que la respuesta de la red neuronal ante el problema sobre qué buena o mala es una jugada será también aleatoria.

Hay pues que entrenar al programa para que aprenda a evaluar las jugadas, lo que vamos a conseguir ajustando evolutivamente los pesos de la red neuronal utilizada. Dicho entrenamiento evolutivo se realizará mediante una estrategia evolutiva.

La estrategia evolutiva será representada por un vector de 9 elementos de tipo real. Esos elementos o individuos de selección se van a corresponder con los pesos de los nodos que contiene la red neuronal, de manera que serán esos pesos los que irán evolucionando.

Así pues, la población en evolución, consistirá en n individuos (con n = 15), que tendrán n hijos, con variación exclusiva por mutación -sin recombinación- y cuya función de desempeño (fitness fuction) será calculada mediante competición -selección por torneo-.
Para el proceso de mutación, hay que tener en cuenta que cada individuo; además de un vector de pesos, contiene un vector de variables de ajuste, que también irá evolucionando junto con los pesos.

La mutación es de la forma:



Con alpha igual 0.2f, y donde xi indica el peso en la posición i del vector de pesos, y N(0,1) indica un valor tomado aleatoriamente de una distribución normal de desviación típica igual a 1, y media igual a 0. La otra variable que interviene en el proceso se corresponde con la variable de ajuste del elemento i, que; como se puede ver, muta antes de que lo haga el peso xi.

La evaluación de un individuo se realiza mediante q partidas (con q = 15), jugadas entre el individuo a evaluar, y otro individuo de la población, tomado aleatoriamente sin reemplazamiento. Cada partida ganada le sumará 1 punto, las perdidas le restará 2, y los empates no suman nada. El valor final será su función de desempeño.

Finalmente, el proceso de selección consistirá en tomar los 15 mejores individuos de entre los 30 (15 padres + 15 hijos) individuos de la generación en curso. En caso de empate en la función de desempeño, se favorecerá a los individuos más longevos.

El paso de generaciones tendrá como resultado un ajuste en los pesos de la red neuronal, lo que dará lugar a un entrenamiento de la misma, que será lo que permitirá; a su vez, al programa a jugar bien, sin intervención heurística alguna.

Detalles adicionales

1º) Para que el aprendizaje automático tenga lugar, es necesario; al menos, prever un movimiento del contrario por adelantado -qué hará él si yo muevo aquí-. Esto se consigue mediante el uso de un árbol min-max de profundidad 2 (ply=2 ), lo que es insuficiente para que la máquina comprenda estrategias, pero que sí permite una base para el ajuste de pesos de la red neuronal. Pero siempre evaluar lo bueno o malo de una jugada será objeto de la red neuronal. Es decir; aunque hay un árbol min-max de ply igual a dos, la evaluación de la tabla de tu movimiento y el mejor movimiento del contrario, la desempeña la red neuronal y no ninguna regla a priori.

2º) La red neuronal utilizada va a devolver siempre un valor real en el rango [-1,1]. Un -1 sólo cuando el movimiento a evaluar termina siendo una victoria del adversario, un 1 si la victoria es suya, y un valor entre (-1, 1) indicando lo bueno que es una jugada para el programa (valores cercanos a 1) o para el contrario (valores cercanos a 1).

3º) Hay un check box llamado no-loss, que, cuando se activa, indica que el proceso de entrenamiento, se hará jugando contra el jugador experto simulado mediante heurística. De esa manera, el aprendizaje es más rápido y siempre termina (tras unas 100 generaciones aproximadamente) alcanzando una estrategia no-loss. Cuando el check está desactivado, el entrenamiento se realiza contra sí mismo y podría ser que la estrategia no-loss no se alcance -aunque siempre quedará cerca-.

4º) El campo llamado Info, en el lateral superior derecho del applet, contiene información sobre el estado del entrenamiento. Conforme pasan las generaciones, la pantalla se actualiza, y muestra datos sobre el mejor individuo de la última generación: su función de desempeño, su edad -cuanto tiempo lleva en el pool evolutivo-, y la media de su juego -resultados/edad-. Cuando juegues contra la máquina, te mostrará la misma información, pero sobre jugador contra el que estás jugando -el mejor que se encontró-.

5º) La mejor manera de saber si hemos llegado a una estrategia no-loss, es ir mirando la pantalla de información, y esperar a que aparezcan datos en los que el mejor jugador encontrado tiene f = 0.0 y una edad avanzada (más de 20). Si pulsamos sobre el botón cancelar, y luego sobre el botón Estadísticas, deberá devolver siempre un 100% de empates contra el jugador experto.

Conclusión

Lo que pensé iba a ser un ejemplo fácil de conseguir, ha resultado ser una verdadera pesadilla, que me ha llevado un par de semanas de mi tiempo libre.

Mi cabezonería me ha impedido abandonar, y ahora me alegro, porque aprendí muchísimo sobre redes neuronales, y he podido avanzar en este campo de la IA que me parece fundamental, y que creo hace un muy buen equipo con la computación evolutiva. Es más, me atrevería a decir, que el futuro desarrollo de ambas ramas podría llegar a conseguir una verdadera inteligencia artificial. No sé si viviré para verlo, pero aquí queda dicho :).

Gracias por compartir vuestro tiempo conmigo, espero que el proyecto les haya gustado, y el código fuente les pueda servir de ejemplo.