Jugadores automáticos basados en árboles de búsqueda de Monte Carlo

Jugadores automáticos basados en árboles de búsqueda de Monte Carlo Trabajo de Fin de Grado Curso 2017–2018 Autor Gabriel David Modia Pozuelo Directores Gonzalo Méndez Pozo Antonio Sánchez Ruiz-Granados Doble grado en Ingeniería Informática y Matemáticas Facultad de Informática y Facultad de Matemáticas Universidad Complutense de Madrid Jugadores automáticos basados en árboles de búsqueda de Monte Carlo Trabajo de Fin de Doble Grado Ingeniería Informática y Matemáticas Departamento de Inteligencia Artificial Autor Gabriel David Modia Pozuelo Directores Gonzalo Méndez Pozo Antonio Sánchez Ruiz-Granados Convocatoria: Septiembre 2018 Doble grado en Ingeniería Informática y Matemáticas Facultad de Informática y Facultad de Matemáticas Universidad Complutense de Madrid 14 de septiembre de 2018 Dedicatoria A Mima y Manolo. v Agradecimientos Este trabajo no habría sido posible sin: Mis tutores Antonio y Gonzalo que me han guiado y dirigido, gracias por su disposición y atención. Mi madre, mi hermano y mi padre que, cada uno a su manera, han hecho un camino más fácil para mi. Alba, que incluso en la más adversa de las situaciones ha estado a mi lado. Alicia, que tanto en clase como en casa siempre nos hemos apoyado. Jose Antonio, Miguel, Marta y todos mis compañeros con los que he compartido innumerables horas de estudio, trabajo y dedicación. A todos ellos, gracias. vii Resumen Dada la enorme cantidad de juegos existentes, una pregunta recurrente ha sido ¿Cuál es la mejor estrategia a seguir para maximizar mi beneficio? en otras palabras, ¿Qué acciones debo elegir entre las posibilidades que tengo para obtener la mayor recompensa posible? Esta cuestión, al darle una perspectiva formal resulta no ser trivial, cada configuración del tablero tiene una probabilidad asociada de ganar, definida por todos los posibles desenlaces que tiene el juego desde esa posición. Sin embargo, obtener este valor es imposible computacionalmente ya que esto implicaría revisar todas las posibles partidas dado que el número de estas es descomunal. Para dar solución a esto, existen diversos algoritmos que intentan aproximar este valor, normalmente mezclando el conocimiento previo del dominio con la búsqueda exhaustiva en el conjunto de todas las partidas, para comprobar si una acción mejora nuestra situación actual. En este trabajo se presenta Monte Carlo Tree Search, un algoritmo que introduce una forma completamente distinta de estimar la probabilidad de ganar de cada estado de la partida. El método será generar simulaciones de partidas en las que las decisiones se toman de forma aleatoria. De esta forma, podremos calcular el porcentaje de veces que una simulación resulta victoriosa en comparación con las veces que se ha simulado, dándonos así una aproximación del valor buscado. Veremos que cuantas más simulaciones lancemos, el resultado será más ajustado a la realidad. Conoceremos 2 versiones, la versión dinámica o MCTS, y la versión plana o PMCTS. Introduciremos métodos de optimización y una perspectiva teórica del funcionamiento. Probaremos este algoritmo en juegos, y para ello obtendremos diversas implementaciones de las 2 versiones y las adaptaremos para jugar al Reversi y al Ajedrez. Los adversarios a batir serán algoritmos varios que irán aumentando gradualmente su dificultad y nos obligarán a ir adaptando los algoritmos y mejorándolos para que sean capaces de dominar. Por último introduciremos algunos algoritmos utilizados en el campo de la Inteligencia Artificial conocido como aprendizaje automático o Machine Learning, para que el lector posea las herramientas necesarias para entender el funcionamiento del jugador automático más potente que existe en la ix Índice de figuras 2.1. Ejemplo de árbol de decisión para un estado dado en el juego deltresenraya.......................... 14 2.2. Simplificación de la búsqueda de caminos en GPS . . . . . . . 17 2.3. Obtención inicial de un árbol de juego . . . . . . . . . . . . . 18 2.4. Ejecución de la inducción hacia atrás en Minimax . . . . . . . 19 2.5. Comienzo del juego en el Reversi . . . . . . . . . . . . . . . . 21 2.6. Visualización de las casillas más y menos provechosas . . . . . 23 2.7. Piezas del ajedrez y colocación inicial . . . . . . . . . . . . . . 24 3.1. Ejemplo de selección utilizando UCB . . . . . . . . . . . . . . 28 3.2. Ejemplo de selección utilizando UCT . . . . . . . . . . . . . . 30 3.3. Resultado de una iteración de MCTS . . . . . . . . . . . . . . 32 4.1. Resultados de usar o no conocimiento del dominio con 750 simulaciones............................ 52 4.2. Comparación de partidas ganadas y perdidas en los diferentes enfrentamientos.......................... 53 4.3. Visualización de los resultados de los experimentos . . . . . . 54 5.1. Regresión (Izquierda) y clasificación (derecha) . . . . . . . . . 62 5.2. Dirección del gradiente y problemas de elegir erróneamente el parámetro α............................ 64 xvii Índice de tablas 2.1. Modelo de disposición de la forma normal para dos jugadores 12 2.2. Dilema del prisionero plasmado en forma normal . . . . . . . 13 4.1. PMCTS y MCTS (70 simulaciones) vs Random . . . . . . . . 41 4.2. PMCTS y MCTS (140 simulaciones) vs Random . . . . . . . 42 4.3. PMCTS y MCTS (70 simulaciones) vs búsqueda en profundidad 44 4.4. PMCTS y MCTS (700 simulaciones) vs búsqueda en profundidad................................ 45 4.5. PMCTS y MCTS(140 simulaciones) vs Alpha-beta (débil) . . 46 4.6. PMCTS y MCTS(140 simulaciones) vs Alpha-beta (fuerte) . . 48 4.7. PMCTS (mejorado y con 140 simulaciones) vs Alpha-beta (fuerte) .............................. 49 4.8. PMCTS (750 simulaciones) vs Alpha-beta (fuerte) . . . . . . 50 4.9. MCTS (70 simulaciones) vs PMCTS (70 simulaciones) . . . . 51 4.10. Random (Blancas) vs MCTS (Negras) . . . . . . . . . . . . . 56 4.11. Random (Blancas) vs PMCTS (Negras) . . . . . . . . . . . . 57 4.12. MCTS(Blancas) vs PMCTS (Negras) . . . . . . . . . . . . . . 58 xix Chapter 1 Introduction Motivation One of the current challenges in Artificial Intelligence is the development of algorithms to implement efficient automatic players. These must give a answer, not only correct but also as wise as possible with the finality of winning the game they were designed for. This development is not trivial at all. The creation of these players, as the optimization for them to be better every time, reports benefits further than the world of video games or table games. After all, the idea is to optimize the decision making processes. Given this, there are applications of these algorithms in economics, politics, etc. The main problem is to decide which of the available moves must be chosen next. For that the most direct approach is to explore the game tree and try to find the best option. This point of view is offered by some algorithms whose most remarkable representative is Minimax. However, although this is an optimal algorithm, it presents a problem: the gigantic combinatorial explosion that it generates. Even though it offers good results for simple challenges, as soon as we try it in more complex systems, it is impossible to treat. There are several alternatives to solve this issue. Throughout this work, we will explore one of them: Monte Carlo Tree Search, commonly shortened as MCTS. This algorithm’s idea is, instead of generating each and every possible branch in the game tree, to use stochastic processes to choose which node to expand, moreover, the way they are expanded will also have a very strong presence of random elements. This way we get to spend much less memory than with the traditional approaches. Furthermore, the development of the tree will use simulations to generate a heuristic value for each 1 2Chapter 1. Introduction node, characterizing them according to if they are more or less promising, optimizing the move election process. Objectives We are going to define some objectives in order to explore the MCTS algorithm: 1. Obtaining a global vision of the predecessors of MCTS, as well as the tools we will use. 2. Give a formal explanation of the functioning of MCTS as well as for it’s plain version known as PMCTS. 3. Obtain an implementation of MCTS for the game known as Othello, compare ir with other algorithms and check how it’s behavior improves depending on the parameter chosen. 4. Implementing an MCTS based player which is capable of playing chess and check the differences with it’s othello version. 5. Reviewing the most modern approaches using MCTS and the necessary tools for it. In the conclusions section, we will review how far we accomplished them. Memory structure We will encompass the marked objectives throughout the memory. The first chapter will give a theoretical review of the algorithms that preceded MCTS as Minimax or Alpha-beta. In addition, it will provide a clear explanation of all the tools and situations that we will use in other chapters as game theory, game tree development, Chess, Othello, etc. The second chapter will show the Mote Carlo Tree Search algorithm, the way it works and it’s implementation. On the other hand, we will also see a detailed explanation of PMCTS, the MCTS’ version without growth. Finally, we will analyze the possibility of reusing memory and how we can approximate the theoretical heuristic of each node through simulations. In the third chapter we will obtain an implementation of MCTS and PMCTS. We will it’s performance with the some others algorithms as Random, Alpha-beta and Backtracking in Othello and later in Chess. We will show and analyze the results obtained. Next we will modify the parameters so it gets better results against their adversaries. 1.3. Memory structure 3 Finally the fourth chapter will explain us how we can use machine learning to improve the results that MCTS offers, for that we will first review some of the cutting edge machine learning algorithms. Additionally we will see how this has been applied to one of the most popular artificial intelligence events of the last years: AlphaGo. Capítulo 1 Introducción Motivación Uno de los desafíos actuales de la Inteligencia Artificial es el desarrollo de algoritmos para implementar jugadores automáticos eficientes. Estos deben dar una respuesta no solo correcta sino lo más acertada posible con el fin de ganar en el juego para el que se haya desarrollado. Este desarrollo no es en absoluto trivial. La creación de estos jugadores así como la optimización para que sean cada vez mejores, reporta beneficios más allá del mundo de los videojuegos o los juegos de tablero. Al fin y al cabo, se trata de optimizar la toma de decisiones, dado esto, existen aplicaciones de estos algoritmos para temas como economía, política, etc (Brams, 2001). El problema principal es decidir cuál de las jugadas disponibles se debe elegir a continuación. Para ello, lo más directo es intentar prever las jugadas a las que podemos llegar desde la posición en la que nos encontramos. La estructura donde se almacenan las jugadas predichas es conocida como el árbol de juego. Esta es la aproximación que ofrecen algunos algoritmos de los cuales el mayor exponente es conocido como Minimax, el cual exploraremos en más detalle en el siguiente capítulo. El problema de esta aproximación es que es imposible revisar todo el árbol para saber con certeza lo bueno que es un nodo. Por tanto, para juegos complicados, se ha intentado paliar esta situación previendo únicamente un número determinado de jugadas, pero esto implica que debemos ser capaces de valorar si son buenos o malos estados intermedios, de los que a priori no tenemos información. Una forma de evaluarlo es obtener conocimiento experto del dominio, es decir, ideas o estrategias que se hayan probado y que sepamos con certeza que funcionan. Aunque puede sonar como una buena idea, el conocimiento experto es muy difícil de conseguir, además, práctica5 12 Capítulo 2. Trabajo relacionado 1/2 a21 a22 . . . a11 u1((a11, a21)), u2((a11, a21)) u1((a11, a22)), u2((a11, a22)) . . . a12 u1((a12, a21)), u2((a12, a21)) u1((a12, a22)), u2((a12, a22)) . . . a13 u1((a13, a21)), u2((a13, a21)) u1((a13, a22)), u2((a13, a22)) . . . . . .. . .. . .... Tabla 2.1: Modelo de disposición de la forma normal para dos jugadores conocemos como funciones de utilidad que nos devuelven los pagos a cierto jugador ipor el vector de acciones elegido por todos los jugadores. (Jackson, 2011). Con estos ingredientes, la forma normal nos representa una matriz donde los elementos de la misma son los pagos que reciben los jugadores en dependencia de la combinación de estrategias elegidas por cada uno. Esta representación funciona especialmente bien cuando se trata de dos jugadores, ya que se puede disponer en una matriz bidimensional. La tabla 2.1 nos da un ejemplo de cómo se disponen los datos en forma normal. Ejemplo: El dilema del prisionero Probablemente el ejemplo más conocido de juego simultáneo es el dilema del prisionero. La situación es la siguiente: "La policía sabe que dos individuos han cometido un crimen aunque no puede probarlo, pero sí que tiene pruebas para incriminarlos por un delito menor. Ante la alarma social levantada, se ven obligados a tener un culpable rápido, por lo que ponen a ambos sospechosos en celdas separadas y les hacen la siguiente propuesta: Si delatas al otro como autor del crimen te perdonamos tu delito menor"(Aguado, 2015). En este supuesto nos encontramos ante dos acciones posibles, a las que llamaremos “Callar” y “Delatar”. Suponiendo una condena de 1 año por el delito menor, 3 en caso de cumplir la sentencia por el mayor individualmente y 2 por hacerlo de forma conjunta nuestro juego queda de la siguiente forma: (N, a, u)=({1,2},{Callar, Delatar}, u) u1((Callar, Delatar)) = u2((Delatar, Callar)) = 3 u1((Delatar, Callar)) = u2((Callar, Delatar)) = 0 u1((Callar, Callar)) = u2((Callar, Callar)) = 1 u1((Delatar, Delatar)) = u2((Delatar, Delatar)) = 2 Podemos representar el problema de forma extensiva como se muestra en la tabla 2.2. 2.2. Teoría de juegos 13 Prisionero 1 \Prisionero 2 Callar Delatar Callar 1,1 3,0 Delatar 0,3 2,2 Tabla 2.2: Dilema del prisionero plasmado en forma normal Juegos secuenciales A diferencia de los juegos simultáneos, en los secuenciales, los diversos agentes se alternan a la hora de tomar decisiones, se conoce cada una de estas alternancias como turno. Después del turno de cada jugador encontramos el juego en una nueva configuración, debido a las decisiones tomadas. A estas las llamaremos estados. Por tanto, podemos definir los juegos secuenciales como una 4-tupla: (N, S, a, u) Donde una vez más N={1, ..., n}es el conjunto de jugadores. Por su parte Ses el espacio de estado. En lo que concierten a las acciones, a:N×S→A es una función que nos devuelve las acciones disponibles para un jugador en cierto estado, por tanto A={{ai}i=1...k1,{ai}i=1...k2...}, es importante destacar que una acción en este caso es una función ai∈acc ∈A ai:S→S. Por último, u:N×S→Res una función que nos devuelve los pagos para un jugador en cierto estado. Para exponer la evolución temporal inherente a la secuencialidad de los juegos no podemos valernos de la forma normal, por eso vamos a utilizar la estructura de árbol para crear lo que llamaremos forma extensiva. Utilizaremos los nodos para guardar los estados del juego y los hijos de cada nodo serán el resultado de la aplicación de cierta acción a dicho estado. A este tipo de árbol lo llamaremos árbol de juego. Árboles de juego y ejemplos El caso más sencillo de árbol de juego aparece cuando abarcamos juegos con N={1}. En este caso todas las decisiones recaen sobre el mismo agente. Esto facilita la exploración del árbol, pues nos basta con indagar lo suficiente hasta llegar a un nodo terminal ganador. Después basta con ejecutar las acciones definidas por el camino que lleva al nodo en cuestión. Ejemplos de estos juegos pueden ser el solitario o el blackjack. La exploración de los árboles de juego se complica al agregar más jugadores, pues los demás agentes tendrán, en principio, tanto poder de decisión como el primero. Los nodos en el mismo nivel en estos árboles comparten el jugador al que le toca realizar una acción y la elección del jugador asignado a cada nivel dependerá de cómo esté definida la variación de turnos. 14 Capítulo 2. Trabajo relacionado Figura 2.1: Ejemplo de árbol de decisión para un estado dado en el juego del tres en raya La figura 2.1 muestra un ejemplo visual del árbol de juego para el tres en raya partiendo de un estado dado. La representación completa del árbol es excesivamente grande para aparecer en un folio. En este tipo de árboles no nos basta con una exploración básica del árbol para conseguir una buena estrategia a seguir, pues aunque encontremos un camino que nos lleve a una situación de victoria, no nos corresponde decidir la totalidad del camino por lo que sería inservible. Para obtener soluciones en esta parte se han desarrollado otros algoritmos, de los cuales el más conocido es Minimax, que veremos en la siguiente sección. Búsqueda en árboles e inducción hacia atrás Explorar árboles para obtener cómo llegar a ciertos nodos, es un problema clásico en el campo de la inteligencia artificial, al que hay que dar solución en muchos sistemas inteligentes actuales. En esta sección exploramos soluciones clásicas y su aplicación en la teoría de juegos. De ahí, pasamos al algoritmo Minimax que nos mostrará cómo explorar un árbol de juego con múltiples agentes y veremos algunas optimizaciones. Algoritmos tradicionales Explorar un árbol desde la raíz hasta algún nodo que nos interese, es un problema que se presenta frecuentemente, y que podemos encontrar en infinidad de situaciones distintas. En el caso que nos atañe son la herramienta 2.3. Búsqueda en árboles e inducción hacia atrás 15 perfecta para dar una solución a los juegos individuales. A pesar de haber numerosas formas de realizar la exploración, vamos a hablar de los métodos más conocidos: la búsqueda primero en profundidad, la búsqueda primero en anchura y la búsqueda A*. Esta última nos servirá también para introducir el concepto de heurística que nos será muy útil más adelante. Primero en profundidad El algoritmo de búsqueda primero en profundidad (conocido como DFS por Depth First Search en inglés), explorará de forma recursiva el árbol, descendiendo por el primer nodo que encuentre hasta llegar a un nodo hoja. Una vez llegados a este punto, en caso de no ser el nodo que buscamos, volvemos al nodo predecesor y elegimos la siguiente opción disponible. Podemos ver el algoritmo en pseudocódigo a continuación: DFS(nodo n) SI n = objetivo DEVOLVER n SINO PARA CADA hijo EN n.hijos DFS(hijo) Del mismo modo, existe una versión para la exploración de otras estructuras de datos diferentes a los árboles, que implementa un control de repeticiones, pero no indagaremos en ella (Rusell y Norvig, 2003). Primero en Anchura El algoritmo de búsqueda primero en anchura (o BFS por Breadth First Search en inglés), propone explorar primero todas los nodos que están al mismo nivel y después pasar al siguiente. Para la implementación de este algoritmo vamos a utilizar una cola. Vemos el pseudocódigo: BFS(nodo raiz) Q = Cola Q.introducir(raiz) MIENTRAS NO Q.vacia n = Q.extraer() SI n = objetivo DEVOLVER n SINO PARA CADA hijo EN n.hijos Q.introducir(hijo) 16 Capítulo 2. Trabajo relacionado Igualmente ignoramos la versión con control de repeticiones (Rusell y Norvig, 2003). Búsqueda A* El algoritmo A* aparece como un ejemplo de búsqueda informada. Al contrario que en las anteriores, en esta vamos a contar con información extra que nos informa de si nos estamos acercando o alejando de la situación conforme exploramos el árbol. Esta información se tratará de una heurística como se ha definido anteriormente. El ejemplo más visual de utilización de A* es en los sistemas de guía por GPS, en los que debemos resolver el problema de ir desde un punto A a otro B en un mapa de la forma más eficiente. La heurística que se suele elegir en estos casos es la distancia en línea recta entre una posición intermedia y el destino. Utilizaremos una cola de prioridad para que el siguiente nodo a evaluar sea aquel que sea más prometedor. Es decir, aquel que minimice la función: f(n) = g(n) + h(n) Dónde h(n)es la heurística del nodo actual al objetivo y g(n)el coste real del camino desde la raíz al nodo actual (ZENG y CHURCH, 2007). En la figura 2.2, vemos un ejemplo de los elementos de A*. Se muestra una simplificación del funcionamiento de un software de GPS para obtener un camino. En este caso podemos ver sobre los vértices la distancia real por carretera entre las ciudades que conformarían nuestra g(n)mientras que sobre los nodos (con números verdes), se ve la distancia en línea recta a nuestro nodo objetivo, estos valores conforman h(n). En el ejemplo el nodo origen es Madrid, marcado en amarillo y el objetivo Castellón de la Plana, en verde. Minimax Tenemos ya unas cuantas herramientas para explorar árboles. Ahora, estos algoritmos no pueden ser aplicados a los árboles de juego, ya que como se ha mencionado anteriormente no corresponde a un mismo agente elegir todos los caminos. Dada esta dificultad surge Minimax. En cada juego, debemos definir una variable de control a la que llamaremos valor de utilidad, que será diferente para cada juego y nos indicará si el nodo en cuestión proporciona un buen resultado. Este valor, vendrá definido 2.3. Búsqueda en árboles e inducción hacia atrás 17 Figura 2.2: Simplificación de la búsqueda de caminos en GPS por los nodos terminales. Debemos tener en cuenta que nuestro adversario tratará de maximizar su valor de utilidad, por lo que entre sus posibles acciones, elegirá siempre aquella que minimice nuestro valor de utilidad (van den Herik, 1999). Siendo así, el algoritmo funciona de esta manera: 1. Generar el árbol de juego completo. 2. Obtener el valor de utilidad de los nodos terminales. 3. Traspasar el valor de utilidad a los nodos superiores, eligiendo el máximo en caso de que el turno corresponda al jugador, y el mínimo en caso de que sea del oponente. Esta parte se llama inducción hacia atrás. 4. Elegir la acción correspondiente al nodo con el mayor valor de utilidad. El problema es precisamente el primer punto, ya que en juegos complejos es impracticable generar el árbol de juego entero. En el ejemplo que mostrábamos anteriormente del tres en raya tenemos un factor de ramificación inicial de 9 (en la primera jugada podemos colocar nuestra ficha en nueve posiciones) que disminuye en uno en cada jugada. Saber el número exacto de partidas posibles es complicado debido a que no todas las partidas requieren los 9 movimientos, a partir de 5 puede haber un ganador y terminar la partida. A pesar de esto, podemos ver que el número de partidas distintas está acotado superiormente por 9·8·7·6..,1 = 9! = 362880 partidas. El problema es igualmente complicado si queremos saber el número total de nodos que tiene el árbol, pero podemos hacer la misma acotación. De esta forma, en cada nivel tendremos 9! (9−n)! nodos, por lo que generaremos 18 Capítulo 2. Trabajo relacionado Figura 2.3: Obtención inicial de un árbol de juego un árbol de juego de tamaño cercano a: 9 X n=1 9! (9 −n)! = 986409 Si un juego tan sencillo genera prácticamente un millón de nodos, es evidente que no resulta factible aplicarlo a juegos más complejos. El ajedrez por ejemplo tiene un factor de ramificación inicial de 20 (16 movimientos de los peones y 4 de los caballos) que puede aumentar, y durante las etapas intermedias un valor típico (Laramée, 2000) por lo que simplemente al predecir 10 jugadas obtendríamos un árbol de cerca de 2,75 ×1015 nodos. Una solución común a este problema es utilizar un Minimax limitado por profundidad. Con este algoritmo exploraremos hasta predecir todas las jugadas posibles en los nsiguientes turnos y obtendremos igualmente el valor de utilidad de los nodos hoja. La figura 2.3 muestra cómo se genera un árbol de profundidad 4, por su parte, la 2.4 muestra cómo funciona la inducción hacia atrás de Minimax. El problema de limitar por profundidad a Minimax es que estaremos llegando a un nodo intermedio, no tiene por qué ser un nodo ganador o perdedor. Por tanto ¿Qué valor de utilidad asignamos a estos nodos? La solución suele ser utilizar conocimiento experto del dominio, es decir, razonamientos basados en la experiencia de juegos anteriores, estrategias que se conoce que han dado un buen resultado, etc. La gran desventaja de esta idea es que el conocimiento experto no solo es complicado de conseguir, sino que además no suele ser fácil de codificar en forma de reglas para que el algoritmo pueda trabajar. Otro problema es que este conocimiento no tiene por qué ser óptimo, puede haber estrategias mejores que simplemente no se hayan desarrollado. Ejemplos de este conocimiento se verán más adelante cuando se expliquen los juegos que se explorarán. 2.3. Búsqueda en árboles e inducción hacia atrás 19 Figura 2.4: Ejecución de la inducción hacia atrás en Minimax Poda Alpha-Beta Vamos a presentar ahora la optimización de Minimax conocida como poda alfa-beta (más conocido por el nombre en inglés: Alpha-Beta pruning). Dado el elevado coste de Minimax, debemos intentar ahorrar tantos cálculos como sea posible. En este sentido, nos damos cuenta de que podemos evitar la exploración de ciertas ramas si sabemos de antemano que no vamos a obtener un valor mejor que el ya obtenido. Veamos el siguiente ejemplo de una operación de maximización - minimización como las que encontramos en Minimax: m´ax{m´ın{3,12,8},m´ın{2, x, y},m´ın{14,5,2}} = m´ax{3, z, 2}= 3 Dado que z≤2, sabemos que nunca va a ser elegido por lo que una vez obtenido el valor 2, no hace falta explorar los valores xeyya que no van a influir (Rusell y Norvig, 2003). Para formalizar esto vamos a definir dos variables que llamaremos αyβ que definimos de la siguiente forma: αEl valor de la mejor (es decir mayor) elección que hemos encontrado hasta ahora en cualquier punto de elección para el camino de MAX. βEl valor de la mejor (es decir menor) elección que hemos encontrado hasta ahora en cualquier punto de elección para el camino de MIN. Si en la exploración de un nodo de maximización encontramos un valor que supere a β, no será necesario seguir explorando las demás ramas de ese nodo. Simétricamente, si en un nodo de minimización encontramos una rama con un valor de utilidad menor que α, podaremos1igualmente. Podemos ver el algoritmo en pseudocódigo a continuación: 1Evitaremos la exploración de dicha rama 20 Capítulo 2. Trabajo relacionado AlphaBeta(nodo) v = Maximizar(nodo, -infinito, +infinito) DEVOLVER v Maximizar(nodo, alpha, beta) SI esEstadoTerminal(nodo) ENTONCES DEVOLVER utilidad(nodo) v = -infinito PARA CADA a EN Acciones(nodo) v = max(v, Minimizar(AplicarAccion(a, nodo), alpha, beta)) SI v >= beta DEVOLVER v alpha = max(alpha, v) DEVOLVER v Minimizar(nodo, alpha, beta) SI esEstadoTerminal(nodo) ENTONCES DEVOLVER utilidad(nodo) v = -infinito PARA CADA a EN Acciones(nodo) v = min(v, Maximizar(AplicarAccion(a, nodo), alpha, beta)) SI alpha >= v DEVOLVER v beta = min(beta, v) DEVOLVER v Juegos para experimentar Presentamos a continuación algunos juegos que vamos a utilizar para nuestra investigación. Además de esto, profundizaremos en estrategias y conocimientos del dominio útiles para implementar jugadores eficientes. Reversi El Reversi, también conocido como Othello, es un juego de mesa cuyo origen proviene de Inglaterra, donde fue comercializado por primera vez en 1880 por Lewis Waterman y John W. Mollet. A día de hoy, el juego es conocido en todo el mundo, teniendo una fuerte presencia en Japón (française dÓthello, 1998). Para jugar necesitaremos un tablero de 8x8 casillas y 64 discos de tamaño inferior a una casilla. Los discos deberán ser de colores distintos en cada cara, estos colores tradicionalmente son negro y blanco, aunque es muy típico también encontrarlos en rojo y azul. Las casillas del tablero se suelen referenciar utilizando una letra de la aa la hde izquierda a derecha para indicar la columna, y un número del 1 al 8 comenzando de arriba hacia abajo para 2.4. Juegos para experimentar 21 Figura 2.5: Comienzo del juego en el Reversi señalar la fila. Al implementar el tablero la elección de representación más simple es utilizar un array bidimiensional de 8×8posiciones, de esta forma, las casillas quedan representadas con un vector [i, j]con 0≤i, j ≤7, esta será la representación que aparecerá en la mayoría de las imágenes. Jugarán dos jugadores y cada uno tendrá asignado un color. Reglas Según Rose (2005) las reglas del juego se definen como sigue: 1. El juego comienza con discos negros en d5 y e4, y discos blancos en d4 y e5 como se puede ver en la Figura 2.5. 2. Los jugadores alternan turnos, comenzando el jugador de fichas de color negro (o azul). 3. Un movimiento legal consiste en colocar un nuevo disco en una casilla vacía y dar la vuelta a uno o más de los discos del oponente. 4. Se dará la vuelta a cualquier disco del color del oponente, comprendido entre el disco que se acaba de jugar y cualquier otro del color del jugador preexistente en el tablero.Llamaremos a esto hacer un "Sándwich". Se pueden crear sándwiches en forma vertical, horizontal y diagonal. Para crear un sándwich, todas las casillas entre el disco nuevo y el preexistente del mismo color deben estar ocupadas por discos del oponente sin casillas vacías. 28 Capítulo 3. Funcionamiento de MCTS Figura 3.1: Ejemplo de selección utilizando UCB Dónde ¯ Xjes la recompensa media obtenida en el nodo j,nel número total de ejecuciones y njel número de ejecuciones en el nodo j. El primer sumando favorece la explotación de nodos pues si un nodo es bueno tendrá una recompensa media alta que aumentará el valor UCB, mientras que el segundo la exploración ya que es un valor alto en aquellos que han sido poco explorados en comparación con el número total de exploraciones. La figura 3.1 nos muestra un ejemplo de aplicación de UCB, después de 13 tiradas nos encontramos con los siguiente valores para los brazos donde se marcan las veces que se ha tirado de cada brazo detrás de la barra y las veces que se ha obtenido recompensa antes. Se muestra en azul el brazo que debería ser estirado a continuación. Monte Carlo Tree Search El algoritmo del árbol de búsqueda de Montecarlo o Monte Carlo Tree Search (MCTS) busca desarrollar un árbol que explore parcialmente el espacio de estados de un problema, intentando que los nodos en los que se dedica más esfuerzo sean los que van a dar un mejor resultado. La idea del algoritmo es precisamente evitar la exploración hasta los nodos terminales pues como se ha comentado esto resulta imposible. Por contra, vamos a estimar la probabilidad de ganar desde el estado intermedio en el que nos encontremos, es decir, calcula un valor heurístico. El medio para estimar este valor será realizar simulaciones de partidas en el que las decisiones se toman de forma aleatoria, por esto diremos que se llama de un método estocástico. La estimación del valor de cada nodo se hace únicamente mediante la simulación de partidas por lo que podemos construir jugadores que tomen buenas decisiones sin ninguna necesidad de conocimiento experto del dominio en el que se trabaja. Existe una gran diversidad de implementaciones de MCTS, sin embargo, en esta sección vamos a explorar el funcionamiento más tradicional y en las subsiguientes veremos las variaciones que han sido necesarias para nuestros casos concretos. El algoritmo pretende explorar un árbol y calcular un valor heurístico a cada nodo para poder elegir el que sea posiblemente el mejor. Partiremos de 3.2. Monte Carlo Tree Search 29 un único nodo raíz y en cada iteración iremos ampliando el conocimiento que tenemos del espacio de estados. Cada una de las mentadas iteraciones del código se divide en 4 partes claramente diferenciadas: selección, expansión, simulación y retropropagación (Browne et al., 2012). Esta partes contestan respectivamente a las preguntas ¿Qué nodo expandimos?¿Cómo lo expandimos?¿Cuán bueno es el nodo resultante?¿Qué efecto tiene esto sobre el resto del árbol? Vamos a necesitar guardar cierta información en los nodos del árbol. Cada uno almacenará: El estado del juego. Un contador de veces que ha sido expandido dicho nodo. Un contador de veces que la expansión ha resultado en una victoria. La acción por la que se ha llegado a ese nodo. Punteros al padre y los hijos. El objetivo es obtener una estimación de cuán buenas son las distintas acciones que tenemos a nuestra disposición. Para esto simplemente al expandir los nodos jugaremos partidas aleatorias desde cierto nodo y comprobaremos si hemos ganado o perdido, este valor se manda hacia arriba en la jerarquía de nodos, de esta forma, todos los nodos tienen la información de sus hijos. Selección El proceso de selección se ocupa de elegir qué nodo es el mejor exponente para ser expandido. Es aquí dónde cobra sentido el desarrollo previo sobre las máquinas tragaperras, pues utilizaremos el algoritmo UCB para seleccionar cuál es el siguiente nodo a expandir. Sin embargo, aparece un problema y es que como acabamos de comentar (y como se explica en profundidad en la sección sobre retropropagación) la información que encontramos en los padres es la suma de la de los hijos. Por esto no podemos utilizar UCB simple, nos vemos obligados a introducir UCT (Upper Confidence bound for Trees). Simplemente sustituiremos el valor de npor el número de veces que se ha seleccionado el nodo padre en lugar del total, de esta forma, se utiliza UCB de forma local permitiendo un funcionamiento correcto del algoritmo. La figura 3.2 muestra un ejemplo de selección utilizando UCT. 30 Capítulo 3. Funcionamiento de MCTS Figura 3.2: Ejemplo de selección utilizando UCT Expansión Una vez elegido el nodo a expandir, debemos dilucidar cómo lo hacemos, aquí empieza a aparecer la aleatoriedad. Hay diversas formas, veamos algunas de ellas: Expansión simple Es la opción más sencilla y con menor coste computacional. Consiste en que, dada la lista de acciones que tenemos disponibles para el nodo seleccionado, elegimos una de ellas, la ejecutamos y obtendremos un nuevo estado, que conformará el nuevo nodo hijo. Después continuamos hacia la siguiente fase (Chaslot et al., 2008). Expansión múltiple Se trata de una ampliación de la anterior, para ello, en lugar de elegir una única acción para expandir, escogemos ny pasamos a la siguiente fase. En este caso deberíamos investigar cuál es el valor óptimo para npues un valor muy elevado significaría un gasto excesivo en esta fase que multiplicaría el gasto en la siguiente. Simulación Una vez elegidos los nodos a expandir, debemos comprobar cuán buenos son estos. Esa es la función de la fase de simulación. Para conocer este valor, partiremos del estado que nos muestra el nodo a simular y comenzamos a tomar decisiones aleatorias, dentro de la lista de acciones disponibles, para definir un camino hasta llegar a un nodo terminal. El estado terminal tendrá 3.3. Simulación 31 un valor dependiendo del problema que estemos abarcando (ganar o perder, el nivel de beneficio obtenido, etc). Tomaremos entonces este como nuestro valor heurístico para el nodo. El ejemplo más sencillo es un juego en que los posibles resultados sean ganar o perder. En este caso, desde el estado que nos proponga el nodo a simular, generamos elecciones aleatorias de las jugadas disponibles hasta llegar a un estado en el que bien habremos ganado o perdido. En caso de ganar asignaremos 1/1al valor heurístico del nodo expandido, mientras que en caso de perder lo marcaríamos a 0/1donde el número detrás de la barra indica el número de veces que se ha simulado. La fase de simulación puede ser lenta si el problema que se está tratando tiene muchos posibles movimientos, si existen ciclos o si el espectro es infinito. Por eso en muchas ocasiones es más eficiente, en lugar de obligar al código a llegar a un estado terminal, elegir algún otro tipo de valor que nos indique cuán bueno es el nodo y hacer una exploración de profundidad limitada o con un tiempo limitado. Esta opción, por contra, nos hace perder uno de los puntos más importantes del algoritmo, la independencia del dominio, pues no necesita nunca conocimiento previo del juego, solamente saber si ha ganado o perdido, la capacidad de valorar un estado no terminal implica que sabemos de antemano lo bueno que es un estado. Realizaremos simulaciones sobre los candidatos a expandirse, ahora, debemos elegir cuántas simulaciones llevar a cabo, ya que realizar una sola sobre cada candidato puede involucrar un error muy grande a la hora de valorarlo, mientras que un número de simulaciones excesivamente grande ralentiza demasiado el algoritmo. En general la toma de decisiones en las simulaciones consumen muy poco tiempo computacional ya que no es necesario detenerse prácticamente a meditar las opciones. El mayor coste de estas viene precisamente de calcular las opciones posibles en cada estado por lo que en juegos complicados se ralentiza de forma significativa. Retropropagación En este momento, tenemos un valor de cuán bueno es el nodo (o los nodos) nuevo(s). Nuestra tarea será trasladar esta misma información a todos los nodos y en particular a los hijos de la raíz que son, al fin y al cabo, entre los que tenemos que elegir. Este proceso se llama retropropagación y es tan simple como recorrer el árbol desde el nodo hoja que acabamos de crear hasta la raíz sumando los valores de resultados e intentos a los contadores de cada nodo que encontremos por medio. Una vez llegados a este punto, hemos completado una iteración del MCTS, y con ello, obtenido un árbol con más nodos y mejor informado sobre lo buenas que son las distintas decisiones. A continuación se lleva a término la 32 Capítulo 3. Funcionamiento de MCTS Figura 3.3: Resultado de una iteración de MCTS siguiente iteración, y es entonces cuando aparece la pregunta: ¿Cuándo paramos? En un problema con un espacio de búsqueda virtualmente infinito, como puede ser, por ejemplo, el ajedrez (del que se hablará más adelante), podríamos explorar el árbol tanto como quisiéramos y siempre mejoraríamos la solución. Por ello, normalmente la estrategia es detenerse dada una condición que puede ser un límite de tiempo, un número máximo de nodos expandidos, una profundidad máxima, etc. Al cumplimiento de esta condición estaremos obligados a elegir el nodo que tenga mejor resultado hasta el momento. Retomando el ejemplo expuesto en la figura 3.2, podemos ver el resultado de realizar una expansión múltiple con n= 2, 5 simulaciones por nodo y la retropropagación del resultado. Se muestra en la Figura 3.3 Mostramos a continuación la estructura general de MCTS en pseudocó- 3.3. Simulación 33 digo: MCTS(raiz) MIENTRAS hayTiempo() HACER seleccionado = seleccion(raiz) expandido = expansion(seleccionado) resultado = simulacion(expandido) retropropagacion(expandido, resultado) DEVOLVER maxheuristica(raiz.hijos) seleccion(arbol) PARA CADA nodo EN arbol calcularUCT() DEVOLVER argmaxuct(arbol) expansion(nodo) PARA i=0 HASTA numeroExpansiones accion = randomchoice(accionesDisponibles(nodo)) nuevoNodo = ejecutar(accion, nodo) nodo.agregarHijo(nuevoNodo) simulacion(nodo) aciertos = 0 PARA i=0 HASTA numeroSimulaciones cnodo = copiar(nodo) MIENTRAS noTerminado(cnodo) HACER accion = randomchoice(accionesDisponibles(cnodo)) cnodo = ejecutar(accion, cnodo) SI ganar(cnodo) aciertos = aciertos +1 DEVOLVER aciertos retropropagacion(nodo, aciertos) nodo.aciertos = nodo.aciertos+aciertos nodo.intentos = nodo.intentos+numeroSimulaciones MIENTRAS nodo.padre != NULL HACER nodo <= nodo.padre nodo.aciertos = nodo.aciertos+aciertos nodo.intentos = nodo.intentos+numeroSimulaciones 34 Capítulo 3. Funcionamiento de MCTS PMCTS Vamos a implementar también la versión de MCTS conocida como Plain Montecarlo Tree Search. Esta versión difiere de la original en la fase de expansión que es ignorada. De esta forma el árbol de juego será estático sin ningún tipo de crecimiento. Recae sobre nosotros decidir la forma del árbol que será generado antes de comenzar las iteraciones. La generación de este árbol inicial es algo arriesgada, pues, según esté definido podría obviar opciones beneficiosas que ya no serán tomadas en consideración en ningún momento. En la versión que hemos implementado, para dar solución a esto, generamos 2 niveles del árbol completos, todas las posibles acciones a tomar por nosotros y por nuestro contrincante. Una vez realizado este paso inicial desarrollamos las otras tres fases tantas veces como iteraciones sean posibles. Eligiendo el árbol de esta manera podemos ahorrar el cálculo de UCT como en el apartado anterior y calcular directamente UCB sobre los nodos hoja, pues la selección del nodo raíz o de algún nodo no hoja implicaría una simulación que forzosamente pasaría por alguna de las hojas, lo que es ineficiente. Podemos apreciar entonces el pseudocódigo del cuerpo principal de este algoritmo: PMCTS(raiz) generarArbolInicial(raiz) MIENTRAS hayTiempo() HACER seleccionado = SeleccionPorUCB() Simulacion(seleccionado) Retropropagacion(seleccionado) DEVOLVER maxheuristica(raiz.hijos) Reaprovechamiento de memoria Cada vez que nos encontremos en un estado nuevo, deberemos generar un árbol de juego que parta únicamente de la raíz, para estimar una vez más la heurística de cada nodo. Una idea interesante es reaprovechar un árbol que tuviéramos creado ya de la última vez que lo generamos, para obtener mejores resultados. El problema con esto es que no podemos predecir qué movimiento va a elegir el adversario o los adversarios, con lo que es posible que este no esté entre los que nosotros hemos considerado. Para ello lo más sencillo es guardar la estructura del árbol de la ejecución anterior y antes de comenzar las nuevas iteraciones, descendemos dos veces por la raíz del árbol imitando las acciones tomadas en el juego real. En caso de 3.6. Aproximación probabilística 35 no tener un vértice a ese nodo empezaríamos de cero, pero si tenemos suerte podemos partir de un árbol con unas cuantas heurísticas ya calculadas, lo que nos permitiría en el mismo tiempo computacional obtener los resultados equivalentes a más simulaciones. Aproximación probabilística En esta sección se utilizan conceptos de probabilidad que no han sido introducidos en apartados anteriores por lo que se recomienda que el lector tenga conocimientos de probabilidad y estadística. En todo caso, si el lector desea repasar las definiciones de estos conceptos, puede hacerlo en el apéndice A. Utilizando el método de Montecarlo estamos intentando aproximar la distribución de probabilidad de una variable aleatoria discreta que nos marcará las expectativas de ganar que podemos tener dada la elección de cierta acción en un estado dado. Si llamamos Xa esta VA. Tenemos dos resultados posibles: X=ganar X =no ganar Según está definido el algoritmo nuestro objetivo es aproximar p(X=ganar|e) mediante simulaciones siendo euna configuración dada dentro del espacio de estados. Vamos a comprobar que efectivamente la probabilidad de que obtener una victoria desde cierto estado es igual a la de que una simulación resulte ganadora. De esta forma nos veremos en las condiciones de aplicar el teorema de Glivenko-Cantelli (que se enuncia y explica en la sección siguiente) y demostrar que efectivamente mediante este procedimiento estamos aproximando la probabilidad real de ganar desde ese estado. Esta última probabilidad la obtenemos de forma recursiva: comenzando con el caso base, si el nodo ees un estado terminal habremos ganado o perdido por lo que: p(X=ganar|e) = 1si e es un estado ganador 0ecc Llamaremos aj ia ejecutar la acción aien el punto de toma de decisión número jy denotaremos por ai(e)al estado resultante de aplicar la acción aiae. En 36 Capítulo 3. Funcionamiento de MCTS caso de no tratarse de un estado terminal tendremos que: p(X=ganar|e) = X i p(X=ganar|e, a1 i)p(a1 i) =X i,j p(X=ganar|e, a1 i, a2 j)p(a1 i, a2 j) =... =X i,...,j p(X=ganar|e, a1 i, ..., ak j)p(a1 i, ..., ak j) Siendo kel número necesario para que a1 i(...(ak j(e))) sea un estado terminal. La distribución de probabilidad conjunta, viene dada por: p(A, B) = P(A∩B) = p(A|B)p(B) aplicando a nuestro caso: p(a1 i, a2 l..., ak j) = p(a2 l..., ak j|a1 i)p(a1 i) =... =Y m p(ar m|ar−1 j, ..., a1 i) Estos datos son conocidos para nosotros, suponiendo que todas las acciones tienen la misma importancia, podemos suponer que p(a1 i) = 1 N(1) siendo N(1) el número de acciones entre las que elegir. Así sucesivamente p(a2 j|a1 i) = 1 N(2) i ... Este es exactamente el comportamiento que tiene nuestra simulación, pues al elegir aleatoriamente la acción a tomar la probabilidad en nuestra simulación p(a)coincide con la aproximada anteriormente. A su vez los estados terminales reportan 1 o 0 dependiendo de su valía por lo que la probabilidad de una simulación de obtener una victoria es exactamente la probabilidad de ganar que hemos obtenido teóricamente. Las simulaciones aproximan la distribución Ya hemos comprobado que las simulaciones tienen la misma función de distribución Fque la variable aleatoria definida en el apartado anterior. Vamos ahora a ver que efectivamente al aumentar el número de simulaciones realizadas nuestro resultado heurístico se acerca a la distribución F. Este resultado está recogido en el teorema de Glivenko-Cantelli que se enuncia a continuación (Ángel Villegas, 2005). 3.6. Aproximación probabilística 37 Teorema 1 (Glivenko-Cantelli) Si se tiene una muestra aleatoria simple de tamaño n de una población X, con función de distribución F(x), para cualquier número real positivo arbitrario ε, se tiene que l´ım n→∞ Psup x∈R|F∗n(x)−F(x)| ≥ ε= 0 La demostración de este teorema se puede consultar en Fisz (1963). Este teorema nos indica que la probabilidad de que el valor supremo de la diferencia entre la función de distribución estimada con la muestra aleatoria simple (en nuestro caso los resultados de las simulaciones) y la función de distribución teórica, sea mayor que cierto valor εes 0 cuanto el tamaño de la muestra tiende a infinito. Con esta sección hemos demostrado que a través de las simulaciones obtendremos un valor heurístico que efectivamente aproxima el valor teórico correspondiente a cada nodo. 44 Capítulo 4. Aplicación de MCTS a juegos Experimento Profundidad PMCTS Profundidad MCTS 1 23 41 23 41 2 17 47 16 48 3 26 38 26 38 4 34 30 11 53 5 10 54 33 31 6 50 14 15 49 7 21 43 27 37 8 23 41 26 38 9 23 41 32 32 10 14 50 30 34 11 27 37 54 10 12 25 39 26 38 13 16 48 13 21 14 13 51 9 55 15 14 50 1 62 16 22 42 8 56 17 29 35 20 44 18 17 46 0 42 19 29 35 44 20 20 26 38 25 39 21 35 29 26 38 22 23 41 16 48 23 55 9 33 31 24 25 39 28 36 25 24 40 39 25 26 47 15 10 54 27 24 40 12 52 28 17 46 21 43 29 20 44 35 29 30 23 41 19 45 Media 25,066 38,8 22,6 39,633 Victorias 5 25 6 23 Tabla 4.3: PMCTS y MCTS (70 simulaciones) vs búsqueda en profundidad 4.1. Aplicación al Reversi 45 Experimento Bactracking PMCTS Backtracking MCTS 1 18 46 11 53 2 19 45 12 52 3 24 40 52 12 4 22 42 20 44 5 23 41 42 22 6 21 43 21 43 7 24 40 30 34 8 21 43 26 38 9 16 48 23 41 10 26 38 21 43 11 29 35 22 42 12 20 44 28 36 13 13 51 31 33 14 37 27 26 38 15 16 48 40 24 16 20 44 19 45 17 18 46 17 47 18 17 47 29 35 19 14 50 18 46 20 24 40 28 36 21 15 49 31 33 22 25 39 36 28 23 19 45 21 43 24 23 41 21 43 25 18 46 20 44 26 14 50 24 40 27 21 43 25 39 28 17 47 30 34 29 20 44 22 42 30 25 39 42 22 Media 20,633 43,366 26,266 37,733 Victorias 1 29 5 25 Tabla 4.4: PMCTS y MCTS (700 simulaciones) vs búsqueda en profundidad 46 Capítulo 4. Aplicación de MCTS a juegos Experimento Alpha-Beta débil PMCTS Alpha-Beta débil MCTS 1 22 42 33 0 2 26 38 48 16 3 25 39 26 38 4 38 26 56 1 5 24 40 27 37 6 19 45 25 0 7 27 37 46 18 8 16 48 32 32 9 28 36 42 22 10 25 39 31 33 11 18 46 47 17 12 19 0 21 0 13 19 45 50 14 14 19 45 31 33 15 41 23 41 23 16 39 25 31 33 17 35 29 55 9 18 22 42 54 10 19 21 43 32 32 20 30 34 29 0 21 29 35 41 23 22 23 41 38 26 23 30 34 31 33 24 26 1 23 0 25 23 0 33 31 26 19 45 36 28 27 32 32 23 41 28 30 34 28 36 29 54 10 21 43 30 30 34 34 30 Media 26,966 32,933 35,5 21,966 Victorias 8 21 18 10 Tabla 4.5: PMCTS y MCTS(140 simulaciones) vs Alpha-beta (débil) 4.1. Aplicación al Reversi 47 menta sustancialmente la capacidad de Alpha-beta, pues reduce las victorias de PMCTS al 36% y las de MCTS al 26,6 %. Por último, con el fin de conseguir vencer con mayor frecuencia a Alphabeta, vamos a introducir contenido específico del dominio en nuestro jugador con mejor resultado, que ha demostrado ser PMCTS. Utilizaremos la misma heurística que hemos proporcionado a Alpha-beta, para ello, una vez realizado todo el algoritmo, antes de elegir el movimiento a realizar, aumentaremos o disminuiremos el valor de bondad del nodo sumando 20 aciertos si la jugada nos haría dominar una esquina, 2 en caso de una casilla ’X’y restaremos 5 para las casillas ’C’. A la vista de esto obtenemos los resultados que se disponen en la tabla 4.7. Podemos ver una leve mejoría respecto al caso anterior, subiendo el porcentaje de victorias al 43,3%. Vamos ahora a comprobar el comportamiento al aumentar el número de simulaciones significativamente para ver si con esto podemos definitivamente sobrepasar a Alpha-beta fuerte. MCTS vs PMCTS Por último, enfrentamos ambas versiones de Montecarlo Tree Search entre si y mostramos los resultados en la tabla 4.9. Ya habíamos visto en los experimentos anteriores que en general tenemos un rendimiento mejor en la versión plana que en la dinámica, aquí lo vemos claramente plasmado cuando PMCTS se alza con un 76 % de victorias. Análisis de resultados Podemos ver que ambas versiones del algoritmo dan muy buenos resultados contra el aleatorio, obteniendo un ratio de no derrotas siempre entre el 90% y el 97 %. Esto nos indica que realmente el algoritmo toma buenas decisiones. Podemos ver aquí, una leve diferencia entre las dos versiones dando pistas de que PTCMS tiene un comportamiento livianamente mejor que su versión original. Vemos que al aumentar las repeticiones disminuye en una las victorias de MCTS. Podemos achacar esto a la simple probabilidad o, que el salto de simulaciones no ha sido suficiente para asegurar un aumento sustancial del rendimiento. Una situación similar encontramos contra el algoritmo de búsqueda en profundidad, en este caso, teniendo un margen mayor de mejora, especialmente en MCTS, damos un salto categórico en la cantidad de simulaciones entre el primer experimento y el segundo. Apreciamos claramente cómo ambas versiones mejoran minimizando las opciones del adversario. Por otra parte, el algoritmo Alpha-Beta obtiene un mayor porcentaje de victorias contra ambos. Esto era de esperar, pues como ya se ha explicado antes, se trata de un algoritmo muy sofisticado. Cabe destacar la importan- 48 Capítulo 4. Aplicación de MCTS a juegos Experimento Alpha-Beta PMCTS Alpha-beta MCTS 1 44 20 21 43 2 31 33 31 33 3 41 23 43 21 4 25 0 47 17 5 44 20 34 30 6 37 27 38 26 7 42 22 46 18 8 21 43 38 26 9 55 9 27 37 10 28 36 30 34 11 37 27 52 12 12 43 21 46 18 13 20 44 58 5 14 26 38 61 1 15 46 16 56 8 16 20 44 25 0 17 51 13 51 13 18 42 22 30 34 19 59 5 32 32 20 59 5 32 33 21 48 16 35 29 22 31 33 29 35 23 55 9 22 42 24 29 35 52 12 25 31 33 38 26 26 31 33 29 0 27 41 23 49 15 28 53 11 42 22 29 49 15 33 31 30 27 37 36 28 Media 38,86 23,76 38,76 22,7 Victorias 19 11 21 8 Tabla 4.6: PMCTS y MCTS(140 simulaciones) vs Alpha-beta (fuerte) 4.1. Aplicación al Reversi 49 Experimento Alpha - Beta PMCTS 1 25 39 2 27 37 3 41 23 4 25 39 5 39 25 6 24 40 7 31 33 8 43 21 9 46 18 10 21 43 11 61 3 12 43 21 13 44 20 14 55 9 15 39 25 16 26 38 17 60 4 18 26 38 19 44 20 20 10 54 21 49 15 22 31 33 23 44 20 24 54 10 25 51 13 26 56 5 27 29 35 28 40 24 29 28 36 30 20 44 Media 37,733 26,166 Victorias 17 13 Tabla 4.7: PMCTS (mejorado y con 140 simulaciones) vs Alpha-beta (fuerte) 50 Capítulo 4. Aplicación de MCTS a juegos Experimento Alpha - Beta PMCTS (informado) Alpha - Beta PMCTS 1 38 26 38 26 2 51 13 51 13 3 17 47 17 47 4 30 34 30 34 5 30 34 30 34 6 48 16 48 16 7 45 19 45 19 8 28 36 28 36 9 29 35 29 35 10 30 34 30 34 11 39 0 39 0 12 27 37 27 37 13 38 26 38 26 14 14 50 14 50 15 41 23 41 23 16 31 33 31 33 17 24 40 24 40 18 31 33 31 33 19 52 12 52 12 20 17 47 17 47 21 44 20 44 20 22 31 33 31 33 23 19 45 19 45 24 46 18 46 18 25 32 32 32 32 26 31 33 31 33 27 24 40 24 40 28 30 34 30 34 29 41 23 41 23 30 43 21 43 21 Media 33,36 29,8 36,46 26,06 Victorias 12 17 14 15 Tabla 4.8: PMCTS (750 simulaciones) vs Alpha-beta (fuerte) 4.1. Aplicación al Reversi 51 Experimento MCTS PMCTS 1 24 40 2 28 36 3 38 26 4 17 47 5 16 48 6 23 41 7 28 36 8 19 45 9 17 47 10 19 45 11 27 37 12 3 61 13 19 45 14 37 27 15 23 41 16 34 30 17 12 52 18 40 24 19 29 35 20 16 48 21 17 47 22 49 15 23 22 42 24 30 34 25 35 29 26 24 40 27 3 51 28 28 36 29 44 20 30 22 42 Media 24,76 38,9 Victorias 7 23 Tabla 4.9: MCTS (70 simulaciones) vs PMCTS (70 simulaciones) 52 Capítulo 4. Aplicación de MCTS a juegos Figura 4.1: Resultados de usar o no conocimiento del dominio con 750 simulaciones cia de la optimización heurística, pues vemos que el α−βsaca más ventaja a los algoritmos de Montecarlo cuando está armada con esta. A pesar de todo, conseguimos un resultado bastante bueno contra ambas versiones, especialmente de PMCTS que gana en la mayoría de los casos contra la versión débil y es capaz de obtener más de un tercio de las victorias contra la versión fuerte. Apreciamos también en este apartado cómo el inyectar cierto conocimiento del dominio hace mejorar a PMCTS hasta estar casi igualado con el algoritmo más fuerte que hemos presentado en el caso de realizar 140 simulaciones. Una vez damos el salto a 750 vemos que PMCTS es capaz de dominar en victorias, además, al resultado es incluso mejor al inyectar conocimiento del dominio. Es notable destacar que en estos últimos experimentos se producen más victorias de PMCTS aunque este consigue una puntuación media peor. Un punto importante a destacar es la diferencia de rendimiento entre la versión plana y la dinámica, ya que en general obtiene un resultado mucho más alto la primera. Una posible razón que explique esta diferencia es la expansión inicial del árbol que realiza PMCTS ya que generamos dos niveles completos con los que no cuenta MCTS que comienza desde la raíz, por lo que con las mismas iteraciones, realmente ha previsto más. Para acabar esta sección, se muestran diferentes gráficas con la exposición de los resultados. En la gráfica presentada en la figura 4.2 podemos ver el resultado medio obtenido en las distintas ejecuciones, en la parte superior se muestra MCTS y en la inferior PMCTS. En esta última se señala como Alpha-beta(mejorado) el enfrentamiento entre Alpha-beta fuerte y PMCTS con conocimiento del dominio. Del mismo modo , la figura 4.1 muestra los resultados del último experimento que compara el uso de conocimiento del dominio con 750 simulaciones. Por otra parte, vemos que la figura 4.3 nos muestra dos gráficas de dispersión con las distintas partidas en las que podemos ver diferenciados los distintos experimentos y obtener una idea global del funcionamiento. Se muestra la barra divisoria en 32 pues es la puntuación mínima que hay que obtener para no perder. 4.2. Aplicación al Ajedrez 53 Figura 4.2: Comparación de partidas ganadas y perdidas en los diferentes enfrentamientos Aplicación al Ajedrez El Ajedrez de por sí es un juego bastante complicado, como ya hemos comentado anteriormente, tiene un factor de ramificación medio de 35, por ello nos es imposible abarcarlo con algoritmos más clásicos como Minimax puro. Además, a diferencia del Reversi, en el Ajedrez se pueden producir ciclos ya que todas las piezas, a excepción de los peones, pueden volver a la posición de inicio de su anterior movimiento, por lo que intentar investigar el espacio de estados completo no resulta factible. Dadas estas bases, vamos a elegir el tipo de expansión y de simulación que nos interesan. Expansión En este caso vamos a probar con la misma versión que utilizamos para el Reversi. Para la versión plana debemos decidir sobre qué árbol vamos a utilizar. Comenzamos generando un árbol de 3 niveles completos (la raíz y dos niveles más), al igual que hacíamos antes. Capítulo 5 Mejorando MCTS con redes neuronales En este capítulo vamos a hacer un recorrido sobre los métodos más modernos implementados con el fin de perfeccionar el rendimiento de Montecarlo Tree Search. Lo dividiremos en dos secciones, en la primera expondremos los temas y conceptos pertinentes para comprender qué es el aprendizaje automático o Machine Learning, y en el segundo cómo lo mezclamos con MCTS para mejorar los resultados. En este tema se utilizarán diversos conceptos sobre probabilidad y álgebra que no han sido introducidos anteriormente en el documento, estos se pueden consultar íntegramente en los apéndices A y B respectivamente. Aprendizaje automático El campo del aprendizaje automático surge de cuando intentamos que un computador sea capaz de reconocer patrones y obtener predicciones a partir de un conjunto de datos. Destacamos dos casos principales a estudiar: regresión y clasificación. El problema de regresión intenta afrontar el dilema de tener dos variables aleatorias correlacionadas XeYy necesitamos determinar una aproximación a la relación existente entre ellas. Los datos nos generarán una nube de puntos y buscamos encontrar una función y(x)que sea la que mejor se ajuste a las observaciones (Rouaud, 2013). La aproximación más típica es conocida como regresión lineal, que fuerza a ya definir un hiperplano del espacio, por lo que esta viene conformada de la forma: y(x) = Wtx+b con la matriz W∈RD×Ky los vectores x∈RDyb∈RKsiendo Dla 61 62 Capítulo 5. Mejorando MCTS con redes neuronales Figura 5.1: Regresión (Izquierda) y clasificación (derecha) dimensión del espacio de los datos y Kla dimensión del resultado a obtener. En la figura 5.1 se muestra un ejemplo de regresión lineal con D=K= 1. Por su parte, el problema de clasificación parte de un conjunto de datos distribuidos en Kclases. Nos gustaría, dado un dato de entrada, asignarlo a una clase Ckcon 1≤k≤K. El problema que probablemente más se estudia es el conocido como clasificación binaria, que se trata del caso en el que k= 2 (Smola y Vishwanathan, 2008). Un ejemplo clásico son los filtros de spam, que, dado el contenido de cierto e-mail, son capaces de diferenciar si estos se tratan de correo basura o no. En caso de que K > 2conoceremos la situación como clasificación multiclase. Encontramos igualmente infinidad de ejemplos como detectar de forma automática el idioma en el que se encuentra un texto o, dadas las mediciones de los síntomas, diagnosticar la etapa del cáncer en la que se encuentra una persona, dando herramientas poderosas a los profesionales sanitarios. Resultados erróneos pueden acarrear severas consecuencias, como en el caso de diagnosticar erróneamente una enfermedad, por ello deben tener unas bases matemáticas bien fundadas para asegurar la exactitud de los resultados. Vamos a presentar 3 algoritmos que dan solución a estos problemas, de menor a mayor complejidad: mínimos cuadrados, el perceptrón y las redes neuronales. Aunque la cantidad de algoritmos desarrollada es extensa, estos son una buena aproximación al campo de estudio, y cada uno representa una evolución del anterior. Nos aportarán herramientas poderosas para mejorar MCTS. Mínimos cuadrados Partimos de un conjunto de entrenamiento, compuesto por Nvectores1 de entrada y la correspondiente etiqueta que nos indicará a qué clase pertenecen, es decir {(xj, tj)}N j=1. Utilizaremos una clasificación para las etiquetas 1en desarrollo todos los vectores son columnas, para indicar un vector fila se indicará como traspuesta 5.1. Aprendizaje automático 63 conocida como one hot, en ella para todo j,tjserá un vector ekde la base canónica2de RK. Deseamos encontrar una función afín y:RD→RK, con lo que obtendremos un vector de dimensión K. Al ser afín sabemos que nuestra función tendrá la forma: y(x) = Wtx+ben las mismas condiciones que se define en la sección anterior. Asignaremos a la clase de la coordenada que haya obtenido un valor mayor, es decir: y∈ Ck|k= arg m´ax 1≤α≤Kyα(x) Para simplificar la notación en el desarrollo llamaremos ˜x=1 xy˜ W= bt W. Agrupando ahora etiquetas y ejemplos de entrenamiento, llamaremos T= (t1, ..., tN)y˜ X= (˜x1, ..., ˜xn). En un caso ideal, querríamos conseguir que: ∀j y(xj) = Wtx+b=˜ Wt˜x=tj o equivalentemente debemos resolver el sistema lineal de ecuaciones: ˜ Wt˜ X=T Sin embargo en la mayoría de situaciones este sistema no tendrá solución por lo que deberemos conformarnos con el resultado que se acerque más, para ello resolveremos el problema de optimización: m´ın ˜ W|| ˜ Wt˜ X−T|| Llamaremos J(˜ W) = || ˜ Wt˜ X−T||, función de coste. Dado que la norma es no negativa, minimizar Jes equivalente a minimizar E(˜ W) = 1 2|| ˜ Wt˜ X−T||2, esto nos facilitará los cálculos más adelante. Presentamos a continuación 2 formas de solucionarlo, una de ellas es un método de aproximación y la otra una solución teórica. Descenso de gradiente El descenso de gradiente es un método iterativo que da solución a minimizar la función E(˜ W). Para ello, calcularemos el gradiente de la función, 2En el espacio vectorial Knel conjunto formado por los nvectores (1,0,0..., 0),(0,1,0, ..., 0), ..., (0,0,0, ..., 1) es una base que recibe el nombre de base canónica de Kn. Estos vectores habitualmente se denominan eidonde (ei)j= 1 si j=iy (ei)j= 0 en cualquier otro caso (Merino y Santos, 2006). 64 Capítulo 5. Mejorando MCTS con redes neuronales Figura 5.2: Dirección del gradiente y problemas de elegir erróneamente el parámetro α este nos indica la dirección de ascenso de máxima pendiente, por ello, si restamos esta cantidad, estaremos decreciendo el valor de la función de coste. Tenemos: ∇E(˜ W) = ˜ X(˜ Wt˜ X−T)t Este resultado se justifica en la sección siguiente. Teniendo esto, definimos la regla de actualización como: ˜ W(r+1) =˜ W(r)−α˜ X(˜ Wt˜ X−T)t Donde αes un parámetro conocido como tasa de aprendizaje. La función de este es determinar el tamaño del salto existente entre una actualización y la siguiente. Un valor muy grande puede llevar a que el método obtenga incluso un resultado opuesto al buscado. Por otra parte, un valor muy pequeño puede llevar a que el algoritmo no converja en un tiempo razonable. Se muestra una visualización de estos resultados en la figura 5.2 en la que se puede ver a la izquierda los gradientes en los distintos puntos y a la derecha el resultado de usar un αmuy grande (en naranja) y el de utilizar uno muy pequeño (en azul). 5.1. Aprendizaje automático 65 Cálculo directo Vamos a calcular el mínimo de la función E(˜ W)de manera explícita. Comenzamos observando que: E(˜ W) = 1 2|| ˜ Wt˜ X−T||2=1 2tr(( ˜ Wt˜ X−T)t(˜ Wt˜ X−T))?? (5.1) =1 2tr(˜ Xt˜ W˜ Wt˜ X−˜ Xt˜ WT −Tt˜ Wt˜ X+TtT) (5.2) Nos encontramos ante una función diferenciable, podemos entonces encontrar los extremos en los puntos que anulen a ∇E(˜ W). Por tanto, dada una matriz cualquiera A∈RK×(D+1): ∇E(˜ W) = l´ım ε→0 E(˜ W+εA)−E(˜ W) ε substituyendo en 5.2: E(˜ W+εA) = 1 2tr(ε2˜ XtAAt˜ X−ε˜ XtAT −εTtAT˜ X +ε˜ Xt˜ WAt˜ X+ε˜ XtA˜ Wt˜ X+˜ Xt˜ W˜ Wt˜ X −˜ Xt˜ WT −Tt˜ Wt˜ X+TtT) si restamos E(˜ W)obtenemos que: E(˜ W+εA)−E(˜ W) = 1 2tr(ε2˜ XtAAt˜ X−ε˜ XtAT −εTtAT˜ X +ε˜ Xt˜ WAt˜ X+ε˜ XtA˜ Wt˜ X) dividiendo por εy teniendo en cuenta la propiedad de la traza 1: E(˜ W+εA)−E(˜ W) ε=1 2tr(ε˜ XtAAt˜ X−˜ XtAT −TtAT˜ X +˜ Xt˜ WAt˜ X+˜ XtA˜ Wt˜ X) 66 Capítulo 5. Mejorando MCTS con redes neuronales añadiendo el límite y considerando las propiedades de la traza 3 y 4: l´ım ε→0 E(˜ W+εA)−E(˜ W) ε=1 2tr(˜ XtAT −TtAT˜ X +˜ Xt˜ WAt˜ X+˜ XtA˜ Wt˜ X) =1 2[tr(( ˜ XtA)( ˜ Wt˜ X−T)) +tr((( ˜ XtA)( ˜ Wt˜ X−T))t)] =tr(( ˜ XtA)( ˜ Wt˜ X−T)) =tr(( ˜ Wt˜ X−T)˜ XtA) =tr(( ˜ X(˜ Wt˜ X−T)t)tA) =D˜ X(˜ Wt˜ X−T)t, AE Dado que esto debe anularse ∀Aentonces debe ser que: ˜ X(˜ Wt˜ X−T)t= 0 ˜ X(˜ Xt˜ W−Tt)=0 ˜ X˜ Xt˜ W−˜ XTt= 0 ˜ X˜ Xt˜ W=˜ XTt ˜ W= ( ˜ X˜ Xt)−t˜ XTt Este método da una solución instantánea y por tanto es preferible su uso al del descenso de gradiente explicado en la sección anterior, sin embargo, no en todos los algoritmos nos va a ser posible calcular explícitamente el mínimo. Perceptrón simple El siguiente algoritmo a estudiar es conocido como perceptrón, el punto más importante de este es que define el elemento básico con el que construiremos nuestra red neuronal: la neurona. Vamos a obtener un algoritmo que sea capaz de realizar una clasificación binaria. Además, vamos a utilizar una codificación distinta a la de la sección anterior para las etiquetas, en este caso tn∈ {1,−1}. Definido de esta forma, nos gustaría que nuestra función y(x)devolviera 1 en caso de que el dato x pertenezca a la clase C1y−1en caso de que corresponda a C2de esta forma definimos (Bishop, 2006): y(x) = f(wtx+b) = f( ˜wt˜x) = 1si wtx+b≥0 −1si wtx+b < 0 5.1. Aprendizaje automático 67 teniendo w∈RD,b∈Ry, con la misma abreviatura que hemos introducido antes ˜x, ˜w∈RD+1, siendo Dla dimensión de los datos de entrada. Afla llamaremos función de activación, su función es llevar los valores al dominio que nos interesa, en este caso ±1. Para este algoritmo la hemos definido como una función de salto, cuando veamos redes neuronales, necesitaremos alguna función más potente que esta para obtener un resultado acertado. Nos interesa obtener un ˜wque consiga ˜wt˜xn>0si el dato xnpertenece a la primera clase y ˜wt˜xn<0en caso de que lo haga a la segunda. Podemos resumir esto en ˜wt˜xntn>0. Tenemos ya una forma de definir nuestra función de coste para cierto dato: E( ˜w) = 0Si el dato está bien clasificado −˜wt˜xntnEn caso contrario la función de coste total será la suma de la función de coste asociada a cada dato de entrenamiento: E( ˜w) = N X i=1 Ei( ˜w) Para entrenarlo utilizaremos una versión modificada del entrenamiento expuesto para mínimos cuadrados: el descenso de gradiente estocástico. Este difiere de la versión original en que en lugar de utilizar la función de coste total actualizaremos mediante la función particular de cada dato. Es conocido como estocástico ya que en su implementación antes de comenzar a repasar los datos uno a uno y realizar el descenso, se suelen reordenar los datos de entrada de forma aleatoria. Dicho esto, basta ahora con encontrar el gradiente de la función de coste que viene definido trivialmente por ∇En( ˜w) = −xntn la regla de actualización queda entonces: ˜w(r+1) =˜w(r)Si el dato está bien clasificado ˜w(r)+xntnEn caso contrario Aunque este algoritmo está pensado para clasificación binaria, es fácilmente generalizable al caso multiclase, basta con utilizar tantos perceptrones como clases existan y entrenar cada uno para diferenciar cierta clase Ckde el resto. En el caso ideal se obtendría en todos -1 excepto en 1, aunque suele ocurrir que más de uno de resultado positivo, en este caso haría falta comparar para cuál de ellos el resultado de ˜wt˜xnes mayor. Redes neuronales Una red neuronal, también conocida como perceptrón multicapa, generaliza el concepto presentado por el perceptrón. La idea es utilizar muchas 68 Capítulo 5. Mejorando MCTS con redes neuronales neuronas que compartan la información entre ellas y sean capaz de realizar las tareas de clasificación y regresión con mayor eficacia. Dicho esto, definimos una red neuronal como una terna (N, V, w)siendo Nun conjunto de neuronas y Vun conjunto {(i, j)|i, j ∈N}cuyos elementos son llamados conexiones entre la neurona iy la neurona j. La función w: V→Rdefine los pesos, donde w((i, j)), representa el peso de la conexión entre la neurona iy la jque abreviaremos como wi,j (Kriesel, 2005). Ahora, queremos dar un poco más de estructura a esta definición, por ello vamos a incluir el concepto de capa. Redefinimos entonces la definición como una terna (N, V, w)solo que ahora N={C1, C2...Cn}es un conjunto de capas, cada uno de estos es entonces un conjunto de neuronas. Vamos a modificar también la definición de Vpara que únicamente se permitan conexiones entre una capa y la siguiente, de esta forma V={(i, j, k)|i, j, k ∈ N}representa la conexión entre las neuronas ide la capa Ck−1yjde Ck. Por ende, el peso de esta conexión vendrá dado por w(i, j, k)que abreviaremos como wk i,j, también utilizaremos la notación Wkpara referenciar la matriz cuyos elementos son Wk i,j =wk i,j. Obtenemos así el concepto de red neuronal multicapa. Nuestra red define una composición de aplicaciones pues el resultado obtenido por la función yserá la consecuencia de atravesar todas las capas de la red. Llamaremos zk:RKk−1→RKka la función cuyos datos de entrada son los resultados obtenidos en la capa anterior y genera los nuevos datos. La dimensión del espacio de entrada es RKk−1será igual al número de neuronas de la capa Ck−1, lo mismo ocurre con la capa siguiente. A su vez, las funciones zkson una composición de dos funciones: zk=hk◦ak aquí, akes una función afín similar a las que hemos visto en los algoritmos anteriores: ak(x) = Wkx+bk Por su parte, la función hkhará el papel de la función fen el algoritmo del perceptrón, pero vamos a buscar que esta sea una función continua. Una elección común suele ser la función sigmoide σ: σ(a) = 1 1 + e−a que tiene valor 0,5si a= 0, tiende rápidamente a 1cuando a→ ∞, y a 0 cuando a→ −∞. Aunque otras opciones pueden ser la tangente hiperbólica o la función softmax: softmax(a) =      exp(a1) K P k=1 exp(ai) , ..., exp(aK) K P k=1 exp(ai)      5.1. Aprendizaje automático 69 Resumiendo: y(x) = zk◦... ◦z1(x)(5.3) =hk◦ak◦... ◦h1◦a1(x)(5.4) Ya tenemos perfectamente delimitada nuestra herramienta, ahora queda en nuestras manos definir el número de capas, las neuronas que habrá en cada capa, y la función de coste para asegurarnos de que efectivamente nos acercamos a nuestro objetivo. Por convenio se llama capa de entrada a C1 yCKse denomina capa de salida, las intermedias se conocen como ocultas. Veremos en un momento que las redes con una capa oculta nos servirán para aproximar cualquier función, aunque dependiendo del dominio el aumento del número de capas puede llevar a un mejor comportamiento de la red. El número de neuronas en las capas de entrada y salida será igual a la dimensión de los espacios en los que se encuentran los datos de entrada y de salida, aunque este último dependerá del tipo de problema que abarquemos. El número de neuronas en las capas ocultas será decisión nuestra, pueden dar resultados distintos dependiendo de este número por lo que en la mayoría de las veces la determinación viene dada por la vía experimental. El único elemento que nos falta ahora es la función de coste. Presentamos tres posibilidades, en caso de que utilicemos la red neuronal para dar respuesta a un problema de regresión buscaremos minimizar la disparidad con los datos de entrenamiento por lo que usaremos (Bishop, 2006): E(w) = 1 2X n||y(xn)−tn||2 Para la clasificación binaria se suele utilizar: E(w) = −X n tnln yn+ (1 −tn) ln(1 −yn) por último, para la clasificación multiclase se utiliza: E(w) = −X nX k tnk log ynk Entrenando las redes neuronales Entrenaremos la redes neuronales mediante un descenso de gradiente, dada la gran cantidad de datos que estas suelen manejar, este suele ser estocástico. Nos encontramos ahora en el problema de encontrar el gradiente en una función definida como en 5.4 lo que resulta no solo complicado teóricamente sino que también muy costoso a nivel computacional, sin embargo, Chapter 6 Conclusions and Future Work General conclusions Given the impossibility of performing a full exploration of the game tree, we have presented 2 practical methods to solve this issue: the one encompassed by Minimax using domain knowledge, and the one proposed by MCTS through simulations. In both cases we are trying to calculate a heuristic for each node which reveals how good the node is. We have seen that a mixed approach that adds up expert knowledge to the one obtained by simulations also brings good results even surpassing algorithms as Alpha-beta improved with a heuristic. It has been shown in this work that the Monte Carlo Tree Search algorithm works in a very solvent way, in environments where it has been proven. It flaunted good results against simple algorithm as well as with expert automatic players with a wide knowledge of the domain in which they are working. The aheuristicity of MCTS allows us to adapt it easily to every game, getting a highly resolutive player in a short time and without the need to inquire in the game. The issues that appear when applying it have also been shown. In particular, we appreciate an important complexity when using it to games which contain cycles, or that do not have a defined length. We also exposed a practical solution to this conflict by sacrificing the aheuristicity. In addition, we have seen that the major waste of computational resources is produced in the simulation phase, and that is in it in where we must make a stronger effort in optimization. We have seen that the more simulations we perform, the higher the reliability of the heuristic calculated for each node. 77 78 Chapter 6. Conclusions and Future Work Objectives review Now we will review, one at the time, each objective in the same order that they were defined in the introduction: 1. Once read this document, the reader, without previous knowledge of the matter, now understands concepts of game theory, data structures, and several solutions given by diverse researchers to the problem of exploring a game tree. Besides, the games that have been used in this research have also been presented. If the reader took the time to review the appendixes, they will have gathered by now concepts of algebra and probability. 2. The reader currently knows the different parts of the Monte Carlo Tree Search algorithm, the way it works, variations and optimizations. This way they understand these same concepts for PMCTS, and also their differences. Moreover, the reader has received the formal proof of why the heuristic value estimation works. 3. We have developed an MCTS based Othello player as well as one PMCTS version. We faced it with Random,Depth First Search and some Alpha-beta versions. During the process we have adapted to each situation to be able to get a good result. 4. Following the same path, we have implemented an automatic player base in each Monte Carlo version to play chess. These have shown not to be as efficient as the ones exposed in the Othello section. Nevertheless, given the low resources they were counting with, they got to offer some good results against Random normally dominating the game although they almost never arrived to a check mate situation. 5. Three powerful tools have been introduce to study the machine learning field: least squares, the perceptron and neural networks. Needful elements in the development of the current most powerful player: AlphaGo. We also explained AlphaGo’s functioning and the roll that MCTS plays. Future work In future lines of work, the simulation’s execution time should be improved. Nowadays, the most common idea to generalize relatively easy calculations is to make them work in parallel in systems with this capacity. The use of graphic accelerators could bring MCTS to a new level, obtaining more 6.3. Future work 79 precise feedback in a lower time. The implementation in systems like CUDA could be a solution to this issue. On the other hand, we think that in chess game, the state space is so big that only with increasing the simulations probably would not be enough. It would be necessary to enhance the power of the system so the simulations are run until the end of the game and also it would be interesting to implement a machine learning system that helps making it more accurate as the time passes. Apéndice A Conceptos de probabilidad Se muestran aquí la definición de diversos conceptos que han sido utilizados a lo largo del documento. Espacio medible. Un espacio medible o probabilizable es el par (Ω,A) dónde Ωes un espacio muestral y Aes un σ-algebra de conjuntos de Ω. (Gonzalez, 2016) σ-álgebra. Dado un espacio muestral Ω, se dice que una familia de subconjuntos A⊂P(Ω) tiene estructura de σ-álgebra si y solo si se verifican: 1. Ω∈ A 2. ∀A∈ A, Ac∈ A 3. ∀{An:n≥1}⊂A, ∞ S n=1 An∈ A Medida de probabilidad. Una función de conjunto P:A → [0,1] es llamada medida de probabilidad si y solo si satisface: 1. P(A)≥0,∀A∈ A 2. P(Ω) = 1 3. ∀{An:n≥1}⊂Atal que Ai∩Aj=∅,∀i6=j P ∞ [ n=1 An!= ∞ X n=1 P(An) (Kolmogorov, 1956) Aplicación medible. Sean (Ω1,A1)y(Ω2,A2)espacios medibles. Se dice que f: Ω1→Ω2es una aplicación medible si y solo si f−1(B)∈ A1∀B∈ A2. (Corral, 2012) 81 82 Apéndice A. Conceptos de probabilidad Función medible. Se llama función medible a toda aplicación medible donde el espacio de destino es (Rn, βn)para algún n. (Corral, 2012) Variable aleatoria. Una variable aleatoria es una función medible f: (Ω,A, P)→(R, β); es decir, donde el espacio inicial es un espacio de probabilidad. (Corral, 2012) Función de distribución. La función F(x)(a) = P(x)(−∞, a) = Px < a donde −∞ y+∞son valores permitidos de a, se llama función de distribución de la variable aleatoria x.(Kolmogorov, 1956) Muestra aleatoria simple. Dada una población Xse llama muestra aleatoria simple de tamaño na la repetición de X1, ..., Xnvariables aleatorias independientes con distribución igual a la de X. Es decir, la función de distribución de la muestra (x1, ..., xn)es F(x1, ..., xn) = n Y i=1 F(xi) donde F(x)es la función de distribución de la población X(Ángel Villegas, 2005) Función de distribución empírica. Dada una realización particular de una muestra (x1, ..., xn), llamamos función de distribución empírica a F∗ n(x) = 0si x < x(1) k nsi x(k)≤x<x(k+1)1si x ≥x(n) donde (x(1), ..., x(n))es la muestra ordenada de menor a mayor.(Ángel Villegas, 2005) Correlación Magnitud que mide el grado de relación existente entre dos variables aleatorias. Es medido por el coeficiente de correlación. Coeficiente de correlación El coeficiente de correlación rde dos variables aleatorias XeYes la media aritmética de los productos de las desviaciones de los valores correspondientes de sus respectivas medias. (Kenney, 1939) r= 1 NP(x−¯x)(y−¯y) σxσy Apéndice B Conceptos de álgebra y análisis Presentamos a continuación definiciones y proposiciones que se han utilizado en el texto. Espacio vectorial. Sea Kun cuerpo y Vun conjunto no vacío; diremos que Ves un espacio vectorial sobre Ksi: 1. En Vhay definida una operación interna, que denotaremos por +, de forma que (V, +) es un grupo abeliano, es decir, verifica estas propiedades: a)(u+v) + w=u+ (v+w); ∀u, v, w ∈V b)u+v=v+u;∀u, v ∈V c)∃0∈Vtal que 0 + v=v+ 0 = v;∀v∈V d)∀v∈V∃−vtal que v+ (−v)=(−v) + v= 0 2. En Vhay definida una operación externa de K, que denotaremos por yuxtaposición, verificando: a)a(u+v) = au +av;∀a∈K,∀u, v ∈V b)(a+b)u=au +bu;∀a, b ∈K∀u∈V c)a(bu)=(ab)u;∀a, b ∈K∀u∈V d)1u=u;∀u∈Udonde 1es la unidad para el producto en K los elementos del espacio vectorial suelen llamarse vectores, mientras que a los del cuerpo Klos llamaremos escalares. (Merino y Santos, 2006) Independencia lineal. Diremos que un conjunto de vectores {v1, v2, ..., vn} son linealmente independientes si de cada combinación lineal a1v1+ ...+anvn= 0 de deduce que a1=... =an= 0.(Merino y Santos, 2006) Sistema de generadores. Un conjunto de vectores Sse dice que es un sistema de generadores del espacio vectorial Vsi todo vector de V es combinación lineal de los vectores de S.(Merino y Santos, 2006) 83 84 Apéndice B. Conceptos de álgebra y análisis Base de un espacio. Dado un espacio vectorial V, un subconjunto B⊆Ves una base de Vsi 1. B es linealmente independiente. 2. B es sistema de generadores de V Dimensión de un espacio vectorial. Llamamos así al número de vectores en cualquiera de las bases.(Merino y Santos, 2006) Subespacio vectorial. Sea Vun espacio vectorial sobre Ky sea Uun subconjunto no vacío de V. Decimos que Ues un subespacio vectorial de Vsi se verifican las siguientes condiciones: 1. ∀u, v ∈Uu +v∈U 2. ∀u∈U∀a∈K, au ∈U Espacio afín. Dado un conjunto no vacío Ay un espacio vectorial Vdiremos que Aes un espacio afín sobre Vsi se tiene definida la aplicación A×A → V que a cada par de elementos de A,(A, B), le hace corresponder un único vectores ~ AB, y que verifica las dos siguientes propiedades: 1. Para cada A∈ A y cada v∈Vexiste un único elemento B∈ A tal que ~ AB =v. 2. Para cada terna A, B, C ∈ A ocurre ~ AB +~ BC =~ AC diremos que Ves el espacio vectorial asociado y definimos la dimensión del espacio afín como la dimensión del espacio vectorial asociado. (Merino y Santos, 2006) Hiperplano. Llamaremos variedad afín a la generalización de espacio vectorial a espacio afín, y llamaremos hiperplano a una variedad afín de dimensión n−1en un espacio de dimensión n.(Merino y Santos, 2006) Traza de una matriz. Suma de los elementos de la diagonal de una matriz. Dada una matriz Adenotaremos su traza como tr(A)la traza cumple las siguientes propiedades: 1. tr(A) + tr(B) = tr(A+B) 2. atr(A) = tr(aA)para todo aescalar 3. tr(A) = tr(At) 4. tr(AB) = tr(BA) 85 Norma de un vector. Dado un vector udefinimos su norma como: ||u|| =√< u, u > (Merino y Santos, 2006) Derivada. Sea I⊆Run intervalo, f:I→Runa función y c∈I. Decimos que un número real Les la derivada de Fen csi dado cualquier ε > 0existe δ(ε)>0tal que si c∈Isatisface 0<|x−c|< δ(ε) entonces  f(x)−f(c) x−c−L < ε En este caso diremos que fes diferenciable en c y escribimos f0(c). Podemos calcular esto entonces como: f0(c) = l´ım h→0 f(c+h)−f(c) h . (Bartle y Shebert, 1927) Derivada direccional. En Rngeneralizamos el concepto de derivada y lo llamamos derivada direccional: Dvf= l´ım h→0 f(x+hv)−f(x) h (Bombal et al., 1988) Gradiente. Llamaremos gradiente de fy lo denotaremos por ∇fal vector: (De1f, ..., Denf) Siendo e1, ..., enlos vectores de la base canónica.(Bombal et al., 1988)