Formación de un agente DQN en el juego de Conecta Cuatro

Configuración

Conceptos fundamentales

Los actores principales en el paradigma de aprendizaje por refuerzo son el entorno y el agente. El entorno es el contexto en el que el agente vive y con el que interactúa.

En cada iteración, el agente recibe una observación del estado actual del juego, decide la mejor acción a tomar y actúa sobre el entorno.

De esta manera, se genera un cambio en el estado del entorno y se obtiene una recompensa a partir de esta transición.

El objetivo de este ejercicio es obtener una estrategia, plan o política de acción (policy) que sea capaz de maximizar esta recompensa, obteniendo así la mejor acción para cada transición y propiciando una aproximación óptima al juego de Conecta Cuatro.

A continuación se introducen las principales clases que fundamentan este paradigma y que nos permitirán dar conformidad a los actores y al contexto del juego.

Entorno

La implementación del entorno consiste en una clase cuyos métodos y acometidos principales son los siguientes:

• get_valid_actions: provee de una lista con todas las acciones válidas dado el estado actual, es decir, el tablero en ese momento del juego.

• step: acomete una transición con la acción recibida por parte del agente (un índice de una columna del tablero), comprueba si se ha ganado o empatado y devuelve una recompensa dependiendo del resultado.

• switch_turn: cambia el turno de juego entre ambos jugadores.

• reset: inicializa el estado y todas las variables del juego y devuelve un estado inicial.

Agentes DQN y DDQN

DQN y DDQN son en esencia unos algoritmos que consisten en aprender un aproximador para una función Q de acción-valor.

En nuestro caso, se intentará aprender las estrategias de ambos jugadores del juego Conecta Cuatro, por lo que en vez de tratarse de un agente que solamente es entrenado en una estrategia, se trataría de una modalidad de multiagente de aprendizaje por refuerzo (MARL).

Entonces, se presenta un escenario de juego alterno de Markov, o un juego de suma cero donde la ganancia de un jugador es proporcional a la pérdida del otro.

La implementación de la clase que se utiliza para instanciar los agentes consiste de los siguientes métodos:

En cada iteración, se insta al agente a que nos proporcione una acción de acuerdo a una estrategia epsilon-greedy para tratar el dilema exploración-explotación.

En ocasiones será nuestro modelo el que prediga la acción a tomar y en otras se muestreará una acción.

Como se puede ver en el gráfico de abajo, en cada iteración la probabilidad de que se exploren nuevas acciones o de que se exploten las acciones aprendidas decaerá exponencialmente en base al ritmo de decadencia eps_decay.

En el método act del agente DQN, a continuación, se implementa esta estrategia.

Si el valor de la muestra es superior al umbral de epsilon, se aproximará la mejor acción dada la última observación del entorno (explotación de las acciones aprendidas).

En caso contrario, se elegirá una acción (exploración) de entre las acciones válidas de manera uniforme.

Se da la opción, mediante enforce_valid_action, de asegurar que la acción elegida sea válida, o de que se inste al modelo a que aprenda qué columnas del tablero pueden optar en cada turno a una nueva ficha, es decir, a que aprenda esta regla del juego.

Los datos que se utilizan para entrenar el agente se generan desde cero durante cada entrenamiento. Estos datos se almacenan en un objeto de clase ExperienceReplay y se muestrean aleatoriamente con el objetivo de optimizar una estrategia o plan de acción (policy).

Las observaciones en cada iteración se adjuntan como tuplas nombradas (itertools' named_tuple) a una lista secuencia (deque, o cola de doble extremo) con capacidad limitada, donde las observaciones se pueden insertar y eliminar desde ambos extremos, creando así una experiencia de juego.

Cada observación incluye un estado (el tablero del juego en ese preciso instante), una acción (el índice de la columna que ha sido elegida), un siguiente estado (el tablero del juego tras considerar la última acción, o None si es un estado final, es decir si se ha tomado una acción ganadora) y una recompensa.

Una vez se hayan obtenido y memorizado más observaciones que el número de batch_size que utilicemos, procederemos a optimizar el modelo.

En nuestro ejemplo, solamente se optimiza una vez por episodio dado que los valores de las transiciones dependerán en algunas ocasiones de transiciones anteriores.

Por ejemplo, cuando un jugador gana la partida obtiene una recompensa positiva, por lo que para la transición del estado en esta iteración se genera una tupla de la siguiente manera:

transition = Transition(state, action, None, reward)

La transición consistiría en el estado en t, la acción tomada, el estado en t+1 (al ser un estado final se le asigna None) y la recompensa obtenida.

Lo que sucede es que durante la generación de la observación en la iteración anterior, no sabíamos todavía de este desenlace y por lo tanto la recompensa no fue negativa por haber perdido el juego.

Por esta razón, una vez termina cada partida del entrenamiento se resuelve esta relación de recompensas para guardarlas posteriormente en memoria.

Por lo tanto, el transición en t-1 de la transición de arriba sería:

transition_t-1 = Transition(state, action, next_state, reward + env.params['rewards']['loss'])

Se suma a la recompensa asignada y no se asigna directamente la recompensa de pérdida dado que es posible configurar una recompensa por prolongación en el juego como hiperparámetro.

El proceso de optimización se muestra a continuación:

En primer lugar, se muestrean en el método optimize un número de observaciones en memoria, y se concatenan todos los valores de estado y acción de las observaciones en matrices independientes.

Además, tanto los estados en t como en t+1 obtienen una nueva dimensión dado que se aplica una transformación del tablero mediante la función get_two_channels.

La idea es que por cada tablero con valores 0, 1 o 2 se obtengan dos matrices con valores binarios, una para cada jugador.

Estas dos matrices serán los dos canales de entrada por observación que obtendrá nuestra red neuronal convolucional.

Después se genera una matriz lógica que se utilizará como máscara para asignar los valores Q a los estados que no sean finales, mientras que los finales tendrán un valor de cero.

En el caso de que se utilice un agente DQN, se utiliza solamente el modelo de target para obtener los valores de Q, obteniendo simplemente los valores de máxima magnitud de entre todas las acciones.

Mientras que con un agente DDQN, para intentar solventar una posible sobreestimación de estos valores, se utilizan tanto nuestro modelo policy como nuestro modelo "fijo" target para obtener los valores de diferencia temporal de Q a los que nos queremos aproximar.

Posteriormente, se calcula la ganancia a largo plazo que se puede anticipar. Para ello, se aplica un factor de descuento gamma y se resta de la recompensa para esa transición (en lugar de sumarse como en la ecuación de Bellman tal y como se sugiere en este cuaderno de Kaggle).

De esta manera adaptamos nuestra optimización para el aprendizaje de ambas estrategias al juego alterno de suma cero que nos ocupa.

Es en este momento cuando se optimizan los parámetros de nuestra policy. Para ello se calcula la pérdida (en nuestro caso se utiliza el criterio torch.nn.HuberLoss) para minimizar el error de la diferencia temporal δ, se asignan valores nulos a los gradientes para posteriormente ser computados mediante backpropagation, se aplica un clipeado de los mismos en caso de que así se haya configurado el entrenamiento y se actualizan los parámetros en base al gradiente calculado.

Una vez optimizados los parámetros de la policy durante el entrenamiento, se plantea si actualizar los parámetros de nuestro target. Para ello se implementan dos estrategias: soft update y hard update.

La primera actualizará los parámetros de forma gradual en cada episodio solamente obteniendo una parte porcentual de los parámetros de policy en base al valor TAU considerado como hiperparámetro en el entrenamiento.

Por ejemplo, si TAU es 0.001, target pasará a utilizar el 0.1% de los parámetros de policy y mantendrá el 99,9%.

Por el contrario, mediante hard update se copiarán todos los parámetros de golpe si se alcanza un número de iteraciones a configurar.

Por último, se implementan tres métodos para guardar transiciones en memoria, guardar parámetros actuales de policy para configurar checkpoints durante el entrenamiento y para cargar los pesos de un modelo guardado al principio de un entrenamiento.

Nótese que el optimizador se instancia una vez se hayan podido cargar los pesos del modelo de uno previamente guardado.

Modelado

El modelo elegido para aprender el juego de Conecta Cuatro consiste de dos capas convolucionales con activación ReLU y dos capas completamente conectadas (la primera también con activación ReLU) en la salida.

En el mismo objeto de clase ConnectFourNet se instancian dos módulos, uno para policy y otro para target. Este último se copia del primero una vez se hayan inicializado sus parámetros (pesos y sesgo).

De esta manera podemos guardar los parámetros de ambos modelos durante el entrenamiento en el mismo diccionario de estados.

Entrenamiento

Como se ha apuntado previamente, el entrenamiento de la política de juego aúna las estrategias de ambos jugadores. Para ello se experimenta con la utilización de los agentes DQN y DDQN.

DQN

En primer lugar configuramos todos los parámetros no solo del entrenamiento sino también de la evaluación, entorno y agente, y con estos parámetros se instancian el módulo con las redes neuronales, el agente y el entorno.

Una vez instanciadas todas las entidades y parámetros que se necesitan podemos iniciar el entrenamiento del agente para optimizar la policy.

La función train muestra métricas de iteraciones de manera periódica. Algunos valores corresponderán a medias obtenidas a partir de valores actuales y de iteraciones previas para poder reconocer las tendencias durante el entrenamiento.

En cada episodio se evalúa el modelo de policy jugando contra un agente random.

Las recompensas para cada episodio suelen ser cero dado que se suma la puntuación ganadora a la perdedora (-1 + 1), en cambio la media que aparece entre paréntesis en ocasiones es diferente a cero. Esto es debido a que en algunos episodios el modelo elige una acción que no es válida y obtiene una recompensa como si hubiese perdido el juego, pero no se le asigna una recompensa ganadora al otro jugador puesto que no se da la transición siguiente.

Como podemos ver, esta media tiende a disminuir, es decir, el modelo tiende a cometer menos errores a la hora de elegir acciones que sean legales.

En los gráficos anteriores podemos comprobar lo que comentamos previamente. Además, se observa cómo la cantidad de iteraciones tiende a aumentar ligeramente durante el entrenamiento y la evaluación.

Cabía esperar que en el entrenamiento se alargasen las partidas dado que a medida que el modelo aprende sigue jugando contra sí mismo.

En cambio, en lo que respecta a la evaluación, y considerando que el modelo juega contra una toma de decisiones aleatorias, cabría esperar que, pese a que hay una ligera reducción en la cantidad de turnos que necesita para ganar con el paso de las iteraciones, la reducción fuese mayor.

De cualquier manera, el modelo tiende a ganar casi la totalidad de las partidas, como podemos ver en Evaluation rates.

Una opción a probar para incentivar al modelo a intentar que las partidas sean más cortas podría ser asignar una recompensa negativa a params_env['rewards']['prolongation'].

Por otra parte, al estar aprendiendo una estrategia o política de acción para un escenario no estacionario, el cual depende de acciones puntuales, solamente se considera el gráfico de Running loss para la elección del hiperparámetro del tamaño del lote de entrenamiento (batch_size) y para comprobar que los gradientes ni aumentan ni disminuyen considerable o exponencialmente (exploding gradients y vanishing gradients).

A continuación podemos comprobar cómo actúa nuestra policy con ejemplos de posibles tableros legales en situaciones clave del juego, solamente por motivos de ilustración.

En primer lugar vemos si es capaz de completar algunas líneas de cuatro para ganar un juego.

Podemos ver como este modelo es capaz de elegir acciones para ganar el juego ya sea horizontal, vertical, diagonal o anti diagonalmente, aunque no para ambos jugadores en todas las modalidades de líneas, sí para ambos jugadores en distintas modalidades.

De manera similar sucede cuando a nuestro aproximador se le presenta la ocasión de bloquear líneas de cuatro fichas consecutivas para ganar un juego justo en el turno anterior de que puedan suceder estas transiciones ganadoras.

DDQN

Por último se ha procedido al entrenamiento de un agente DQN doble en el mismo ejercicio. Se han utilizado hiperparámetros de entrenamiento similares.

Como podemos ver a continuación, los resultados del entrenamiento son similares al agente DQN, en cambio, los resultados del modelo frente a una toma de decisiones aleatoria son ligeramente peores.

De nuevo, solo por motivos de ilustración, le planteamos a nuestro modelo unas observaciones de escenarios clave en el juego para tener una idea de cómo se desenvuelve.

Como vemos, sigue siendo capaz de resolver la mejor acción en la mayoría de tableros tanto para ganar la partida como para bloquear al jugador contrario a que la gane:

Cabe la posibilidad que los modelos no rindan tan bien en partidas prolongadas del juego dado que durante el entrenamiento reciben más observaciones de tableros con menos fichas.

Hay muchos parámetros del entrenamiento a modificar e intentar una mejor generalización del modelo. Por ejemplo, las recompensas, la tasa de decadencia de epsilon, el tamaño del lote de observaciones, la capacidad de la memoria, la tasa de aprendizaje o incluso implementar otra arquitectura de red neuronal o modificar y/o incluir capas convolucionales o las completamente conectadas.

Además, se pueden implementar algoritmos de aprendizaje por refuerzo más modernos como la optimización de políticas proximales (PPO), o hacer uso de una memoria de observaciones con muestreado priorizado.

La librería TorchRL, que es una librería de aprendizaje por refuerzo para PyTorch, implementa estas y otras muchas opciones.

Exportación

Como se apunta en la introducción de este cuaderno de Jupyter, este modelo se utiliza en una aplicación web descentralizada de conocimiento cero.

Por esta razón, se hace uso del módulo torch.onnx para convertir el gráfico de cálculo nativo de PyTorch a un gráfico ONNX y así mediante la librería de JavaScript ONNX Runtime Web se pueda desplegar este modelo de aprendizaje automático en nuestra aplicación web.