PDF de programación - Jugador virtual del Go, basado en el algoritmo de Monte Carlo

Jugador virtual del Go, basado en el algoritmo de Monte Carlo

Marcos Pividori

Docente: Ana Casali

Facultad de Cs. Exactas, Ingeniería y Agrimensura

Universidad Nacional de Rosario

Resumen. En este trabajo se presenta el desarrollo de un jugador virtual del Go, basado en Monte-Carlo Tree
Search (MCTS). Inicialmente se desarrolla una librería general, adaptable y eficiente para el algoritmo MCTS,
con múltiples ejemplos de uso en distintos dominios. Luego, se procede a trabajar en el problema particular
del juego Go, introduciendo mejoras principalmente en la etapa de simulación a través de la incorporación de
conocimiento de dominio. En particular, se implementan mejoras a través de la detección de patrones en el tablero
y la consideración de múltiples movimientos claves en el juego. También, se exponen diferentes decisiones en
el diseño del programa haciendo énfasis en una plataforma eficiente y reusable. Finalmente se presentan los
resultados obtenidos del jugador desarrollado en comparación a otros programas alternativos.
Introducción

1
Como trabajo final de la materia Introducción a la Inteligencia Artificial, se decidió implementar un programa que
juegue al Go. Revisando el estado del arte (por ej. [1] [5] [6] [9] [12]), se puso en manifiesto que el enfoque
principal que se utiliza hoy en día para enfrentar este problema son los programas construidos sobre el algoritmo
de Monte Carlo Tree Search [5].
El Go ha sido considerado siempre un gran desafío para la Inteligencia Artificial. Uno de los mayores obstáculos
para la construcción de un programa, ha sido la dificultad de conseguir una adecuada función de evaluación. Para
hacer frente a esta dificultad, se presenta el algoritmo MCTS, que permite evaluar una posición simulando un
conjunto de partidas partiendo de dicha posición y analizando los resultados obtenidos al final.
En este informe, inicialmente se exploran las principales alternativas independientes del dominio de aplicación,
desarrollando una librería general para el algoritmo MCTS. Luego, se procede a trabajar en el problema particular
del Go, investigando las mejoras disponibles en el estado del arte, principalmente a través de la incorporación
de conocimiento de dominio en la etapa de simulación. Se implementan varias de ellas, considerando las más
significativas en el rendimiento, y de esta manera se construye un programa de cierto nivel competitivo sobre el
que se pudo investigar e implementar diferentes mejoras propias. Finalmente se presentan resultados del jugador
desarrollado en comparación a otros programas alternativos.
2 MCTS
Monte Carlo Tree Search (MCTS) es un método para toma óptima de decisiones en problemas de Inteligencia
Artificial. Combina la generalidad de simulaciones aleatorias con la precisión de una búsqueda en el árbol de
posibilidades. MCTS no requiere una función de evaluación de posición, en contraste con la búsqueda alfa beta.
Está basado en una exploración aleatoria del espacio de búsqueda, pero usa los resultados de previas exploraciones.
Para ello, MCTS construye gradualmente un árbol en memoria, que mejora sucesivamente estimando los valores
de los movimientos más prometedores.

Figura 1: Etapas del algoritmo MCTS [5].

MCTS consiste en cuatro etapas principales, repetidas tantas veces como tiempo se disponga. En cada una de las
iteraciones se parte de la situación actual del juego.
• Selección: El árbol se recorre desde el nodo raíz hasta alcanzar un nodo hoja. Se toma una rama u otra depen-
diendo de la estrategia de selección que se emplee y la información almacenada en el nodo en ese momento,
como el valor y el número de visitas.

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761215 Dentro de las diferentes opciones, UCT (Upper Confidence bounds applied to Trees) [4] es la más utilizada
por su simplicidad y eficiencia. La estrategia UCT calcula para cada uno de los movimientos posibles una
combinación de dos valores, la tasa de éxito de ese nodo y la relación entre el número de veces que se ha
visitado el nodo padre y el número de veces que se visitó dicho nodo (hijo). El primer valor está relacionado
con la explotación y el segundo con la exploración. A través de un coeficiente C utilizado en la combinación
de ambos valores, se puede dar mayor prioridad a la explotación o exploración. Un punto importante a favor de
la estrategia UCT, es su independencia del dominio de aplicación.

UCT: V alU CT (Ni) = tasaExitoi + C ∗ln(np)/ni

Donde: np y ni son el número de visitas al nodo padre y al nodo Ni respectivamente, C es el coeficiente de
exploración.
• Expansión: Se añaden nodos al árbol MCTS según una estrategia de expansión. Según el criterio, se puede
expandir siempre que se visite un nodo, o cuando se alcanza un determinado número de visitas mínimo, lo
que permite ahorrar espacio en memoria, regulando cuánto crece el árbol en relación al número de ciclos del
algoritmo. Además, se pueden tomar dos caminos a la hora de expandir: en cada expansión añadir un solo nodo
hijo de todos los posibles movimientos o añadir directamente todos los nodos hijos.
• Simulación: Se simula una partida a partir del nodo hoja alcanzado en las fases anteriores. Durante esta partida,
el programa juega solo, realizando los movimientos de todos los jugadores que intervienen hasta que finalice
y se obtenga un resultado. Las estrategias que se utilizan consisten o bien utilizar movimientos aleatorios o
combinar la aleatoriedad con una heurística asociada al problema concreto. En estos casos es necesario buscar
un equilibrio entre la exploración, que da la aleatoriedad, y la explotación, que dirige hacia un movimiento más
prometedor.
• Retropropagación: El resultado de la simulación se propaga hacia los nodos atravesados previamente. Par-
tiendo del nodo hoja y subiendo por la relación con los nodos padres hasta llegar a la raíz, se actualiza cada nodo,
incrementando en una unidad el número de visitas y actualizando su valor con el resultado de la simulación.

}
La cual se implementará para cada dominio en particular. Por ejemplo: StateTateti, StateGo, StateConnect4, etc.
Cada nodo del árbol almacenará información Data, de un movimiento determinado. Entonces, partiendo de un
estado inicial, es posible ir recorriendo el árbol desde la raíz, aplicando los pasos que se encuentran en cada nodo
hasta llegar a una hoja, donde se iniciará la simulación. De esta manera se evita almacenar un estado en cada nodo,
almacenando únicamente los datos de la transición realizada (Data).
Para las 4 etapas principales: Selección, Expansion, Simulación, Retropropagación, se crearon clases abstractas
con las interfaces mínimas necesarias para llevar a cabo el algoritmo.
Diferentes implementaciones que corresponden a diferentes criterios, pueden heredar de cada una de ellas, como
por ejemplo: SelectionUCT, implementará la selección utilizando el algoritmo UCT, mientras que SelectionUC-

Implementación MCTS

Por último, a la hora de seleccionar el movimiento final, se considerará el mejor hijo del nodo raíz, es decir, el
movimiento más prometedor de acuerdo a la información recaudada. Para determinar qué nodo “es mejor” se
pueden tomar diferentes criterios, considerando la tasa de éxito, o el número de visitas, etc.
3
Para la implementación del algoritmo MCTS, principalmente se buscó:
• Que sea reusable. Es decir, que la implementación del árbol y el algoritmo MCTS sean independiente del do-
minio de aplicación, y además se puedan agregar nuevos módulos para modificar diferentes etapas del algoritmo
(Selección, Expansión, Simulación, etc.), en caso de tomar diferentes criterios.
• Que sea eficiente. Este punto siempre estuvo presente en la implementación. Para lograr buenos resultados,
es vital realizar la mayor cantidad de ciclos del algoritmo en el menor tiempo posible. Por esto, se intentó
optimizar en todo lo posible, y en muchas casos se recurrió al uso de templates, funciones inline, guardar
cachés de ciertos valores para evitar hacer cálculos redundantes, sobre todo de funciones costosas (por ejemplo
las llamadas a log() y sqrt() en las selecciones uct y rave), etc.

Buscando un código reusable, se decidió abstraer toda la lógica del dominio de aplicación en una clase State y
un tipo Data. La clase State abstrae las formas en que puede transicionar el sistema, todas las reglas de juego, el
cálculo de puntajes, los posibles pasos a tomar en un determinado punto, etc. El tipo Data, almacenará los datos
de una transición a realizar en un determinado momento, por ejemplo, en el caso del tateti, Data almacenará las
coordenadas de la ficha a incorporar y si es cruz o círculo. Luego, State contará con una interfaz mínima:
c l a s s S t a t e {

S t a t e ( S t a t e ∗ s r c )
g e t p o s s i b l e m o v e s ( v e c t o r <Data>& v )
a p p l y ( Data )
Value g e t

f i n a l v a l u e ( )

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761216 TRave, incorporará además la evaluación amaf siguiendo la propuesta de optimización RAVE.
4 Paralelización
Con respecto a la paralelización del algoritmo, se consideraron diferentes opciones, de igual manera a las men-
cionadas en [3]. Luego de hacer algunas pruebas con diferentes enfoques, se decidió proseguir con el principio
de Tree Parallelization [3] con un lock global. En este enfoque, cada thread bloqueará el árbol cuando necesite
acceder al mismo, en las etapas de selección, expansión y retropropagación. Puede parecer muy limitante, pero
como el mayor tiempo se pierde en la etapa de simulación, este criterio termina siendo muy válido y se pueden
lograr resultados muy buenos con una implementación muy simple, solamente de debe agregar un lock global para
el acceso al árbol.
Como segunda opción, se implementó el enfoque Root Parallelizat