Repositorio Institucional de Documentos

Proyecto Final de Carrera Ingenier´ıa Inform´atica Curso 2011-2012 M´etodo de Monte-Carlo Tree Search (MCTS) para resolver problemas de alta complejidad: Jugador virtual para el juego del Go Beatriz Nasarre Embid Junio de 2012 Director: Dr. Francisco Ser´on Arbeloa Co-Director: Dr. Manuel Gonz´alez Bedia Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza A todos los que hac´eis cumplir mis sue˜nos Todo aquello que hoy es una realidad, antes era s´olo parte de un sue˜no imposible (William Blake) Agradecimientos Quiero agradecer a mis directores, Paco y Manolo su ayuda y dedicaci´on durante estos meses. Concretamente a Paco, por darme la oportunidad de trabajar este proyecto tan interesante, por la confianza depositada en m´ı y por todos tus consejos y a Manolo por transmitirme ese inter´es por los sistemas cognitivos. Tambi´en quiero dar las gracias a mis amigos de clase que me han ayudado a˜no tras a˜no, disfrutando de su compa˜n´ıa, compartiendo los buenos y malos momentos y d´andome ese empujoncito cuando lo necesitaba. Gracias a todos los que form´ais AEGEE por transmitirme siempre esa energ´ıa, cari˜no, motivaci´on, trabajo e ilusi´on. Quiero agradecer tambi´en los Adebaneros el compartir conmigo esos buenos momentos. Finalmente, dar las gracias a mi familia, por apoyarme siempre, estar ah´ı y ense˜narme a luchar por lo que quiero. Derechos de autor Los derechos de la presente obra pertenecen a D ª .Beatriz Nasarre Embid, al Dr.D.Francisco Jos´e Ser´on Arbolea y al Dr.D.Manuel Gonz´alez Bedia, del Departamento de Inform´atica e Ingenier´ıa de Sistemas de la Escuela de Ingenier´ıa y Arquitectura de la Universidad de Zaragoza. Queda prohibida la reproducci´on total o parcial de esta obra, por cualquier medio, sin el permiso escrito de los autores. Ficha t´ecnica T´ıtulo M´etodo de Monte-Carlo Tree Search (MCTS) para resolver problemas de alta complejidad: Jugador virtual para el juego del Go Autora Beatriz Nasarre Embid DNI 17754254 Especialidad Inform´atica Directores Francisco Ser´on Arbeloa y Manuel Gonz´alez Bedia Departamento Departamento de Inform´atica e Ingenier´ıa de Sistemas Centro Escuela de Ingenier´ıa y Arquitectura Universidad Universidad de Zaragoza Fecha Junio 2012 vi ´ INDICE GENERAL Cap´ıtulo 1 Introducci´on El problema de b´usqueda en ´arboles es un problema en el cual los estados se representan como nodos de un ´arbol, y las acciones pueden ser representadas como ejes entre los nodos. Se define un ´arbol como un grafo ac´ıclico donde cada nodo tiene un conjunto de cero o m´as nodos hijos, y al menos un nodo padre. 1Distinguimos tres tipos de problemas relacionados con el mundo de los juegos2[1, 2, 3]: 1) Problemas sin oponentes (llamados tambi´en problemas de optimizaci´on, juegos de un jugador o puzles); 2) Problemas con un oponente (juegos de dos jugadores, en los que se lucha contra el oponente o se colabora con ´el) y 3) Problemas con m´ultiples oponentes (juegos multijugador donde se puede crear coaliciones). Sin embargo, tambi´en se pueden clasificar seg´un intervengan alg´un elemento aleatorio (Problemas estoc´asticos[5]) o no (Problemas deterministas[4]). La Tabla 1.1 muestra un esquema de ejemplos para estos problemas. Un jugador Dos jugadores Multi-jugadores Determinista Problema del viajante Go, ajedrez Damas chinas Estoc´astico Problema de navegaci´on Backgammon Catan Simplificado Cuadro 1.1: Problemas de b´usqueda en ´arboles Un algoritmo de b´usqueda toma un problema (ej. un juego) como entrada y devuelve una soluci´on en forma de una secuencia de acciones (ej. secuencia de movimientos). Muchos algoritmos de b´usqueda se han desarrollado durante el ´ultimo siglo. Durante d´ecadas, el algoritmo αβ [6]ha sido el est´andar de la b´usqueda en ´arboles para juegos de dos jugadores. Este algoritmo requiere una funci´on de evaluaci´on3para dar resultados satisfactorios. Sin embargo, est´a funci´on de evaluaci´on no est´a disponible para el Go (juego elegido para el proyecto), donde el efecto de colocar una pieza es solo visible a largo plazo. Como consecuencia, los mejores programas de Go en 2005 utilizaron una combinaci´on de la b´usqueda αβ, sistemas expertos, heur´ısticos y patrones, donde la metodolog´ıa usada era completamente dependiente del dominio. Una alternativa que emergi´o sobre esta ´epoca, fue usar las simulaciones de Monte-Carlo como alternativa a la funci´on de evaluaci´on de posici´on, que pronto dar´ıa lugar a una nueva t´ecnica, el m´etodo Monte-Carlo Tree Search (MCTS) en espa˜nol B´usqueda en ´ Arbol de Monte-Carlo. En 2006 comenzaron a surgir las distintas versiones de este m´etodo, seg´un las estrategias que se usasen en ´el. Hoy en d´ıa el m´etodo MCTS aun sigue siendo tema de investigaci´on interesante. 1Russell and Norvin 1995 2Los problemas de juegos son aquellos en que uno o varios jugadores compiten por lograr un mismo objetivo. 3Es una funci´on que estima con un valor num´erico cada una de las posiciones analizadas en algoritmos de b´usqueda en arboles. [7, 8] 1 2CAP´ ITULO 1. INTRODUCCI ´ ON 1.1. Contexto Este proyecto ha sido desarrollado en el GIGA (Grupo de Inform´atica Gr´afica Avanzada) en la Universidad de Zaragoza, utilizando las instalaciones del Laboratorio del Instituto de Investigaci´on de Ingenier´ıa de Arag´on. El estudio del m´etodo Monte-Carlo Tree Search plateado pretende analizar las posibilidades del mismo, con objeto de analizar su uso en otras de las ramas de trabajo del grupo. El juego del Go se ha visto como un buen instrumento para la ilustraci´on y comprensi´on del m´etodo. Hasta el momento, el grupo no hab´ıa realizado ning´un estudio previo en este campo, por lo que el c´odigo implementado no se apoya en otro anterior. 1.2. Objetivos El objetivo del proyecto es la realizaci´on en lenguaje Java de un jugador virtual que sea capaz de enfrentarse en el juego del Go a un jugador humano, aplicando el m´etodo MCTS. El proyecto consta de cinco grandes tareas que pasamos a detallar a continuaci´on: 1. Estudio del juego del Go y el uso de la Inteligencia Artificial en ´el. 2. Estudio del m´etodo MCTS y sus diversas variantes. 3. Implementaci´on del juego del Go. 4. Implementaci´on del m´etodo MCTS, intentando que dicha implementaci´on sea lo m´as general posible, de cara a poder utilizarse en otros problemas interesantes para los directores de este proyecto. 5. Implementaci´on de un programa que enfrente al usuario y al ordenador en el juego del Go. El ap´endice B de requisitos se explica en m´as detalle los objetivos de las tareas de implementaci´on. 1.3. Estructura del documento El resto del documento se organiza de la siguiente manera: el cap´ıtulo 2 presenta el juego del Go; el cap´ıtulo 3 se explica la implementaci´on realizada de ´este; en el cap´ıtulo 4 se explica el m´etodo MCTS; en el cap´ıtulo 5 la implementaci´on de ´este; en el cap´ıtulo 6 se explica la implementaci´on de la aplicaci´on y el cap´ıtulo 7 muestra las conclusiones obtenidas. Se incluyen como ap´endices: 1. Gesti´on de proyecto: incluye metodolog´ıa del desarrollo, fases realizadas, gesti´on del tiempo y esfuerzos, supervisi´on y herramientas utilizadas. 2. Requisitos: explica los objetivos de una manera m´as detallada. 3. Aplicaciones MCTS: explica algunas de las aplicaciones del m´etodo MCTS y algunos de sus logros en estos campos. 4. Ejemplo de simulaci´on: explica paso a paso como se desarrolla una simulaci´on MCTS 5. Validaci´on: explica como se ha llevado a cabo la validaci´on y pruebas realizadas 6. Manual de usuario: contiene el manual de usuario de la aplicaci´on Cap´ıtulo 2 Juego del Go El Go es el juego de mesa estrat´egico m´as antiguo del mundo1. Millones de personas en Oriente juegan al Go, y en Occidente el n´umero de jugadores sigue creciendo. Podr´ıa decirse que el Go es tan popular en Oriente como el ajedrez en Occidente. El objetivo del juego es simple: controlar territorio y rodear al enemigo. Famoso por la simplicidad de sus reglas y la complejidad estrat´egica que este esconde, el Go, se considera un elemento muy importante en la cultura oriental. Hay mucho escrito sobre la historia del Go, su relaci´on con la ciencia, el arte, la filosof´ıa y la educaci´on. Numerosos estudios demuestran que su aprendizaje y su pr´actica facilitan el desarrollo de la inteligencia, pensamiento l´ogico, creatividad, habilidad para tomar decisiones acertadas, creaci´on de estrategias y muchas otras destrezas. Tanto es as´ı que el Go se ense˜na en West Point, la Academia militar estadounidense, y en universidades japonesas se permite el ingreso sin examen a los jugadores de Go que acrediten un cierto nivel.[12] En Jap´on, China, Corea y Taiw´an algunos de sus jugadores profesionales gozan de un gran prestigio nacional y ganan importantes sumas de dinero. Debido a la gran importancia de las competiciones de este juego, existen empresas dedicadas exclusivamente a retransmitir y analizar los partidos de Go. El Go adem´as tiene su espacio en la cultura y la ciencia. Aparece en publicaciones (novelas, mangas, art´ıculos cient´ıficos y psicol´ogicos...), televisi´on (series como Andromeda o Mentes criminales, el anime Hikaru no Go ...), e incluso cine (The Go Master, Una mente maravillosa, Tron, The Valiant Ones ...) .[10] Figura 2.1: Imagen de la pel´ıcula “Una mente maravillosa” 1Originado en China hace m´as de 2500 a˜nos 3 4CAP´ ITULO 2. JUEGO DEL GO 2.1. Elementos del juego Para poder jugar se necesitan un tablero, las piedras o piezas y dos jugadores. Figura 2.2: Partida de Go 2.1.1. Tablero El Go se juega sobre un tablero cuadrado formado por una cuadricula de l´ıneas horizontales y verticales. El est´andar es 19x19, pero se puede jugar con cualquier otro tama˜no. Los tama˜nos m´as comunes para partidas r´apidas suelen ser 9x9 o 13x13. El tama˜no preferido por los principiantes es 9x9 ya que suele ser m´as estimulante al inicio jugar m´as n´umero de partidas que jugar una partida muy larga. Por simplicidad en los ejemplos se ilustrar´an las reglas con tableros peque˜nos, como puede ser uno de 5x5. Una intersecci´on es un punto donde se cruza una l´ınea horizontal con una l´ınea vertical. En tableros grandes como 19x19 se marcan unos puntos de referencia sobre las intersecciones tal cual se observa en la Figura 2.3. Figura 2.3: Tablero de 19x19 Dos intersecciones se dicen adyacentes si son distintas y est´an conectadas por una l´ınea horizontal o vertical sin ninguna otra intersecci´on entre ellas. La Figura 2.4 muestra a la izquierda dos im´agenes de intersecciones adyacentes y a la derecha una imagen de dos intersecciones no adyacentes. 2.1.2. Piedras Las piedras son las fichas del juego. Cada jugador utiliza las piedras de un color (negro o blanco). Tradicionalmente se juega con 181 piedras negras y 180 piedras, esto es casi siempre m´as que suficiente, pero si llegasen a faltar podr´ıan usarse piedras extra. La forma de las piedras puede apreciarse en la figura 2.5. Las piedras se colocan sobre las intersecciones y una vez colocada una pieza esta no puede moverse. 2.1. ELEMENTOS DEL JUEGO 5 Figura 2.4: Adyacencia de intersecciones. Figura 2.5: Piedras Las piedras verticalmente y horizontalmente adyacentes del mismo color forman un grupo. Para ser adyacentes deben estar conectadas por las l´ıneas de la cuadr´ıcula directamente, sin otras intersecciones intermedias. La figura 2.6 muestra una situaci´on posible del tablero, donde cada n´umero corresponde a un grupo diferente. Aparecen por tanto, cuatro grupos de piedras negras y cuatro grupos de piedras blancas. Figura 2.6: Grupos de piedras. Se llama libertad de una piedra a una intersecci´on libre adyacente a ella. Un grupo tiene las libertades que tengan todas las piedras que lo conforman. La Tabla 2.1 muestra las libertades que tiene cada grupo de piezas para la situaci´on del tablero reflejada en la Figura 2.7. 2.1.3. Jugadores En Go compiten dos jugadores, llamados Negro y Blanco. El Negro usar´a piedras de color negro y comenzar´a la partida. El Blanco usar´a piedras de color blanco y tendr´a una puntuaci´on extra adicional por haber empezado m´as tarde. Esta puntuaci´on extra es pactada antes del comienzo de la partida y tiene un valor decimal que impide el empate. Si los jugadores tienen distinto grado, el jugador m´as d´ebil ser´a el Negro. Este podr´ıa colocar incluso pre-colocar varias piedras a modo de h´andicap antes de que comience el juego para compensar 6CAP´ ITULO 2. JUEGO DEL GO Grupo 1 2 3 4 5 6 7 Libertades c,d,h d,e,f,g,h g,h a,b c d,h f,e Cuadro 2.1: Tabla de libertades para el ejemplo de Figura 2.7 Figura 2.7: Ejemplo de libertades la diferencia de fuerzas. Este h´andicap normalmente suele consistir en comenzar la partida precolocando las piedras sobre los puntos de referencia del tablero mencionados en el apartado anterior. Si los jugadores no se ponen de acuerdo acerca de los colores con que jugar, entonces uno cualquiera coge una o varias piedras del mont´on y el otro jugador tiene que adivinar si el n´umero es “par” o “impar”. Si lo acierta este jugador jugar´a con piedras negras y en caso de fallar jugar´a con piedras blancas. 2.2. Reglas La mec´anica general del juego es la siguiente, la partida comienza con el tablero vac´ıo, primero juegan Negras (jugador con piedras negras) y despu´es se juega alternativamente Blancas y Negras, como se observa en la Figura 2.8. Durante su turno, cada jugador puede colocar una pieza (piedra) o pasar (perder su turno). En competiciones el tiempo por turno esta delimitado y medido con cron´ometro. La partida finaliza cuando los dos jugadores pasan consecutivamente, momento en el que se hace el recuento de puntos para ver quien es el ganador. Figura 2.8: Ejemplo de inicio del juego En cuanto a la colocaci´on de una piedra, las piedras se colocan sobre las intersecciones libres del tablero siempre que no incumplan las reglas de suicidio y Ko, las cuales se explicar´an m´as adelante. Adem´as la colocaci´on de una pieza puede tener como efecto la captura de piedras del jugador contrario tal y como se explica a continuaci´on. 2.2.1. Captura Una piedra o grupo de piedras se captura cuando al colocar una piedra del oponente se pierde la ´ultima libertad que la piedra o grupo pose´ıa, es decir, se queda sin intersecciones adyacentes 2.2. REGLAS 7 libres. La piedra o grupo de piedras capturado se elimina del tablero y se guarda hasta que la partida finalice. Las figuras 2.9 y 2.10 muestran algunos ejemplos de captura. Figura 2.9: Ejemplos de captura La figura 2.9 contiene dos ejemplos en los que se captura una sola piedra blanca al colocar una piedra negra sobre la intersecci´on a. En el ejemplo de la figura 2.10 la piedra colocada, sobre la intersecci´on a, es de color blanco y produce la captura de un grupo formado por cuatro piedras negras. Figura 2.10: Ejemplo de captura 2.2.2. Suicidio No est´a permitido la colocaci´on de una piedra que suponga la eliminaci´on de libertades de una piedra o grupo de piedras del jugador que tenga el turno, ya que estas piedras morir´ıan y supondr´ıa un suicidio. La Figura 2.11 muestra un par de ejemplos de situaciones de suicidio, en los que colocar la piedra sobre la intersecci´on asupondr´ıa una auto-captura (suicidio) y por lo tanto no es una jugada v´alida. La excepci´on, es que en la jugada se capture piedras enemigas, porque quedar´ıan intersecciones adyacentes libres y la piedra colocada seguir´ıa viva. Esto se puede observar en la Figura 2.12; aparentemente al colocar la piedra negra sobre la intersecci´on asupondr´ıa la desaparici´on del grupo de negras, pero como las libertades del grupo de blancas desaparecer´ıan, el jugador Negro es el que captura al grupo de Blancas. 2.2.3. Ko Los jugadores no tienen permitido hacer un movimiento que devuelva al juego a su posici´on inmediatamente anterior, debido a que crear´ıa un ciclo y podr´ıa darse una situaci´on de Ko o infinitud. Una vez realizado un movimiento distinto, el jugador podr´a realizar el movimiento prohibido anteriormente si se diese la situaci´on. 8CAP´ ITULO 2. JUEGO DEL GO Figura 2.11: Ejemplos de suicidio. Figura 2.12: Ejemplo de captura con falso suicidio La Figura 2.13 ilustra este concepto; inicialmente tenemos una situaci´on del tablero donde la ´ultima piedra colocada es blanca distinta a b, seguidamente se coloca una piedra sobre la intersecci´on a. Si el jugador blanco colocase la piedra sobre la intersecci´on b, se volver´ıa a la situaci´on inicial, por lo tanto debe colocar su piedra en otro lugar. Despu´es de que juegue el jugador negro si la intersecci´on best´a libre, el jugador blanco puede colocar su piedra sobre b. Figura 2.13: Idea de Ko 2.3. Recuento de puntos Una vez finalizada la partida (al pasar los dos jugadores consecutivamente), se toma la situaci´on del tablero en ese momento y se procede al recuento de la puntuaci´on. En la situaci´on final, una intersecci´on vac´ıa se dice que pertenece al territorio de un jugador si est´a conectada solo con piedras de ese jugador (negras/blancas) o con intersecciones vac´ıas. Con la excepci´on de que cuando el tablero est´a vac´ıo las intersecciones no pertenecen a ning´un jugador. Cada jugador recibe un punto por intersecci´on vac´ıa dentro de su territorio. Veamos un ejemplo, en la Figura 2.14 se muestra la situaci´on final de una partida sobre tablero 9x9. En ella las intersecciones con letra apertenecen al territorio del jugador negro y las intersecciones con letra bpertenecen al territorio del jugador blanco. La intersecci´on con letra cal estar en contacto con piedras de ambos jugadores no pertenece al territorio de ninguno. La puntuaci´on 2.3. RECUENTO DE PUNTOS 9 de territorios es de 18 para negras y de 14 para blancas. Esta puntuaci´on se utiliza en el c´alculo de la puntuaci´on final. Figura 2.14: Territorios Existen dos modos de recuento: el japon´es y el chino; ambos emplean los territorios y la compensaci´on que posee el blanco2. En el japon´es se incluye las piedras capturadas y en el chino el n´umero de piedras sobre el tablero. El cuadro 2.2 muestra las f´ormulas de recuento de puntos para los jugadores negro y blanco para el sistema japon´es y chino. Negro Blanco Japon´es PtosTerritorioNegro + N º PiedrasBlancasCapturadas PtosTerritorioBlanco + N º PiedrasNegrasCapturadas + Compensaci´on Chino PtosTerritorioNegro + N º PiedrasNegrasEnTablero PtosTerritorioBlanco + N º PiedrasBlancasEnTablero + Compensaci´on Cuadro 2.2: F´ormulas de recuento de puntos Continuando con el ejemplo de la Figura 2.14, se calcula la puntuaci´on final para cada color seg´un los dos modos de recuento. Se sabe que al inicio de partida se pact´o dar 2,5 puntos de compensaci´on al jugador blanco y que durante el transcurso de ella el jugador blanco captur´o 3 piedras negras y el negro 2 piedras blancas. Calculando la puntuaci´on final usando las f´ormulas anteriores, tal y como muestra la Tabla 2.3, el jugador Negro ganar´ıa fuera cual fuera el sistema de puntuaci´on usado para el recuento. Sistema/Jugador Negro Blanco Japon´es 18+2=20 14+3+2,5=19,5 Chino 18+26=44 14+22+2,5=38,5 Cuadro 2.3: Puntuaciones finales 2.3.1. Clasificaci´on de los jugadores En Go, el rango de un jugador indica su habilidad en el juego. Los rangos se miden mediante un sistema de grados de kyu y dan, un sistema que tambi´en ha sido adoptado por diversas artes marciales. 2Compensaci´on por haber empezado m´as tarde, es decimal y se pacta al comienzo de la partida. 16 CAP´ ITULO 3. IMPLEMENTACI ´ ON DEL JUEGO DEL GO Figura 3.5: Un bloque representa un grupo de piedras del tablero Figura 3.6: Estructura de almacenamiento de los grupos de piezas ya que pertenecen al mismo grupo. La interconexi´on entre la matriz de bloques y el vector de bloques es lo que da rapidez al sistema a cambio de necesitar un trabajo de mantenimiento. 3.4.2. Las operaciones Debido a la simplicidad de los m´etodos de la clase bloques (a˜nadir una piedra al bloque, comprobar si una piedra est´a dentro de ´el u obtener la piedra que ocupa la posici´on idel bloque), nos vamos a centrar en las operaciones de la clase ConjBloques. Dentro de la clase ConjBloques vamos a ver las acciones que modifican la informaci´on de los bloques, y por tanto necesitan una gesti´on que mantenga la consistencia de la estructura: Figura 3.7: Crear Bloque Crear bloque: Crea un nuevo bloque con la posici´on dada, lo a˜nade al final del vector de bloques y actualiza la matriz de bloques con el valor correspondiente. La figura 3.7 ilustra 3.4. LOS BLOQUES 17 con un ejemplo de colocaci´on de una piedra blanca sobre la posici´on 0,2 partiendo de la figura anterior. A˜nadir a bloque: A partir de una posici´on y un ´ındice del bloque, busca el bloque con este ´ındice y a˜nade la posici´on dada a ´este, luego actualiza la matriz de bloques con el ´ındice del bloque. La figura 3.8 muestra el efecto de colocar una piedra negra sobre la posici´on 1,3 partiendo de la figura anterior. Figura 3.8: A˜nadir a Bloque Eliminaci´on de bloque: A partir del ´ındice del bloque, se elimina ´este del conjunto de bloques y se actualizan los valores de la matriz de bloques. La actualizaci´on consiste en poner como vac´ıas todas las posiciones que tengan como valor el ´ındice del bloque y decrementar en una unidad todas cuyos ´ındices sean superiores al ´ındice del bloque eliminado. La figura 3.9 muestra el ejemplo de eliminaci´on del bloque 7 partiendo de la figura anterior. Observamos que el bloque 8 al tener un´ındice superior a 7 se decrementa su ´ındice en la matriz de bloques. Figura 3.9: Eliminaci´on de un bloque 18 CAP´ ITULO 3. IMPLEMENTACI ´ ON DEL JUEGO DEL GO Fusi´on de bloques: Fusiona el bloque icon el bloque j, siendo estos distintos. Es decir, copia los elementos del bloque jsobre el bloque i, elimina el bloque jy actualiza los valores de la matriz de bloques. En esta matriz se decrementan en una unidad los valores que sean mayores que j, se actualizan los valores de jai (si i<j) o a i-1 (si i>j). La figura 3.10 muestra el paso de colocar una piedra negra sobre la posici´on 0,2 partiendo de la figura anterior. Esta piedra ser´a el punto de uni´on entre los bloques 0 y 2. Como primer paso, se a˜nade al primer bloque (bloque 0) y como segundo se realiza la fusi´on entre los bloques 0 y 2. Depende como llamemos a la funci´on tenemos los dos casos explicados. En el primero con i= 0 < j = 2, la fusi´on se realiza primero a˜nadiendo los elementos del bloque 2 al bloque 0, segundo eliminando el bloque 2 del vector de bloques y finalmente actualizando los valores de la matriz de bloques de los bloques con ´ındice mayor o igual a dos. Para i= 2 > j = 0, la fusi´on se realiza primero a˜nadiendo los elementos del bloque 0 al bloque 2, segundo eliminando el bloque 0 del vector de bloques y finalmente actualizando los valores de la matriz de bloques de los bloques con ´ındice mayor o igual a cero, es decir, todos los bloques no vac´ıos. Al ser i>jel bloque resultante pasa a tener ´ındice 1 en vez de ´ındice 2. Figura 3.10: Fusi´on de bloques Cap´ıtulo 4 Algoritmo MCTS Monte-Carlo Tree Search (MCTS) es el primer m´etodo de b´usqueda que no requiere una funci´on de evaluaci´on de posici´on[7, 8], en contraste con la b´usqueda αβ[6] . Esta basado en una exploraci´on aleatoria del espacio de b´usqueda, pero usa los resultados de previas exploraciones. Para ello MCTS construye gradualmente un ´arbol en memoria, que mejora sucesivamente estimando los valores de los movimientos m´as prometedores. MCTS es aplicable si al menos se satisfacen estas tres condiciones: 1) La puntuaci´on del juego est´a acotada; 2) Las reglas son conocidas (informaci´on completa[18]) y 3) Las simulaciones terminan relativamente r´apido (la longitud del juego es limitada). Gracias a la estructura de ´arbol y un alto n´umero de simulaciones aleatorias, el m´etodo MCTS puede estimar a largo plazo el potencial de cada movimiento. La t´ecnica MCTS se ha incorporado recientemente en algoritmos para juegos, obteniendo bastantes buenos resultados. Se utiliza en: Problemas de gesti´on, optimizaci´on de rendimiento en bibliotecas, SameGame, Morpion Solitario, Dominio de Navegaci´on, El juego de las amazonas, Lines of Action (LoA), Damas chinas, Colonos del Cat´an, Juegos de prop´osito general, y en particular, el Go. Desde un punto de vista m´as global, el MCTS es tambi´en atractivo para muchos m´as dominios en los que se necesita mejorar el “atasco en la adquisici´on de conocimiento”. Los detalles de las aplicaciones del algoritmo y los logros mejorados se explican con m´as detalle en el ap´endice C. En esta secci´on se presentan la estructura del ´arbol y las cuatro etapas principales del MCTS: selecci´on, expansi´on, simulaci´on y retropropagaci´on. Cada etapa tiene asociada una estrategia, implementada con una pol´ıtica espec´ıfica. El ap´endice D muestra con detalle un ejemplo de simulaci´on para el juego del Go, en el que se puede seguir visualmente cada una de las fases con objeto de facilitar la comprensi´on del mismo. 4.1. Estructura Una partida se representa como un ´arbol, en la que cada nodo corresponde a un estado particular. El nodo ra´ız representa la posici´on de inicio de partida. Los hijos de cada nodo son estados alcanzables en un movimiento. En un ´arbol MCTS cada nodo irepresenta una posici´on alcanzada (tambi´en llamado estado) de una partida. Un nodo contiene al menos las siguientes informaciones:  vies el valor actual de la posici´on, dependiendo el problema representar´a una cosa u otra.  nies el contador de visitas que ha sufrido esa posici´on.  Cies el contenido asociado al problema concreto en el que estemos trabajando, que representa un movimiento realizado desde el estado del nodo padre. Por ejemplo para el juego del Go, cada contenido Cirepresenta una jugada (colocaci´on de piedra en una intersecci´on concreta o pasar), viel n´umero de partidas ganadas desde ese nodo. 19 20 CAP´ ITULO 4. ALGORITMO MCTS Figura 4.1: Estructura MCTS 4.2. El algoritmo MCTS consiste en cuatro pasos principales, repetidos tantas veces como tiempo disponible haya. En una de las iteraciones se parte de la situaci´on inicial de la partida (situaci´on de la partida en el momento de la simulaci´on), pero se conserva el ´arbol MCTS, complet´andose durante las distintas fases y simulaciones. Figura 4.2: Esquema general MCTS Las fases del algoritmo son las siguientes:  Selecci´on: El ´arbol se recorre desde el nodo ra´ız hasta alcanzar un nodo hoja.  Expansi´on: Se a˜naden nodos al ´arbol MCTS seg´un una estrategia de expansi´on.  Simulaci´on: Se realiza una partida simulada partiendo del nodo o estado alcanzado en las fases anteriores. Durante esta partida simulada, el programa juega solo, realizando los movimientos de todos los jugadores que intervienen hasta que la partida finalice y se obtenga un resultado, con el que actualizar´a los valores del nodo.  Retropropagaci´on: El resultado de la simulaci´on se propaga hacia los nodos atravesados previamente. Cuando el tiempo o n´umero de simulaciones haya finalizado, el movimiento elegido en el programa ser´a el m´as prometedor teniendo en cuenta la informaci´on almacenada. El pseudoc´odigo del MCTS se muestra en el Algoritmo 4.1. En ´este, Aes el ´arbol que contiene todos los nodos del ´arbol de b´usqueda. Seleccionar(NodoN) es el procedimiento que devuelve un hijo del nodo N.Expandir(NodoN) es el procedimiento que a˜nade seg´un las estrategia de expansi´on los nodos al ´arbol, devolviendo el nodo desde el que realizar la simulaci´on. JugarP artidaSimulada(NodoN) es el procedimiento que realiza una simulaci´on de la partida desde el nodo devuelto en la expansi´on y devuelve un resultado R.Retropropagaci´on(IntegerR) 4.3. LAS FASES 21 Algoritmo 4.1 Pseudoc´odigo del MCTS Datos: nodoRaiz Resultado: mejorMovimiento MientrasQue (haya_tiempo) hacer nodoActual ←nodoRaiz /* Selecci´on */ MientrasQue (nodoActual ∈A)hacer nodoActual ←Seleccionar(nodoActual) Fin /* Expansi´on del nodo */ nodoActual ←Expandir(nodoActual) /* Simulaci´on de una partida*/ R←JugarP artidaSimulada(nodoActual) /* Retropropagaci´on del resultado */ MientraQue(nodoActual ∈A)hacer Retropropagaci´on(nodoActual, R) nodoActual =nodoActual.padre Fin Fin Devuelve mejorMovimiento =MejorHijo(nodoRaiz) es el procedimiento que actualiza el valor del nodo dependiendo del resultado Rde la ´ultima partida simulada. MejorHijo(NodoN) devuelve el hijo m´as prometedor seg´un los valores de estos. En los siguientes apartados se explica detalladamente cada una de las fases y la selecci´on del movimiento final. 4.3. Las fases Como hemos visto, el m´etodo MCTS repite una serie de pasos o fases hasta llegar a un n´umero de simulaciones o tiempo dado. En este apartado, analizaremos cada una de las fases as´ı como distintas estrategias a seguir en cada una de ellas. La explotaci´on y exploraci´on del espacio de b´usqueda son elementos clave de cualquier m´etodo de b´usqueda y optimizaci´on. Mientras la explotaci´on gu´ıa la b´usqueda hacia las mejores soluciones encontradas hasta el momento, la exploraci´on favorece el descubrimiento de regiones sin explorar y evita una convergencia antes de tiempo. Lograr un balance entre estos dos objetivos es un problema de vital importancia que enfrentan la mayor´ıa de las t´ecnicas de b´usqueda y optimizaci´on actuales. 4.3.1. Selecci´on Figura 4.3: Selecci´on 22 CAP´ ITULO 4. ALGORITMO MCTS En la fase de selecci´on, se avanza desde la ra´ız del ´arbol hasta alcanzar un nodo hoja tal y como muestra la Figura 4.3. Se toma una rama u otra dependiendo de la estrategia de selecci´on que se emplee y la informaci´on almacenada en el nodo en ese momento, como el valor y el n´umero de visitas. A continuaci´on se detallan algunas de estas estrategias: OMC (Objective Monte-Carlo): Donde se calcula la urgencia 1de cada uno de los movimientos (nodos) posibles y se juega un movimiento u otro seg´un los valores de urgencia calculados y el n´umero de visitas realizadas. PBBM (Probability to be Better than Best Move): Similar a la anterior, pero tiene en cuenta la desviaci´on t´ıpica[22] del mejor movimiento a la hora de calcular la urgencia. UCT (Upper Confidence bounds apllied to Trees): Es la estrategia m´as usada y ha dado lugar a diversas variantes. La estrategia UCT calcula para cada uno de los movimientos posibles una combinaci´on de dos valores, la tasa de ´exito de ese nodo y un n´umero asociado a la relaci´on del n´umero de veces que se ha visitado el nodo en relaci´on a un nodo padre. El valor de la tasa de ´exito est´a relacionado con la explotaci´on y el valor del n´umero asociado esta relacionado con la exploraci´on. Dependiendo del coeficiente empleado en la combinaci´on de ambos valores, se puede dar mayor prioridad a la explotaci´on o a la exploraci´on. Todas estas estrategias de selecci´on, son independientes del juego y no usan ning´un dominio del conocimiento. La estrategia UCT es una de las m´as usadas debido a su simplicidad y eficiencia. Por ello, es la que se ha usado en la implementaci´on realizada. 4.3.2. Expansi´on El paso de expansi´on a˜nade nodos al ´arbol MCTS. En la mayor´ıa de los problemas en los que no es posible almacenar en memoria el juego completo es necesario poseer una estrategia de expansi´on. Seg´un cuando se expande podemos encontrar estas dos estrategias: Siempre: Se expande sea cual sea las veces visitadas Al alcanzar un n º de visitas: Se expande solo cuando se alcanza un n´umero m´ınimo MIN de visitas ni. Figura 4.4: Modelo de expansi´on La no expansi´on hasta que no se alcance un n´umero m´ınimo de simulaciones, permite ahorrar espacio en memoria, pudiendo evitar en muchos casos crear ramas innecesarias. El nodo ra´ız se trata como un caso especial, al reflejar la situaci´on de partida no es ´util realizar simulaciones directamente sobre ´el, por lo que siempre se expande. La Figura 4.4 muestra el esquema en donde 1Es un valor proporcional a la probabilidad de que un movimiento sea mejor al actual mejor movimiento[1] 4.3. LAS FASES 23 el nodo hoja Nisolo se expande si el n´umero de visitas nialcanza un m´ınimo MIN. En el caso de expandirse, puede crear un solo hijo o todos ellos tal y como explicamos a continuaci´on. Seg´un el n´umero de hijos a expandir se tienen estas dos estrategias: Crear un solo hijo: Ocupa menos memoria, pero durante cada iteraci´on del proceso de selecci´on se deber´a calcular si hay m´as movimientos posibles que partan de ese nodo y no han sido a˜nadidos, lo que supone una carga de procesado considerable. Crear todos los hijos de golpe: Ocupa m´as espacio en memoria, pero solo se calculan todos los movimientos posibles alcanzables desde el nodo actual una vez. En este caso se debe seleccionar un nodo cualquiera de los creados, desde el cual se realizar´a la simulaci´on. En la implementaci´on realizada se ha decidido expandir todos los nodos de golpe cuando se haya visitado el nodo un n´umero m´ınimo de veces. 4.3.3. Simulaci´on A partir del nodo hoja Nidado por la fase anterior, se realiza una partida simulada. Durante esta partida simulada, el programa juega solo, realizando movimientos de todos los jugadores que intervienen de forma aleatoria hasta que la partida finalice y obtenga un resultado R. Podemos ver este proceso en la Figura 4.5. Figura 4.5: Actualizaci´on de valores Las estrategias que se utilizan consisten o bien utilizar los 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´on, que da la aleatoriedad, y la explotaci´on, que dirige hacia un movimiento m´as prometedor. Debido a que se desea generar un algoritmo MCTS gen´erico independiente del problema, se ha decidido utilizar la estrategia aleatoria. 4.3.4. Retropropagaci´on En el paso de Retropropagaci´on se realiza la actualizaci´on de los valores de los nodos, actualizando primero el nodo hoja, luego el nodo padre de ´este y as´ı consecutivamente hasta alcanzar la ra´ız del ´arbol, tal y como muestra la Figura 4.6. La actualizaci´on de cada nodo, consiste en incrementar en una unidad el n´umero de visitas niy actualizar su valor viusando el resultado R de la simulaci´on. Veamos distintas estrategias existentes de actualizaci´on del valor vide un nodo: Simples: Se actualiza en funci´on ´unicamente del resultado obtenido. Max: Adquiere el valor m´aximo de sus hijos. Media: Adquiere la media de sus valores hijos. 24 CAP´ ITULO 4. ALGORITMO MCTS Figura 4.6: Retropropagaci´on Mezcla: Combina las estrategias de valor m´aximo y media. MCTS-Solver: Considera a un nodo ganador si alguno de sus hijos lo es y perdedor si todos sus hijos lo son. En este proyecto se ha seleccionado el m´etodo “Simple”, dadas las caracter´ısticas del problema seleccionado, el juego del Go. 4.4. Selecci´on del movimiento final Despu´es de las simulaciones, es el momento de elegir el mejor movimiento a realizar, la elecci´on vendr´a dada por el “mejor hijo” de la ra´ız. Hay distintas formas de elegir qu´e hijo es el mejor: 1. Valor m´aximo: Es el hijo que tenga el mayor valor vi. 2. M´as robusto: Es el hijo que tiene un mayor contador de visitas ni. 3. Robusto-Valor m´aximo: Es el hijo que tiene tanto el mayor valor vi, como el n´umero de visitas ni. 4. M´as seguro: Es el hijo que maximiza un l´ımite inferior del intervalo de confianza[23, 1]. Seg´un el problema puede ser m´as conveniente usar un m´etodo u otro. Experimentos aplicados al Go relacionados por expertos con los distintos m´etodos muestran que no hay una diferencia significativa entre ellos si hay un suficiente n´umero de simulaciones por movimiento jugado. Sin embargo, si el tiempo de simulaci´on por movimiento es corto (ej. 1 seg), la elecci´on por Valor m´aximo da unos resultados significativamente peores que el resto de los m´etodos. La selecci´on elegida en este proyecto ha sido la de “M´as robustez”, porque su simplicidad de implementaci´on, menor consumo de tiempo y por presentar mismas prestaciones que otros m´etodos al aplicarse al juego del Go. Cap´ıtulo 5 Implementaci´on del m´etodo MCTS En esta secci´on se explica la soluci´on final desarrollada. Recordemos que uno de los objetivos era que el modulo del m´etodo MCTS a implementar fuese gen´erico, de forma que pudiese aplicarse a distintos problemas, no solo al juego del Go. Si se quiere conocer en m´as detalle como ha sido la evoluci´on seguida en la implementaci´on del m´etodo, en el ap´endice A se describe la metodolog´ıa seguida y los grandes pasos dados antes de llegar a la soluci´on final. 5.1. Las clases La Figura 5.1 muestra el diagrama de clases MCTS del m´etodo MCTS implementado. Veamos m´as a fondo cada una de las clases, sin entrar en detalle en la clase Go ya explicada en la secci´on anterior. 5.1.1. NodoUCT Esta clase representa un nodo del ´arbol MCTS. Con la referencia al nodo padre y a los nodos hijos que el nodo posee se consigue la estructura del ´arbol MCTS necesaria para realizar las simulaciones. Este nodo, es un nodo gen´erico y debe instanciarse en el momento de su creaci´on, tanto el tipo de contenido (asociado a las acciones o movimientos del problema a resolver) como el tipo de valor (que debe ser de tipo num´erico y se usar´a en las distintas fases del m´etodo). La figura 5.2 muestra la representaci´on gr´afica del nodo que implementa la clase. 5.1.2. Contenido La clase Contenido, ilustrada por la figura 5.3, no es m´as que una estructura con la que se instanciar´a al nodo del ´arbol MCTS y que representa una acci´on asociada al juego del Go: Pasar o colocar una pieza en una posici´on concreta. Esta estructura est´a formada por un booleano que indica si la acci´on es pasar (en caso de ser el booleano cierto) o colocar una pieza (en caso de ser booleano falso) y por dos valores enteros (x,y) que indican donde la pieza seria colocada. El tipo valor en el caso del juego del Go representa el n´umero de partidas ganadas (representadas por un entero). Por lo que el nodo se instancia con el tipo entero para el tipoValor y con el tipo Contenido para el tipoContenido. 25 32 CAP´ ITULO 5. IMPLEMENTACI ´ ON DEL M´ ETODO MCTS Cap´ıtulo 6 Aplicaci´on La aplicaci´on del Go implementada permite de una forma visual jugar al juego del Go contra el ordenador, seleccionar las opciones de juego y dispone de informaci´on complementaria de ayuda por si fuera necesaria para el seguimiento del juego o simplemente para recordar las reglas. Este apartado muestra el esquema de clases implementado, la interfaz creada, sus funcionalidades y el valor UCT seleccionado. 6.1. Esquema En cuanto a la implementaci´on, se ha creado una clase para cada una de las ventanas y una especializaci´on de las clases Go y Tablero. La figura 6.1 muestra la relaci´on que existe entre estas clases. Figura 6.1: Diagrama de clases para la Aplicaci´on 6.2. Interfaz La interfaz esta formada por las ventanas de: Inicio, reglas, opciones y juego; adem´as de la clase tablero, que genera el tablero de la ventana de juego. A continuaci´on se explica un poco m´as en detalle cada uno de estos elementos. 6.2.1. Ventana Inicio Corresponde a la clase Go Interfaz Menu, que crea la ventana de inicio o men´u mostrada por la figura F.2. Adem´as asocia los botones a las ventanas correspondientes: El bot´on “Jugar” crea 33 34 CAP´ ITULO 6. APLICACI ´ ON la ventana opciones (objeto de la clase Go Interfaz Opciones), el de “Reglas” la ventana de reglas (objeto de la clase Go Interfaz Reglas) y el bot´on “Salir” cierra las ventanas y finaliza el programa. Figura 6.2: Ventana de Inicio 6.2.2. Ventana de reglas Corresponde a la clase Go Interfaz Reglas, que crea la ventana de ayuda mostrada en la figura 6.3. Esta ventana esta formada por un directorio ´arbol y por un texto. El texto va variando seg´un la parte del ´arbol seleccionada, mostrando informaci´on relacionada con ´el. Figura 6.3: Ventana de Reglas 6.2.3. Ventana de opciones Figura 6.4: Ventana de opciones 6.2. INTERFAZ 35 Corresponde a la clase Go Interfaz Menu, que crea la ventana de selecci´on de opciones mostrada en la figura F.3. Al cliquear el bot´on “Confirmar” se crea una nueva partida de Go (Interfaz) con las opciones seleccionadas. Pulsar el bot´on “Cancelar” cierra la ventana de opciones y el bot´on “Ayuda” abre la ventana de Reglas por la secci´on de ayuda en opciones. El Go (interfaz) creado, adem´as de realizar las tareas del Go correspondientes, crea la clase Tablero en su especializaci´on de interfaz que ser´a usada por la ventana de juego. Adem´as a˜nade una serie de funciones como por ejemplo almacenar el color de piedras de la m´aquina. 6.2.4. Ventana de juego Corresponde a la clase Go Interfaz Juego, que crea la ventana de juego mostrada en la figura F.4. Esta ventana esta formada por tres elementos principales: Botones: Permiten salir de la partida pulsando “Abandonar”, abrir la ventana de reglas pulsando el bot´on “Reglas” o pasar turno pulsando sobre el bot´on “Pasar”. Tablero: El tablero es incorporado por la ventana de juego en la interfaz de la ventana, pero la gesti´on de este y su dibujado se realizan en su propia clase. Otros elementos: Adem´as de esos elementos principales, la ventana dispone de otros elementos que complementan al juego, como son el fondo y la informaci´on de piedras capturadas, el temporizador de cada turno y los mensajes de ayuda. Figura 6.5: Ventana de juego Al finalizar la partida tal y como muestra la figura 6.6 muestra un mensaje con la puntuaci´on final. 36 CAP´ ITULO 6. APLICACI ´ ON Figura 6.6: Ventana emergente mostrando la puntuaci´on final 6.2.5. Tablero La parte relacionada con la interfaz del tablero se lleva a cabo en la clase Tablero interfaz, que es una clase hija de la clase Tablero. Al inicializar el tablero, se crea la parte gr´afica: Se carga el fondo del tablero, las letras y n´umeros de gu´ıa y las l´ıneas (cuadr´ıcula). Las piedras se gestionan usando una matriz de im´agenes. Si la intersecci´on correspondiente a los ´ındices de la matriz est´a libre, la matriz de im´agenes no almacenar´a en ella nada (valor null), en cambio si hay una piedra colocada en esta intersecci´on, se almacena la imagen de esa piedra. Posteriormente se pueden eliminar estas piedras (debido a una captura) marcando las im´agenes como no visible y marc´andolas como libres en la matriz de im´agenes. Adem´as esta clase implementa la acci´on de colocar pieza. Captura los clic producidos sobre el tablero y act´ua en consecuencia: Coloca la pieza si la jugada es v´alida, avisa al usuario si no es posible realizar la jugada o no realiza ninguna acci´on si no es el turno del jugador o se ha cliqueado fuera del rango de las intersecciones1. La figura 6.7 muestra un mensaje emergente en caso de poder realizarse la jugada por ser suicidio o por ser Ko. Figura 6.7: Ventana emergente Movimiento no v´alido 1Se llama rango de intersecci´on al ´area cercana a la intersecci´on, de forma que cliquear dentro de este ´area significa haber cliqueado en la propia intersecci´on. 6.3. VALOR DEL COEFICIENTE UCT 37 6.3. Valor del coeficiente UCT La estrategia UCT selecciona los mejores movimientos encontrados hasta el momento pero tambi´en explora otros movimientos menos prometedores.2 Algoritmo 6.1 F´ormula UCT para el nodo Ni V alorUCT (Ni) = tasaExitoi+C×qln(np) ni Comenzando por la ra´ız, UCT busca un camino de movimientos a trav´es del ´arbol calculando el valor de cada posici´on candidata de acuerdo a la tasa de ´exito (tasaExitoi) , el valor del coeficiente C, el n´umero de visitas del nodo niy el n´umero de visitas del nodo padre np, tal y como muestra la f´ormula 6.1. Si hay hijos de un nodo que no se han visitado ninguna vez (ni= 0), se elige uno de ellos aleatoriamente. Como este m´etodo no asume ning´un conocimiento, lo natural es que se visite cada uno de ellos al menos una vez. Es necesario definir el valor del coeficiente UCT (C) que ser´a usado en la fase de selecci´on del MCTS. Tenemos que determinar un compromiso entre explotaci´on y expansi´on. Si el valor es peque˜no se dar´a m´as importancia a la explotaci´on, en cambio si el valor es grande se da importancia a la exploraci´on. Explotaci´on (Valores comprendidos entre 0 y 1): dan m´as importancia al movimiento m´as prometedor. La importancia dada ser´a mayor cuanto menor sea el valor. Igualdad (Valor 1): da igual importancia a la explotaci´on como a la exploraci´on. Exploraci´on (Valores mayores de 1): da m´as importancia a la exploraci´on. La importancia ser´a mayor cuanto mayor sea el valor. En esta implementaci´on se ha optado por la igualdad (valor 1), ya que explora un n´umero suficiente de veces cada rama, pero una vez dirigido hacia la soluci´on desarrolla solo la rama m´as prometedora, mientras esta de buenos resultados. La figura 6.8 muestra los datos obtenidos en una simulaci´on de Go sobre tablero 3x33. Como se puede observar en la gr´afica el aumentar el valor del factor disminuye el n º de visitas de la rama m´as prometedora, pero aumenta el del resto de ramas, not´andose cada vez m´as cuales son los siguientes movimientos m´as prometedores. Debido a la simetr´ıa del tablero, el movimiento m´as prometedor para tableros 3x3 es tanto el (0,1) ,(1,0) (1,2) como el (2,1). 2Esto lo hace mediante la f´ormula del algoritmo 6.1, es decir sumando un n´umero a la tasa de ´exito de cada movimiento, menor conforme el nodo haya sido m´as veces visitado. Este n´umero tambi´en crece cuando el nodo padre ha sido visitado pero se ha seleccionado otro de los nodos hijos. Esto significa que la tasa de ´exito + el n´umero crecer´a hacia movimientos no explorados de forma que en ciertos momentos la suma del nodo ser´a mayor que la del resto de movimientos que tienen tasas de ´exito superiores. Si el movimiento funciona (es exitoso), se incrementa la tasa de ´exito y podr´a pr´oximamente ser seleccionado de nuevo. Si falla (no es exitoso), la tasa de ´exito decrece junto con el n´umero y el movimiento deber´a esperar un tiempo mayor antes de que sea seleccionado de nuevo. Un movimiento puede tambi´en seleccionarse si el resto de movimientos resultan fallidos y por lo tanto las tasas de ´exito del resto de competidores descienden. 3Con 50000 iteraciones, tablero 3x3, 0.5 de penalizaci´on, n´umero de simulaciones antes de expandir 30 y modo de recuento Japon´es 38 CAP´ ITULO 6. APLICACI ´ ON Figura 6.8: N º de visitas en simulaciones 3x3 para distintos factores Cap´ıtulo 7 Conclusiones 7.1. Marco de trabajo En primer lugar, este proyecto ha implicado tomar contacto con un juego y un m´etodo desconocidos hasta el momento por m´ı. Se ha realizado un trabajo de comprensi´on de la naturaleza e importancia tanto para el juego Go, como para el m´etodo MCTS. Se ha visto que el m´etodo MCTS necesita que la informaci´on sea perfecta y abarca todos los campos donde esta condici´on se cumple: Juegos deterministas o estoc´asticos de uno, dos o tres jugadores. En todos ellos se han obtenido resultados que incluso superan en algunos aspectos a los mejores programas hasta el momento. Su car´acter general, permite adem´as obtener buenos resultados en programas de prop´osito general. En cuanto a la aplicaci´on del m´etodo MCTS al juego del Go (juego determinista de dos jugadores), se sabe que se ha obtenido una gran mejora con respecto a programas que usaban otros m´etodos, pero aun as´ı necesita el apoyo de potentes ordenadores y sigue sin ser capaz de vencer a los humanos m´as expertos. El gran n´umero de casillas y jugadas posibles en cada turno hace que las combinaciones posibles de movimientos sean incre´ıblemente grandes, ofreciendo aun un gran reto para la inform´atica. El motivo de este trabajo ha sido conocer el comportamiento del m´etodo MCTS de cara a utilizarlo en otros problemas interesantes para los directores de este proyecto. 7.2. Resultados obtenidos El objetivo del proyecto era la realizaci´on en lenguaje Java de un jugador virtual que fuera capaz de enfrentarse en el juego del Go a un jugador humano, aplicando el m´etodo MCTS. El proyecto constaba de estas cinco grandes tareas: 1. Estudio del juego del Go y el uso de la Inteligencia Artificial en ´el. 2. Estudio del m´etodo MCTS y sus diversas variantes. 3. Implementaci´on del juego del Go. 4. Implementaci´on del m´etodo MCTS, intentando que dicha implementaci´on sea lo m´as general posible, de cara a poder utilizarse en otros problemas interesantes para los directores de este proyecto. 39 40 CAP´ ITULO 7. CONCLUSIONES 5. Implementaci´on de un programa visual que enfrente al usuario y al ordenador en el juego del Go. Todas estas tareas se han realizado satisfactoriamente, cumpli´endose adem´as los objetivos detallados de las tareas de implementaci´on recogidos en el ap´endice B. 7.3. Diagrama de tiempos El diagrama de la figura 7.1 muestra los tiempos dedicados en las principales fases del proyecto. Este diagrama junto con todo lo relacionado en la gesti´on del proyecto (metodolog´ıa, fases, gesti´on de tiempo y esfuerzos, supervisi´on del proyecto y herramientas utilizadas) aparece explicado en el ap´endice A. Figura 7.1: Diagrama de tiempos 7.4. L´ıneas de trabajo futuro En la creaci´on del m´odulo MCTS se eligieron unas estrategias concretas para cada una de las fases. Por lo que una l´ınea futura podr´ıa ser la modificaci´on de este m´odulo eligiendo unas estrategias distintas. A partir del m´odulo MCTS implementado podr´ıa tambi´en implementarse una versi´on no gen´erica de ´el, donde se usasen simulaciones pseudoaleatorias (en vez de aleatorias) de acuerdo con el problema a tratar, que condujesen de una forma m´as r´apida a la soluci´on. Adem´as resultar´ıa muy interesante la paralelizaci´on del m´etodo. En cuanto al juego Go implementado, una de las l´ıneas futuras ser´ıa poder permitir un h´andicap, para compensar la diferencia de niveles antes de comenzar una partida. En cuanto a la aplicaci´on que enfrenta en el juego del Go al usuario con un jugador virtual (ordenador) una l´ınea futura ser´ıa crear un servidor que enfrentase tanto a jugadores humanos como jugadores virtuales. Como trabajo futuro, se contempla el poder aplicar el m´etodo a cualquiera de sus diversos campos. Concretamente dentro del GIGA (Grupo de Inform´atica Gr´afica Avanzada) en los campos de trabajo con los que se trabaja, como pueden ser el de los videojuegos o el c´alculo de la iluminaci´on de una escena. 7.5. PROBLEMAS ENCONTRADOS 41 7.5. Problemas encontrados Aqu´ı se enumeran los principales problemas encontrados: Comprensi´on del m´etodo MCTS: La compresi´on del m´etodo result´o bastante costosa, pr´acticamente un mes. La documentaci´on encontrada sobre el tema explicaba el m´etodo de forma general, pero carec´ıa de ejemplos concretos que facilitasen su comprensi´on. El encontrar un pseudo-c´odigo en internet[19] supuso un avance importante, ya que se aplicaba a un ejemplo concreto. Las ideas presentadas por este pseudo-c´odigo se emplearon en la implementaci´on de la primera versi´on. La ejecuci´on de esta versi´on sirvi´o para ver paso a paso como se pasaba por las distintas fases del m´etodo, alcanzando con ello su total comprensi´on. Despu´es de ello ya se pudo comenzar a estudiar a fondo cada una de las fases viendo cual era m´as conveniente para la soluci´on buscada en este PFC. Estrategias a usar en el m´etodo MCTS implementado: El decantarse por una estrategia u otra en cada una de las fases fue tambi´en una labor no siempre f´acil. Generalizaci´on del m´odulo MCTS: Uno de los objetivos del proyecto era que el m´odulo MCTS implementado fuese lo m´as gen´erico posible. Este hecho supuso entrar en profundidad en cada una de las fases y ver como se pod´ıa hacer lo m´as gen´ericas posible. Se vio que la estructura hasta entonces utilizada depend´ıa mucho del problema aplicado (juego del Go) por lo que fue necesario enfocar de forma diferente tanto la estructura como las fases del m´etodo. Recuento de puntuaci´on en el juego del Go: En la mayor´ıa de documentaci´on encontrada, se define el sistema de recuento del Go como el explicado en el cap´ıtulo 2. Sin embargo, en internet se encontraban im´agenes sobre el recuento de puntuaciones que no siempre coincid´ıa con esta definici´on. Este hecho resulto bastante desconcertante, y hubo que intentar averiguar cual era el sistema correcto de recuento. Finalmente se descubri´o[16] que una variaci´on de la versi´on japonesa del juego bastante extendida, es que para contar los territorios se tiene en cuenta el concepto de “Vida y muerte”[17]1. Esto hace que al finalizar la partida algunas piedras sean “retiradas” debido a que ser´ıan matadas en un futuro y se tienen en cuenta a la hora del recuento de la misma forma que las piedras capturadas. El problema es que con este m´etodo hay situaciones en las que no se sabe si los territorios pertenecen a un jugador u otro. En el sistema Chino, se da por hecho que los jugadores pasan porque no tienen m´as movimientos posibles, o estos provocar´ıan una misma puntuaci´on tras el recuento. De forma que si los jugadores pasan teniendo m´as movimientos posibles significa que asumen la puntuaci´on del tablero seg´un las reglas explicadas en el cap´ıtulo 2. Se decidi´o dejar el sistema de recuento explicado en el cap´ıtulo 2, debido a la complejidad que supone en la implementaci´on de la variante japonesa aqu´ı explicada y un aparentemente incumplimiento de dos de las condiciones para que se aplicase el m´etodo MCTS2. El lenguaje Java: Al iniciar este proyecto solo se conoc´ıan los aspectos m´as b´asicos del lenguaje, por lo que en ocasiones resulto algo m´as costoso de lo normal descubrir como implementar ciertas cuestiones. Concretamente no se conoc´ıa nada de la parte gr´afica ni de los threads. Pero gracias a la librer´ıa gr´afica Java Swing[27] fue mucho m´as sencillo desarrollar sobre todo la labor est´etica. 1Se define un grupo de piedras como ”vivo”, si tiene posibilidad de permanecer en el tablero, o ”muerto”, si el grupo ser´a ”capturado”. La idea b´asica puede expresarse sencillamente as´ı: Un grupo debe tener dos ojos (libertades internas seguras) para vivir. 2No hay conocimiento completo (las reglas de recuento no son claras) y las simulaciones no terminar´ıan r´apido. 48 AP´ ENDICE A. GESTI ´ ON DEL PROYECTO Ap´endice B Requisitos Tres de los objetivos del proyecto consist´ıan en la implementaci´on de distintos elementos: El juego del Go, el m´etodo MCTS y una aplicaci´on que enfrentase el usuario al ordenador en el juego del Go. Para cada uno de estos objetivos se marcaron una serie de requisitos a cumplir. Los requisitos son de dos tipos: 1) Funcionales: Que definen el comportamiento interno del software: c´alculos, detalles t´ecnicos, manipulaci´on de datos y otras funcionalidades espec´ıficas y 2) No funcionales: Que especifican criterios que pueden usarse para juzgar la operaci´on de un sistema. Los requisitos marcados en el proyecto se recogen en los cuadros: B.1 para el juego del Go, B.2 para el m´etodo MCTS y B.3 para la aplicaci´on. C´odigo Descripci´on RF-0 Se debe permitir elegir entre modo de recuento chino o japon´es. RF-1 Se debe poder elegir entre tableros de distinta dimensi´on. RF-2 Se podr´a seleccionar el valor de compensaci´on. RF-3 Una vez comenzada la partida no podr´an ser modificadas las opciones anteriores RF-4 Permitir´a al usuario, “colocar pieza” o “pasar” RF-5 Se deber´an respetar las reglas del juego (captura, suicidio,Ko...) RF-6 Se podr´a volver a comenzar una partida en cualquier momento del juego. RF-7 Al comenzar una nueva partida se guardan las opciones definidas anteriormente. RNF-0 Deber´a funcionar en tiempo real RNF-1 Debe ser implementado en lenguaje Java Cuadro B.1: Requisitos del Go En los cuadros aparecen numerados cada uno de los requisitos, se nombran con RF a los requisitos funcionales y con RNF a los requisitos no funcionales. Por ejemplo en el cuadro B.1 aparecen 8 requisitos funcionales y 2 requisitos no funcionales. 49 50 AP´ ENDICE B. REQUISITOS C´odigo Descripci´on RF-0 Deber´a poder adaptarse al problema, en lo que se refiere a contenido y valor. RF-1 Debe permitir realizar sucesivas simulaciones hasta un n´umero tope o un tiempo l´ımite dado. RF-2 Debe permitir avanzar por las ramas del ´arbol seg´un contenidos (movimientos) dados. RF-3 Debe permitir reutilizar el ´arbol en simulaciones y b´usquedas posteriores. RF-4 Antes de comenzar la simulaci´on se tienen que poder modificar los valores de todas las constantes usadas en el m´etodo. RF-5 Debe ser gen´erico y poderse usar en distintos problemas (incluido el Go) como particularizaci´on del m´odulo gen´erico. Cuadro B.2: Requisitos del m´odulo MCTS En el cuadro B.2 los seis requisitos son funcionales y en B.3 aparecen seis requisitos funcionales y uno no funcional. C´odigo Descripci´on RF-0 El sistema debe poseer una interfaz que permita al usuario jugar interactivamente al juego del Go contra un jugador virtual. RF-1 Antes de comenzar el juego se deber´a poder seleccionar las opciones del Go adem´as de tiempo l´ımite por turno, color de piezas en el juego y nombre del usuario. RF-2 El jugador virtual usar´a el m´etodo Monte-Carlo Tree Search (MCTS) para seleccionar la jugada a realizar. RF-3 Al finalizar la partida se mostrar´a el resultado seg´un el modo de recuento anteriormente seleccionado. RF-4 La ventana de juego deber´a mostrar al menos: un tablero, las piezas colocadas, n´umero de piezas capturadas y el tiempo que le queda a cada jugador. RF-5 Las ventanas dispondr´an de elementos de ayuda como ventanas o textos indicativos. RNF-0 La interfaz deber permitir al usuario jugar de una forma agradable y sencilla. Cuadro B.3: Requisitos de la aplicaci´on Ap´endice C Aplicaciones MCTS El m´etodo implementado en este PFC se ha aplicado solo al juego del Go. Este ap´endice muestra de forma resumida distintas aplicaciones realizadas por expertos en distintos dominios, si desea profundizar en cualquiera de ellos use las referencias bibliogr´aficas, est´an enlazadas a los art´ıculos correspondientes. Los dominios que trataremos ser´an exclusivamente los que tengan informaci´on perfecta. Veremos a continuaci´on que el m´etodo MCTS ha conducido a los mejores programas en varios de los dominios y adem´as es muy atractivo para muchos otros. MCTS parece permitir superar el problema de adquisici´on de conocimiento permitiendo hacer de una forma m´as sencilla esta adquisici´on en muchos campos. C.1. Deterministas C.1.1. Deterministas de un jugador El m´etodo MCTS se ha aplicado a problemas de gesti´on y producci´on (Production Management Problems) obteniendo resultados bastante aceptables[29]. Otra aplicaci´on fue el juego SameGame, con el que se gan´o el record mundial de este juego usando variantes del MCTS[30]. Adem´as estos m´etodos superaban tambi´en las mejores puntuaciones humanas para el Morpion Solitario[31]. Figura C.1: SameGame y Morpion Solitario Considerando los problemas de optimizaci´on como juegos de un jugador, se han usado variantes MCTS en la optimizaci´on de librer´ıas para diferentes plataformas (Library Performance Turing). 51 52 AP´ ENDICE C. APLICACIONES MCTS C.1.2. Deterministas de dos jugadores Para juegos deterministas de dos jugadores como el ajedrez y las damas, el uso de αβ con una funci´on de evaluaci´on fuerte fue la base para la construcci´on de un fuerte jugador de Inteligencia Artificial. Sin embargo, donde el MCTS ha tenido m´as ´exito es en el campo del Go, cuyos programas ganan los torneos de las olimpiadas de computaci´on desde 2006. Adem´as del Go, MCTS se usa tambi´en para otros juegos deterministas de dos jugadores, como Amazons (Juego de las amazonas)[33] oLinesOfAction(LOA)[34], en el primero ganaron las olimpiadas de 2008 y 2009 y en el segundo se ha conseguido el mismo nivel que el mejor juego del mundo. Figura C.2: Amazons y LinesOfAction C.1.3. Deterministas multijugadores En 2008 Sturtevant aplic´o MCTS en juegos multijugador como Las Damas Chinas,Spades and Hearts (Picas y corazones). En las damas chinas demostr´o que MCTS era capaz de superar los m´etodos de b´usqueda estandard maxnyparanoid equipados con una fuerte funci´on de evaluaci´on. Para las versiones de Spades and Hearts, MCTS se posicion´o al mismo nivel que el estado del arte. Figura C.3: Damas chinas y Spades and Hearts C.2. Estoc´asticos C.2.1. Estoc´asticos de un jugador Las primeras aplicaciones de MCTS para juegos estoc´asticos de un jugador fueron en el dominio de navegaci´on[35]. El dominio de navegaci´on es un problema estoc´astico que busca el menor camino entre dos puntos bajo condiciones de viento variable. Este problema fue tratado usando el m´etodo UCT con C.2. ESTOC ´ ASTICOS 53 el que se consigui´o que se necesitasen significativamente menos simulaciones para alcanzar el mismo rendimiento que los programas existentes hasta entonces. C.2.2. Estoc´asticos de dos jugadores Uno de estos juegos es el Backgammon[36], en el que un programa con selecci´on UCT y simulaciones completamente aleatorias fue capaz de encontrar la mejor forma de comenzar el juego en un tercio del tiempo que otros programas, pero sin embargo, era significativamente m´as d´ebil que los programas del estado del arte. Figura C.4: Backgammon C.2.3. Estoc´asticos de varios jugadores La popularidad de los juegos modernos de estrategia de tablero est´a increment´andose desde que nacieron el la d´ecada de los 90. Los juegos de estrategia de tablero, son de especial inter´es para los investigadores de la inteligencia artificial, ya que suponen un puente entre los juegos cl´asicos de tablero (deterministas de dos jugadores) y los videojuegos. Se aplic´o el MCTS al juego multijugador Colonos del Cat´an[37], aumentando el algoritmo con un conocimiento limitado del juego. En los experimentos, en los que las reglas fueron cambiadas para conseguir una estoc´astica perfecta informaci´on del juego, se obtuvo que el programa era capaz de derrotar convincentemente al mejor programa de c´odigo abierto de Inteligencia Artificial disponible, y que es un razonable fuerte jugador para los humanos. Figura C.5: Colonos del Cat´an 54 AP´ ENDICE C. APLICACIONES MCTS C.3. Juegos de prop´osito general El prop´osito de los juegos de prop´osito general es crear agentes inteligentes que autom´aticamente aprendan como jugar a diferentes juegos a un nivel experto sin intervenciones de los humanos. El m´as exitoso agente en el pasado hab´ıa usado la tradicional b´usqueda en ´arboles de juego combinada con funciones heur´ısticas de aprendizaje autom´atico para evaluar los estados de juego. Sin embargo desde 2007, los programas MCTS han ganado los torneos de juegos de prop´osito general usando UCT, con un algoritmo de aprendizaje online para las simulaciones[38]. Ap´endice D Ejemplo de simulaci´on Para comprender mejor el m´etodo MCTS, en este ap´endice se explica un ejemplo de simulaci´on para el juego del Go de tama˜no 3x3, que expande sus nodos cuando se han visitado dos veces. Primero se explica la estructura del nodo, luego se explica en detalle las veinte iteraciones realizadas y finalmente se explica algunas ideas, por si estas no quedasen claras o no se visualizasen durante el ejemplo. Decir que durante las simulaciones, se trabaja sobre una copia del Go, realizando acciones sobre esta copia sin tocar la partida de Go en la que se juega con el adversario. En cada iteraci´on, primero se vuelve a copiar sobre la copia el estado del Go proporcionado al inicio de la simulaci´on MCTS, y se trabajar´a sobre esta copia realizando sobre ella los movimientos seg´un la selecci´on que realcemos y los movimientos aleatorios de la simulaci´on aleatoria. Durante este ejemplo al hablar de partida del Go, se referir´a a la copia del Go sobre la que se trabaja. Como se observar´a m´as adelante el ´arbol se mantiene, actualiz´andose tras las distintas iteraciones. D.1. La estructura del nodo Figura D.1: Nodo MCTS del Go El nodo MCTS consta de dos partes: Datos para el algoritmo MCTS y Contenido. Tal y como muestra la figura D.1, para el caso del Go, como datos para el algoritmo MCTS tenemos el n´umero de partidas ganadas (de las simuladas a partir de ese nodo u hijos) y n´umero de simulaciones realizadas (desde ´el o sus hijos). En cuanto a la informaci´on correspondiente al juego, es decir al contenido, en el Go corresponde con las acciones de colocar pieza y pasar; que se representa mediante un booleano que indica si la acci´on consiste en pasar o no y las coordenadas x,y que indican la posici´on donde se ha colocado la pieza, usando como punto de referencia es la esquina superior izquierda del tablero. Durante el resto de la explicaci´on usaremos la versi´on abreviada del 55 56 AP´ ENDICE D. EJEMPLO DE SIMULACI ´ ON nodo, mostrada en la figura D.2. Donde el nodo ser´a de un color u otro dependiendo del turno del jugador que realiza la acci´on (negro/blanco). Figura D.2: Simplificaci´on del nodo MCTS Go Un caso especial es la representaci´on del nodo ra´ız aunque no se haya realizado ninguna acci´on (colocaci´on de pieza o pasar), es decir, al inicio de la partida. En el Go se ha representado con el siguiente contenido: Pasar=false, x=-1, y-1. En las figuras del ejemplo, se indica que un nodo es ra´ız del ´arbol cuando est´e se˜nalado por una flecha naranja. La figura D.3 muestra la ra´ız del ´arbol para tablero vac´ıo. Figura D.3: Ra´ız para comienzo de la partida Adem´as durante el ejemplo se acompa˜na la representaci´on del ´arbol en las figuras con un dibujo que se indica la situaci´on del tablero y el turno, en el Go usado para la simulaci´on. En la figura D.4 muestra la situaci´on del tablero y turno al comienzo de una partida. Figura D.4: Situaci´on tablero y turno D.2. Forma del ´arbol En el juego del Go, se alterna turno de negras y de blancas. Como el ´arbol representa las jugadas realizadas por estos (salvo el nodo ra´ız), el ´arbol por lo tanto tambi´en alterna color: primer nivel jugador negro, segundo jugador blanco, tercero negro... En la figura D.5 se puede ver ´esta idea. D.3. Iteraciones D.3.1. Primera iteraci´on Comenzamos con la primera iteraci´on. Partimos de la situaci´on de inicio de partida del Go (tablero vac´ıo y turno para el jugador negro, tal y como indica la figura D.4), en la que el ´arbol D.3. ITERACIONES 57 Figura D.5: Forma del ´arbol Figura D.6: Ra´ız para comienzo de la partida solo posee un nodo ra´ız, tal y como muestra la figura D.3. 1. Selecci´on: Como el nodo ra´ız no tiene hijos, no se selecciona ninguno de ellos y no se avanza. La situaci´on de la partida y del ´arbol permanecen iguales. 2. Expansi´on: La ra´ız siempre se expande, por lo tanto se crean todos sus hijos. Y sobre los hijos creados, se selecciona uno cualquiera. En la simulaci´on realizada, el nodo seleccionado ha sido el de colocar una pieza en la posici´on 1,0 , cuya acci´on ser´a aplicada a la partida del Go de la simulaci´on. La Figura D.7 ilustra la creaci´on de los hijos (cada hijo corresponde a una jugada posible que puede realizar el jugador negro, el cual pose´ıa el turno, representados con un negro gris´aceo) y la selecci´on del nodo 1,0 (representado por un negro puro) realizando la colocaci´on de la piedra negra sobre la intersecci´on 1,0 del tablero y pasando el turno al jugador blanco. Figura D.7: Efectos de la fase de expansi´on 3. Simulaci´on: La simulaci´on parte del nodo anteriormente seleccionado, es decir, de la situaci´on del tablero obtenida despu´es de la fase de expansi´on. A partir de esta se van realizando acciones v´alidas aleatoriamente (colocar pieza/pasar) sobre la partida de Go hasta que finalice 64 AP´ ENDICE D. EJEMPLO DE SIMULACI ´ ON Figura D.24: Iteraci´on 15: Retropropagaci´on Figura D.25: Iteraci´on 16: Situacion de partida 2. Expansi´on: El nodo seleccionado se ha visitado dos veces (ni= 2) alcanzando as´ı el n´umero de visitas m´ınimo para expandirse (ni= 2) y expandi´endose. Al expandirse crea tantos hijos como situaciones alcanzables desde el nodo inicializando los valores niyvide sus nodos a cero. En la partida del Go el turno es del jugador blanco, por lo que estos nodos representan jugadas del jugador blanco. De todos los nodos creados se selecciona uno al azar, en este caso se ha seleccionado el 0,0 tal y como muestra la figura D.27. Se realizan las acciones acordes con esta selecci´on, es decir colocar una piedra blanca sobre la posici´on 0,0 y el turno pasa al jugador negro. 3. Simulaci´on: En este paso se realiza una simulaci´on aleatoria partiendo de situaci´on actual de la partida (tablero vac´ıo con piedra negra sobre intersecci´on 0,1 , blanca sobre 0,0 y turno de blancas) de la misma forma que en las iteraciones anteriores. En este caso blancas gana. 4. Retropropagaci´on: El resultado obtenido (blancas gana) se propaga desde la hoja a la ra´ız actualizando los nodos, tal y como ilustra la figura D.28. D.3.9. Iteraciones de la de la decimos´eptima a la vig´esima En la iteraci´on decimos´eptima se ha seleccionado el nodo 0,2 , que se expande, eligiendo el nodo pasar y perdiendo la simulaci´on. En la decimoctava, se selecciona en nodo 1,1 que se expande, eligiendo el nodo 1,0 y perdiendo la simulaci´on. En la decimonovena se selecciona el nodo 0,1, el D.3. ITERACIONES 65 Figura D.26: Iteraci´on 16: Selecci´on Figura D.27: Iteraci´on 16: Expansi´on cual no se expande y pierde la simulaci´on. En la vig´esima iteraci´on se selecciona el nodo 1,2, el cual no se expande y pierde la simulaci´on. D.3.10. Futuras iteraciones El ejemplo se ha realizado solo para veinte simulaciones, debido a que solo pretende ilustrar el m´etodo. Sin embargo hay algunos conceptos que este no se reflejan en el ejemplo y que explicamos a continuaci´on. Selecci´on: En el paso de selecci´on se avanza desde la ra´ız hasta las hojas, decidiendo en cada uno de ellos que hijo seleccionar. El camino tomado puede conducir a que se atraviesen varios niveles, tal y como muestra la figura D.29. Expansi´on: Conforme nos vamos acercando al final de la partida, el n´umero de jugadas posibles suele ser menor. Puede llegar el caso en que no se pueda realizar ninguna jugada, por lo tanto el nodo al expandirse no cree ning´un hijo. En el juego del Go indica que la partida ha finalizado (se ha pasado dos veces consecutivas). Simulaci´on aleatoria: Las simulaciones aleatorias mostradas en el ejemplo eran relativamente 66 AP´ ENDICE D. EJEMPLO DE SIMULACI ´ ON Figura D.28: Iteraci´on 16: Retropropagaci´on Figura D.29: Selecci´on en el Go cortas. El n´umero de movimientos realizado antes de acabar la partida puede ser muy peque˜no o muy grande, dependiendo de la situaci´on de partida y hacia donde se dirija ´esta con los movimientos realizados. Retropropagaci´on: En la retropropagaci´on se recorren tantos nodos como nivel tenga la hoja. Esto quiere decir que se actualizan m´as nodos o menos dependiendo el nivel al que se encuentre la hoja. D.4. Elecci´on del mejor nodo En el ejemplo realizado, tras realizar las veinte iteraciones del m´etodo se ha obtenido el ´arbol representado en la figura D.30. Como solo se necesita observar los nodos del primer nivel, el resto se representan en la figura con un tama˜no menor. Para la elecci´on del mejor nodo, se observan los valores de los nodos alcanzables desde la ra´ız, D.5. N ´ UMERO DE SIMULACIONES 67 tanto el contador de visitas nicomo el n´umero de partidas ganadas vi. El m´etodo implementado para seleccionar el mejor nodo ha sido el de “M´as robustez” que elige el nodo que tiene un mayor n´umero de visitas ni1. En este caso corresponden a los nodos: 0,1 , 0,2 , 1,0 y 1,1. El nodo 0,1 al tener un valor vimenor se descarta. Elegir uno de los otros tres, dados los resultados conocidos, resulta indiferente, se elegir´ıa por ejemplo el primero, en este caso el 0,2. Figura D.30: ´ Arbol generado tras la simulaci´on de veinte iteraciones D.5. N´umero de simulaciones En el ejemplo ilustrado se han realizado 20 iteraciones del m´etodo, un n´umero realmente peque˜no. Es necesario usar un n´umero significativo de iteraciones (dependiendo del problema podr´a convenir uno u otro), es dif´ıcil saber el n´umero apropiado por ello es muy ´util limitar este con el tiempo2. 1En caso de que varios tengan el mismo nodo coger´a el que mayor valor tenga. Si adem´as hay varios con el mismo valor elegir´a uno cualquiera de ellos. 2Hacer todas las iteraciones que se pueda en un tiempo dado. 68 AP´ ENDICE D. EJEMPLO DE SIMULACI ´ ON Ap´endice E Validaci´on E.1. Go Para validar el juego del Go, lo que se ha hecho ha sido forzar distintas situaciones y comprobado que los resultados sean correctos. Al ser progresiva la implementaci´on se ha ido probando poco a poco las funcionalidades a˜nadidas en cada caso. Para la comprobaci´on se ha visualizado por pantalla el contenido de la matriz tablero, matriz de bloques y conjunto de bloques seg´un conviniese. Figura E.1: C´odigo que prueba los bloques 69 70 AP´ ENDICE E. VALIDACI ´ ON E.1.1. Reglas y bloques Debido a que para crear ciertas situaciones se necesita colocar un gran numero de piezas y ver el proceso de cada una resultar´ıa costoso. Se fueron realizando pruebas de forma incremental a˜nadiendo cada vez algunas l´ıneas de c´odigo para forzar situaciones a partir de ejemplos anteriores. El ejemplo que se muestra a continuaci´on ilustra el funcionamiento de bloques, las reglas de captura, suicidio y la del Ko. El c´odigo de la prueba correspondiente aparece en la figura E.1. Para seguir el desarrollo del ejemplo se muestra paso a paso, la traza obtenida por pantalla junto con una ilustraci´on que muestra el tablero y los grupos de piedras. Adem´as se acompa˜na de explicaciones para la total comprensi´on de la prueba. Durante las explicaciones se emplea tanto la palabra bloque como la palabra grupo, para hablar de los grupos de piedras conectados debido a su adyacencia, explicado en la parte te´orica del juego. En las figuras siguientes se agrupan los tableros de cuatro en cuatro y de dos en dos, igual que las salidas para hacer que ocupen menos espacio y sea m´as sencilla su lectura. Figura E.2: Jugadas (1-3) La figura E.2 muestra la situaci´on del tablero y los grupos para las primeras jugadas. En la figura E.3 se ven las trazas obtenidas para cada una de las situaciones anteriores. Como vemos se parte de tablero vac´ıo, en el que no hay ning´un grupo. A continuaci´on se coloca una piedra negra creando el primer grupo formado por una ´unica pieza. Luego el blanco coloca su piedra, creando un nuevo grupo (con ´ındice 1) y le sigue el negro colocando una piedra adyacente a la blanca, pero al ser de distinto color forma un grupo nuevo. E.1. GO 71 Figura E.3: Trazas jugadas (1-3) Figura E.4: Jugadas (4-7) La figura E.4 muestra la situaci´on del tablero y los grupos para las jugadas siguientes. En la figura E.5 se ven las trazas obtenidas para cada una de las situaciones anteriores. Como vemos en la jugada 6, la pieza blanca colocada se une al bloque ya existente. 72 AP´ ENDICE E. VALIDACI ´ ON Figura E.5: Trazas jugadas (4-7) Figura E.6: Jugadas (8-11) La figura E.6 muestra la situaci´on del tablero y los grupos para las jugadas siguientes. En la E.1. GO 73 figura E.7 se ven las trazas obtenidas para cada una de las situaciones anteriores. Como vemos la jugada 8, no es v´alida ya que supone la eliminaci´on de libertades y por lo tanto suicidio. La traza indica tambi´en que la acci´on no es v´alida y no realiza cambio en el tablero ni los grupos. En la jugada 10, con la colocaci´on de la piedra negra se realiza una fusi´on entre dos grupos de color negro, actualizando los valores de los ´ındices de los grupos seg´un corresponda. Algo similar ocurre en la jugada 11, la colocaci´on de la piedra blanca genera tambi´en una fusi´on y actualizaci´on de los ´ındices de los grupos. Figura E.7: Trazas jugadas (8-11) La figura E.8 muestra la situaci´on del tablero y los grupos para las jugadas siguientes. En la figura E.9 se ven las trazas obtenidas para cada una de las situaciones anteriores. 80 AP´ ENDICE E. VALIDACI ´ ON Figura E.21: Trazas jugadas (23-24) Figura E.22: Jugadas (25-26) La figura E.22 muestra la situaci´on del tablero y los grupos para las jugadas siguientes. En la figura E.23 se ven las trazas obtenidas para cada una de las situaciones anteriores. Como vemos en la imagen al colocar la piedra blanca en la jugada 25 se captura una piedra negra. En la jugada 26, el jugador negro quiere colocar una pieza para matar a la piedra blanca, pero esta jugada no es posible, debido a que el tablero volver´ıa a la situaci´on anterior (jugada 24) infringiendo la regla de Ko. E.1. GO 81 Figura E.23: Trazas jugadas (25-26) Figura E.24: Jugadas (27-28) La figura E.24 muestra la situaci´on del tablero y los grupos para las jugadas siguientes. En la figura E.25 se ven las trazas obtenidas para cada una de las situaciones anteriores. Como vemos en la jugada 27 coloca pieza el jugador negro ya que la jugada anterior no era v´alida. 82 AP´ ENDICE E. VALIDACI ´ ON Figura E.25: Trazas jugadas (27-28) Figura E.26: Jugada (29) La figura E.26 muestra la situaci´on del tablero y los grupos para las jugadas siguientes. En la figura E.27 se ven las trazas obtenidas para cada una de las situaciones anteriores. Ahora si que puede colocar el jugador negro la pieza en esta posici´on, sin incumplir la regla del Ko, ya que la situaci´on del tablero no corresponde a la de la jugada anterior (jugada 27). E.1. GO 83 Figura E.27: Trazas jugada (29) E.1.2. Recuento de puntuaciones Comprobemos ahora que el recuento de puntos es correcto. Para el recuento se usa un sistema de bloques pero en vez de bloques de piedras se crean bloques de casillas libres. Si ese conjunto de casillas libres est´a rodeado por piezas de un solo jugador ese bloque pertenecer´a a ese jugador. Comenzaremos viendo la salida de bloques y puntuaci´on para el ejemplo anterior. Figura E.28: Territorios del recuento de puntuaciones Tal y como mesta la figura E.28 y la figura E.29, hay 8 bloques de vac´ıas. Algunos de ellos no pertenecen a ning´un jugador y otros al jugador negro. En este ejemplo el jugador blanco no consigue ning´un territorio. En el dibujo del tablero las intersecciones marcadas con a, indican que pertenecen a territorios del jugador negro y las marcadas con ca ninguno de los dos jugadores. Observemos que como durante la partida se hab´ıan capturado diversas piezas estas se tienen en cuenta para el c´alculo de la puntuaci´on final. Veamos ahora otro ejemplo. La situaci´on final del tablero viene representada por la figura E.30, en ella las intersecciones marcadas por apertenecen al territorio del jugador negro, las intersecciones marcadas por bal territorio del jugador blanco y las intersecciones marcadas por ca ninguno de 84 AP´ ENDICE E. VALIDACI ´ ON Figura E.29: Recuento de puntuaciones para el ejemplo anterior los dos jugadores. El c´odigo se ha elaborado de forma que no se produce ninguna captura, adem´as lo omitimos debido a su gran extensi´on y carencia de inter´es. Figura E.30: Situaci´on de prueba puntuaci´on En la figura E.31 podemos ver la traza que se muestra por pantalla en lo que respecta al c´alculo de territorios. Podemos ver los bloques de conjuntos vac´ıos creados y su asignaci´on a los jugadores. E.1. GO 85 Figura E.31: Bloques prueba territorios En la figura E.32 vemos las puntuaciones obtenidas tanto para modo de recuento japon´es (arriba) como chino (abajo). Figura E.32: Puntuaci´on prueba territorios 86 AP´ ENDICE E. VALIDACI ´ ON E.2. MCTS Como sistema de validaci´on, por un lado se ha realizado un n´umero determinado de simulaciones y comprobado que en cada uno de los pasos se realizan las acciones pertinentes. La clase dispone de un booleano que si es activado muestra poco a poco cada uno de los pasos de la simulaci´on realizada. Activado este flag, los resultados se muestran poco a poco, avanzando conforme se pulse la tecla enter, haciendo as´ı m´as f´acil seguir la simulaci´on. El Ap´endice D contiene un ejemplo de salida de simulaci´on que se apoya en distintas im´agenes para hacer m´as sencillo el seguimiento de este y su comprensi´on. Por otro lado, se ha forzado a que se diesen distintas situaciones “especiales” y visto si los resultados obtenidos son los adecuados. Estas situaciones corresponden a probar la parte de reutilizaci´on del ´arbol para diversas simulaciones y permitir realizar la simulaci´on desde distintos puntos, es decir, todo lo relacionado con el apartado 5.2 de la memoria. Como el tama˜no del tablero no interviene en estas pruebas, hemos tomado un tablero 2x2 debido a que a tama˜no menor es mucho m´as sencillo seguir el ejemplo, e incluso podemos representar el ´arbol de forma gr´afica. El nodo se extender´a cuando se hayan visitado al menos dos veces. E.2.1. Eficiencia del m´etodo La eficiencia del m´etodo MCTS no ha podido ser testada, ya que no se dispone de jugadores profesionales a quien enfrentarse, ni de ordenadores tan potentes como los usados en las competiciones reales, pero si que se ha visto que posee cierta inteligencia seg´un las jugadas realizadas, sobre todo en tama˜nos de tablero peque˜nos o con tiempos grandes de procesado. En las pruebas realizadas a los usuarios, recogidas en la secci´on E.3.2 de este mismo cap´ıtulo, se realizan varias preguntas asociadas a la inteligencia proporcionada por el m´etodo al juego. Se observa que todos los usuarios consideran al jugador virtual como “inteligente”. E.2.2. Avanzar cu´ando el ´arbol es vac´ıo Partiendo de tablero vac´ıo, veamos el efecto que produce las operaciones primero de avance y luego b´usqueda en el ´arbol. La figura E.33 muestra el ejemplo gr´afico de lo que sucede y la figura E.34 muestra la traza obtenida. Como vemos en la traza se mantiene lo que la figura representa. Figura E.33: Avance y b´usqueda a partir de ´arbol vac´ıo E.2. MCTS 87 Figura E.34: Traza del ejemplo (Avance y b´usqueda a partir de ´arbol vac´ıo) E.2.3. Avanzar cu´ando el ´arbol es no vac´ıo En este ejemplo, primero se ha realizado una b´usqueda para que el ´arbol se cree y luego se ha avanzado sobre ´el. Finalmente se ha realizado otra b´usqueda (despu´es de avanzar) para verificar que todo ha funcionado correctamente. La figura E.35 muestra el ejemplo gr´afico de lo que sucede y la figuraE.36 muestra la traza obtenida. Como vemos en la traza se mantiene lo que la figura representa. Como el n´umero de simulaciones realizadas no es muy alto, no todos los nodos llegan a expandirse, si el nodo con el que se avanzas fuera uno que no lleg´o ha expandirse, funciona completamente igual, este nodo pasa a ser ra´ız y al no tener hijos pues el ´arbol tendr´a solo un nodo hasta que se llame a la funci´on de simulaci´on. Figura E.35: Avance y b´usqueda a partir de ´arbol vac´ıo 88 AP´ ENDICE E. VALIDACI ´ ON Figura E.36: Traza del ejemplo (Avance y b´usqueda a partir de ´arbol vac´ıo) E.2.4. Mezcla de las anteriores: Avanzar sobre ´arbol vac´ıo y no vac´ıo. Partiendo de tablero vac´ıo, veamos el efecto que produce las operaciones primero de avance, luego b´usqueda en el ´arbol, luego de nuevo b´usqueda, avance y b´usqueda otra vez. La figura E.37 muestra el ejemplo gr´afico de lo que sucede (obviando la ´ultima b´usqueda) y la figuraE.38 muestra la traza obtenida. Figura E.37: Avance y b´usqueda a partir de ´arbol vac´ıo E.3. APLICACI ´ ON 89 Figura E.38: Traza del ejemplo (Avance y b´usqueda a partir de ´arbol vac´ıo) E.3. Aplicaci´on Las pruebas de la aplicaci´on pueden dividirse en dos grandes bloques: pruebas de funcionamiento y pruebas de usabilidad. Veamos cada una de ellas. E.3.1. Pruebas de funcionamiento En estas pruebas se ha probado que la aplicaci´on realiza las acciones que le fueron encomendadas. A continuaci´on detallamos las principales pruebas realizadas. Navegaci´on entre ventanas: Se comprob´o que cada ventana se abre una ventana cuando se tiene que abrir o se cierra cuando se tiene que cerrar. Opciones seleccionadas: Las opciones de la partida de Go que se juega en la ventana de juego deben corresponder a las opciones seleccionadas en la ventana anterior (ventana de opciones). Para ello se han seleccionado las opciones y comprobado que efectivamente corresponden. En la ventana de juego viendo la interfaz se comprob´o que el nombre del jugador, tama˜no del tablero, color de piedras del jugador y tiempo l´ımite coincid´ıa con el seleccionado. Y al finalizar la partida en la ventana emergente, que el tipo de recuento y la penalizaci´on correspond´ıan con los seleccionados en la ventana de opciones. Esta prueba fue llevada a cabo en varias ocasiones probando a seleccionar opciones distintas a las anteriores y cambiando solo algunas de ellas. 96 AP´ ENDICE F. MANUAL DE USUARIO Glosario PFC: Proyecto fin de carreara GIGA: Grupo de Inform´atica Gr´afica Avanzada Negras / Negro: Jugador con piedras negras Blancas / Blanco: Jugador con piedras blancas kyu: grado de Go correspondiente a estudiante, abreviado k dan: grado de Go correspondiente a experto, abreviado d MCTS: M´etodo de Monte-Carlo Tree Search (B´usqueda en ´arboles de Monte-Carlo) UCT: Upper Confidence bounds applied to Trees RF: Requisito funcional RNF: Requisito no funcional 97 98 AP´ ENDICE F. MANUAL DE USUARIO Bibliograf´ıa [1] G.M.J-B.Chaslot. Monte-Carlo Tree Search, 2010. http://www.unimaas.nl/games/files/phd/Chaslot thesis.pdf [2] Teor´ıa de juegos http://es.wikipedia.org/wiki/Teor%C3%ADa de juegos [3] Algoritmos de juegos http://www.gran-angular.net/wpcontent/uploads/2008/07/algoritmos-de-juegos.pdf [4] Sistema determinista http://es.wikipedia.org/wiki/Sistema determinista [5] Sistema estoc´astico http://es.wikipedia.org/wiki/Estoc%C3%A1stico [6] Poda αβ http://es.wikipedia.org/wiki/Poda alfa-beta [7] Funci´on de evaluaci´on http://www.fenach.cl/docs/memoria/node47.html [8] Funci´on de evaluaci´on. Wikipedia. http://es.wikipedia.org/wiki/Funci%C3%B3n de evaluaci%C3%B3n [9] Go. Wikipedia espa˜nola. http://es.wikipedia.org/wiki/Go [10] Go - Game. Wikipedia inglesa. http://en.wikipedia.org/wiki/Go %28game%29 [11] Computer Go. Wikipedia inglesa. http://en.wikipedia.org/wiki/Computer Go [12] Por qu´e aprender a jugar al go por Franklin Bassarsky http://www.go.org.ar/page.php?name=porque [13] Camino interactivo hacia el Go http://www.thinkchile.com/playgo/ [14] KGS Go http://www.gokgs.com/tutorial/index.jsp [15] Asociaci´on del Go de Andaluc´ıa http://www.andaluciago.org/index.php?page=main [16] Go rules. Wikipedia inglesa. http://en.wikipedia.org/wiki/Rules of Go#End 2 [17] Go vida y muerte http://es.wikipedia.org/wiki/Vida y muerte %28go%29 [18] Informaci´on completa http://es.wikipedia.org/wiki/Informaci%C3%B3n completa [19] Sensei’s Library, Web colaborativa sobre el juego del Go. http://senseis.xmp.net/ [20] Yenny Noa Vargas, Estrategias para mejorar el Balance entre Exploraci´on y Explotaci´on en Optimizaci´on de Enjambre de Part´ıculas http://www.yorku.ca/sychen/research/theses/2011 Yenny MSc.pdf [21] Random Search Algorithms http://www.wpi.edu/Pubs/E-project/Available/E- project-041808-104235/unrestricted/Random Search Algorithms Final Presentation.pdf 99 100 BIBLIOGRAF´ IA [22] Desviaci´on est´andar. Desviaci´on t´ıpica. http://es.wikipedia.org/wiki/Desviaci%C3%B3n est%C3%A1ndar [23] Intervalo de confianza http://en.wikipedia.org/wiki/Confidence interval [24] G.M.J-B. Chaslot, S. Bakkes, I. Szita, and P. Spronck. Monte-Carlo Tree Search: A New Framework for Game AI. In Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference. AAAI Press, Menlo Park, CA, 2008. http://sander.landofsand.com/publications/Monte-Carlo Tree Search - A New Framework for Game AI.pdf [25] The Monte-Carlo Revolution in Go, JFFoS’2008: Japanese-French Frontiers of Science Symposium. http://remi.coulom.free.fr/JFFoS/JFFoS.pdf [26] The Java Tutorials http://docs.oracle.com/javase/tutorial/java/ [27] Lesson: Using Swing Components http://docs.oracle.com/javase/tutorial/uiswing/components/index.html [28] G.M.J.B. Chaslot, M.H.M. Winands, and H.J. van den Herik. Parallel montecarlo tree search. Proceedings of the Conference on Computers and Games 2008 (CG 2008), volume 5131 of Lecture Notes in Computer Science, pages 60-71. Springer, Berlin Heidelberg, 2008. http://www.personeel.unimaas.nl/mwinands/documents/multithreadedMCTS2.pdf [29] G.M.J-B. Chaslot, S. de Jong, J-T. Saito, and J.W.H.M. Uiterwijk. Monte-Carlo Tree Search in Production Management Problems. In Proceedings of the 18th Be- NeLux Conference on Artificial Intelligence, Namur, Belgium, pages 91-98, 2006. http://www.personeel.unimaas.nl/G-chaslot/papers/pmp.pdf [30] Maarten P.D. Schadd, Mark H.M. Winands, H. Jaap van den Herik, Guillaume M.J- B. Chaslot, and Jos W.H.M. Uiterwijk. Single-Player Monte-Carlo Tree Search, 2008. http://www.informatik.uni-freiburg.de/∼ki/teaching/ws0910/gamesem/schadd-et- al-2008.pdf [31] Christopher D.Rosin. Nested Rollout Policy Adaptation for Monte Carlo Tree Search, 2011. http://www.chrisrosin.com/rosin-ijcai11.pdf [32] Arpad Rimmel. Thesis : Improvements and Evaluation of the Monte-Carlo Tree Search Algorithm, 2009. http://www.lri.fr/∼rimmel/Files/ArpadRimmelThese.pdf [33] Julien Kloetzer, Hiroyuki Iida, and Bruno Bouzy. The Monte-Carlo Approach in Amazons, 2007. http://web.mi.parisdescartes.fr/∼bouzy/publications/KIB- MCAmazons-CGW07.pdf [34] Mark H.M. Winands, Yngvi Bj¨ ornsson, and Jahn-Takeshi Sai- to. Monte-Carlo Tree Search in Lines of Action, 2010. http://www.ru.is/faculty/yngvi/pdf/WinandsB10a.pdf [35] Levente Kocsis and Csaba Szepesv´ari. Bandit based Monte-Carlo Planning https://web.engr.oregonstate.edu/∼afern/classes/cs533/notes/uct.pdfhttps://web.engr.oregonstate.edu/∼afern/classes/cs533/notes/uct.pdf [36] Fran  cois Van Lishout, Guillaume Chaslot, and Jos W.H.M. Uiterwijk. Monte-Carlo Tree Search in Backgammon http://orbi.ulg.ac.be/bitstream/2268/28469/1/vanlishout backgammon.pdf [37] I. Szita; G.M.J-B. Chaslot, P. Spronck. Monte-Carlo Tree Search in Settlers of Catan. In Proceedings of the Twelfth International Advances in Computer Games Conference (ACG’09), Pamplona, Spain, May 11-13, 2009. In Press. http://www.personeel.unimaas.nl/g-chaslot/papers/ACGSzitaChaslotSpronck.pdf BIBLIOGRAF´ IA 101 [38] Hilmar Finnsson, Yngvi Bj¨ ornsson. CadiaPlayer: Search-Control Techniques http://posgrado.escom.ipn.mx/biblioteca/CadiaPlayer%20Search- Control%20Techniques.pdf