Siguiendo con la serie de ejemplos prácticos -pulsa aquí para ver el ejemplo II: Aprendizaje de estrategias no-loss en el juego 3 en raya o Tic-tac-toe- y disponibles con licencia GPL, de algoritmos evolutivos, voy a mostrar ahora otro ejemplo práctico. En esta ocasión se trata de diseñar un algoritmo capaz de aprender por si solo a jugar bien al famoso juego Conecta 4 -o cuatro en línea-.
El esquema principal seguido es el mismo del ejemplo II de la serie de ejemplos evolutivos prácticos que estoy desarrollando. Es decir; se sigue la idea detrás 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-.
Ejemplo práctico III: Proyecto Evolutivo para el juego Cuatro en Línea -o Conecta 4-
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 Cuatro en Línea, 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 demasiado bien.
Si pulsamos en el botón Estadísticas, podremos ver cuántas partidas empata o pierde en este momento el programa tras jugar 150 veces contra un jugador que puede ver 6 jugadas hacia delante (ply =6).
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.
Debajo del siguiente applet con el ejemplo III, 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:
Podéis descargar el código fuente del ejemplo III desde este enlace.
Explicación técnica del ejemplo
El proyecto de ejemplo III, 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 una capaa oculta (hidden layer).
La capa de entrada contiene 42 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.
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 1848 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º) 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ó-.
No hay comentarios:
Publicar un comentario