Tutor de algoritmos de juegos

1 2 3 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA GRADO EN INGENIERÍA INFORMÁTICA (COMPUTACIÓN) TUTOR DE ALGORITMOS DE JUEGOS ADVERSARIAL SEARCH TUTOR Realizado por Cristina Gómez Gómez Tutorizado por José Antonio Montenegro Montes Departamento Lenguajes y Ciencias de la Computación UNIVERSIDAD DE MÁLAGA MÁLAGA, Septiembre 2016 Fecha defensa: El Secretario del Tribunal 4 5 Resumen: La asignatura Sistemas Inteligentes, impartida en los tres grados de Ingeniería Informática en la Universidad de Málaga, es un primer contacto del alumno de informática con la Inteligencia Artificial (IA). La asignatura tiene como objetivo mostrar al alumno una serie de técnicas de IA, explicando detalladamente el funcionamiento de los algoritmos más representativos de cada técnica. Para conseguir tal fin se realiza una doble tarea, inicialmente los algoritmos son explicados en clase y se realizan ejercicios de una duración apropiada para poder ser realizados a mano y en el laboratorio ejecutamos los algoritmos sobre problemas más complejos para ver la aplicación del algoritmo a problemas más extensos. Hasta el momento los profesores de la asignatura han desarrollado una serie de prácticas sobre algunos algoritmos de la asignatura. La idea general es actualizar las prácticas con problemas actuales. El objetivo de este proyecto es la generación de una práctica, en concreto del tema de Juegos, que permita de forma detallada al alumno observar y realizar el seguimiento de los algoritmos Minimax y Expectimax. En concreto el juego escogido es el 2048. Palabras: Inteligencia Artificial, Juegos, 2048, Heurísticas, Algoritmos, Minimax, AlfaBeta, Expectimax Abstract: The course “Intelligent Systems”, taught in the three degrees of Computer Science at the University of Málaga, is student's first contact with the Artificial Intelligence (AI). The course aims to show students a number of AI techniques, explaining in detail the most representative algorithms of each technique. In order to achieve this purpose a double task is carried out, initially algorithms are explained in class and some exercises with an appropiate duration are made by hand and later, in laboratory, we run these algorithms to solve more complex problems in order to see the application of the algorithm to more extensive problems. Until now, the course professors have developed a number of practices about some algorithms. The general idea is to update practices with current problems. The aim of this project is to develop a practice that allows the student to observe in detail and track the Minimax and Expectimax algorithms. Specifically, the chosen game is 2048. Keywords: Artificial Intelligence, Games, 2048, Heuristics, Algorithms, Minimax, Alpha-Beta, Expectimax 6 7 ÍNDICE Contenido Introducción ............................................................................................................... 9 1.1 Estado del arte .................................................................................................. 9 1.2 Motivación y objetivos ......................................................................................10 1.3 Tecnologías a utilizar .......................................................................................10 1.4 Contenido y estructura de la memoria .............................................................11 Inteligencia artificial para Juegos ...............................................................................12 2.1 Definición formal de un juego ...........................................................................12 2.2 Algoritmos ........................................................................................................13 2.2.1 Algoritmo minimax .....................................................................................13 2.2.2 Algoritmo Alfa-beta ....................................................................................16 2.2.3 Algoritmos expectiminimax y expectimax ..................................................19 Inteligencia artificial aplicada al 2048 ........................................................................23 3.1 Juego 2048 ......................................................................................................23 3.2 Definición formal del 2048 ................................................................................24 3.3 Funciones de evaluación: heurísticas ..............................................................26 3.3.1 Heurísticas para 2048 ...............................................................................26 8 3.4 Aplicación de algoritmos al juego .....................................................................33 Diseño de la aplicación .............................................................................................36 Resultados .................................................................................................................42 Conclusiones .............................................................................................................53 Referencias bibliográficas ..........................................................................................55 Anexos técnicos .........................................................................................................56 Anexo A. Implementación ..........................................................................................56 Implementación del juego ......................................................................................56 Implementación de los algoritmos ..........................................................................71 Implementación gráfica ..........................................................................................72 Anexo B. Manual de usuario ......................................................................................74 9 1 Introducción 1.1 Estado del arte Los juegos siempre han sido un ámbito de interés en el campo de la inteligencia artificial. Muchos de los pioneros de la informática ya intentaron trabajar con el problema del ajedrez. Por ejemplo, Alan M. Turing, considerado padre de la informática, desarrolló el primer programa de ordenador de la historia para jugar al ajedrez, a finales de los años 40. Otros también abordaron el problema del ajedrez, como Konrad Zuse, Noibert Wiener y Claude Shannon, conocidos por sus importantes aportaciones en la informática. ¿Qué tenía de especial para los primeros informáticos el ajedrez? ¿Por qué sigue siendo de tanto interés la aplicación de la inteligencia artificial a juegos? Los juegos son interesantes porque son demasiado difíciles para resolverlos. Por ejemplo, actualmente la complejidad de árbol de juego del ajedrez se calcula en torno a 10123. Esto, además, nos hace darnos cuenta que la eficiencia debe ser importante, pues el árbol de juego suele ser de dimensiones realmente considerables. A partir de su nacimiento por aquel entonces, la inteligencia artificial ha conseguido avanzar considerablemente, de manera que las máquinas ya consiguen ganar a los mejores jugadores del mundo en algunos juegos, como el ajedrez o el backgammon. Uno de los retos en la Inteligencia Artificial durante las últimas décadas ha sido el Go debido a su gran complejidad. Hasta este mismo año había sido imposible que una máquina venciera al mejor jugador de este juego, sin embargo, el pasado mes de marzo el programa AlphaGo, desarrollado por Google, ganó al campeón coreano del juego de mesa Go, Lee Sedol. Esto demuestra que éste es un campo que continúa en desarrollo, alcanzándose logros hasta el día de hoy. La inteligencia artificial ha ido ganando terreno en los juegos de tablero. En 1979, el programa BKG de Hans Berliner vence al campeón del mundo en Backgammon. Años más tarde, en 1994, cayeron las damas a manos de Chinook. Poco después, en 1997, el ajedrez gracias a Deep Blue, la supercomputadora que venció al campeón del mundo de ajedrez por aquel entonces, Gary Kaspárov. 16 2.2.2 Algoritmo Alfa-beta La poda alfa beta es una optimización del algoritmo minimax, pues reduce el número de nodos evaluados en el árbol de juego de dicho algoritmo. 2.2.2.1 Desarrollo del algoritmo En la poda alfa-beta se utilizan dos parámetros que actuarán de cotas sobre el valor minimax de un nodo (α,β): ● Para un nodo MAX: α valor de la mejor elección para MAX (valor más alto) que hemos encontrado en el camino hasta ahora ● Para un nodo MIN: β valor de la mejor elección para MIN (valor más bajo) que hemos encontrado en el camino hasta ahora El algoritmo actualiza los valores de a y B conforme se ejecuta, recorriendo el árbol. ¿En qué condiciones se realiza la poda? Sea v el valor de un nodo:  Si el nodo es MAX y v ≥ β Se puede podar por debajo de dicho nodo.  Si el nodo es MIN y v ≤ α Se puede podar por debajo del nodo. En la siguiente subsección aparece un breve ejemplo que ayudará a comprender su funcionamiento. El pseudocódigo del algoritmo será el siguiente: function ALPHA-BETA-SEARCH(state) returns an action v = MAX-VALUE(state, -∞, +∞, depth) return the action in ACTIONS(state) with value v function MAX-VALUE(state,α,β, depth) return a utility value if node is a terminal node or depth == 0 return the heuristic value of node v := -∞ for each child of node v := max(v, MIN-VALUE(child, α, β, depth-1)) 17 if v ≥ β then return v α := max(α, v) return v function MIN-VALUE(state,α,β,depth) return a utility value if node is a terminal node or depth == 0 return the heuristic value of node v := +∞ for each child of node v := min(v, MAX-VALUE(child, α, β, depth-1)) if v ≤ α then return v α := min(α, v) return v 2.2.2.2 Ejemplo Ilustración 3: Ejemplo de ejecución del algoritmo Alfa-Beta a) A partir del nodo B, se genera su primer hijo, que es terminal y su función de utilidad nos da el valor 3. Por tanto, como B es un nodo MIN, sabremos que su valor final será menor o igual a 3, es decir, estará en el rango [-∞, 3]. Por ello, β = 3. 18 b) Se genera el siguiente hijo de B, cuyo valor es 12. Como 12 es mayor que el β actual, el valor de β no cambia. c) Se genera el siguiente hijo del nodo B, con valor 8 y ocurre lo mismo que en caso anterior. Como ya se han generado todos los hijos del nodo B, ya podemos darle definitivamente el valor de β, en este caso su valor será 3. Al establecer un valor para el nodo B, ya podemos saber que el valor del nodo A es 3 o más, pues es un nodo MAX. Por tanto, estará en el rango [3, ∞], y α = 3. d) Se generan el primer hijo de C, el segundo hijo del nodo raíz A. Su valor es 2, por tanto, como C es un nodo MIN, sabremos que su valor definitivo será menor o igual que 2, es decir, está en el rango [-∞,2]. Por ello, β = 2. Como sabemos que el nodo A tendrá un valor superior a 3, porque el nodo B es mejor, podemos descartar el nodo C, pues tendrá un valor menor que 3. Por eso no es necesario que generemos sus hijos restantes, es decir, se poda el árbol. e) Pasamos a generar los hijos del nodo D, tercer hijo del nodo raíz. Su valor es 14, por tanto, como C es un nodo MIN, sabremos que su valor definitivo será menor o igual que 14, es decir, está en el rango [-∞,14]. Por ello, β = 14. Como el valor de D será menor de 14, el valor de A, como mucho podrá valer 14, por tanto, estará en el rango [3,14]. f) Al generar los siguientes hijos de D, le daremos el valor 2, pues es el menor valor de sus hijos. Finalmente, como el nodo A es MAX, seleccionará el valor 3, del nodo B, pues es el mayor. Como vemos, se ha conseguido eliminar una parte del árbol. 2.2.2.3 Eficiencia La eficiencia de la poda Alfa-Beta depende del orden en el que se examinan los sucesores, es decir, el algoritmo se comportará de forma más eficiente si examinamos primero los mejores sucesores. Tal y como hemos indicado antes, la complejidad del algoritmo minimax es O(bm). Si lográramos ordenar los sucesores, el algoritmo Alfa-Beta tendrá solamente que examinar O(bm/2). Esto implica que Alfa-beta podrá alcanzar un nivel aproximadamente dos veces mayor que Minimax en la misma cantidad de tiempo. Complejidad Minimax Poda Alfa-Beta Tiempo O(bm) O(bm/2)* Espacio O(bm) O(bm) Tabla 1: Comparativa de la complejidad entre Minimax y Expectimax *Con una ordenación perfecta en los sucesores 19 Existen otras variaciones del algoritmo como: 1) Búsquedas con aspiración 2) Búsqueda sobre la variación principal 3) Profundización progresiva 4) Tablas de transposición 5) Procedimiento MTG(f) 2.2.3 Algoritmos expectiminimax y expectimax Existen juegos que incluyen un elemento aleatorio, juegos estocásticos. Uno de los juegos más comunes de este tipo es el Backgammon, pero también podemos incluir el 2048 en este tipo de juegos, como veremos a partir de su descripción en el siguiente capítulo. Por ello nos son de interés algoritmos que tengan en cuenta esta aleatoriedad. 2.2.3.1 Algoritmo expectiminimax El expectiminimax es una variante del algoritmo Minimax. En el Minimax tradicional tenemos nodos “MIN” y nodos “MAX”, mientras que en el expectimax tendremos además nodos “CHANCE”, o “posibilidad”. Dichos nodos “CHANCE” se intercalan con los nodos MIN y MAX. En dichos nodos, en lugar de tomar el máximo o el mínimo de los valores de utilidad de sus hijos, como se hace en el Minimax, se toma una media ponderada de los valores de sus hijos, en la cual los pesos serán las probabilidades de los sucesores. La forma de intercalar dichos nodos depende de cada juego. Cada turno del juego se evalúa como un nodo “MAX”, que representa el turno del jugador, un nodo “MIN”, que representa al adversario, o un nodo “CHANCE”, que representa un jugador o efecto aleatorio. Por ejemplo, consideremos un juego en el que cada ronda consta de un solo tiro de dados y, a continuación, las decisiones tomadas por el primer jugador de la IA, y luego otro oponente inteligente. El orden de los nodos en este juego se alterna entre " CHANCE ", " MAX " y " MIN ". 20 Ilustración 4: Ejemplo del algoritmo Expectiminimax Explicaremos cómo funciona el algoritmo mediante el ejemplo anterior. 1. En primer lugar, se genera el árbol, al igual que en el algoritmo Minimax. Mediante una función de utilidad se da valor a las hojas de este, situadas en el nivel 4. 2. En el nivel 3 tenemos nodos MIN, por lo que cada nodo seleccionará el menor valor de los valores de sus hijos, siendo 2,4,0 y -2 los valores escogidos. 3. En el nivel 2, los nodos son de tipo CHANCE. ¿Cómo se calculará su valor? Situémonos en el nodo de la izquierda de nivel dos. Calcularemos su valor de la siguiente manera: 𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 2 + 0.5 ∗ 4 = 1 + 2 = 3 Por tanto, su valor esperado será 3. Para el nodo de la derecha tendremos: 𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑_𝑣𝑎𝑙𝑢𝑒 = 0.5 ∗ 0 + 0.5 ∗ (−2)= −1 Por lo que su valor será -1. 4. El nodo de nivel 1, la raíz, es de tipo MAX, por lo que seleccionará el mayor valor de ambos, el 3. Este ejemplo es bastante sencillo y, además las probabilidades son las mismas para todos los hijos, lo que correspondería a una media simple, sin embargo, no siempre es así, pues la probabilidad dependerá del juego en concreto. 21 2.2.3.1.1 Pseudocódigo function expectiminimax(node, depth) if node is a terminal node or depth = 0 return the heuristic value of node if the adversary is to play at node // Return value of minimum-valued child node let α := +∞ foreach child of node α := min(α, expectiminimax(child, depth-1)) else if we are to play at node // Return value of maximum-valued child node let α := -∞ for each child of node α := max(α, expectiminimax(child, depth-1)) else if random event at node // Return weighted average of all child nodes' values let α := 0 for each child of node α := α + (Probability[child] * expectiminimax(child, depth-1)) return α 2.2.3.2 Algoritmo expectimax En el caso del expectimax, sólo tendremos nodos MAX y nodos CHANCE, no habrá nodos MIN. 2.2.3.2.1 Pseudocódigo function expectimax(node, depth) if node is a terminal node or depth = 0 return the heuristic value of node if the agent is MAX // Return value of maximum-valued child node let α := -∞ foreach child of node α := max(α, expectimax(child, depth-1)) else if random event at node // Return weighted average of all child nodes' values let α := 0 foreach child of node 22 α := α + (Probability[child] * expectimax(child, depth-1)) return α Un inconveniente de estos algoritmos es que no se le puede aplicar la poda alfa-beta debido a que debemos expandir todos los hijos de un nodo para calcular su valor, ya que dicho valor será una media ponderada de los valores de los hijos. 23 3 Inteligencia artificial aplicada al 2048 Una vez vista la forma de definir formalmente los juegos y los algoritmos usados para resolverlos, pasamos a definir el 2048 basándonos en los conceptos anteriores y posteriormente a aplicar los algoritmos vistos. Para ello, antes es necesario conocer dicho juego. 3.1 Juego 2048 El 2048 es un juego desarrollado en marzo de 2014 por el joven desarrollador italiano Gabriele Cirulli que alcanzó una gran popularidad. El objetivo del juego es conseguir una casilla cuyo valor sea 2048, de ahí su nombre, deslizando y combinando las casillas del tablero. En su versión original, el tablero contiene 4x4 casillas las cuales, a su vez, contienen un número, de manera que las casillas tendrán distintos colores dependiendo del número que contengan. Inicialmente el tablero contendrá sólo dos casillas, con valor 2 o 4. A partir de ellas podremos hacer algún movimiento hacia alguna dirección. Mediante las teclas de dirección del teclado podemos mover las casillas, deslizándolas por la cuadrícula. De esta manera podemos mover las casillas deslizándolas hacia posiciones vacías. Si dos casillas de igual valor colisionan en un movimiento se combinan en una nueva casilla cuyo valor será la suma de los valores colisionados. Por ejemplo, si dos baldosas con el número 8 colisionan, se formará una con valor 16. Después de realizar un movimiento aparece una casilla nueva en un lugar vacío del tablero, que contendrá el número 2 (en un 90% de los casos) o el número 4 (en el 10% restante). Se acumula una puntuación, que comienza en cero y se incrementa al combinar dos casillas, con el valor de dicha combinación. 24 El usuario ganará el juego si consigue obtener una casilla con el número 2048. Sin embargo, si no se puede hacer movimientos, es decir, ya no quedan lugares vacíos y no existen casillas adyacentes con el mismo valor, el juego termina. Ilustración 5: Ejemplos de tableros del 2048 Inicialmente el juego fue desarrollado en el lenguaje Javascript, estando disponible su código en el siguiente enlace: https://github.com/gabrielecirulli/2048 Posteriormente se lanzó para smartphones, en Android e iOS. Debido a que alcanzó una popularidad abrumadora han sido numerosas las diferentes implementaciones, en múltiples lenguajes y las diferentes versiones diseñadas a partir de este juego, en parte ambas posibilitadas por el fácil acceso al código original de Gabriel Cirulli. Como digo, existen múltiples implementaciones, desde las que representan el tablero con un sólo número, hasta las que consideran que el tablero es una matriz. Este es un claro ejemplo de que existen diferentes formas de representar el espacio de estados de los juegos. 3.2 Definición formal del 2048 Puesto que ya conocemos cómo se juega y sabemos qué tenemos que definir para aplicar los algoritmos, pasamos a definir formalmente el 2048. 25 Debemos definir el conjunto de estado y los movimientos para el 2048. - Conjunto de estados: matriz de 4x4 que contenga casillas cuyos números sean las potencias de 2, excluyendo el 0. En el estado inicial aparecen dos casillas, las cuales pueden contener los valores 2 o 4. Un estado será objetivo si alguna de las casillas contiene el número 2048. - Movimientos: En este juego los movimientos del usuario son distintos a los del computador. Los movimientos del usuario serán mover las casillas hacia arriba, derecha, abajo o izquierda. Sin embargo, para evitar bucles infinitos en la ejecución de algoritmos de búsqueda, considero que no siempre es posible que el jugador realice los cuatro movimientos. Realizar un movimiento será posible siempre que al realizarlo se deslicen las casillas en el tablero o se combinen, de manera que “cambie” algo en el tablero. Por tanto, si realizar dicho movimiento no supondría ningún cambio, ni se combinan celdas ni se deslizan, ese movimiento no estaría disponible. En el caso del computador, el movimiento a realizar será introducir una casilla con valor 2 o 4 en un lugar vacío. - Test terminal. Un estado será terminal si cumple una de estas dos condiciones: ● alguna de las casillas contiene el número 2048 (estado objetivo) ● no se pueden aplicar movimientos (no existen reglas aplicables), es decir, no quedan lugares vacíos y no existen casillas adyacentes con el mismo valor que puedan agruparse al mover, de manera que no se pueden hacer movimientos. Es necesario también establecer una función de utilidad que dé un valor a los estados terminales, de manera que podamos aplicar los algoritmos vistos en el primer capítulo. Además, hemos visto que en la práctica el método minimax es impracticable excepto en supuestos sencillos pues vemos que realizar la búsqueda completa requerirían cantidades excesivas de tiempo y memoria. Por ello se propone limitar la profundidad de la búsqueda y determinar el valor de los nodos hoja (que en este caso pueden ser no terminales) mediante una función de evaluación heurística. 32 Ejemplo 3 Supongamos ahora que tenemos el siguiente estado: Ilustración 8: Ejemplo para heurísticas 3  Score. Se puede ver en la figura 8, la puntuación actual es 9228.  Casillas vacías El número de casillas vacías es 7.  Similitud o 𝐶𝑒𝑙𝑑𝑎 (0,0): |1024−1024|+ |1024−32|+ |1024−16|+ |1024−4| 4 = 3020 4 = 755 o 𝐶𝑒𝑙𝑑𝑎 (0,1): |32−1024|+ |32−32|+|32−4|+ |32−16|+ |32−4| 5 = 1064 5 = 212.8 o 𝐶𝑒𝑙𝑑𝑎 (0,2): |4−32|+|4−4|+|4−2|+|4−4| 4 = 30 4 = 7.5 o 𝐶𝑒𝑙𝑑𝑎 (0,3): |2−4|+|2−2| 2 = 2 2 = 1 o 𝐶𝑒𝑙𝑑𝑎(1,0): |16−1024|+ |16−32|+ |16−16| + |16−4|+ |16−8| 5 = 1044 5 = 208.8 o 𝐶𝑒𝑙𝑑𝑎 (1,1): |4−1024|+ |4−32|+ |4−4|+ |4−16|+ |4−4|+ |4−8| 6 = 1064 6 = 177.3333 o 𝐶𝑒𝑙𝑑𝑎 (2,0): |8−16|+ |8−4|+|8−8|+|8−2| 4 = 18 4 = 4.5 o 𝐶𝑒𝑙𝑑𝑎 (3,0): |2−8|+ +|2−2| 2 = 6 2 = 3 o 𝐶𝑒𝑙𝑑𝑎 (3,2): |4−4| 1 = 0 1 = 0 𝑆𝑖𝑚𝑖𝑙𝑖𝑡𝑢𝑑 = 1369.9333  Monotonía 𝑀𝑜𝑛𝑜𝑡𝑜𝑛í𝑎 = 1024 ∗ 7 + 16 ∗ 6 + 32 ∗ 6 + 8 ∗ 5 + 4 ∗ 5 + 4 ∗ 5 + 2 ∗ 4 + 0 ∗ 4 + 0 ∗ 4 + 2 ∗ 4 + 0 ∗ 3 + 0 ∗ 3 + 0 ∗ 3 + 4 ∗ 2 + 0 ∗ 2 + 0 ∗ 1 = 7560 33 Heurísticas: Heurística 1 = Score + Monotonía − Similitud + log(Score)∗ Celdas vacías =9228 + 7560 − 1369.9333333333332 + log(9228) ∗ 7 = 15481.976650001723 ≈ 15481.98 Heurística 2 = Monotonía − Similitud + log(Score)∗ Celdas vacías =7560 − 1369.9333333333332 + log(9228) ∗ 7 = 6253.976650001722 ≈ 6253.98 Heurística 3 = Score − Similitud + log(Score)∗ Celdas vacías =9228 − 1369.9333333333332 + log(9228) ∗ 7 = 7921.976650001722 ≈ 7921.98 Heurística 4 = Score + (Celdas vacías ∗ log2𝑚𝑎𝑥)+ Monotonía = 9228 + (7 ∗ log21024) + 7560 = 16858 3.4 Aplicación de algoritmos al juego Una vez hechas las anteriores definiciones podemos aplicar los algoritmos vistos en el segundo capítulo a este juego. Como sabemos, estos algoritmos generan un árbol de juego. Veíamos anteriormente, a modo de ejemplo, parte del árbol del juego de las tres en raya. ¿Cómo sería el árbol para 2048? El jugador MAX sería el usuario, o la IA mientras que el jugador MIN será el computador encargado de colocar una nueva casilla tras cada movimiento del jugador MAX. Como realizan movimientos alternativamente cada nivel del árbol se corresponderá a uno de los jugadores. ¿De qué forma será dicho árbol? ¿Cuántos hijos tendrá cada nodo? Un nodo MIN tendrá tantos hijos como casillas vacías multiplicado por dos, ya que, tras tu turno, el computador podrá poner una ficha en cada posición vacía con valor 2 o con valor 4. Un nodo MAX podrá tener, a lo sumo, cuatro hijos, correspondientes a los cuatro movimientos posibles (arriba, derecha, abajo e izquierda). Sin embargo, si al realizar un movimiento sobre un tablero no se produce ningún cambio, dicho movimiento se considerará no válido para evitar ciclos. 34 Ilustración 9: Parte del árbol de juego de 2048 La figura 9 muestra un ejemplo de árbol del juego, en el que sólo se muestran 8 estados pero que nos ayuda a ver cómo se generaría dicho árbol. Además, nos permite intuir las dimensiones del árbol completo. En el capítulo anterior hemos descrito además del algoritmo Minimax y la poda Alfabeta, el algoritmo expectimax, utilizado en juegos que incluyen un elemento aleatorio. Sin lugar a dudas el 2048 es de este tipo de juegos, ya que la introducción de una nueva casilla tras cada movimiento se realiza de manera aleatoria. Por tanto, es posible utilizar el algoritmo expectimax en el juego 2048, pues en el turno del jugador, estaríamos en un nodo MAX, y en el turno del ordenador, que añade un valor (2 o 4) en una celda aleatoria, estaríamos en un nodo CHANCE. Recordemos que el valor de un nodo CHANCE vendrá dado por una media ponderada de los valores de sus sucesores en la cual los pesos serán las probabilidades de estos. ¿Cuál es la probabilidad de cada movimiento? La probabilidad de que el computador coloque la nueva casilla en un determinado lugar es la misma para todas las casillas. Sin embargo, la probabilidad de que sea 2 es del 90% y de que sea 4 es del 10%. Por tanto, la probabilidad de un movimiento será. - Si se añade un 2: 𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑑𝑎𝑑 = 1 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑐𝑎𝑠𝑖𝑙𝑙𝑎𝑠 𝑣𝑎𝑐í𝑎𝑠 ∗ 0.9 - Si se añade un 4: 𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑑𝑎𝑑 = 1 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑐𝑎𝑠𝑖𝑙𝑙𝑎𝑠 𝑣𝑎𝑐í𝑎𝑠 ∗ 0.1 35 Hay otra cosa a tener en cuenta con el algoritmo Expectimax, pues la función de evaluación heurística debe tener unos requisitos especiales. Con Minimax, la escala de los valores no importa, sin embargo, Expectimax necesita utilizar valores grandes, ya que, al realizar las medias ponderadas progresivamente hacia arriba, los valores se van a ir reduciendo, de manera que si a los nodos terminales se les asocia un valor muy pequeño el valor que llegará a la raíz será siempre 0. Por ello, como para Minimax y Alfa-Beta, no importa la escala, podemos seleccionar funciones de evaluación que asocien números grandes, de manera que las descritas en la sección anterior cumplen esta propiedad. 36 4 Diseño de la aplicación El presente trabajo está diseñado de manera que pueda ser de utilidad en la explicación de los contenidos de la asignatura Sistemas Inteligentes. En la parte práctica de dicha asignatura se utiliza el paquete AIMA, que es un paquete de clases Java que permite definir y resolver problemas de Sistemas Inteligentes de manera que el diseño permite separar la representación del problema de los algoritmos. Por ello, la implementación del 2048 abarcada en este trabajo está elaborada en función de la biblioteca AIMA, de manera que pueda servir como práctica de la asignatura anteriormente citada. Pasamos a mostrar el diagrama UML del proyecto. Sin embargo, por su tamaño es imposible analizarlo en su totalidad, por lo que lo haremos por partes. 37 Ilustración 10: Diagrama UML del Juego 38 La figura 10 muestra las clases necesarias para modelar el juego en sí. La clase Movimiento nos permitirá identificar y diferenciar las diferentes acciones del juego. La clase G2048State identificará el estado del tablero y contendrá los métodos necesarios para realizar los movimientos, calcular las heurísticas... La clase Game2048 implementará la interfaz Game<STATE, ACTION, PLAYER>, del paquete AIMA. En este caso, los estados son de tipo G2048State, las acciones de tipo Movimiento y los jugadores de tipo Integer. En dicha clase se implementan los métodos de la interfaz. Ilustración 11: Diagrama UML de los algoritmos Además, tal y como hemos comentado antes, el algoritmo Minimax es imposible de utilizarlo en la práctica en problemas grandes, pues la complejidad es demasiado alta. Una manera de optimizar dicho algoritmo era limitando la profundidad, por lo que he creado las clases necesarias para usar los algoritmos Minimax y Alfa-beta con limitación de la profundidad. 39 Otro de los algoritmos comentados, el Expectimax, también ha sido implementado con el mismo objetivo. En la figura 11 podemos ver las relaciones entre los algoritmos implementados. Las clases AlphaBetaLimitado, MinimaxLimitado y Expectimax implementan la interfaz AdversarialSearch, implementado los métodos de ésta. En ellas se ejecutan los algoritmos descritos en el presente documento. Para ello hacen uso de un objeto de la clase Game, pues necesitarán una partida. Sin embargo, en la clase Expectimax será de tipo Game2048, pues se usan probabilidades que dependerán del juego en concreto. 40 Ilustración 12: Diagrama UML de la interfaz gráfica 41 Con el fin de implementar la interfaz gráfica se han creado las clases de la figura 12. La clase G2048App implemente la interfaz gráfica y contiene diferentes clases como paneles, frames y ventanas de diálogo, necesarias en la aplicación y se hace del uso de un KeyEventDispatcher, para recoger la entrada por teclado. 48 Ilustración 16: Porcentaje de partidas ganadas usando la heurística 4 Podemos ver cómo, sin lugar a dudas, para las cuatro heurísticas, el algoritmo que mejor funciona, obteniendo un mayor número de partidas ganadas, es el espectimax con diferencia. Con un límite de profundidad 3 vemos cómo claramente empieza a despuntar este algoritmo con la heurística 4 y, para las demás heurísticas basta con establecer el límite de profundidad en 4 niveles para alcanzar un número aceptable de partidas ganadas, destacando sobre los algoritmos Minimax y Alfa-Beta. Vemos cómo, usando el expectimax, en profundidades como 6 y 7 obtenemos un porcentaje muy cercano a 100, cosa que no ocurre con los demás algoritmos. Esto nos muestra lo bien que funciona este algoritmo con este juego, es el más adecuado. Los resultados de Minimax y Alfa-Beta, evidentemente son similares, variando en pocas partidas ya que, como sabemos, el algoritmo Alfa-Beta devuelve el mismo resultado que el Minimax. Sin embargo, debido a la aleatoriedad del turno del computador no siempre se tomarán las mismas decisiones a medida que la partida avanza, de ahí las diferencias. Incluso, para un mismo estado inicial cada ejecución será distinta. Básicamente, con el expectimax podemos alcanzar los mismos resultados que con los demás algoritmos estableciendo un límite de profundidad más pequeño. 30 40 57 53 65 29 38 54 62 66 63 80 87 88 94 0 10 20 30 40 50 60 70 80 90 100 34567 PORCENTAJE DE PARTIDAS GANADAS Heurística 4 Alfa-Beta Minimax Expectimax 49 Las siguientes figuras nos servirán para comparar entre las heurísticas. Ilustración 17: Porcentaje de partidas ganadas usando el algoritmo Alfa-Beta Ilustración 18: Porcentaje de partidas ganadas usando el algoritmo Minimax 51 40 62 69 73 3 17 61 59 76 7 35 32 56 59 30 40 57 53 65 0 10 20 30 40 50 60 70 80 3 4 5 6 7 PORCENTAJE DE PARTIDAS GANADAS PROFUNDIDAD Alfa-Beta Heurística 1 Heurística 2 Heurística 3 Heurística 4 51 41 64 65 75 515 68 71 72 5 40 49 57 62 29 38 54 62 66 0 10 20 30 40 50 60 70 80 3 4 5 6 7 PORCENTAJE DE PARTIDAS GANADAS PROFUNDIDAD Minimax Heurística 1 Heurística 2 Heurística 3 Heurística 4 50 Ilustración 19: Porcentaje de partidas ganadas usando el algoritmo Expectimax Como vemos, una de las mejores heurísticas es la primera, pues destaca sobre las demás en la mayoría de los casos. Cuando el límite de profundidad es más alto, las heurísticas 1 y 2 están bastante igualadas. Sin embargo, cuando el límite de profundidad es bajo (3 o 4), sin duda es mucho mejor la primera. Vemos también que en la mayoría de los casos la peor heurística es la tercera, por lo que no nos conviene usarla si lo que queremos es obtener un porcentaje alto de victorias. Todo esto nos indica que debemos seleccionar la heurística en función de la profundidad y algoritmo que vayamos a usar. Por ejemplo, si queremos usar el Minimax con un límite de profundidad de 3, sin duda deberíamos usar la primera heurística. Hemos comparado los algoritmos y las heurísticas en función al número de partidas ganadas. Sin embargo, otro parámetro de gran interés a analizar es el tiempo que tarda en resolverse la partida. Como se puede intuir, el algoritmo Alfa-Beta, será el más rápido. Para comparar los tiempos entre los diferentes algoritmos según la heurística podemos analizar las siguientes imágenes. 56 84 87 94 97 12 58 80 93 95 10 54 57 78 87 63 80 87 88 94 0 10 20 30 40 50 60 70 80 90 100 34567 PORCENTAJE DE PARTIDAS GANADAS PROFUNDIDAD Expectimax Heurística 1 Heurística 2 Heurística 3 Heurística 4 51 Ilustración 20: Tiempo medio de las partidas para las diferentes heurísticas en función del algoritmo y la profundidad Se ve claramente que el algoritmo más rápido es, tal y como se esperaba, el AlfaBeta. Mientras que el Minimax y el Expectimax tienen unos tiempos muy similares, siendo éste último algo más lento, pues tiene que hacer un número mayor de cálculos correspondientes con las probabilidades. Podemos analizar también cuál de las heurísticas es más rápida o al contrario mediante las siguientes figuras. 52 Ilustración 21: Tiempo medio de las partidas para cada algoritmo Por ejemplo, podemos ver que la heurística más costosa en cuanto al tiempo es la heurística número 3, que además era la que peores resultados obtenía. Por lo que esto nos puede indicar que es mejor descartar dicha heurística, lo que nos indica que la monotonía es una característica muy importante a mantener en el tablero, ya que esta heurística no la tiene en cuenta. 53 6 Conclusiones Durante el presente proyecto se ha desarrollado una aplicación que nos permite aplicar diferentes algoritmos y técnicas de la Inteligencia artificial al juego 2048. Como bien comentábamos en la primera sección, los juegos siempre han sido un reto para la Inteligencia Artificial desde sus inicios, aplicándose cada día tanto a los juegos más novedosos como a los antiguos. Por ello, la asignatura Sistemas Inteligentes se encarga de mostrar dichas técnicas, para lo que hace uso de prácticas de laboratorio. Con el objetivo de actualizar dichas prácticas, se proponía aplicar todos los conceptos estudiados al juego 2048 de manera que la aplicación sirviera como apoyo a la enseñanza de éstos. Esto nos obligaba a definir varios conceptos como los estados, los movimientos, la función de utilidad y una función de evaluación heurística. En este caso han sido propuestas cuatro funciones de evaluación con el objetivo posterior de probar su funcionamiento. Por tanto, para aplicar las técnicas estudiadas a este juego, éste debe definirse de manera formal, definiendo los conceptos antes mencionados, lo que hace necesario un análisis del juego. Una vez definido formalmente el juego, podemos aplicar los algoritmos, en este caso el Minimax, la poda Alfa-Beta y el Expectimax, aplicable únicamente en juegos estocásticos, que incluyan un elemento aleatorio como el 2048. La aplicación creada es una forma de ver lo que nos permiten estos algoritmos. Sus funcionalidades aparecen en el manual de usuario, en el Anexo B. Con el fin de estudiar los resultados y comparar los algoritmos utilizados, se ha realizado una batería de pruebas. A partir de su análisis podemos concluir que el algoritmo que mejores resultados ofrece es el Expectimax, pues con límite de profundidad 7 consigue ganar casi todas las partidas. Sin embargo, es el más lento, siendo el más rápido el Alfa-Beta, como era de esperar. Además, también se hace un análisis de las heurísticas propuestas, dependiendo su buen funcionamiento del límite de profundidad establecido. Como ampliación del trabajo podrían proponerse nuevas heurísticas. 54 Por tanto, se cumplen los objetivos previstos, ya que se ha elaborado la aplicación propuesta, de manera que sirva como práctica de la asignatura y todos los análisis y definiciones que su desarrollo conlleva. 55 Referencias bibliográficas [1] Russell, S. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach (3th ed.). Upper Saddle River, NJ: Prentice Hall.: http://aima.cs.berkeley.edu/ [2] What is the optimal algorithm for the game 2048?. Stackoverflow.com. [Fecha de consulta: 10 agosto 2016] Disponible en: http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-forthe-game-2048 [3] Cirulli, G. gabrielecirulli/2048. GitHub. [Fecha de consulta: 10 agosto 2016]. Disponible en: https://github.com/gabrielecirulli/2048?files=1 [4] Zettlemoyer, L. (2011). Artificial Intelligence: Adversarial Search. [Fecha de consulta: 10 agosto 2016]. Disponible en: https://courses.cs.washington.edu/courses/cse473/11au/slides/cse473au11adversarial-search.pdf [5] Java Platform SE 7. (2016). Docs.oracle.com. [Fecha de consulta: 10 agosto 2016]. Disponible en: https://docs.oracle.com/javase/7/docs/api/ 56 Anexos técnicos Anexo A. Implementación El presente trabajo está diseñado de manera que pueda ser de utilidad en la explicación de los contenidos de la asignatura Sistemas Inteligentes. En la parte práctica de dicha asignatura se utiliza el paquete AIMA, que es un paquete de clases Java que permite definir y resolver problemas de Sistemas Inteligentes de manera que el diseño permite separar la representación del problema de los algoritmos. Por ello, la implementación del 2048 abarcada en este trabajo está elaborada en función de la biblioteca AIMA, de manera que pueda servir como práctica de la asignatura anteriormente citada. Implementación del juego Clase Movimiento Nos servirá para identificar las acciones del juego. En este caso vamos a diferenciar dos tipos de movimientos: el que hace el usuario y el que hace el ordenador. 1. Mover las fichas: puede ser en 4 direcciones distintas (arriba, derecha, abajo e izquierda) 2. Añadir una ficha nueva. La clase contendrá 4 variables que nos permitirá identificar el movimiento: ● boolean mover: true si movemos, false si añadimos ● int x: contendrá la coordenada x de la casilla en el caso de añadir una celda nueva ● int y: contendrá la coordenada y de la casilla en el caso de añadir una celda nueva ● int movimiento: 57 o si el movimiento trata de mover las fichas, esta variable contendrá la dirección o si el movimiento trata de añadir una celda nueva, contendrá el valor (2 o 4) de ésta Por lo tanto, tenemos dos constructores, uno para cada tipo de movimiento. Clase G2048State Nos permite identificar el tablero de la partida y contiene los métodos necesarios para su tratamiento. 64 Move Este método recibe una variable de tipo Movimiento, que indicará el movimiento a realizar sobre el tablero. En el caso de que la variable mover del objeto action sea true, llamaremos al método moveCells con la dirección que almacena dicho objeto. En el caso de que sea false, significa que tendremos que añadir una nueva celda, por lo que llamamos al método rellenarCelda, en las coordenadas y con el valor que nos indica action. 65 Getters getUtility() Da un valor de “cómo de bueno es el estado”. En este caso, si el estado no es terminal he usado una función heurística. 66 Similitud Puesto que nos interesa que los números iguales o, al menos, parecidos estén cercanos, obtengo las distancias entre los vecinos de cada celda, acumulando la media de las distancias para cada celda con sus vecinos. Matriz valores Como se ha comentado en la sección de Heurísticas, uno de los trucos principales que la mayoría de jugadores sigue al jugar al juego es colocar la casilla con mayor valor en una esquina y, a partir de ella ir decreciendo su valor. Normalmente también evitaremos que las casillas con valores más pequeños queden aisladas. Esta heurística nos permite tender a tener un tablero más organizado. Para ello, con este método, sumamos los valores de las casillas del tablero ponderados de la manera siguiente: 67 7 6 5 4 6 5 4 3 5 4 3 2 4 3 2 1 68 Heurísticas Calculan las diferentes heurísticas propuestas a partir de los métodos anteriores. 69 Clone isEqual toString 70 Clase Game2048 Esta clase implementará la interfaz Game<STATE, ACTION, PLAYER>. En este caso, el estado vendrá dado por la clase G2048State. Las acciones será de la clase Movimiento. Los jugadores (humano y ordenador) serán representados por enteros. 71 Implementación de los algoritmos Además, tal y como hemos comentado antes, el algoritmo Minimax es imposible de utilizarlo en la práctica en problemas grandes, pues la complejidad es demasiado alta. Una manera de optimizar dicho algoritmo era limitando la profundidad, por lo que he creado las clases necesarias para usar los algoritmos Minimax, Alfa-beta y Expectimax con limitación de la profundidad. El código de los algoritmos Minimax y Alfa-beta es similar al utilizado en las clases que proporciona AIMA, simplemente se le introduce la opción del límite de profundidad. Para ello debemos añadir un argumento a las funciones minValue, maxValue, la profundidad e ir decrementándolo en cada llamada que se haga a las funciones, de manera que cuando se alcance una profundidad igual a 0, se considere que dicho estado es un nodo hoja y se devuelva su evaluación, como si se tratara de un estado terminal. 72 if (game.isTerminal(state) || depth==0 ) return game.getUtility(state, player); En el caso del algoritmo Expectimax, se usa la misma función maxValue del algoritmo Minimax limitado y debe implementarse la función expValue, pues no es proporcionado por AIMA. Implementación gráfica La clase G2048App contiene el código asociado a la interfaz gráfica. A su vez contiene clases asociadas a los paneles, frames y dialogs de los que hace uso. Describo a continuación lo más relevante del proyecto: la clase GPanel, encargada de dibujar el tablero y el método solveAndPaint cuyo objetivo es resolver la partida e ir mostrando la ejecución de la misma. Clase GPanel Los métodos getTileColor y getTextColor devolverán el color del fondo de la celda y del número de la misma en función de dicho valor. Para dibujar el tablero usaremos dos bucles for anidados. En las variables x e y tendremos la posición a dibujar, y variarán en función del tamaño del marco (variable marco) y del tamaño de la celda (tamCelda). Mediante el método anterior getTileColor, obtendremos el color de la celda, para posteriormente usar la función fillRect en la posición (x,y). Para dibujar el valor dentro de la casilla, en primer lugar lo pasamos a String y calculamos, mediante funciones de FontMetrics su anchura y altura, para poder dibujarlo centrado en la celda. Una vez conocidos dichos parámetros, pasaremos a dibujar su valor mediante la función drawString. 73 Finalmente, tras dibujar el tablero, se comprueba si es un estado terminal para mostrar los mensajes "¡Has ganado!" o "¡Has perdido!" en los casos correspondientes. Debajo del tablero se muestra la puntuación actual. Método solveAndPaint() Otro método relevante del proyecto es el solveAndPaint, cuyo objetivo es, como su nombre indica, resolver y pintar el tablero a medida que va eligiendo los movimientos. Por ello es necesario que se lance una hebra. En primer lugar se eligen el algoritmo y la heurística a utilizar accediendo a la opción seleccionada en un ComboBox. Posteriormente, hasta que se alcance un estado terminal,se hace uso del método makeDecision que tienen las clases de los algoritmos. Dicho método devolverá el movimiento a realizar. Además también se llama al método nuevaCelda, para colocar una celda nueva después de ejecutar el movimiento devuelto por el método makeDecision. En cada iteración del bucle se llamará a repaint(), de manera que se volverá a dibujar el tablero, actualizándose. Existe las opciones de escribir los movimientos en un fichero, siempre que la opción recorder, esté activada. El método proposeMove() es similar a este, sin embargo sólo devuelve un movimiento, no es necesario un bucle y, por tanto, no es necesario lanzar una hebra. El código restante hace referencia a los diferentes elementos de las ventanas para las distintas funcionalidades de la aplicación. Existen métodos correspondientes a la lectura y escritura de los tableros en ficheros, que permiten la funcionalidad de guardar y reproducir partidas. Hay varias clases correspondientes a los JFrames, JDialog y JPanel utilizados, que hacen uso de los múltiples diversos componentes de Java Swing para la composición de la interfaz como JMenu, JFileChooser, JButton, JComboBox, JCheckBoxMenuItem, JLabel, JScrollPanel… entre otros. Para recoger la entrada de teclado mediante las flechas en el juego, se hace uso de la clase KeyEventDispatcher ya que KeyListener, utilizado en las prácticas de la asignatura, no funciona al tener varios paneles. De esta manera también sirve de ejemplo, pues es una manera alternativa de recoger la entrada por teclado. En caso de querer consultar el código al completo, se recomienda acceder al proyecto Java. 80 Ilustración 30: Menús para guardar partidas Podemos elegir el nombre del fichero y dónde guardarlo, mediante “Elegir ubicación” en el mismo menú (figura 30). En ese caso se abrirá un explorador de archivos que nos permitirá elegir dónde vamos a guardar el archivo y el nombre de este (figura 31). Ilustración 31: Explorador para elegir ruta y nombre del fichero Si no elegimos ningún nombre ni ubicación, el fichero tendrá como nombre la fecha y hora en el que es creado y se almacenará en la ruta de la aplicación. Este proceso podemos realizarlo en cualquier momento de la partida, no es necesario que se comience a guardar la partida desde el inicio. Cuando queramos reproducir una partida almacenada debemos pulsar “Elegir archivo” dentro del menú “Reproducir” (figura 32). Ilustración 32: Menú para repetir partidas 81 Una vez pulsado se abrirá un explorador de archivos que nos permitirá seleccionar el fichero que contenga la partida que deseamos reproducir. Al seleccionar el archivo de la partida se abrirá una ventana nueva con el aspecto mostrado en la figura 33. Ilustración 33: Ventana de repetición de una partida Veremos el tablero inicial, el primero que se grabó. En este caso se trata del tablero inicial del ejemplo anterior. A partir de éste podremos reproducir la partida de diferentes formas. Al clicar en el botón “Paso” se ejecutará un solo paso, tal y como indica su nombre. Si queremos reproducir la partida al completo, podemos elegir la velocidad entre sus pasos mediante la barra central y posteriormente pulsar en “Resolver”. Cuanto más a la derecha desplacemos la barra más rápido se reproducirá. Si únicamente queremos 82 ver la solución obtenida debemos pulsar “Solución”. Además, a medida que se reproduce la partida también veremos el Score actualizado. Pulsando “Solución” en el ejemplo anterior obtendremos: Ilustración 34: Tablero obtenido tras reproducir la partida guardada Podemos ver que es la misma solución obtenida durante la ejecución de la partida. Otra funcionalidad de la aplicación es la posibilidad de realizar pruebas. Para ello debemos seleccionar la opción “Realizar pruebas” del menú Pruebas. Ilustración 35: Menú para realizar pruebas Una vez seleccionado se abrirá una ventana nueva con el aspecto de la figura 36. Como vemos en la figura 37, podremos seleccionar el algoritmo, la heurística, la profundidad y el número de pruebas a realizar. Una vez seleccionadas las opciones deseadas pulsamos “Iniciar pruebas”. Se realizarán tantas partidas como se haya 83 seleccionado, y se indicará si se ha ganado o perdido y el porcentaje de ganadas. Cuando se concluyan todas, además aparecerá una media del tiempo de las partidas en segundos. Ilustración 36: Ventana para la realización de pruebas Ilustración 37: Ejemplo de una batería de pruebas Mientras se están ejecutando las pruebas podemos seguir jugando en la ventana principal del juego.