Introduccion

Reinforcement learning

Reinforcement Learning es una rama de inteligencia artificial que basa su aprendizaje en el concepto de "prueba y error". Todo algoritmo de Reinforcement Learning presenta a un agente que actúa en un entorno y recibe una recompensa (positiva o negativa) por cada una de sus acciones. El objetivo de un agente es encontrar una estrategia que maximize su recompensa a largo plazo.

Breakout video:

breakout video

Bucle de Reinforcement Learning.

Por cada escalón de tiempo t:

• El Agente:
  1. Recibe recompensa r_t
  2. Recibe observación s_t
  3. Emite acción a_t
• El Entorno:
  1. Recibe acción a_t y la ejecuta. La ejecución de la acción a_t modifica el entorno.
  2. Emite recompensa r_t+1
  3. Emite observación s_t+1

El entorno

Estados

El entorno para este taller es el juego del 4 en raya. Incluso para un juego tan "sencillo" como el 4 en raya, hay 4,531,985,219,092 posibles estados.

El set de posibles estados de un entorno se denomina S. Cada valor denota una posible representación del estado de un entorno. s_t es la representación del entorno para cada instante t. Normalmente, escoger una buena representación del estado s_t no es fácil, y una buena representacion puede simplificar mucho la tarea de aprendizaje.

Para este taller, la representación será una matriz de 2 dimensiones, que representa el tablero del 4 en raya, nos referiremos al estado como Board (tablero en ingles). Board_ij denotara el estado de la casilla en la fila i y columna j. Board_ij = 0: casilla vacia. Board_ij = 1: ficha del jugador 1. Board_ij = 2: ficha del jugador 2.

Acciones

El set de posibles acciones disponibles en un entorno se denomina A. Para este taller, un estado s_t tendrá un máximo de 7 acciones posibles, A = [0, 1, 2, 3, 4, 5, 6]. Cada acción representa la acción de colocar un ficha en una de las 7 columnas del tablero. En caso de que en un estado s_t la columna número i este llena, no se podra colocar una ficha en ella, con lo cual la acción a_i no se podrá ejecutar en el estado s_t.

Cuando se ejecuta una acción a_t en el entorno, este se modifica. Tras la modificación, el entorno presenta un nuevo estado s_t+1 junto con una recompensa r_t+1 al agente.

Recompensa

Cada posible acción, en cada estado, tiene asociada una recompensa. Una recompensa mide, a corto plazo, lo buena o mala que es una acción en un estado concreto.

Para este taller nos interesa ganar la partida. Con lo cual una acción que gane la partida otorgará al agente una recompensa de +1, cualquier otro movimiento otorgara una recompensa de 0.

El agente

Estrategia

Por cada instante t el agente "observa" el estado s_t. Tras "observar" el estado s_t, el agente escoge que acción a_t va a ejecutar usando una estrategia representada por la letra griega . Una estrategia es un mapeado de estados a acciones, y es todo lo necesario para definir el comportamiento de un agente. representa el mapeado de un estado s_t a una acción a_t. La tarea de "aprendizaje" de un agente en reinforcement learning es la tarea de encontrar una estrategia que maximize su recompensa a largo plazo a partir de recompensas a corto plazo.

Representación de un agente y un entorno.

Taller

Monte Carlo Tree Search (MCTS)

MCTS es un método de Monte Carlo. Los métodos de Monte Carlo son métodos de aproximación estadísticos que se basan en la siguiente idea: hay un fenómeno que queremos estudiar. Este fenómeno es generalmente una expresión matemática compleja, con lo que intentamos aproximarlo. Para ello, tenemos acceso a un modelo (un simulador) del entorno donde ocurre este fenómeno. Utilizando el modelo podemos generar muchas simulaciones. Con ellas, podemos calcular estadísticas pertinentes del fenómeno que queremos estudiar. En el campo de inteligencia artificial para videojuegos, el modelo suele ser las reglas del juego. Dado un estado s_t en un entorno, el fenómeno a averiguar es el valor de cada posible acción a_t en un estado s_t. Si tenemos una aproximación del valor real de cada acción posible a_t para cada estado s_t, podemos escoger la acción de mayor valor en cada momento t para jugar de forma óptima.

Monte Carlo Tree Search - Upper Confidence Bound applied to Trees (MCTS-UCT)

Monte Carlo Tree Search - Upper Confidence Bound applied to Trees (MCTS-UCT) es un algoritmo que se usa para aproximar la estrategia óptima para un agente a cada paso de la partida. MCTS-UCT se usa para responder a la siguiente pregunta. Dado un estado s_t ¿Qué acción a_t nos dará una mayor recompensa a largo plazo? Que es lo mismo que preguntar ¿Qué acción tiene mas probabilidades de ganar la partida? Si un agente utiliza MCTS-UCT en cada uno de sus turnos, está aproximando en todo momento la decisión óptima.

La idea de MCTS-UCT es la próxima. Para averiguar que acción a_t tomar en s_t, simulamos muchisimas partidas, con cada partida aprendemos estadisticas que nos informan sobre lo buena (o mala) que es una acción en el estado s_t. Con estas estadísticas, escogemos que acciones vamos descartando y que acciones prometedoras seguimos investigando.

Estructura del algoritmo MCTS-UCT

El algoritmo de MCTS-UCT se divide en 4 fases, seleccion, expansion, simulacion y retropropagacion (backpropagation).

Selección

Fórmula de UCB1:

• w_i: número de victorias acumuladas en el nodo hijo i.
• n_i: número de simulaciones acumuladas en el nodo hijo i.
• N_i: número de simulaciones acumuladas en el nodo actualmente seleccionado.
• c: parametro de exploracion, es una constante. Nos permite escoger entre los dos términos de la equación de UCB1. Un c grande da más importancia a la exploracion. Un c pequeño (c < 1) da más importancia a la explotación. Ver (ingles) explotación-vs-exploración

Esta fase empieza seleccinando el nodo raiz R. En caso de que todos los movimientos se hayan seleccionado al menos una vez, aplicamos la fórmula UCB1 a todos los nodos hijo y seleccionamos el que de un valor mayor. Es decir, el nodo hijo i que reciba el valor UCB1 mas alto sera seleccionado. Este proceso se repite hasta que se seleccione un nodo que no este completamente expandido (que tenga nodos hijo que nunca hayan sido seleccionados) o al llegar un nodo hoja / terminal. Si seleccionamos un nodo el cual tiene algún movimiento que no se haya expandido, expandimos uno de estos movimientos no seleccionados, terminado la fase de selección.

Expansión

El paso mas sencillo. Una vez se ha seleccionado un nuevo hacemos dos cosas. Primero, lo añadimos al game tree que se esta construyendo en la ejecución de MCTS-UCT. Segundo, lo iniciamos con contadores para diferentes estadísticas que serviran para guiar la fase de selección en futuras iteraciones. Viendo la equacion de UCB1 las estadísticas que nos interesa guardar son:

• w_i: número de victorias acumuladas en el nodo hijo i.
• n_i: número de veces que el nodo hijo i ha sido seleccionado.

Simulación

En términos generales, una simulación es una sucesion de acciones por partes de todos los agentes que cambian el entorno hasta llegar a un estado terminal. En un game tree, una simulacion empieza en el estado s correspondiente a un nodo raiz y se toman acciones posibles que llevan a otros nodos. La simulacion termina cuando se llega a un nodo hoja / terminal.

Terminada la expansión del nodo escogido, comenzamos una simulacion del juego (en este taller 4 en raya) desde este nodo. Cada una de las acciones escogidas durante toda la simulacion son aleatorias (los dos agentes juegan movimientos aleatorios). Otros terminos utilizados para hablar de simulaciones en la literaturas son rollout o playout.

Nota: Exceptuando el nodo donde comienza la simulacion todos los otros nodos por los que se pasa en cada simulacion NO forman parte del game tree que se esta formando durante MCTS-UCT.

Retropropagación

El resultado de la simulación se propaga por todos los nodos del game tree empezando por el nodo creado en la fase de expansión y terminando en el nodo raiz del game tree. Para actualizar las estadísticas basta con actualizar el número de simulaciones y victorias (en caso de que la simulación haya sido victoriosa) en cada uno de los nodos. Este proceso también se conoce como backpropagation.

Selección de acción.

El uso de las estadisticas calculadas durante las previas fases es la de seleccionar una accion a_t para tomar en el movimiento numero t. Donde s_t es el estado correspondiente al nodo raiz del game tree generado por MCTS-UCT. Inspeccionamos a todos los nodos hijo correspondientes al nodo raiz y tomamos el que tiene un valor mayor de posibilidad de victoria. Tomamos la accion asignada al nodo hijo c cuyas estadisticas maximizen la equacion:

• w_c: número de victorias acumuladas en el nodo hijo c.
• n_c: número de simulaciones acumuladas en el nodo hijo c.

Animacion de MCTS

El Reto

¡Implementa el algoritmo MCTS-UCT en python para jugar al 4 en raya contra una inteligencia artificial!

Instalación

Necesitarás Python 2.7 para este ejercicio. La implementación del algoritmo no requiere ninguna herramienta que no venga dentro de la distribucion estandard de Python 2.7. El script solo tiene una dependencia: colorama, un módulo para imprimir texto con colores en la terminal, su uso en este ejercicio es puramente estético ¿Pero quién no quiero tener texto de colores en la terminal? Para instalar colorama:

pip install colorama

El script

El script MCTS.py contiene todo el código necesario para los dos talleres. También es el único archivo que deberá ser modificado durante los talleres. Su contenido está escrito en inglés para facilitar busquedas relacionadas en internet. Los comentarios están en español. Utiliza los comentarios dentro del codigo como documentación del mismo.

Para jugar una partida entre 2 humanos ejecuta: python MCTS.py