« Resolviendo Problemas… « || Inicio || » Modelado de Sistemas … »

Algoritmo de Montecarlo aplicado a Búsquedas en Espacios de Estados

Última modificación: 22 de Mayo de 2018, y ha tenido 348 vistas

Etiquetas utilizadas: || || ||

Aproximaciones Clásicas

Cuando se trata el tema de la IA aplicada a juegos normalmente se comienza hablando de los llamados Juegos con Información Perfecta, generalmente basados en turnos, en los que todos los jugadores pueden acceder a toda la información disponible de los demás jugadores y donde no hay elementos de azar en la mecánica del juego (como podría ser el uso de dados). Algunos ejemplos de juegos de este tipo son el 3 en raya (Tic Tac Toe), Conecta 4, Damas, Reversi, Ajedrez, y Go, entre muchos otros.

Para este tipo de juegos se puede construir, al menos en teoría, un árbol de estados completo que contiene todos los resultados posibles, y bastaría asignar un valor de victoria o pérdida a las posibles ramas que parten del estado inicial para encontrar una estrategia con la mejor jugada posible (sería como evaluar todos los posibles futuros a partir del estado actual y seleccionar aquel que convenga más al jugador). Un algoritmo como Minimax se basa precisamente en esta idea evaluando la bondad de las jugadas por medio de etiquetas en los estados finales (hojas) que se propagan hasta el estado actual para decidir qué camino en el árbol (jugada) es el que ofrece mejores resultados al jugador.

El problema que presenta un algoritmo como Minimax, y otros algoritmos similares, es que el tamaño del árbol de jugadas/estados puede ser tan grande que la construcción y búsqueda dentro de él se vuelva impracticable, algo que ocurre con relativa facilidad si el juego para el que estamos intentando construir una IA interesante tiene un mínimo de complejidad (por ejemplo, que tenga un alto número promedio de movimientos disponibles por turno), haciendo que el tamaño del árbol crezca exponencialmente por niveles. Por supuesto, en todos estos algoritmos se han proporcionado métodos para mitigar este problema, como por ejemplo acotar la profundidad de búsqueda hacia adelante (y posteriormente usar una función de evaluación para estimar cómo de buena es esa vía, aunque no hayamos llegado a un estado final del juego), o podar ramas para evitar visitar aquellas opciones de juego que, a priori, puedan resultar menos beneficiosas. Sin embargo, la mayoría de estas técnicas requieren de un conocimiento previo del juego que puede resultar difícil de obtener, y podemos encontrar casos que cubren todas las opciones, desde juegos en los que esta aproximación es óptima (como en el caso del 3 en raya), hasta aquellos para los que es posible generar jugadores artificiales de una calidad aceptable (como en el caso del ajedrez), o incluso algunos en los que estas técnicas se muestran claramente insuficientes (como en el caso del Go, sobre todo en sus versiones con tableros completos de 19x19).

Montecarlo Tree Search

Como respuesta a este tipo de aproximaciones hace unos años surgió la técnica de Montecarlo Tree Search (Búsqueda en árboles con Montecarlo) que ofrece algunas ventajas inherentes:

  • la principal ventaja es que se puede aplicar a juegos con un factor de ramificación tan grande que resultan inabordables con las técnicas tradicionales anteriores;
  • además se puede configurar para que se detenga después de una cantidad de tiempo prefijada, haciendo que con tiempos mayores se obtengan jugadores más fuertes;
  • no requiere necesariamente de un conocimiento específico del juego, por lo que puede ser utilizado como motor de juego general;
  • y es adaptable a juegos que incorporan aleatoriedad en las reglas.

Y también algunas desventajas insalvables:

  • es un método probabilístico, por lo que no siempre tiene porqué encontrar la solución óptima;
  • si realizar simulaciones de jugadas es costoso, el proceso completo puede ser inabordable.

En esta entrada mostraremos cómo funciona esta técnica, y nos centraremos específicamente en una variante llamada UCBT (Upper Confidence Bound applied to Trees, o en español Cota de Confianza Superior aplicada a Árboles).

Tras la escritura de esta entrada se ha publicado un post similar que quizás también pueda interesar al lector, ya que introduce algunas notas acerca de cómo se ha usado esta técnica para los famosos Alpha Go (que se enfrentó con Lee) y Alpha Zero (que generaliza el método para otros juegos de tablero consiguiendo niveles increiblemente altos a partir de conocimiento nulo del juego).

Problema de las Tragaperras Múltiples

Imaginemos que nos enfrentamos a una fila de máquinas tragaperras, cada una con características diferentes, tanto en probabilidad como en cantidad de ganancia (premio). Lo ideal sería usar una estrategia que nos permita maximizar la ganancia total. Supongamos, además, que no hay nadie cerca jugando a las mismas máquinas, por lo que no podemos obtener información adicional sobre cuál es la mejor máquina para elegir (es decir, no podemos definir una heurística óptima a priori). La única opción es recopilar esta información personalmente, intentando equilibrar la cantidad jugada en todas las máquinas y concentrando el mayor número de jugadas en la mejor máquina observada hasta el momento.

En su versión más simple (la que nos ocupa aquí), un problema de $K$ tragaperras se puede definir haciendo uso de conceptos básicos de estadística por medio de una sucesión de variables aleatorias $X_{i,n}$ con $1\leq i\leq K$ y $n\geq 1$, donde $i$ es el índice de cada tragaperra. Las jugadas sucesivas de la máquina $i$ da lugar a una sucesión $X_{i,1}$, $X_{i,2}$, ..., independientes e identicamente distribuidas siguiendo una ley desconocida de media $\mu_i$. Además, también pedimos que haya independencia entre las máquinas, es decir, que para cada $1\leq i < j\leq K$, y $s,t \geq 1$, se tiene que $X_{i,s}$ y $X_{j,t}$ son independientes (aunque, normalmente, no serán identicamente distribuidas).

En estas condiciones, una estrategia (policy) es un algoritmo $A$ que elige la siguiente máquina en la que jugar basándose en la secuencia de jugadas anteriores y premios recibidos. Si $T_i(n)$ es el número de veces que el algoritmo $A$ ha seleccionado a la máquina $i$ durante las primeras $n$ jugadas, entonces la pérdida de $A$ se define como:

$$\mu^* n - \sum_{j=1}^K \mu_j E[T_j(n)]$$

donde $\mu^*=max_{1\leq i\leq K}\mu_i$. Es decir, la pérdida esperada debido a que la estrategia no siempre conoce cuál es la mejor máquina.

Apoyándonos en algunos resultados de estadística, podemos hacer uso de una estrategia, llamada UCB1 (Upper Confidence Bound. añadir referencia), que construye intervalos estadísticos de confianza para cada máquina de la forma:

$$\overline{X_i}(n) \pm \sqrt{\frac{2\ln n}{T_i(n)} }$$

donde, $\overline{X_i}(n)$ es la media de ganancias experimental que ofrece la máquina $i$ tras los $n$ pasos.

Sabemos que en las condiciones en las que estamos $\overline{X_i}(n)$ tenderá a $\mu_i$ al aumentar el número de muestreos (jugadas) con esa máquina. Por tanto, una estrategia válida entonces sería escoger siempre la máquina con el límite superior más alto. Al usarla, el valor medio observado para esa máquina se desplazará a su valor real y su intervalo de confianza se reducirá (ya que en esta máquina $T_i(n)$ aumenta más rápido que $\ln n$), a la vez que todos los intervalos de las otras máquinas se van ampliando (ya que, para esas otras máquinas, el valor de $T_i(n)$ permanece constante mientras no las usemos, pero $\ln n$ crece). Eventualmente, alguna de las otras máquinas podrá tener un límite superior mayor al de la máquina seleccionada actual, y entonces lo mejor será cambiar a esa otra máquina.

Esta estrategia verifica que la diferencia entre lo que hubieramos ganado jugando únicamente en la mejor máquina y las ganancias esperadas bajo la estrategia usada crece sólo como $O(\ln n)$ (es decir, perdemos poco respecto a la mejor jugada posible), que es la misma tasa de crecimiento que la mejor estrategia teórica para este problema (denominado Problema de Tragaperras Múltiples), y tiene el beneficio adicional de ser muy fácil de calcular, ya que basta llevar un contador para cada máquina.

Existen otras estrategias que ofrecen un rendimiento similar, pero UCB1 es posiblemente la estrategia más simple con este buen comportamiento, así que será suficiente para la primera aproximación de Montecarlo a problemas de búsqueda que estamos ofreciendo aquí.

Y aquí es donde entra en juego el método de Montecarlo aplicando el método anterior, donde las diferentes tragaperras se cambian por los diversos movimientos válidos del juego (en general, acciones válidas en el sistema), y los premios de la sucesión de máquinas elegidas se cambian por las ganancias en el juego de la sucesión de movimientos realizados (obsérvese la relación existente con el aprendizaje por refuerzo... REFERENCIA).

Aplicación a Búsquedas

En un proceso estándar de Montecarlo:

  1. Se generan un gran número de simulaciones aleatorias desde la posición del tablero para la que se desea encontrar el mejor movimiento siguiente.
  2. Se almacenan las estadísticas para cada movimiento posible a partir de este estado inicial y, posteriormente,
  3. Se devuelve el movimiento con los mejores resultados generales.

La desventaja de este método general, sin embargo, es que para cualquier turno dado en la simulación, puede haber muchos movimientos posibles, pero sólo uno o dos que son buenos, por lo que, si se elige un movimiento aleatorio en cada turno, es extremadamente improbable que la simulación proporcione el mejor camino hacia la solución perfecta.

Ante este problema se han propuesto variantes, como la llamada UCT que presentaremos a continuación, que suponen una mejora que permite minimizar los riesgos, y que se basa en la idea de que si tenemos estadísticas de bondad disponibles para todos los estados sucesores del estado actual, entonces podemos extraer una estadística de bondad para el mismo... de forma similar a como se hace en el problema de las tragaperras múltiples anterior.

En vez de hacer muchas simulaciones puramente aleatorias, esta variante hace muchas iteraciones de un proceso que consta de varias fases y que tiene como objetivo mejorar nuestra información del sistema (exploración) a la vez que potencia aquellas opciones más prometedoras (explotación):

  1. La primera fase, Selección, se realiza mientras tengamos las estadísticas necesarias para tratar cada nodo/estado alcanzado como un problema de tragaperras múltiples. Comenzando por el nodo raíz, que representa el estado actual del juego/problema, seleccionamos recursivamente el nodo más urgente de acuerdo a una función de utilidad (en nuestro caso, por medio del algoritmo UCB1), hasta que se alcanza un nodo que o bien representa un estado terminal, o bien no está completamente extendido (es decir, un nodo en el que hay posibles movimientos o acciones que no han sido consideradas).
  2. La segunda fase, Expansión, ocurre cuando ya no se puede aplicar la fase anterior. Para ello, se elige aleatoriamente una posición sucesora no visitada del nodo que no estaba completamente extendido y se añade un nuevo nodo al árbol de estadísticas con el fin de completar dicha información.
  3. Tras la expansión, nos encontramos en la fase de Simulación, que sigue los mismos parámetros de una simulación típica de Montecarlo. Es decir, partiendo del estado recién añadido se simula una partida completa, ya sea al azar, con una simple heurística de ponderación, o utilizando heurísticas y evaluaciones computacionalmente costosas para una estrategia más elaborada (para juegos con un factor de ramificación pequeño, como el 3 en raya, una simple heurística de ponderación puede dar buenos resultados). Junto a la partida completa se obtiene un valor (premio, recompensa, etc) que determina la utilidad de esa rama para el jugador.
  4. Finalmente, la cuarta fase es la de Actualización o Retropropagación. Con el estado final de juego alcanzado en la fase anterior se actualizan las estadísticas de todas las posiciones previas visitadas durante la simulación completa que se ejecutó a partir del nuevo nodo (incluyendo la cuenta de ganancias si el jugador ganó la simulación).

Obsérvese que en este proceso hay tres estrategias involucradas:

  • Estrategia de selección de nodos del árbol según su utilidad (en la fase de selección). Hay muchas opciones, por ejemplo: seleccionar el sucesor con mayor ganancia, el que ha sido visitado en mayor número de partidas ganadoras, el que verifique las dos condiciones anteriores (si no lo hay, se sigue realizando la búsqueda hasta que haya uno que lo verifique), o el que maximiza la estrategia UCB1 explicada anteriormente.
  • Estrategia de creación de nuevos nodos (en la fase de expansión). Es normal elegir una creación aleatoria uniforme entre las acciones disponibles, pero si se dispone de alguna información adicional del problema se puede usar para decidir qué acción tomar (y, en consecuencia, qué nodo se crea).
  • Estrategia de al generar una partida completa a partir del nuevo nodo creado (en la fase de simulación). Aquí es relativamente común introducir, si se considera necesario, algún conocimiento específico del dominio del problema (del juego).

Este algoritmo se puede configurar para detenerse tras un período de tiempo deseado, o bajo cualquier otra condición deseada. A medida que se van ejecutando más y más simulaciones, el árbol de estadísticas crece en memoria y el movimiento que finalmente se elija converge hacia el juego óptimo real (aunque esta convergencia puede requerir muchísimo tiempo, dependiendo del juego), como ocurre en el problema de las tragaperras múltiples.

En el caso de aplicar el algoritmo UCB1 como estrategia de selección del nodo siguiente el objetivo es maximizar la fórmula equivalente siguiente (y que al aplicarla a la búsqueda en árboles pasa a llamarse UCTUpper Confidence on Trees):

$$UCT(s)=\frac{Q(s)}{N(s)}+2 C_p\sqrt{\frac{\ln N(s_0)}{N(s)} }$$

donde $N(s_0)$ es el número de veces que el nodo $s_0$ (el padre de $s$) ha sido visitado, $N(s)$ es el número de veces que el nodo hijo, $s$, ha sido visitado, $Q(s)$ es la recompensa total de todas las jugadas que pasan a través del nodo $s$, y $C_p > 0$ es constante.

El término $\overline{X_i}(s)$ de UCB1 se reemplaza aquí por $\frac{Q(s)}{N(s)}$, que representa la recompensa media de todas las jugadas. Cuando $N(s)=0$, es decir, el sucesor nunca se ha visitado (todavía), el valor de UCT toma el valor infinito y, por tanto, el sucesor sería elegido por la estrategia. Esta es la razón por la que esta fórmula solo se utiliza en caso de que todos sus hijos hayan sido visitados al menos una vez. Al igual que en la fórmula de UCB1, hay un equilibrio entre el primer término (explotación) y el segundo (exploración). La contribución del término de exploración decrece a medida que se visita cada estado que se visita, ya que aparece en el denominador. Por otra parte, el término de exploración crece cuando se visita otro sucesor de su nodo padre (un hermano suyo). De esta forma, el término de exploración asegura que incluso sucesores con recompensas bajas sean seleccionadas si se da el tiempo suficiente.

La constante del término de exploración $C_p$ se puede escoger para ajustar el nivel de exploración deseado. Kocsis y Szepesvári demostraron que $C_p = 1/\sqrt{2}$ es un valor óptimo cuando las recompensas/ganancias se encuentran en el intervalo $[0, 1]$, pero si no es el caso, entonces el valor adecuado de $C_p$ debe ser determinado esperimentalmente.

Además, Kocsis y Szepesvári también demostraron que la probabilidad de seleccionar una acción subóptima (es decir, no la mejor) para la raíz del árbol tiende a $0$ a velocidad polinomial si el número de iteraciones tienen a infinito, lo que significa que, con suficiente tiempo y memoria, UCT tiende al árbol Minimax y por tanto es óptimo.

El Algoritmo

El algoritmo en pseudocódigo podría quedar como:

Algoritmo UCT
1: Función: MCTS-UCT(s_0)
2:   Crear nodo raíz n_0 con estado s_0
3:   Mientras haya recursos computacionales
4:     n ← Seleccion(n_0)
5:     G ← Simula(s(n))
6:     Retropropaga(n,G)
7:   Devuelve a(MejorHijo(n_0))

1: Función: Seleccion(n)
2:   Mientras s(n) no sea terminal
3:     Si n no está completamente expandido entonces
4:       Devuelve Expande(n)
5:     si no
6:       n ← MejorSucesorUCT(n,c)
7:   Devuelve n

1: Función: Expande(n)
2:   a ← elige acción no probada de Acciones(s(n))
3:   Añadir un nuevo sucesor m de n
4:   s(m) ← aplica(a,s(n))
5:   a(m) ← a
6:   Devuelve m

1: Función: MejorSucesorUCT(n)
2:   Devuelve argmax UCT(n)

1: Función: Simula(s)
2:   Mientras s no sea terminal
3:     a ← un elemento de A(s)
4:     s ← f(s,a)
5:   Devuelve ganancia del estado s

1: Procedimiento: Retropropaga(n,G)
2:   Mientras n no sea nulo
3:     N(n) ← N(n) + 1
4:     Q(n) ← Q(n) + G
5:     n ← Padre de n

Una versión simplificada de este algoritmo se consigue haciendo que la recompensa esté limitada a 3 posibles valores: 1, cuando el jugador gana; -1, cuando el jugador pierde; y 0, cuando se produce un empate entre ambos jugadores (llamado tablas en algunos juegos de tablero).

Implementación en NetLogo

En una entrada posterior vamos a presentar una implementación del algoritmo anterior en NetLogo. Nos basaremos en una implementación anterior, BSS, usada para la construcción de espacios de estados de problemas generales, y veremos cómo usar la implementación que hagamos para proporcionar una IA básica a algún juego, como el 3 en raya.

« Resolviendo Problemas… « || Inicio || » Modelado de Sistemas … »