Desarrollo de estrategias de Inteligencia Artificial para el entorno dinámico y colaborativo Geometry Friends
Abstract
Geometry Friends es un complejo juego de plataformas en el que dos figuras geo- métricas deben alcanzar diamantes prestando atención a los diferentes obstáculos de cada nivel. Cada año, participantes de distintas universidades desarrollan nuevos agentes inteligentes que son capaces de resolver correctamente una gran variedad de niveles, y estos participan en competiciones organizadas por los creadores del juego y que se celebran en importantes conferencias internacionales de Inteligencia Artificial. Existen tanto modos de juego individuales, en los que solo participa una de las figuras geométricas, como cooperativos. Nuestro objetivo en este trabajo es el desarrollo de agentes que funcionen tanto de manera individual como cooperativa y que sean capaces de competir con los mejores agentes de competiciones pasadas, para poder participar en la competición de este año, que se celebrará en agosto. Para ello, exploramos qué técnicas de Inteligencia Artificial han sido más fructíferas en las competiciones pasadas y buscamos la forma de mejorar los resultados de estos agentes mediante diferentes estrategias. Además, desarrollamos un sistema que permite explicar las acciones que toman nuestros agentes. Finalmente, comprobamos mediante diferentes pruebas que nuestros agentes logran superar al jugador humano medio y a todos los agentes anteriores en todas las modalidades de juego.
Full text
Desarrollo de estrategias de Inteligencia Artificial para el entorno dinámico y colaborativo Geometry Friends Development of Artificial Intelligence techniques for the dynamic and collaborative environment Geometry Friends Trabajo de Fin de Grado Curso 2022–2023 Autores Alberto Almagro Sánchez Juan Carlos Llamas Núñez Directores Belén Díaz Agudo Antonio Alejandro Sánchez Ruiz-Granados Doble Grado en Ingeniería Informática y Matemáticas Facultad de Informática Universidad Complutense de Madrid
Desarrollo de estrategias de Inteligencia Artificial para el entorno dinámico y colaborativo Geometry Friends Development of Artificial Intelligence techniques for the dynamic and collaborative environment Geometry Friends Trabajo de Fin de Grado en Ingeniería Informática Autores Alberto Almagro Sánchez Juan Carlos Llamas Núñez Directores Belén Díaz Agudo Antonio Alejandro Sánchez Ruiz-Granados Convocatoria: Junio 2023 Doble Grado en Ingeniería Informática y Matemáticas Facultad de Informática Universidad Complutense de Madrid 28 de mayo de 2023
Dedicatoria A nuestros padres, por su incondicional apoyo durante todos estos años. iv
Agradecimientos A nuestros tutores, por los consejos y orientaciones que nos han dado durante toda la realización del trabajo. A las personas que han dedicado su tiempo a aprender a jugar y permitirnos comparar nuestros resultados con los suyos. Y a los profesores que tanto nos han enseñado durante toda la carrera, gracias a los cuales pronto podremos decir con orgullo que somos matemáticos e informáticos. v
Resumen Geometry Friends es un complejo juego de plataformas en el que dos figuras geométricas deben alcanzar diamantes prestando atención a los diferentes obstáculos de cada nivel. Cada año, participantes de distintas universidades desarrollan nuevos agentes inteligentes que son capaces de resolver correctamente una gran variedad de niveles, y estos participan en competiciones organizadas por los creadores del juego y que se celebran en importantes conferencias internacionales de Inteligencia Artificial. Existen tanto modos de juego individuales, en los que solo participa una de las figuras geométricas, como cooperativos. Nuestro objetivo en este trabajo es el desarrollo de agentes que funcionen tanto de manera individual como cooperativa y que sean capaces de competir con los mejores agentes de competiciones pasadas, para poder participar en la competición de este año, que se celebrará en agosto. Para ello, exploramos qué técnicas de Inteligencia Artificial han sido más fructíferas en las competiciones pasadas y buscamos la forma de mejorar los resultados de estos agentes mediante diferentes estrategias. Además, desarrollamos un sistema que permite explicar las acciones que toman nuestros agentes. Finalmente, comprobamos mediante diferentes pruebas que nuestros agentes logran superar al jugador humano medio y a todos los agentes anteriores en todas las modalidades de juego. Palabras clave Geometry Friends, Inteligencia Artificial, aprendizaje por refuerzo, modelización física, IA explicable (XAI), sistema experto, entorno físico, cooperación, entorno multiagente. vi
Abstract Geometry Friends is a complex platform game in which a pair of geometric figures must reach diamonds while paying attention to the different obstacles on each level. Every year, participants from different universities develop new intelligent agents that are capable of correctly solving a wide variety of levels, and they participate in competitions organized by the game’s creators and held at major international Artificial Intelligence conferences. There are both individual game modes, in which only one of the figures participates, as well as cooperative ones. Our goal in this work is the development of agents that work both individually and cooperatively and that are capable of competing with the best agents from past competitions in order to participate in this year’s competition, which will be held in August. To do this, we explore which Artificial Intelligence techniques have had the most success in previous competitions and we look for ways to improve the results of these agents through different strategies. Besides, we developed a system that allows us to explain the actions that our agents take. Finally, we check through several tests that our agents manage to outperform the average human player and all previous agents in all game modes. Keywords Geometry Friends, Artificial Intelligence, Reinforcement Learning, physical modeling, explainable AI (XAI), expert system, physical environment, cooperation, multiagent environment, vii
Índice 1. Introducción 5 1.1. Motivación................................. 5 1.2. Objetivos ................................. 6 1.3. Plandetrabajo.............................. 7 1.4. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5. Código asociado al trabajo . . . . . . . . . . . . . . . . . . . . . . . . 9 1. Introduction 10 1.1. Motivation................................. 10 1.2. Objectives................................. 11 1.3. Workplan................................. 12 1.4. Documentstructure............................ 13 1.5. Associated code to this project . . . . . . . . . . . . . . . . . . . . . 14 2. Descripción del entorno Geometry Friends 15 2.1. Introducción a Geometry Friends . . . . . . . . . . . . . . . . . . . . 15 2.2. Competiciones............................... 19 2.3. Estadodelarte .............................. 20 2.3.1. CIBot ............................... 20 2.3.2. KUAS-ISLab........................... 21 2.3.3. OPU-SCOM............................ 21 2.3.4. RL-Agent ............................. 22 2.3.5. RRT-Agent ............................ 23 2.3.6. Subgoal A* Agent . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.7. KITAgent............................. 25 2.3.8. Supervised DL Agent . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.9. Neural Reinforcement Agent . . . . . . . . . . . . . . . . . . . 27 2.3.10.MARL-GFAgent......................... 27 2.3.11.NKUST .............................. 28 2.3.12.AGAgent ............................. 29 2.3.13.Otrosagentes ........................... 29 2.3.14.Resumen.............................. 30 1
ÍNDICE 2 2.3.15.Conclusiones ........................... 31 3. Desarrollo común al círculo y el rectángulo 34 3.1. Introducción................................ 34 3.2. Software y herramientas . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3. Arquitectura de la solución . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1. Representación del nivel . . . . . . . . . . . . . . . . . . . . . 38 3.3.2. Trazado de un plan a seguir . . . . . . . . . . . . . . . . . . . 41 3.3.3. Ejecución del plan . . . . . . . . . . . . . . . . . . . . . . . . 48 4. Desarrollo del círculo 51 4.1. Introducción................................ 51 4.2. Representación del nivel . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.1. Generación de movimientos . . . . . . . . . . . . . . . . . . . 53 4.2.2. Filtrado de movimientos . . . . . . . . . . . . . . . . . . . . . 58 4.3. Ejecucióndelplan ............................ 60 4.3.1. Replanificación . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.2. Determinación del siguiente movimiento a realizar . . . . . . . 61 4.3.3. Elección de la acción a realizar . . . . . . . . . . . . . . . . . 63 4.3.4. Política de saltos . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.5. Comentarios adicionales sobre la ejecución del plan . . . . . . 71 5. Desarrollo del rectángulo 74 5.1. Introducción................................ 74 5.2. Representación del nivel . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2.1. Plataformas del rectángulo . . . . . . . . . . . . . . . . . . . . 76 5.2.2. Generación de movimientos . . . . . . . . . . . . . . . . . . . 79 5.2.3. Filtrado de movimientos . . . . . . . . . . . . . . . . . . . . . 97 5.3. Trazado de un plan a seguir . . . . . . . . . . . . . . . . . . . . . . . 100 5.4. Ejecucióndelplan ............................101 5.4.1. Replanificación . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4.2. Consideraciones sobre la forma del rectángulo . . . . . . . . . 102 5.4.3. Acción que más acerca al rectángulo a la posición del movimiento106 5.4.4. Acción asociada al tipo de movimiento . . . . . . . . . . . . . 109 5.4.5. Comentarios adicionales sobre la ejecución del plan . . . . . . 113 6. Implementación de técnicas cooperativas 119 6.1. Introducción y retos derivados de la cooperación . . . . . . . . . . . . 119 6.2. Representación del nivel . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.2.1. Plataformas cooperativas . . . . . . . . . . . . . . . . . . . . . 125 6.2.2. Generación de movimientos . . . . . . . . . . . . . . . . . . . 130 6.2.3. Filtrado de movimientos . . . . . . . . . . . . . . . . . . . . . 133 6.3. Trazado de un plan a seguir . . . . . . . . . . . . . . . . . . . . . . . 135 6.4. Ejecucióndelplan ............................139 6.4.1. Ejecución de los movimientos de tipo CIRCLETILT . . . . . . 139 6.4.2. Ejecución de movimientos del círculo que aterrizan en el rectángulo ..............................140
1.5. Código asociado al trabajo 9 comentamos otras maneras en las que este trabajo puede ser útil para futuros desarrollos. Además, se explican los planes de cara a la competición que se celebrará en agosto de este mismo año. Durante el documento, hay enlaces a breves animaciones o vídeos que permiten explicar conceptos de una manera más clara y visual, y se identifican por estar subrayados y en color azul, como en el siguiente ejemplo (este no es un enlace, solo un indicador de cómo es el formato que se utiliza). Si no se pudiera acceder a dichos enlaces, el conjunto de todas las animaciones y vídeos es accesible mediante la siguiente url, correspondiente a una lista de reproducción de YouTube: https: //bit.ly/3qay7Lr. Esta lista contiene de manera ordenada los vídeos a los que se hace referencia durante el documento. Avisamos a que, debido a problemas de compatibilidad, la calidad de la mayoría de ellos no es tan alta como querríamos. 1.5. Código asociado al trabajo Todo el código desarrollado y empleado en el proyecto se puede encontrar en un repositorio de Github de uno de los autores, que será accesible para la evaluación a través de https://github.com/alberalm/TFG-Geometry-Friends. Sin embargo, el repositorio no será público hasta que se celebre la competición en la que tenemos intención de participar, con el fin de evitar pérdida y/o robo de código. Una vez se celebre la competición, el código que hayamos subido será accesible a través de la página web, por lo que abriremos el repositorio entonces con una licencia MIT. Aún así, se dará acceso anticipado a los miembros correspondientes del tribunal evaluador del trabajo. Advertimos de que, aunque a simple vista parece que la amplia mayoría de los commits han sido realizados por solamente uno de los miembros del grupo, esto se debe a que la mayoría del desarrollo se ha llevado a cabo mientras se utilizaba la herramienta Live Share de Visual Studio3, que permite la programación simultánea del código por parte de varios contribuidores. Por tanto, dado que siempre era uno de los autores el que hacía de anfitrión para la sesión, el código se guardaba localmente en su ordenador, convirtiéndolo aparentemente en el principal contribuidor del repositorio. 3Véase https://visualstudio.microsoft.com/services/live-share/.
Chapter 1 Introduction 1.1. Motivation In recent years, there have been significant advances in all Artificial Intelligence branches. In the field of game theory, many agents that reach a superhuman level have been implemented, and the techniques in their development have been applied to other areas. Already in the 90s, a chess analysis engine capable of defeating the best players in the world [10] was being developed, and since then, there are only a few games in which humans still dominate. Notable examples include complex games like go [37], games with incomplete information like poker [8], and real-time games like Starcarft [43] or Dota 2 [5]. In this work, we deal with Geometry Friends, a two-dimensional platform game in which a green rectangle and a yellow circle participate, and whose objective is to reach a series of diamonds (purple rhombus) in the shortest possible time. In this sense, it is different from the games mentioned above as there is no opponent to beat. There are levels in which only one agent participates, but there are also those in which the two characters must cooperate to reach some diamonds that they cannot take separately, like the ones in Figure 1.1, in which we show how the game looks like. In addition to platforms with different properties and tricky diamond positions, which force agents to solve challenges such as deciding the correct order in which to reach them, the game presents many other difficulties. First of all, it is a dynamic environment, in which physics play a significant role and precision in movements is essential to achieve good results. The movements are limited (for example, the circle always jumps with the same impulse), but many times the resulting trajectories are complex. On the other hand, each agent has its own set of actions, which results in their behaviors being very different. Finally, the cooperation of agents with different 10
1.2. Objectives 11 Figure 1.1: Example of a cooperative level of the game. roles is such a challenge that the best agents developed to date are still far from the level of an expert player. These features make Geometry Friends a very interesting game from the point of view of Artificial Intelligence. So much so, that in recent years the competitions that creators hold annually, in which participants present the best agents they have been able to develop, have been linked to important international conferences, such as the Conference of Games (CoG) and the International Joint Conference on Artificial Intelligence (IJCAI). These competitions have three categories: CircleTrack, RectangleTrack and CooperationTrack, and we intend to beat the best results obtained so far in each of them. The competitions will be held once more in August this year, being associated one more time with the CoG1and IJCAI2conferences. 1.2. Objectives In this section, we are going to talk about the objectives that we want to achieve during the completion of this work. Our main goal is to develop agents to participate in the individual and cooperative competitions of the Geometry Friends game, whose performance reaches that of the best state-of-the-art agents. To do this, we will address the following objectives: O1 To study the Artificial Intelligence techniques used in the development of the agents of previous competitions, examining the specific implementations of those that have obtained the best results. 1https://2023.ieee-cog.org/competitions/ 2https://ijcai-23.org/competitions/
1.3. Work plan 12 O2 To identify patterns in the game that allow abstracting and characterizing the environment, while acquiring expert knowledge about its mechanics. O3 To incorporate expert knowledge to implement individual agents that solve most levels. O4 To adjust individual agents to be able to collaborate and solve cooperative levels. O5 To analyze how reinforcement learning can be used in the context of the game, comparing it with other approaches. O6 To develop an XAI system that allows the agents’ decisions to be explained in the game’s graphical interface. O7 To acquire the necessary knowledge about the C#language, in which the game is coded, and in which the agents must be developed. O8 To evaluate the developed agents by comparing them with the best agents from previous competitions and with human players. 1.3. Work plan In order to complete the previous objectives, we describe the work plan that we have followed during the course. First, we studied the state of the art for this problem, exploring the agents developed for the circle and the rectangle, both individual and cooperative. We examined the different proposals, analyzing the results in the competitions of previous years. We dedicated the first months of the course to this, until the beginning of December. Next, we developed the two agents corresponding to the individual competitions. Since they have different roles, the development of both required independent effort, even though there were some features we were able to reuse. For the circle agent’s implementation, we dedicated the months of December and January, and, for the rectangle agent, the months of February and March. Once the individual agents had been implemented, we adapted them for cooperative competition, for which we used the months of March and April. Regarding the general organization, we have used suitable platforms for collaborative work, such as GitHub (to manage the code), Overleaf (to write this document) and Google Drive (to store the documents we use as references).
1.4. Document structure 13 Finally, we have written this memory as we progressed in the project. We have also held meetings every two weeks with the tutors, so that we could discuss our progress and the next steps to follow. 1.4. Document structure In Chapter 2, we provide a more detailed introduction to the environment we deal with, explaining how the associated competitions are run. We also describe the agents that have participated in previous competitions (that is, the state-of-theart), giving a final summary that recapitulates the strategies followed. The following chapters are dedicated to the detailed explanation of the implementations we have made for the agents. In Chapter 3, we describe the part that is common to both agents, and we present the tools we had at our disposal to carry out their development. In Chapters 4 and 5, we explain the details and particularities that we have followed during the development of the individual agents, being Chapter 4 the one corresponding to the circle and Chapter 5 the one to the rectangle. In these chapters, we cover what we consider relevant about their implementation. In Chapter 6, we explain the cooperative techniques we developed that allow our agents to collaborate at the corresponding levels. To do so, we introduce the adaptations and modifications we implemented to the individual versions of the agents. In addition, we dedicate a chapter section to the visual explainability system we have developed for our cooperative agents, which makes it easier to understand their behavior. After these chapters, which constitute the main body of the report, there is Chapter 7. This is the results chapter, made from a selection of levels corresponding to competitions from previous years, in which we compare human players and the best state-of-the-art agents (both individual and cooperative) with those that we have developed. Finally, there is Chapter 8, in which we will summarize the work done, drawing conclusions from the results we have obtained. In that same chapter, we detail multiple ways to improve the implemented agents, and we comment on other ways in which this work can be useful for future developments. In addition, we explain our goals regaring this year’s competition, which will be held in August. Throughout the document, there are links to short animations or videos that allow concepts to be explained in a clearer and more visual way, and they are identified by being underlined and in blue, as in the following example (this is not a link, just
1.5. Associated code to this project 14 an indicator of how links are highlighted). If these links could not be accessed, the set of all animations and videos is accessible through the following url, which corresponds to a YouTube playlist: https://bit.ly/3qay7Lr. This playlist contains, in an ordered manner, the videos that are referred to throughout the document. Please note that, due to compatibility issues, the quality of most of them is not as high as we would like. 1.5. Associated code to this project All the code we have developed and used in the project can be found in a Github repository of one of the authors, which will be accessible via https://github.com/ alberalm/TFG-Geometry-Friends. However, the repository will not be public until the competition in which we intend to participate is held, in order to avoid loss and/or theft of code. Once the competition is held, the code that we will have uploaded will be accessible through the website, so we will open the repository with an MIT license. Even so, early access will be given to the corresponding members of the evaluation panel of the work. Please note that, while at first glance it appears that the vast majority of commits have been made by just one of our group members, this is because most of the development has been made while using the Visual Studio Live Share tool3, which allows simultaneous code programming by multiple contributors. Therefore, since one of us was always the session host, the code was stored locally on his computer, apparently making him the repository’s main contributor. 3See https://visualstudio.microsoft.com/services/live-share/.
Cap´ ıtulo 2 Descripción del entorno Geometry Friends En este capítulo, realizamos una introducción al entorno Geometry Friends en el que se desarrolla el juego, así como las competiciones en las que se puede medir el rendimiento de los agentes. Para finalizar el capítulo, revisamos el estado del arte y estudiaremos las técnicas que utilizan los mejores agentes desarrollados hasta el momento. 2.1. Introducción a Geometry Friends Geometry Friends es un juego de plataformas cooperativo de dos jugadores desarrollado por GAIPS INESC-ID1. El juego está compuesto por una serie de niveles en un mundo bidimensional y dirigido por un motor físico en el que dos agentes, un círculo y un rectángulo, deben conseguir el mayor número de diamantes en el menor tiempo posible. Los agentes participan individualmente o cooperando, según el modo de juego. Los niveles finalizan cuando se alcanzan todos los diamantes o se acaba el tiempo disponible. Cada personaje tiene un conjunto propio de acciones de acuerdo a sus características. El círculo puede rodar hacia la derecha o la izquierda y también cuenta con la posibilidad de saltar. Por su parte, el rectángulo puede deslizarse hacia la izquierda y la derecha y puede redimensionarse. Esto quiere decir que puede cambiar su forma de manera continua y manteniendo constante su área (y su masa). El rango de formas varía desde una en la que su base es ancha y tiene poca altura a otra en la que su base es estrecha y tiene altura máxima, pasando por la forma de un cuadrado. Sin embargo, el rectángulo no puede saltar, haciendo que llegar a los puntos más elevados del nivel con este agente suela suponer un reto. 1http://gaips.inesc-id.pt/ 15
2.1. Introducción a Geometry Friends 16 Figura 2.1: Ejemplo de un nivel del juego con diferentes tipos de plataformas. Los niveles del juego están definidos por la disposición de los obstáculos o plataformas y los diamantes, así como la posición inicial de cada uno de los personajes. Las plataformas pueden ser de tres colores: amarillo, verde y negro. El círculo, que es de color amarillo, y el rectángulo, que es de color verde, atraviesan las plataformas que son de su mismo color, mientras que colisionan con las que son de colores distintos. Es decir, el círculo ignora las plataformas amarillas, mientras que rebota contra los obstáculos verdes y negros, y el rectángulo tiene un comportamiento análogo. Los personajes también chocan entre sí. Un ejemplo de la apariencia de estas plataformas se encuentra en la figura 2.1. Nótese que se muestra información del tiempo transcurrido en el nivel y del número de diamantes recogidos hasta el momento. El entorno en el que se desarrolla el juego es dinámico y controlado por un simulador físico. Sobre los personajes actúan la fuerza de la gravedad y el rozamiento con las superficies. Estas fuerzas no tienen el mismo impacto sobre los dos personajes, ya que, por ejemplo, el rectángulo y el círculo no se desplazan con la misma aceleración. Además, se simulan colisiones inelásticas con los demás objetos. El estado del juego viene dado, por tanto, por las posiciones y velocidades de los agentes, la altura (o anchura) del rectángulo y los diamantes que todavía no se han recogido. Este entorno físico genera limitaciones naturales. El círculo, por ejemplo, aunque es el único agente que puede saltar, solo puede hacerlo con una velocidad vertical inicial determinada. Esto quiere decir que no se puede regular un salto según la altura a la que se quiere saltar, sino que se deben buscar alternativas para llegar a esa altura deseada con precisión. Asimismo, no puede cambiar su velocidad horizontal durante el vuelo, lo que hace imposible corregir un salto que no sigue la trayectoria ideada. Es por tanto imprescindible una alta precisión en la toma de acciones. Por otro lado, el rectángulo también posee sus dificultades. Por ejemplo, el agente solo puede ejecutar las acciones de crecer y decrecer si su orientación es paralela al suelo, como en la figura 2.1. En consecuencia, algunos movimientos para cambiar de
2.1. Introducción a Geometry Friends 17 Figura 2.2: Ejemplo de una configuración en la que el rectángulo se ha quedado estancado. plataforma solamente son posibles cuando se realizan con una forma específica. En caso contrario, el agente tiene la posibilidad de quedarse estancado, es decir, en una configuración de la que el rectángulo no puede salir, como en la figura 2.2. Pero la mayor limitación del rectángulo es su impedimento de saltar y su gran dificultad para ascender a plataformas que estén a una altura mayor que la actual. Profundizaremos más en las dificultades de cada personaje en los capítulos correspondientes. Las distintas configuraciones de obstáculos y diamantes proporcionan una amplia variedad de retos y dificultades que los personajes deben sortear para completar el nivel. Entre estos desafíos, hay niveles en los que es imprescindible la cooperación entre los personajes y la coordinación de las acciones, mientras que en otros la estrategia óptima es la división de tareas para que cada personaje consiga los diamantes que tiene más accesibles. También es relevante el orden en el que se capturan los diamantes, ya que, en ocasiones, hay acciones que no permiten retroceder al estado anterior y lanzarse a conseguir un diamante puede suponer que el nivel se vuelva irresoluble. Por ejemplo, en el nivel mostrado en la figura 2.1, el diamante de arriba a la derecha solamente es accesible si el círculo salta desde encima del rectángulo, que además debe estar situado encima de la plataforma amarilla. Si el rectángulo decidiese coger primero los diamantes de abajo a la derecha, no habría forma de que volviera a subir a ayudar al círculo. El ejemplo más común de colaboración surge cuando se debe alcanzar un diamante que está en una posición muy elevada del mapa, de modo que la única manera de alcanzarlo es haciendo que el rectángulo sirva de plataforma para el círculo. Sin embargo, hay otras situaciones en las que se requiere otro tipo de colaboración, como puede ser el nivel mostrado en la figura 2.3. En este nivel, vemos cómo la única manera de resolverlo es si el rectángulo consigue acceder a la parte superior de la plataforma negra, ya que es el único que puede
2.1. Introducción a Geometry Friends 18 Figura 2.3: Ejemplo de un nivel que requiere otro tipo de colaboración. Figura 2.4: Colaboración en la que el círculo sirve como base. atravesar la plataforma verde. Sin embargo, él solo no tiene las habilidades suficientes para hacerlo. Una solución consiste en que el rectángulo se vuelva lo más alto y estrecho posible y gire alrededor del círculo, de forma que este último salte cuando el rectángulo esté encima suya, impulsándole hacia arriba. Esta configuración se muestra en la figura 2.4, en la que, si el círculo saltara en ese momento, el rectángulo subiría a la plataforma negra. Hay más ejemplos con diferentes situaciones, lo que hace que el entorno sea mucho más complejo de lo que pueda parecer a primera vista.
2.3. Estado del arte 25 2.3.6. Subgoal A* Agent El desarrollador de este agente [15], de la Universidad de Maastricht, participó en 2015 en la competición RectangleTrack. La aproximación seguida es similar a la del agente CIBot, donde en primer lugar se crea una abstracción del nivel en forma de grafo dirigido, cuyas aristas se etiquetan con la forma que debe tener el rectángulo para poder pasar por ellas. Los nodos son los puntos de interés del nivel, que pueden ser, por ejemplo, extremos de las plataformas, posiciones de caída del rectángulo o localizaciones justo debajo de los diamantes. Tras computar el grafo, se lanza el algoritmo de búsqueda Subgoal A*, que es una modificación del algoritmo A* desarrollada por el propio autor.2Una vez generado el camino, se procede a la ejecución del mismo mediante un sistema de reglas. Los resultados obtenidos son mejores que los de los ganadores de los años 2013 y 2014, y se proclamó vencedor de la edición del año 2015 de la competición RectangleTrack. En las competiciones posteriores, este agente fue usado de referencia para comparar el rendimiento de las nuevas implementaciones. 2.3.7. KIT Agent Los desarrolladores del agente KIT Agent [28], del Instituto Tecnológico de Kioto, participaron en las ediciones de los años 2017 y 2022 de la competición para el círculo. Dividen la resolución del nivel en dos fases: encontrar el camino más corto que consiga recolectar todos los diamantes y seleccionar las acciones del agente para seguir dicho camino. En la primera fase, generan un grafo dirigido que representa el nivel y aplican el algoritmo de búsqueda Subgoal A* para encontrar el camino buscado. La aproximación que siguen para generar el grafo es novedosa respecto a las implementaciones previas, ya que las aristas son generadas analizando las posibles trayectorias de salto y caída del agente desde una plataforma. En primer lugar, se parte de la simplificación de que la trayectoria del agente no tiene obstáculos y que esta, al encontrarnos en un entorno dinámico, viene dada por las ecuaciones del tiro parabólico. Es decir, la posición del móvil a tiempo tviene dada por las ecuaciones x(t) = x0+vxt, y(t) = y0+vyt−gt2 2, donde (x0, y0)es la posición inicial del móvil, vxes la velocidad horizontal inicial, vy 2En este algoritmo, la heurística se fija a 0, pero a los nodos se les añade información relativa al orden y número de diamantes ya recogidos. Por tanto, los nodos finales son aquellos en los que se capturan todos los diamantes. Sin embargo, se limita el tiempo dedicado a la búsqueda. Si tras alcanzar dicho límite no se ha conseguido un camino que consiga recolectar todos los diamantes, se resta 1 al número de diamantes que se quiere recolectar y se vuelve a ejecutar el algoritmo, y así hasta que se tiene éxito.
2.3. Estado del arte 26 es la velocidad vertical inicial y ges la aceleración de la gravedad. En este contexto, el valor de ges una constante proporcionada por el juego. Para los saltos, vyes otra constante proporcionada por el juego y, para los casos en los que el agente cae por un extremo de la plataforma, vy= 0. Además, para una plataforma concreta, y0, es decir, la altura de la plataforma, es un valor fijo y xi≤x0≤xdsiendo xiyxdla posición de los extremos izquierdo y derecho de la plataforma, respectivamente. Por otro lado, |vx| ≤ vmax para cierta constante positiva vmax que indica la velocidad horizontal máxima del agente y que es un parámetro proporcionado por el juego. Por tanto, tenemos dos variables libres, x0yvx, que se mueven en un cierto intervalo y que nos determinan la trayectoria del agente en los saltos desde una plataforma concreta. La solución propuesta consiste en discretizar los intervalos anteriores y probar todas las combinaciones de valores x0yvx, que generarán una buena aproximación de todos los posibles saltos y caídas desde una plataforma. Para cada una de las trayectorias, se analiza a qué plataforma se llega tras realizar dicho salto o caída y si se intercepta algún diamante. Si la plataforma de llegada es distinta de la que se parte, se genera una arista que se etiqueta con la información (x0, vx). Es decir, si el agente se encuentra en la posición x0con velocidad vxy salta (o se deja caer, dependiendo del caso), entonces llegará a la plataforma destino. Por tanto, el problema de desplazarse de una plataforma a otra y de alcanzar los diamantes se reduce a que el agente aprenda a llegar a una determinada posición x0con una determinada velocidad vx. Este aprendizaje se realiza mediante Q-Learning y la representación de estados propuesta utiliza las simetrías del juego para acelerar el proceso de aprendizaje. Las principales limitaciones del agente [27] se producen por el hecho de no tener en cuenta que las trayectorias pueden encontrarse con obstáculos y porque la plataforma de llegada puede ser demasiado estrecha y, al llegar a ella con una velocidad horizontal demasiado elevada, puede que el agente no tenga suficiente tiempo para frenar y caiga por uno de los extremos. Con todo, los resultados obtenidos son muy buenos. 2.3.8. Supervised DL Agent En 2017, un estudiante de Máster del Instituto Técnico de Lisboa [7] intentó usar varios enfoques diferentes mediante Deep Learning [2] para desarrollar varios agentes del círculo. En primer lugar, implementó un agente que emplea únicamente Aprendizaje Supervisado [13], intentando clasificar los diferentes estados del juego según qué acción se debía realizar en ellos. Sin embargo, tenía muy pocos datos para entrenar el modelo, ya que los tuvo que generar jugando él mismo. A continuación, creó varios agentes que utilizaban Aprendizaje por Refuerzo [35]. Entre ellos, hay uno basado en Q-Learning con redes neuronales (algoritmo DQN [26]), otro que optaba por descenso de gradiente y otro que utilizaba demostraciones (algoritmo
2.3. Estado del arte 27 DQfD [19]), que también hacía uso de partidas jugadas por humanos. El primero de los agentes es el que obtuvo un mejor rendimiento, seguido del agente basado en el algoritmo DQfD. Sin embargo, comparados con otros agentes, no destacan en cuanto a resultados. 2.3.9. Neural Reinforcement Agent El desarrollador de este agente [1], de la Universidad de Lisboa, participó en la edición de 2017 en la competición CircleTrack. Esta propuesta se basa en Aprendizaje por Refuerzo, utilizando una red neuronal prealimentada para aproximar la función de valor. Se modela el entorno como un MDP (Markov Decision Process) y se utiliza Q-Learning para aproximar la función de valor, que mide la recompensa esperada a largo plazo de realizar una determinada acción en un determinado estado. De esta forma, la política óptima es elegir en cada estado la acción que maximice la función de valor. Se define la función de recompensa de tal forma que se premie al agente al acercarse a los diamantes y se le penalice cada iteración para que el tiempo que invierta sea mínimo. Los estados finales son aquellos en los que se captura un nuevo diamante y se sigue una estrategia ε-greedy. El algoritmo de aprendizaje utilizado fue una modificación de Neural Fitted Q Iteration [30], que entrena la red por descenso de gradiente estocástico para minimizar el error de la predicción de la función de valor. El autor reconoce que esta aproximación requiere de un mayor tiempo de entrenamiento y un mayor volumen de datos para obtener buenos resultados. 2.3.10. MARL-GF Agent El desarrollador de este agente [36], de la Universidad de Lisboa, participó en las tres competiciones (CircleTrack, RectangleTrack y CooperationTrack) del año 2019. Se inspiró en la solución propuesta por el agente KIT y la extendió al rectángulo y al modo cooperación. Para el rectángulo, la fase de entrenamiento consistió en que el agente aprendiera mediante Q-Learning a alcanzar una determinada posición con una determinada velocidad horizontal, de manera similar a cómo fue entrenado el agente KIT (círculo), pero teniendo en cuenta que la altura del rectángulo es variable. Para ello, redujo las posibles formas del rectángulo a base ancha, cuadrado o base estrecha, y el resto del problema se abordó de manera idéntica a como lo hace el agente KIT, aunque sin considerar que el agente pueda saltar. En cuanto al modo cooperación, se sigue una estrategia en la que el círculo actúa como líder y se comunica con el rectángulo para conseguir los objetivos. Durante la fase de modelado del nivel, cada agente crea su propio grafo. Lo novedoso es que
2.3. Estado del arte 28 el círculo incluye plataformas cooperativas, que son plataformas ficticias sobre las plataformas alcanzables por el rectángulo y que representan la posibilidad de que el círculo se sitúe encima del rectángulo. Estas plataformas tienen una altura dinámica y pueden ser vistas como 3 plataformas, situadas a cada una de las posibles alturas del rectángulo. Todas las plataformas, incluyendo las cooperativas, son utilizadas para analizar las posibles trayectorias de salto del círculo al estudiar la conectividad entre plataformas. Durante la fase de ejecución, los agentes tienen un sistema de mensajes tal que, si el círculo va a efectuar un movimiento que requiera de una plataforma ficticia, demanda la ayuda del rectángulo para situarse en una posición específica. Utilizan el método de aprendizaje cooperativo Team Q-Learning [11], aunque también se probó a utilizar OAL (Optimal Adaptative Learning) [44]. Se les entrenó para que se desplazasen manteniendo la posición en la que el círculo se sitúa sobre el rectángulo hasta llegar a una posición determinada. Los estados objetivos son aquellos en los que se llega a una determinada posición con velocidad 0 y el círculo se mantiene sobre el rectángulo. Aunque los resultados obtenidos para el rectángulo son solamente algo mejores que los de las ediciones anteriores, en el modo cooperación obtuvieron puntuaciones considerablemente mayores a las de los agentes ya existentes. 2.3.11. NKUST Los agentes NKUST [20] también abordan la cooperación. La “posición de conducción” es el enfoque principal, ya que se considera que es el tipo de colaboración más común a través de los niveles presentados. Primero, se calcula el área donde se puede mover el rectángulo y, por lo tanto, qué diamantes puede atrapar. Con esto, el personaje del círculo puede obtener más información sobre las áreas a las que puede llegar, ya que el rectángulo se ve como una plataforma móvil. Al buscar un camino, la prioridad es atrapar los diamantes en un orden que permita capturar la mayor cantidad de diamantes usando una búsqueda en profundidad. Luego, se intenta encontrar un camino con el algoritmo A*. Si no se encuentra una ruta completa, el agente sigue, de las que ya descubrió, la que tiene más diamantes. En términos de división de tareas, el rectángulo tiene prioridad. Si este personaje puede atrapar todos los diamantes por sí mismo, entonces el círculo no se usa. Solo cuando hay uno o más diamantes que el rectángulo no puede atrapar, el círculo realiza la planificación de la ruta considerando el espacio de movimiento del rectángulo. Siempre que el círculo necesita del rectángulo para llegar a una posición, esta información se agrega a los “nodos colaborativos” de la búsqueda. Finalmente, cuando el círculo termina su planificación, el rectángulo realiza otra, con la información de los nodos que necesitan colaboración si los hubiere. Para realizar estas
2.3. Estado del arte 29 tareas cooperativas, el agente que llegue antes esperará al otro. 2.3.12. AGAgent Los desarrolladores de este agente [12], de la Universidad de Texas en Arlington, participaron en la competición CircleTrack en el año 2019. Dividen la resolución de los niveles en creación del modelo, planificación y ejecución. En primer lugar, siguiendo una idea parecida a la de los agentes KIT y MARL-GF, convierten el nivel en un grafo dirigido que construyen incrementalmente, partiendo de la posición actual del agente y estudiando la conectividad entre segmentos (lo que otros autores llaman plataformas) y diamantes de acuerdo a las posibles trayectorias parabólicas, que ignoran la presencia de obstáculos. Sin embargo, sí que tienen en cuenta cómo de cerca pasan las trayectorias de las esquinas de los obstáculos y, en la medida de lo posible, favorecen trayectorias que no pasan próximas a estos, ya que tienen más posibilidades de ser precisas. En la fase de planificación, se realiza una búsqueda en anchura sobre el grafo para encontrar un camino que recorra el mayor número de diamantes. Finalmente, en la fase de ejecución, utilizan unas ciertas políticas de control que genera la fase de planificación. Estas consisten en subobjetivos de alto nivel, que se combinan para resolver el problema. Cuando una acción falla, se repite el proceso de generación del grafo desde la plataforma en la que se encuentra el agente. Los resultados que obtienen son bastante buenos, ya que afirman que consiguen completar todos los niveles de todas las competiciones anteriores al año 2019. Sin embargo, en algunas ocasiones, el proceso de creación del grafo, aunque útil a la hora de generar información precisa relativa al movimiento entre plataformas, es costoso en tiempo y tiene que ser limitado. 2.3.13. Otros agentes Mencionamos dos agentes más que, aun habiendo sido desarrollados y podido encontrar detalles de su implementación, no participaron en ninguna competición. Los autores de ambos agentes modificaron ligeramente el juego para poder desarrollarlos. En primer lugar, algunos desarrolladores de la Universidad Técnica de Estambul [47], crearon un agente para la competición del círculo en el que utilizan una red neuronal convolucional [24] para recibir como entrada la imagen de la pantalla, junto con la puntuación y el tiempo. Para procesar la pantalla, se convierte esta imagen a una escala de grises y se cambia el tamaño a un 30 % de la original. Para el estado se usa una superposición de 4 frames, y las acciones solo se toman cuando el círculo
2.3. Estado del arte 30 Agente CircleTrack RectangleTrack CooperationTrack CIBot 2013-2015 2013-2015 2013-2015 KUAS-IS Lab 2014 2014 No OPU-SCOM No 2014-2015 No RL-Agent 2015-2016 2016 2016 RRT-Agent 2015-2017 2015-2017 2016-2017 RRT2017 2017-2019 2017-2019, 2022 2017-2019, 2022 Rule Based RRT No No 2019 Subgoal A* Agent No 2015 No KIT Agent 2017, 2022 No No Supervised DL Agent 2017-2019 No No Neural Reinforcement Agent 2017 No No MARL-GF Agent 2019 2019 2019 NKUST No No 2019 AGAgent No 2019 No Tabla 2.1: Ediciones en las que participaron los agentes analizados. está en una plataforma o en el suelo. El resultado es bastante malo, siendo apenas mejor que un agente aleatorio. En segundo lugar, investigadores de la Universidad de Aveiro [38] utilizaron el aprendizaje profundo asíncrono para crear nuevos agentes. Los autores explicaron que inicialmente tuvieron dificultades durante la capacitación debido al alto coste del tiempo por pasos de capacitación y a la cantidad insuficiente de muestras para lograr políticas decentes. Para ayudar a acelerar el proceso de capacitación, utilizaron el enfoque de migas de pan y técnicas de modelado de entrada para disminuir la complejidad de la red. 2.3.14. Resumen Tras esta recapitulación de algunas soluciones propuestas para el juego Geometry Friends, vamos a mostrarlas de manera más compacta resaltando las características más destacadas de cada agente. En primer lugar, la tabla 2.1 recoge las ediciones y las competiciones en las que participaron los agentes analizados. La tabla 2.2 resume las técnicas de IA utilizadas por cada agente. En ellas, se han excluido los agentes que no han participado en ninguna competición. Por último, en la tabla 2.3 se muestran los agentes ganadores en cada una de las 3 competiciones de cada año según los resultados publicados en la página web del concurso.
2.3. Estado del arte 31 Agente Planificación Ejecución CIBot Dijkstra, MCTS Sistema de reglas KUAS-IS Lab A* Q-Learning OPU-SCOM Dijkstra, PSO, NEAT Sistema de reglas RL-Agent DFS, Dijkstra Q-Learning RRT-Agent RRT Controlador PID RRT2017 RRT Controlador PID RRT2017 RRT Sistema de reglas Subgoal A* Agent Subgoal A* Sistema de reglas KIT Agent Subgoal A* Q-Learning Supervised DL Agent DL, RL DL, RL Neural Reinforcement Agent RL RL MARL-GF Agent Subgoal A* Q-Learning,Team Q-Learning NKUST A* Q-Learning AGAgent A* (BFS) Q-Learning Tabla 2.2: Técnicas de IA utilizadas por los agentes. CircleTrack RectangleTrack CooperationTrack 2013 CIBot CIBot CIBot 2014 CIBot CIBot CIBot 2015 RRT Agent Subgoal A* Agent - 2016 RRT Agent RRT Agent RRT Agent 2017 KIT RRT2017 RRT2017 2019 KIT MARL-GF Agent MARL-GF Agent GF-CoG 2022 KIT RRT2017 - GF-IJCAI-ECAI 2022 KIT RRT2017 MARL-GF Agent Tabla 2.3: Ganadores de las competiciones celebradas hasta el momento. 2.3.15. Conclusiones Una vez expuestas todas las ideas de las implementaciones anteriores, nos gustaría identificar patrones comunes en las diferentes propuestas de agentes. Podemos distinguir dos ramas claramente diferenciadas en cuanto al funcionamiento de los agentes. Por un lado, tenemos las implementaciones que están fuertemente asociadas al modelo que se crea del nivel. Estas soluciones, a grandes rasgos, siguen un planteamiento común. En primer lugar, parten de un procesamiento del nivel en el que se genera un grafo para representar la disposición de los agentes, diamantes y obstáculos en el mapa. Este preprocesamiento se hace al principio del nivel y no afecta al tiempo de juego. Hay dos vertientes para la generación del grafo, pudiendo optarse o bien por analizar los puntos críticos en el mapa, o bien por estudiar la conectividad entre plataformas
2.3. Estado del arte 32 Generación del grafo Algoritmo de búsqueda Puntos de interés Trayectorias parabólicas Subgoal A* Subgoal A* Agent KIT Agent MARL-GF Agent A* KUAS NKUST Dijkstra CIBot OPU-SCOM RL-Agent BFS/ DFS AGAgent RL-Agent Otro CIBot OPU-SCOM RRT Tabla 2.4: Organización conceptual de los agentes que representan el nivel en forma de grafo basada en trayectorias parabólicas de saltos y caídas. Los resultados muestran que la segunda de las opciones tiene un mejor rendimiento. Posteriormente, hay una fase de planificación, que consiste en lanzar algún algoritmo de búsqueda sobre el grafo generado para encontrar un camino óptimo o subóptimo que recorra todos los diamantes. De entre todos los algoritmos utilizados, uno que es implementado por agentes que obtienen buenos resultados es Subgoal A*. Sin embargo, debido a que los grafos generados no son excesivamente grandes, no parece que la elección del algoritmo de búsqueda sea determinante a la hora de resolver el problema, ya que algunos algoritmos de búsqueda exhaustiva han sido utilizados con buenos resultados. Por último, el plan de acción generado en la planificación se le proporciona a un controlador, que elige los movimientos básicos del agente para seguir dicho plan. Dentro de este grupo de agentes, existen diferencias entre aquellos que realizan una replanificación cuando completan algún hito del plan (lo que les sirve para corregir errores), y otros que manteniendo el mismo plan adaptan las acciones a ejecutar. Esta clasificación se resume en la tabla 2.4. La otra aproximación no utiliza un modelo del nivel, sino que se apoya en el uso de aprendizaje supervisado profundo para que el agente aprenda por sí solo a resolver el nivel. La principal dificultad con la que se topan estos agentes es la falta de niveles de entrenamiento. Para entrenar las redes neuronales en las que se basan estas implementaciones, el volumen necesario de niveles debería ser inmenso. Si existiera un gran repertorio de niveles que se supiera que son resolubles, se podría utilizar como base para el entrenamiento, y esta aproximación tendría más oportunidades de resultar exitosa. Sin embargo, aunque no es muy complicado generar niveles automáticamente, resulta imposible saber de antemano si un nivel va a ser resoluble al generarlo.
2.3. Estado del arte 33 Así, en el contexto actual, los resultados de estos agentes son significativamente peores que los que toman la otra alternativa de implementación, y apenas superan los agentes que eligen sus acciones de forma aleatoria. Estos agentes son OPU-SCOM en su versión de 2015, Supervised DL Agent, Neural Reinforcement Agent y el agente de la Universidad Técnica de Estambul. Tras haber descrito las aproximaciones del estado del arte, en el siguiente capítulo comenzamos a explicar nuestra propuesta de solución. En concreto, hablaremos sobre la arquitectura común de los personajes del círculo y el cuadrado.
Cap´ ıtulo 3 Desarrollo común al círculo y el rectángulo En el presente capítulo, se detallará la parte de la arquitectura de la solución que es común a ambos agentes y podremos entender, en líneas generales, cuál es la estrategia global que siguen los agentes para resolver los niveles individuales. Las particularidades del círculo se explicarán con más detalle en el capítulo 4, mientras que las del rectángulo se encuentran en el capítulo 5. Asimismo, se presentan las herramientas que se van a necesitar durante el desarrollo de los agentes. 3.1. Introducción Nuestro objetivo principal del trabajo es el desarrollo de agentes individuales y cooperativos que puedan participar en las competiciones de Geometry Friends y obtener resultados equiparables a los mejores agentes creados hasta el momento. Para abordarlo, vamos a comenzar desarrollando los agentes individuales ya que, más allá de que todo lo que aprendamos en el desarrollo de los mismos es aplicable al caso de la cooperación, los retos para la IA que aparecen en estos modos de juego tienen interés per se. En esta sección, pretendemos dar una visión general de aquello que explicaremos con más detalle en la sección 3.3 y en los capítulos 4 y 5, la arquitectura de la solución. Describimos la forma que tienen nuestros agentes de abordar los niveles a continuación. En primer lugar, el juego proporciona la información del nivel al agente. Fundamentalmente, esta información es la posición de los obstáculos y del agente. Con esta información el agente crea una representación propia del nivel, más simplificada que la que le proporciona el juego y que tiene que procesar. Este procesamiento consiste fundamentalmente en tres aspectos: 1. Identificar las plataformas, es decir, las partes superiores de los obstáculos que 34
3.3. Arquitectura de la solución 41 acciones. Las acciones son atómicas y se toman en cada llamada al método Update. Recordamos que para el círculo son ROLL_RIGHT, ROLL_LEFT, JUMP y NO_ACTION, mientras que para el rectángulo son MOVE_RIGHT, MOVE_LEFT, MORPH_UP, MORPH_DOWN y NO_ACTION. Sin embargo, los movimientos son de más alto nivel y representan conectividad entre plataformas o posibilidad de alcanzar algún diamante. Como veremos, para completar un movimiento, es necesario tomar multitud de acciones atómicas. Los movimientos vienen determinados por la posición del agente dentro de la plataforma, su velocidad horizontal y el tipo de movimiento. Al generar cada movimiento, se calcula la plataforma sobre la que aterriza, así como los diamantes que el agente cogería por el camino. Lógicamente, las características propias del rectángulo y el círculo hacen que los tipos de movimientos que puedan realizar sean distintos. Por ejemplo, ambos pueden dejarse caer con cierta velocidad por los extremos de las plataformas, pero solo el círculo puede saltar y solo el rectángulo puede hacerse más estrecho para caer por el hueco entre dos plataformas. De entre todos los movimientos que simulamos, solamente guardamos una selección de ellos, que contiene aquellos más interesantes de cara a una posible planificación. Detallaremos más esta selección y daremos más información acerca de los movimientos en sí en los capítulos 4 y 5, correspondientes a cada uno de los tipos de agentes. Una vez retorna la función CreateLevelMap, se ha obtenido una representación discretizada del nivel, una lista de todas las plataformas encontradas, y una lista de movimientos relevantes. Hemos decidido realizar esta modelización de los niveles por lo aprendido al revisar toda la bibliografía del estado del arte. En rasgos generales, la discretización, la representación de plataformas y el establecimiento de conexiones entre ellas ha dado buenos resultados en el pasado. En lo que nos detendremos y pondremos especial énfasis en los capítulos del círculo y el rectángulo es en la generación de movimientos y en su filtrado. Gran parte del desempeño de los agentes recae en que la simulación de los movimientos que hacemos se ajuste de la forma más precisa posible a la realidad y en que seamos capaces de establecer reglas generales para saber cuándo un movimiento es mejor (en algún sentido) que otro. 3.3.2. Trazado de un plan a seguir El diseño del plan a seguir se realiza una vez generadas las plataformas y los movimientos que se pueden realizar desde ellas, es decir, cuando se ha completado la representación inicial. Generamos un grafo con los movimientos que habíamos almacenado, donde los vértices representan nuestras plataformas y las aristas son las conexiones entre ellas mediante los movimientos. En la creación del grafo, se le asocia a cada diamante una lista de plataformas desde las cuales existe un movimiento que alcanza ese diamante y aterriza en la misma plataforma.
3.3. Arquitectura de la solución 42 Figura 3.5: Representación de plataformas y movimientos del nivel 5 de la competición del círculo de 2014. Para ilustrar lo que comentamos, recomendamos analizar la figura 3.5. En ella podemos observar el nivel 5 de la competición del círculo del año 2014, en el que ya están representados los movimientos que permiten cambiar de plataforma y alcanzar diamantes. Aunque habrá que esperar hasta la sección 4.2.1 para introducirlos formalmente, adelantamos que los movimientos del círculo son caer, saltar y mantenerse quieto para alcanzar un diamante. En la figura 3.5 los movimientos de salto están representados por las flechas verdes y amarillas, las caídas por las azules y los movimientos que mantienen al círculo en reposo, alcanzando un diamante, por los puntos naranjas. Nótese que ya se ha realizado el filtrado y no existen dos movimientos que partan de la misma plataforma y aterricen en la misma plataforma. Por ejemplo, a la derecha de la plataforma 3 hay una flecha azul que representa que el círculo puede caer desde esta a la plataforma 4 por el borde derecho. Sin embargo, no aparece la caída simétrica por el extremo izquierdo de la plataforma 3 porque sería redundante. Este modelo es el que se tiene al finalizar la fase de representación del nivel y con él podemos construir el grafo asociado de la figura 3.6. Como se puede apreciar, las plataformas se han convertido en los vértices del grafo y los movimientos, es decir, la conectividad entre plataformas, en las aristas. A su vez, las aristas tienen la información de los diamantes que alcanzan. Por ejemplo, los puntos naranjas se han transformado en auto-aristas naranjas, que llegan a la misma plataforma de la que parten y alcanzan el diamante. Algo similar sucede con el salto amarillo que sale y aterriza en la plataforma 4 y alcanza un diamante. Por último, destacamos que el vértice que representa la plataforma en la que se encuentra el círculo está apuntado por una flecha y es desde donde comienza el plan. Es sobre este grafo simplificado sobre el que se lanza la búsqueda que da como resultado el plan de actuación. El plan consiste, fundamentalmente, en una lista de movimientos que permiten cambiar de plataforma y está generado de tal manera
3.3. Arquitectura de la solución 43 Figura 3.6: Grafo asociado al nivel 5 de la competición del círculo de 2014. que si el agente, antes de realizar cada uno de los movimientos para cambiar de plataforma, se asegura de haber alcanzado todos los diamantes que se encuentran sobre su plataforma actual entonces el agente alcanza todos los diamantes. La representación interna de nuestro grafo posee estructuras de tipo nodo. Los nodos, que se usan para el algoritmo de búsqueda, contienen la lista de movimientos (cambios de plataforma) que se han tomado desde la plataforma de partida, es decir, el plan hasta el momento, una lista de booleanos que representan si se ha cogido cada diamante concreto, el número de diamantes cogidos, y si el nodo es arriesgado (en unos párrafos veremos exactamente qué significa esto). Tras construir el grafo, se llama al algoritmo de búsqueda, que aparece detallado en el algoritmo 1. Se trata de una búsqueda en anchura con control de repetidos y límite de tiempo, que recorre el grafo y encuentra la mejor solución posible. Hay que tener en cuenta que por “mejor solución”, entendemos aquel plan que alcanza todos los diamantes efectuando un menor número de movimientos para cambiar de plataforma, aunque también se toman en consideración conceptos como la dificultad de los movimientos (nodos arriesgados). Asimismo, hacemos notar que la solución que menos cambia de plataforma no tiene por qué ser la óptima en tiempo. No obstante, como podremos comprobar, los resultados obtenidos hacen que esta simplificación sea suficientemente buena y no sea necesario realizar un enfoque más complejo, que implicaría también al módulo de ejecución. Este algoritmo se llama al principio de cada nivel, pero también puede volver a ser llamado si un movimiento no se ha efectuado correctamente y el agente ha aterrizado en una plataforma diferente de la esperada. Esto es lo que denominamos replanificación, y lo detallaremos más en la siguiente sección.
3.3. Arquitectura de la solución 44 Algoritmo 1 Algoritmo de búsqueda para la generación de un plan 1: queue ←Cola con nodo raíz 2: hay_plan_completo ←false 3: mejor_sol ←Nodo vacío con plan vacío 4: nodos_sin_riesgo ←1 5: vistos ←Conjunto vacío 6: while queue es no vacía && tiempo de búsqueda <T do 7: node ←queue.pop 8: if node no es arriesgado then 9: nodos_sin_riesgo −− 10: end if 11: move ←Último movimiento del plan parcial en nodo 12: p←plataforma de aterrizaje de move 13: Procesar move yp 14: if node ya se ha visitado then 15: Continuar 16: else 17: Añadir node avistos 18: if node es mejor que mejor_sol then 19: mejor_sol ←node 20: end if 21: if Plan de node coge todos los diamantes then 22: hay_plan_completo ←true 23: if Plan de node no es arriesgado || nodos_sin_riesgo == 0 then 24: Devolver plan de node 25: end if 26: else 27: foreach Movimiento mque salga desde py cambie de plataforma do 28: Crear nuevo_nodo expandiendo node con m 29: Actualizar nodos_sin_riesgo 30: Introducir nuevo_nodo en queue 31: end foreach 32: if nodos_sin_riesgo == 0 && hay_plan_completo then 33: Devolver plan de mejor_sol 34: end if 35: end if 36: end if 37: end while 38: Devolver plan de mejor_sol Durante el algoritmo, surgen una serie de preguntas y cuestiones que respondemos a continuación: ¿Qué significa que un nodo sea arriesgado?
3.3. Arquitectura de la solución 45 Un nodo puede llamarse arriesgado debido a alguno de estos dos factores: 1. Alguno de los movimientos que contiene su plan es arriesgado. Como veremos, existen algunos movimientos muy complejos que preferiremos evitar en la medida de lo posible, aún si eso conlleva seguir un plan más largo (el primer ejemplo se verá en la sección 5.2.2). Esta clase de movimientos los llamaremos arriesgados, y los identificaremos mediante un bit risky. 2. Alguno de los movimientos que contiene su plan coincide con el último movimiento efectuado que ha fallado. Esto puede suceder si se ha llamado al algoritmo como motivo de una replanificación. En este caso, el algoritmo recibe el movimiento que ha fallado. Si alguno de los movimientos del plan del nodo coincide con este movimiento, potencialmente puede volver a fallar, por lo que intentaremos buscar otro camino (aunque sea más largo) con la esperanza de que tenga mejores resultados. ¿Qué significa que un nodo sea mejor que otro? Un nodo se considera mejor que otro si bien coge más diamantes (independientemente de cuáles sean) o bien coge los mismos, pero este nodo no es arriesgado y el otro sí. Esta manera de comparar es útil para asegurar que priorizamos la solución que coja el mayor número de diamantes posible, pero en caso de haber varias, preferimos quedarnos con una solución que no sea arriesgada. ¿Cómo se procesan una plataforma y un movimiento? Con procesar un movimiento, nos referimos a marcar que el nodo coge todos los diamantes que se alcanzan mientras se ejecuta el movimiento. Esto es, por ejemplo, que si procesamos un movimiento del círculo de tipo salto que mueve el círculo de una plataforma a otra y, durante la trayectoria del salto se alcanza un diamante, se añade el diamante como capturado al nodo (ver tipos de movimiento del círculo en la sección 4.2.1). Con procesar una plataforma, queremos decir que marcamos que el nodo coge todos los diamantes que se pueden alcanzar desde esa plataforma sin necesidad de abandonarla. Para esto es para lo que, durante la creación del grafo, hemos asociado a cada diamante desde qué plataformas existen movimientos que cogen el diamante sin abandonarla. Esta manera de procesar movimientos y plataformas garantiza la propiedad esencial de nuestro plan que es la siguiente: si antes de tomar el siguiente movimiento del plan (que cambia de plataforma), el agente se asegura de haber alcanzado todos los diamantes disponibles asociados a su plataforma actual, entonces el agente alcanzará todos los diamantes. ¿Cómo se expande un nodo? Si tenemos un nodo n, para cada movimiento mque parte desde la plataforma de llegada del último movimiento del plan de n, podemos expandir na través de m. Para ello, consideramos un nuevo nodo cuyo plan sea el de nyuxtapuesto a m. Así,
3.3. Arquitectura de la solución 46 podremos coger diamantes durante el movimiento y alcanzar una nueva plataforma desde la que conseguir más diamantes. Expandir un nodo con un movimiento se refiere a recorrer una de las aristas del grafo (la asociada al movimiento) para llegar a un nuevo vértice. Además del nuevo plan, debemos calcular también si el nuevo nodo es arriesgado, para lo que evaluaremos si nya lo era o si mes un movimiento arriesgado, de acuerdo a alguno de los dos criterios que ya hemos comentado. ¿Para qué sirven las variables nodos_sin_riesgo y hay_plan_completo? La variable nodos_sin_riesgo lleva la cuenta de los nodos que quedan en la cola que no son arriesgados. Hacemos notar que, si encontramos una solución completa (es decir, que capture todos los diamantes), no siempre vamos a querer terminar la búsqueda. Esto puede deberse a que la solución que hayamos encontrado es arriesgada, y aún quede la posibilidad de encontrar otra solución que no lo sea. Sin embargo, si al encontrar la solución arriesgada sabemos que todos los nodos que quedan en la cola son arriesgados, sabemos que la solución que tenemos es la mejor posible, por lo que podemos terminar la búsqueda con seguridad (esto se ve en las líneas 23-25 del algoritmo 1). Lo mismo sucede si al expandir un nodo que no era arriesgado solo nos quedamos con nodos arriesgados. Si ya hemos encontrado una solución completa (que será arriesgada, ya que en caso contrario se habría devuelto al encontrarla), sabemos que será la solución que buscamos (líneas 32-34 del algoritmo 1). La variable hay_plan_completo guarda si la mejor solución encontrada hasta el momento captura todos los diamantes. Además de la utilidad mencionada en el párrafo anterior, esta variable cobrará más importancia durante el preprocesamiento de los niveles cuando hablemos del rectángulo que hemos desarrollado, concretamente, en la sección 5.3. ¿Cómo se lleva a cabo el control de repetidos? Para realizar el control de repetidos, utilizamos el conjunto vistos (clase HashSet de C#), en el que introducimos una tupla que contiene la plataforma en la que se encontraría el agente después de realizar los movimientos del plan (es decir, la plataforma de llegada del último movimiento) y un entero que identifica el conjunto de diamantes obtenido. Este entero se calcula mediante una función de valor, que suma 2isi el nodo captura el diamante i. Esto permite comparar dos nodos de manera sencilla, y limita enormemente la cantidad de elementos que puede haber en el conjunto, ya que, entre otras cosas, siempre que se esté en una plataforma, se habrán cogido los diamantes que se puedan alcanzar desde ella. Sin embargo, hay que tener en cuenta una pequeña consideración adicional. Queremos ser capaces de distinguir nodos arriesgados de nodos no arriesgados, y, si utilizáramos la función de valor tal y como la hemos descrito en el párrafo anterior, no seríamos capaces de hacerlo. Para ello, basta hacer que si el nodo es arriesgado se
3.3. Arquitectura de la solución 47 devuelva el opuesto del valor que tendría el nodo si no lo fuera. Es decir, el valor de un nodo arriesgado es no positivo (puede ser 0), y el de un nodo no arriesgado es no negativo. Por supuesto, esta función de valor no es la que se utiliza para determinar si un nodo es mejor que otro, sino que se hace según lo explicado en uno de los párrafos anteriores. ¿Cuánto tiempo empleamos para la búsqueda? Si bien el algoritmo que hemos presentado es completo, en el sentido de que encuentra una solución si la hay, y contamos con un control de repetidos poco costoso para mejorar el tiempo de cálculo, es conveniente tener un límite de tiempo en la búsqueda. Es cierto que antes de comenzar el nivel podemos utilizar todo el tiempo que queramos para planificar, pero las replanificaciones se realizan en tiempo de ejecución y no sería sensato adentrarnos en una búsqueda que puede ser potencialmente larga si el nivel es muy complejo y tiene muchas plataformas. Por ello, al comenzar la búsqueda iniciamos un cronómetro, y al tratar cada nodo de la cola comprobamos si ya hemos superado el tiempo límite de búsqueda. Hemos establecido el tiempo límite de la búsqueda en las replanificaciones a 400 ms. En la práctica este es un tiempo más que suficiente para encontrar un plan completo. No obstante, si el tiempo expirara antes de conseguirlo, se devolvería un plan parcial. Tras ejecutar dicho plan parcial se realizaría otra replanificación y, si hay suerte, la composición de esos dos planes parciales, aunque no sea óptima, puede llevar al agente a completar el nivel. Vamos a mostrar el resultado de aplicar el algoritmo de búsqueda anterior al grafo de la figura 3.6. El plan que obtenemos es el dado por la figura 3.7, es decir, 1→ 3→2→0y su interpretación es la siguiente: 1. Coger todos los diamantes alcanzables desde la plataforma 1 (no hay). 2. Moverse desde la plataforma 1 a la plataforma 3 con el movimiento azul (la caída). 3. Coger todos los diamantes alcanzables desde la plataforma 1 (se alcanza el diamante mediante el movimiento naranja). 4. Moverse desde la plataforma 3 a la plataforma 2 con el movimiento verde (el salto). 5. Coger todos los diamantes alcanzables desde la plataforma 2 (no hay). 6. Moverse desde la plataforma 2 a la plataforma 0 con el movimiento verde (el salto). 7. Coger todos los diamantes alcanzables desde la plataforma 0 (se alcanza el diamante mediante el movimiento naranja).
3.3. Arquitectura de la solución 48 Figura 3.7: Plan asociado al nivel 5 de la competición del círculo de 2014. Destacamos que las plataformas únicamente se abandonan cuando ya se han conseguido todos los diamantes alcanzables desde esa plataforma con movimientos que aterrizan en esa misma plataforma. Asimismo, los diamantes alcanzables desde las plataformas 3 y 4 son en realidad el mismo, con lo que, en la línea 13 del algoritmo 1, al procesar la plataforma de aterrizaje de la caída desde la plataforma 1 a la 3, se habrá marcado el diamante como capturado. Por tanto, no será necesario en el plan visitar la plataforma 4 porque ese diamante ya se habrá alcanzado desde la plataforma 3. Esto concluye la explicación del trazado de un plan a seguir. En la siguiente sección, detallamos cómo se sigue el plan que se ha retornado como resultado de la llamada al algoritmo 1. 3.3.3. Ejecución del plan La principal diferencia que presenta la Ejecución del plan frente a los pasos de Representación del nivel yTrazado de un plan a seguir es el tiempo. Mientras que los dos primeros se realizan antes de que se inicie el nivel, y por tanto no tienen límite de tiempo, la ejecución del plan se debe hacer en tiempo real, por lo que es un factor a tener en cuenta a la hora de realizar algoritmos complejos en esta parte. Aunque la ejecución concreta del plan es muy diferente para los dos agentes, ya que depende en gran medida del tipo de movimiento que se vaya a ejecutar, sí que posee ciertas similitudes. El algoritmo general se muestra en el algoritmo 2. En ambos casos se parte del plan que ha sido generado en la fase anterior y que está compuesto por una lista de movimientos que permiten pasar de una plataforma a
3.3. Arquitectura de la solución 49 Algoritmo 2 Algoritmo de actuación general 1: while El juego no ha terminado do 2: if Plataforma actual != Plataforma origen del primer paso del plan then 3: Replanificar 4: end if 5: if Quedan diamantes por coger en la plataforma actual then 6: m←Movimiento que alcanza el diamante más cercano 7: Ejecutar mejor acción que lleva a completar m 8: else 9: if El plan es no vacío then 10: m←Primer movimiento del plan 11: Ejecutar mejor acción que lleva a completar m 12: else 13: Realizar una acción aleatoria 14: end if 15: end if 16: end while otra. Dentro de cada plataforma y antes de pasar a la siguiente, el agente deberá coger todos los diamantes alcanzables desde dicha plataforma, ya que esta era una asunción que realizaba el algoritmo de planificación. Al igual que en la sección anterior, merece la pena detallar algunos de estos puntos: Replanificación Ya adelantamos en la sección anterior en qué consistía la replanificación. Dadas las características del juego, en muchas ocasiones la resolución de los niveles depende en gran medida de un grado de precisión muy alto en la toma de acciones, que resulta en la práctica inalcanzable, debido a las sucesivas discretizaciones, simplificaciones y aproximaciones efectuadas a lo largo de todo el proceso. Este no es un problema exclusivo de los agentes ya que, como se verá en el capítulo de resultados, el juego presenta retos de coordinación que los humanos no podemos resolver siempre de manera óptima. Es por tanto inevitable que se puedan llegar a tomar acciones que provoquen que el agente acabe en un estado indeseado o al menos imprevisto. En virtud a lo anterior, es oportuno contar con un mecanismo de recuperación en el caso de que algo no salga de la manera esperada. Por lo tanto, antes de realizar una acción se comprueba si ha surgido cualquier tipo de eventualidad, verificando si la plataforma actual es la plataforma origen del primer paso del plan. Si este no es el caso, lanzamos nuevamente el algoritmo de búsqueda sobre el grafo para construir un nuevo plan partiendo de la plataforma actual. En la práctica, estas replanificaciones solamente se ejecutan cuando el agente no ha llegado a la plataforma destino tras tratar de realizar el movimiento que tenía previsto.
3.3. Arquitectura de la solución 50 Como ya comentamos, a la función de búsqueda del grafo se le proporciona el último movimiento que falló (en caso de que exista) y, en la medida de lo posible, el algoritmo intenta generar un nuevo plan evitando realizar ese movimiento. Esto es porque, si un movimiento falla, es posible que se deba a que es potencialmente complicado de realizar y es conveniente explorar otros caminos, aunque tengan más pasos. Por supuesto, si este es el único movimiento posible, el nuevo plan lo incluirá. Movimientos y acciones a tomar Ya mencionamos que los movimientos se referían a objetivos de alto nivel como un cambio de plataforma o la posibilidad de alcanzar algún diamante. Por ejemplo, dejarse caer por un lado de una plataforma es lo que llamaremos un movimiento de tipo FALL, y tanto el círculo como el rectángulo pueden efectuarlo. Todos los movimientos que planifiquemos tendrán un tipo asociado, que identificará cómo debe actuar el agente para completarlo. Por otro lado, las acciones son atómicas, y se refieren a qué debe hacer el agente en cada instante. El conjunto de acciones posibles ya viene determinado por el juego, y no podemos modificarlo. Para completar un movimiento, necesitaremos realizar una serie de acciones. Cómo elegir la mejor acción en cada momento para lograr ese objetivo es algo que depende de cada agente y tipo de movimiento, por lo que lo especificaremos en los capítulos correspondientes. Acciones aleatorias Si el agente no es capaz de encontrar ningún plan y no puede coger más diamantes desde la plataforma en la que se encuentra, quiere decir que o bien el conjunto de movimientos que ha generado es insuficiente para completar el nivel o bien ha fallado un movimiento y se ha quedado en un estado desde el que no puede coger todos los diamantes. En estos casos, los agentes de otros años optaban por no hacer nada, es decir, tomaban siempre la acción NO_ACTION. Sin embargo, nosotros hemos optado por realizar acciones aleatorias, ya que, si bien es probable que no sirva de nada (especialmente en el segundo de los casos anteriores), alguna vez ha conseguido rescatar a un agente de la posición en la que se encontraba, o ha realizado un movimiento que el agente no había sido capaz de encontrar, llevándole a completar el nivel. No es común, pero es una pequeña mejora de rendimiento que consideramos mejor que resignarse y no realizar ninguna acción. Esto concluye la descripción de la arquitectura de nuestra solución para los agentes individuales que es común al círculo y al rectángulo. En el siguiente capítulo comenzaremos a detallar las particularidades del círculo en cuanto a la representación del nivel y a la ejecución del plan.
4.2. Representación del nivel 57 Figura 4.5: Caídas simuladas desde los extremos de una plataforma. Comentarios adicionales sobre la generación de movimientos Llegados a este punto, nos encontramos con la problemática de que el número de parábolas a analizar es considerablemente alto. Nótese que si el número de plataformas es Np, la anchura media de una plataforma es Lpuntos y discretizamos el número de velocidades en Nv, el número de caídas y saltos a tratar es del orden de Np×(L+ 1) ×Nv. Para paliar este inconveniente, decidimos paralelizar los cálculos para obtener los movimientos más rápidamente. También ha sido útil no tratar algunos movimientos que son imposibles de conseguir por las limitaciones de las plataformas o que podrían ser complicados. En relación a lo primero, debemos eliminar las parábolas que requieran de una velocidad horizontal inicial que es imposible de alcanzar en ese punto de la plataforma. Para lo último, nos es útil calcular durante la simulación el mínimo de las distancias de la trayectoria a los obstáculos. En general, queremos que esta distancia sea lo mayor posible, ya que así evitaremos que el círculo choque con obstáculos por potenciales problemas de aproximación o por márgenes de error al tomar estas parábolas. Aun así, es posible que no haya ningún camino alternativo, en cuyo caso nos quedamos con ellos. Recordamos que las acciones del círculo en una determinada plataforma son: rodar hacia la izquierda, rodar hacia la derecha, o no realizar ningún movimiento. Las dos primeras aplican una fuerza constante al círculo, que provoca que este se mueva según las ecuaciones del movimiento uniformemente acelerado. De esta forma, se puede calcular el espacio necesario para, partiendo en reposo desde el origen, alcanzar una velocidad vxdada. Para ello, despejamos la distancia dde la Ecuación 4.1,
4.2. Representación del nivel 58 correspondiente a un movimiento uniformemente acelerado:1 v2 f=v2 0+ 2ad (4.1) Donde vfes la velocidad final, v0es la velocidad inicial, aes la aceleración (con signo), y des el desplazamiento, es decir, la diferencia entre la posición final y la posición inicial. Puesto que la velocidad inicial en este caso es nula, deducimos que, para llegar a un determinado punto con velocidad vx, se necesita como mínimo un espacio de v2 x 2apara acelerar, en el sentido apropiado según el signo de la velocidad. Para evaluar si es factible realizar determinados saltos o caídas, simplemente hay que comprobar que hay suficiente espacio en la plataforma para alcanzar la velocidad deseada. 4.2.2. Filtrado de movimientos Pasamos ahora a explicar el filtrado de los movimientos. Como hemos argumentado anteriormente, se han generado muchos movimientos y, para realizar las búsquedas posteriores, es conveniente quedarnos con los más apropiados. Por tanto, cuando se genera un nuevo movimiento se evalúa si es mejor, si es peor, o si no se puede comparar con los actuales. Los únicos movimientos que nos interesan son aquellos que cogen algún diamante o los que sirven para cambiar de plataforma. Cualquier movimiento que no cumpla ninguna de estas dos condiciones es automáticamente descartado. Si el movimiento pasa este primer filtro, se compara con todos los movimientos actuales. Para que dos movimientos sean comparables, deben partir de la misma plataforma y llegar a la misma plataforma. En primer lugar, priorizamos que un diamante se alcance con un NOMOVE frente a un JUMPMOVE. Esto se debe a que si el diamante está a la altura de una plataforma, es más rápido llegar a esa posición rodando que saltando (rodando se puede aumentar la velocidad horizontal y en los saltos la velocidad horizontal es constante). Dentro de los NOMOVE que alcanzan el mismo diamante, nos vamos a quedar con aquel que tenga como coordenada xla misma que la del diamante. Nótese que hay movimientos de tipo NOMOVE que alcanzan el diamante sin estar justo en su vertical. Como para alcanzar un diamante sobre una plataforma todos estos movimientos nos sirven y querríamos quedarnos únicamente con uno, es lógico elegir este. Por otro lado, están los movimientos que cambian de una plataforma a otra, que pueden ser o saltos o caídas. Si el conjunto de diamantes alcanzados en un movimiento contiene estrictamente al conjunto de diamantes que se recogen con otro, es claro que preferimos el primero. Si ambos conjuntos contienen algún diamante que el otro movimiento no coge, los movimientos son incomparables y querremos quedarnos con ambos. Por último, si los diamantes alcanzados son exactamente los mismos, tenemos que tener en consideración otros factores. 1La deducción de esta fórmula se puede encontrar en la sección 2.3 de [42].
4.2. Representación del nivel 59 Figura 4.6: Punto idóneo de aterrizaje. Un problema típico, y que se hace evidente tras analizar algunas partidas en el juego, es caerse por los lados al aterrizar cerca de los extremos de una plataforma. Por tanto, descartamos los movimientos que aterrizan demasiado cerca de los extremos de las plataformas frente a los que no lo hacen. Por último, tomamos en consideración otros cuatro elementos cuya importancia relativa no es clara. Estos son: Distancia del punto de aterrizaje al extremo de la plataforma por donde se puede caer el círculo si no hay suficiente espacio para frenar. En general, vamos a querer minimizar la distancia del punto de aterrizaje al punto xde la figura 4.6 (d1). Velocidad horizontal del salto (vx). Relacionado con el factor anterior: cuanto menor sea la velocidad horizontal, menos espacio se necesitará para frenar. Distancia de la trayectoria a los obstáculos (d2). Como adelantamos, queremos maximizar esta distancia para evitar choques indeseados con obstáculos. Distancia del punto de salto al centro de la plataforma de origen (d3). Aunque idealmente nuestro agente tomará siempre los movimientos que ha planeado, en ocasiones no llegará con la velocidad adecuada para realizar exitosamente el salto. Detallaremos el comportamiento del círculo en estas situaciones más adelante, pero adelantamos que habrá situaciones en las que el agente no saltará. Para evitar que un salto abortado precipite una caída por un extremo de la plataforma de origen, queremos tener suficiente espacio para frenar si esto sucede, justificando así por qué queremos minimizar la distancia anterior. Tomando lo anterior en consideración, elegiremos el movimiento con menor valor de la combinación lineal Value =d1/3 + vx/10 −d2+d3/10. Los pesos se han elegido teniendo en cuenta que las distancias y velocidades tienen escalas distintas.
4.3. Ejecución del plan 60 Algoritmo 3 Algoritmo de actuación del círculo 1: while El juego no ha terminado do 2: if Plataforma actual != Plataforma origen del primer paso del plan then 3: Replanificar 4: end if 5: if Quedan diamantes por coger en la plataforma actual then 6: Obtener el movimiento mque alcanza el diamante más cercano 7: if Pos. círculo ≈Pos. m&& Velocidad círculo ≈Velocidad m.then 8: Realizar acción asociada al tipo de movimiento m 9: else 10: if (Pos. círculo, Velocidad círculo) es igual de válido que mthen 11: Realizar acción asociada al tipo de movimiento m 12: else 13: Realizar acción que más acerque al círculo a (pos. m, vel. m) 14: end if 15: end if 16: else 17: if El plan es no vacío then 18: Obtener el primer movimiento mdel plan 19: if Pos. círculo ≈Pos. m&& Velocidad círculo ≈Velocidad m.then 20: Realizar acción asociada al tipo de movimiento m 21: Desapilar el primer movimiento del plan 22: else 23: if (Pos. círculo, Velocidad círculo) es igual de válido que mthen 24: Realizar acción asociada al tipo de movimiento m 25: else 26: Realizar acción que más acerque al círculo a (pos. m, vel. m) 27: end if 28: end if 29: else 30: Realizar una acción aleatoria 31: end if 32: end if 33: end while 4.3. Ejecución del plan En esta sección, partimos de un plan de actuación que ha sido generado tras realizar una búsqueda en un grafo donde los vértices son las plataformas y las conexiones, las aristas. Recordamos que el plan se compone de una lista de movimientos entre plataformas (saltos o caídas) donde la plataforma origen del primer salto es la plataforma sobre la que se encuentra el círculo. En rasgos generales, el algoritmo que sigue el círculo es el que se describe en el algoritmo 3.
4.3. Ejecución del plan 61 Analizando el algoritmo, quedan todavía varias incógnitas por resolver. ¿Cómo se realiza la replanificación? ¿Qué significa que la posición del círculo y su velocidad sean aproximadamente las del movimiento? ¿Qué significa que dos movimientos sean igual de válidos? ¿Cómo se obtiene la acción que más acerca al círculo a la posición y velocidad deseadas? A continuación, procedemos a aclarar estas y otras cuestiones que surgen del algoritmo presentado. 4.3.1. Replanificación En primer lugar, hablaremos sobre la replanificación. Aunque la necesidad de contar con este mecanismo de recuperación se motivó en la sección 3.3.3, queremos detallar en qué situaciones puede ser útil. En el caso del círculo, la replanificación se aplica especialmente a los saltos, que es el tipo de movimiento más complejo, pero también se puede usar en el caso de las caídas. Como ya dijimos, antes de realizar una acción se comprueba si la plataforma actual es la plataforma origen del primer paso del plan. De no ser así, lanzaríamos nuevamente el algoritmo de búsqueda sobre el grafo para construir un nuevo plan partiendo de la plataforma actual. En la práctica, estas replanificaciones solamente se ejecutan cuando el agente no ha llegado a la plataforma destino tras realizar un salto o en las caídas. Recordamos que a la función de búsqueda del grafo se le proporciona el último movimiento que falló (en caso de que exista) y, en la medida de lo posible, el algoritmo intenta generar un nuevo plan evitando realizar ese movimiento, aunque, lógicamente, si este es el único movimiento que permite completar el nivel, el nuevo plan lo incluirá. En el caso particular del círculo, dado que no almacenamos demasiadas parábolas, es infrecuente que haya más de dos caminos alternativos para completar el nivel, y más aún que nuestro agente falle en la ejecución de ambos. Por ello, a la hora de replanificar, nos basta considerar el último movimiento mal ejecutado, en lugar de almacenar en una lista el histórico de movimientos que no se han podido completar. Así, en caso de que el agente falle continuamente, en la práctica alternará entre dos caminos diferentes, aunque pueda haber más. 4.3.2. Determinación del siguiente movimiento a realizar Una vez se ha replanificado, pueden darse dos situaciones. O bien queda un diamante por coger desde la plataforma actual, o bien es necesario cambiar de plataforma. Existen situaciones en las que un mismo diamante puede alcanzarse con un movimiento que no cambia de plataforma y otro que sí cambia de plataforma. En un principio, según la asociación que hacemos en el grafo por la que se determina para cada diamante si es posible alcanzarlo desde alguna plataforma sin necesidad de
4.3. Ejecución del plan 62 Figura 4.7: Nivel en el que es más eficiente no coger el diamante recuadrado sin cambiar de plataforma. cambiar a otra, favorecemos los primeros. Sin embargo, existen situaciones en las que es conveniente modificar esta política. Consideremos por ejemplo el nivel de la figura 4.7. En este nivel, el diamante recuadrado puede ser alcanzado desde la plataforma superior, aterrizando en la misma. No obstante, una vez el círculo está en esa plataforma, su siguiente movimiento en el plan es la parábola roja, que, como vemos, alcanza el mismo diamante (además de otros dos). Por tanto, es más eficiente simplemente realizar el movimiento del plan, que primero saltar para coger el diamante recuadrado y luego efectuar el plan. Por tanto, nuestro agente elige el movimiento que captura el diamante más cercano, manteniéndose en la plataforma actual, siempre y cuando ese diamante no se capture en el siguiente movimiento del plan. Si esto sucediera, ya hemos visto que es más eficiente no perder tiempo en coger ese diamante. Cuando no se encuentra ningún movimiento que capture un diamante desde la plataforma actual, se consulta el siguiente movimiento del plan. Es importante remarcar que esta selección para obtener el siguiente movimiento que se debe realizar no se lleva a cabo en el algoritmo de búsqueda. Allí, se asume que al llegar a una determinada plataforma se capturan todos los diamantes posibles sin abandonarla. De esta manera se reduce el tiempo de búsqueda.
4.3. Ejecución del plan 63 Figura 4.8: Reducción del problema de la imagen de la izquierda donde x<xobjetivo a su problema simétrico. 4.3.3. Elección de la acción a realizar Supongamos ahora que ya tenemos un movimiento mseleccionado que nos ayuda a coger algún diamante o nos permite cambiar de plataforma. El movimiento está determinado por el tipo de movimiento, la posición de origen del movimiento en la plataforma en la que nos encontramos y la velocidad horizontal que el círculo debe llevar en ese punto. Si la simulación que realizamos en la representación del nivel fue correcta y el agente cumple las precondiciones de posición y velocidad, al realizar la acción asociada al tipo de movimiento, deberá alcanzar los diamantes del movimiento y deberá aterrizar en la plataforma destino. Por tanto, nuestro objetivo ahora es conseguir que el círculo llegue a una determinada posición de la plataforma con una velocidad concreta. Este problema consiste en, dados los datos (x,vx,xobjetivo,vobjetivo) que representan la posición y velocidad actual y la posición y velocidad objetivos, respectivamente, encontrar la acción A∈ {ROLL_RIGHT, ROLL_LEFT}más adecuada. Nótese que podemos realizar una primera reducción, que es la siguiente: podemos asumir que el círculo se encuentra siempre a la derecha del punto objetivo, es decir, x≥ xobjetivo. En caso contrario, el problema se reduce a encontrar la acción asociada al problema simétrico de entrada I=(¯x,¯vx,¯xobjetivo,¯vobjetivo)=(2xobjetivo −x,−vx, xobjetivo,−vobjetivo). Si la acción asociada a la entrada Ies ROLL_RIGHT, la acción apropiada para el problema original es ROLL_LEFT, y viceversa. En la figura 4.8, mostramos visualmente la reducción efectuada. La flecha amarilla representa la velocidad objetivo, la flecha verde, la velocidad actual y los puntos rojos son las posiciones actual y objetivo. Conservaremos esta convención en sucesivas figuras, aunque se omitirá por claridad el punto que representa la posición del círculo. Una segunda simplificación que nos reducirá la dimensión de la entrada es considerar únicamente la diferencia d=x−xobjetivo ≥0. Está reducción es equivalente a fijar el origen de coordenadas en la posición objetivo. Para elegir la siguiente acción a realizar, y, como ya adelantamos en la introducción del capítulo, presentamos dos soluciones alternativas: un sistema de reglas basado en las ecuaciones del movimiento y una aproximación basada en aprendizaje por
4.3. Ejecución del plan 64 refuerzo. Elección de la acción mediante un sistema de reglas El sistema de reglas consiste en una serie de heurísticas que permiten al agente saber la acción que debe tomar en función de las distancias que necesita para frenar o acelerar según distintos casos. Este sistema basado en las ecuaciones de la física dará lugar al agente que bautizamos como UCM Physics. Las acciones de rodar hacia la derecha e izquierda inducen un movimiento uniformemente acelerado en el eje horizontal del círculo, hasta que este alcanza una cierta velocidad límite. Asimismo, asumimos nuevamente que el rozamiento es despreciable, que el círculo es una masa puntual y que no hay movimiento en el eje vertical. Por un lado, asociado al movimiento del círculo tenemos lo que llamaremos el punto de frenado, xfrenado. Dada la posición del círculo y su velocidad queremos saber en qué posición alcanzará velocidad nula si tomamos la acción que frena al círculo, es decir, aquella cuya aceleración tiene el signo contrario a la velocidad. Si la posición objetivo se toma como punto de referencia, se obtiene fácilmente mediante la Ecuación (4.1) que la distancia de frenado es −v2 x 2a, pues la velocidad inicial es vxy la velocidad final es nula. Así, si el círculo está actualmente en la posición x0, el punto de frenado será xfrenado =x0−v2 x 2a, donde a(la constante de aceleración) es negativa cuando el movimiento es hacia la derecha y positiva cuando el movimiento es hacia la izquierda, es decir, siempre opuesta a la velocidad actual. En las figuras, cuando sea necesario, indicaremos el punto de frenado con un punto verde, ya que este depende esencialmente de la velocidad horizontal, representada a su vez con una flecha verde. De manera análoga, podemos definir un punto de aceleración xaceleracion. Queremos saber la posición desde donde, partiendo en reposo, debemos empezar a acelerar para llegar al punto objetivo con la velocidad objetivo. Con cálculos análogos, donde ahora atiene el mismo signo que la velocidad objetivo, se obtiene que xaceleracion =−v2 objetivo 2a. Nótese que si vobjetivo >0, entonces a > 0 y el punto de aceleración se encuentra lógicamente a la izquierda del origen. Por consistencia, en las figuras el punto de frenado aparecerá representado con un punto amarillo. Se puede observar que el punto de frenado y el punto de aceleración solamente dependen de x0,vxyvobjetivo, ya que |a|es constante y su signo viene determinado por los signos de vxovobjetivo según el caso. Distinguimos ahora cuatro casos en función del signo de la velocidad actual y de la velocidad objetivo.
4.3. Ejecución del plan 65 Figura 4.9: Caso vx≥0yvobjetivo ≥0. Figura 4.10: Caso vx≥0,vobjetivo <0yxfrenado < xaceleracion. (a) vx≥0yvobjetivo ≥0. Representa la situación en la que el círculo está a la derecha del punto objetivo y está moviéndose hacia la derecha. La velocidad objetivo es también hacia la derecha (ver figura 4.9). En este caso, el círculo debe dar media vuelta porque está yendo en la dirección contraria al punto objetivo y debe tomar siempre la acción ROLL_LEFT. (b) vx≥0yvobjetivo <0. Esta situación es parecida a la anterior, pero en este caso la velocidad objetivo es negativa. Esto hace que la acción a tomar no sea tan evidente. ¿Debemos seguir rodando hacia la derecha para tener más espacio para acelerar? ¿Tenemos que cambiar ya de sentido porque nos estamos alejando demasiado? Estas preguntas se responden observando los puntos de aceleración y de frenado. Hacemos notar que, por los signos de las velocidades, tanto el punto de frenado como el de aceleración son positivos. Hay entonces tres casos posibles: Si el punto de frenado está a la izquierda del punto de aceleración (figura 4.10) significa que, si frenáramos ahora, el círculo se detendría por completo antes de tener espacio suficiente para acelerar. Por tanto, la acción correcta no es frenar, sino acelerar más, es decir, ROLL_RIGHT. Si el punto de frenado está a la derecha del punto de aceleración (figura 4.11) significa que si seguimos acelerando, este punto cada vez se alejará más del punto de aceleración y tendremos que desandar el camino después. Por tanto, la acción correcta en este caso no es acelerar sino empezar a frenar, es decir, ROLL_LEFT. Si ambos puntos coinciden (figura 4.12), debemos empezar a frenar, ya que alcanzaremos la velocidad nula en la posición adecuada para empezar a acelerar. Por tanto, elegimos la acción ROLL_LEFT.
4.3. Ejecución del plan 66 Figura 4.11: Caso vx≥0,vobjetivo <0yxfrenado > xaceleracion. Figura 4.12: Caso vx≥0,vobjetivo <0yxfrenado =xaceleracion. Figura 4.13: Caso vx<0,vobjetivo ≥0yxfrenado > xaceleracion. (c) vx<0yvobjetivo ≥0. Representa la situación en la que el círculo está a la derecha del punto objetivo, moviéndose hacia la izquierda y la velocidad objetivo es hacia la derecha. Es una situación bastante parecida a la anterior en la que, para saber cómo actuar, hay que atender a los puntos de frenado y aceleración. En este caso, el punto de aceleración es negativo porque a > 0, pero el signo del punto de frenado no es claro. Distinguimos entonces varios casos: Si el punto de frenado está a la derecha del punto de aceleración (figura 4.13) y el agente frenara en ese instante, llegaría al punto de frenado en un cierto tiempo con velocidad 0. Pero el punto de frenado está más cerca del origen que el punto de aceleración y no habría espacio suficiente para alcanzar la velocidad deseada. Por tanto, la acción correcta es seguir acelerando, es decir, ROLL_LEFT. Si el punto de frenado está a la izquierda del punto de aceleración (figura 4.14) no tiene sentido seguir acelerando porque el círculo aleja cada vez más su punto de frenado del punto de aceleración. La acción adecuada en este caso es frenar, es decir, ROLL_RIGHT. (d) vx<0yvobjetivo <0. En esta situación, el círculo está a la derecha del origen, dirigiéndose hacia él y la velocidad objetivo es negativa (figura 4.15). En este caso no es evidente cuál es la acción apropiada.
4.3. Ejecución del plan 73 Para solucionar este problema, implementamos una comprobación, que no hemos incluido en el algoritmo 3 por claridad, y que evalúa si el círculo está en el último píxel de una plataforma o si está en el primer píxel fuera de la plataforma. En ese caso, ordenamos al agente que ruede hacia el centro de la plataforma. Esta verificación se lleva a cabo antes incluso de la replanificación, ya que en estas situaciones queremos elegir esta acción antes de realizar ningún cálculo que pueda demorar la ejecución de la acción y empeorar la situación a un estado desde el que el agente ya no pueda recuperarse. Se puede ver cómo actúa el sistema para evitar caídas en la animación del siguiente enlace. Con el sistema para evitar caídas concluimos la última sección del capítulo sobre las particularidades del círculo. Recordemos que esta sección se ha centrado en desgranar el algoritmo 3, que describe la ejecución del agente círculo. En el siguiente capítulo abordaremos las particularidades del rectángulo. La estructura será similar a la de este capítulo, comenzando por la representación propia del nivel que hace el rectángulo y finalizando con un algoritmo de ejecución para ese personaje.
Cap´ ıtulo 5 Desarrollo del rectángulo En este capítulo, y de manera análoga al capítulo 4, explicamos el funcionamiento del rectángulo que hemos desarrollado. Para ello, completaremos lo explicado en el capítulo 3 sobre el desarrollo común de los agentes. En la sección 5.1 ofrecemos una breve introducción al rectángulo, en la cual se recuerdan sus características básicas y se recogen algunas de las constantes físicas que han sido útiles para el desarrollo. En la sección 5.2, nos centraremos en la representación de los niveles, explicando las plataformas del rectángulo, la generación de movimientos y su posterior filtrado. En la sección 5.3 ampliamos la exposición realizada en la sección 3.3.2 sobre el trazado del plan a seguir. Por último, en la sección 5.4, se comenta en detalle el algoritmo de ejecución del rectángulo. 5.1. Introducción El rectángulo es el segundo personaje del juego Geometry Friends. Se trata de un rectángulo verde que puede variar su forma y desplazarse a izquierda y derecha. Aunque existe una modalidad en la que el círculo y el rectángulo deben colaborar para alcanzar los diamantes, eso lo dejaremos para el capítulo 6 y antes nos vamos a centrar en aquellos niveles en los que únicamente participa el rectángulo. Las acciones características del rectángulo son diferentes a las del círculo y eso se aprecia en el conjunto de acciones que puede tomar. Estas son MOVE_RIGHT, MOVE_LEFT, MORPH_UP, MORPH_DOWN y NO_ACTION. Las dos primeras permiten al rectángulo deslizarse hacia la derecha y la izquierda. Esto se consigue aplicándole una fuerza mientras se elige dicha acción, que se traduce en que el rectángulo sufre una aceleración constante que hace que se desplace hacia uno de los lados. Las acciones MORPH_UP y MORPH_DOWN sirven para redimensionar el rectángulo. Su área debe mantenerse constante, pero puede ser más vertical si su 74
5.2. Representación del nivel 75 altura crece al tomar la acción MORPH_UP o más horizontal si su base se ensancha al tomar la acción MORPH_DOWN. La acción NO_ACTION, se muestra como alternativa cuando no se desea tomar ninguna de las acciones anteriores. Como ya comentamos en capítulos anteriores, el rectángulo colisiona contra los obstáculos cuyo color no es verde. Es decir, atraviesa los obstáculos verdes y choca contra los amarillos y los negros. Antes de comenzar a desarrollar el rectángulo, fue de gran utilidad calcular experimentalmente las siguientes constantes, que sabíamos que nos serían imprescindibles para poder realizar una modelización adecuada del problema: El área del rectángulo. Las alturas máxima y mínima del rectángulo. La aceleración que experimenta al aplicarle una acción de desplazamiento. La aceleración de la gravedad. La velocidad máxima horizontal que puede alcanzar el rectángulo. Además, comprobamos que la fuerza de rozamiento tenía un efecto despreciable sobre la velocidad, por lo que la descartamos de todos nuestros cálculos. Dado que la representación del estado del entorno del juego quedó detallada en el capítulo 3, común al círculo y al rectángulo, la primera particularidad del rectángulo la encontramos en la definición de las plataformas. En las siguientes secciones también trataremos la generación de movimientos, su filtrado, la elaboración del plan y su ejecución. 5.2. Representación del nivel En primer lugar, detallamos las consideraciones tomadas durante el preprocesamiento de un nivel. En las siguientes subsecciones trataremos temas que ya habíamos anticipado en la sección 3.3.1 como son las plataformas del rectángulo y los movimientos propios del rectángulo y su posterior filtrado.
5.2. Representación del nivel 76 Figura 5.1: Diferentes formas del rectángulo. 5.2.1. Plataformas del rectángulo De acuerdo a lo que comentamos en la sección 3.3.1, donde explicamos cómo se realizaba la discretización y se identificaba cada punto discretizado como OBSTACLE, PLATFORM, DIAMOND o EMPTY, quedó pendiente explicar las particularidades de las plataformas del rectángulo. Recordamos que una plataforma es un conjunto de puntos contiguos horizontalmente donde el agente puede apoyarse sin intersecar con otros obstáculos. Para el círculo era fácil identificar las plataformas porque simplemente había que evaluar si la discretización exterior del círculo (ver Figura 4.2) situada sobre cada uno de los putos de un obstáculo intersecaba con otro obstáculo. Como comentamos, esto era sencillo porque la forma del círculo es siempre la misma. Sin embargo, el rectángulo tiene la particularidad de que puede cambiar de forma tomando las acciones MORPH_UP y MORPH_DOWN. Con ello puede variar su forma de manera continua, manteniendo constante su área, como se puede ver en la Figura 5.1. Puede partir desde una en la que está completamente horizontal, hasta otra en la que está completamente vertical, pasando por todas las formas intermedias, como por ejemplo la forma de cuadrado. Por lo tanto no es tan sencillo definir en este caso qué es una plataforma para el rectángulo, porque es posible que el rectángulo pueda descansar sobre un obstáculo en posición horizontal, pero no en posición vertical, como se muestra en la Figura 5.2. Es necesaria una extensión de la definición de las plataformas para el caso del rectángulo. Por simplicidad, de aquí en adelante y salvo que se indique lo contrario, únicamente vamos a tratar con las tres formas del rectángulo que aparecen en la Figura 5.1, es decir, horizontal, cuadrado y vertical, y descartaremos todas las demás formas intermedias. Como antes, una plataforma será un conjunto de puntos contiguos horizontalmente sobre los cuales se puede situar el rectángulo sin que interseque con ningún otro obstáculo. Sin embargo, en esta ocasión, se debe cumplir que el subconjunto de las tres formas destacadas de la Figura 5.1 con las que el rectángulo puede descansar sea el mismo en todos los puntos. Esto se entiende mejor con una imagen como la de la Figura 5.3. En ella podemos
5.2. Representación del nivel 77 Figura 5.2: El rectángulo puede descansar en posición totalmente horizontal pero no en posición totalmente vertical. Figura 5.3: Identificación de las plataformas del rectángulo en el nivel 5 de la competición del año 2013. ver identificadas con distintos colores las plataformas según las formas posibles del rectángulo en cada una de ellas. Además, aparecen las formas destacadas del rectángulo en lugares estratégicos para tomar una referencia de los tamaños y guiar la explicación. Hay siete posibles tipos de plataforma. Con color marrón, representamos las plataformas en las que la única forma posible es el cuadrado, por ejemplo, las plataformas 1, 9 y 12. En la plataforma 1, nos podemos plantear por qué no se puede extender la plataforma más hacia la derecha, continuando hasta la pared o por qué no podemos situar en la plataforma 12 la forma horizontal. La respuesta es que el centro del rectángulo es lo que se utiliza para situarlo. Para cada punto del obstáculo, se
5.2. Representación del nivel 78 sitúa cada una de las formas de tal manera que el rectángulo descanse sobre el suelo y el centro del rectángulo se proyecte sobre dicho punto. Tal y como se puede apreciar, el cuadrado de la esquina superior derecha está pegado a la pared y el centro del mismo se proyecta en el extremo derecho de la plataforma 1. Si extendiéramos la plataforma 1 un punto más hacia la derecha, entonces deberíamos poder mover el cuadrado un punto más a la derecha, lo cual es imposible porque atravesaría la pared. De igual manera, no se puede situar en la plataforma 12 la forma horizontal porque tomamos como referencia el centro. Como se puede apreciar el rectángulo descansa sobre las plataformas 11, 12 y sobre un obstáculo de cuadros rojos y blancos. Sin embargo, para nosotros el rectángulo está situado sobre la plataforma 11, ya que es donde se proyecta su centro. Por último, es claro que no se puede situar el centro del rectángulo en forma horizontal sobre la plataforma 12 sin que este choque con el obstáculo de la derecha. De color morado, están pintadas las plataformas en las que la única forma de rectángulo posible es la horizontal, como son las plataformas 6, 25 y 27. Es claro que, en la plataforma 6, la única forma que se puede situar sin que choque con el obstáculo superior es la horizontal, pero para las plataformas 25 y 27 no es tan evidente. Pero el motivo es el mismo que en el caso anterior: la referencia es el centro de los rectángulos y no sus extremos. En este caso, el centro del rectángulo vertical se proyecta sobre la plataforma 28. Las plataformas en las que la única forma posible es la vertical aparecen marcadas de amarillo (2, 13, 17, 21, ...). Como se puede apreciar, en la plataforma 2 por ejemplo, como la anchura del rectángulo en forma vertical es mínima, el centro del mismo puede estar más próximo a las paredes y, por tanto, se generan plataformas amarillas donde únicamente se puede situar el rectángulo en forma vertical. De color anaranjado aparecen coloreadas las plataformas que admiten tanto la forma horizontal como el cuadrado, pero no la vertical. Por ejemplo, las plataformas 0, 7, 10, 11, 18, etc. Aunque pueda parecer extraño en un primer momento, también hay plataformas en las que se puede estar en la forma horizontal y vertical, pero no en forma de cuadrado. Estas están coloreadas de rojo y ejemplos de ellas son la plataforma 5 o la 28. Las plataformas verdes son aquellas que admiten la forma cuadrada y vertical, pero no la horizontal, como las plataformas 3, 14 o 15. Por último, aquellas plataformas en las que se puede situar el rectángulo con cualquier tipo de forma las señalamos con color azul oscuro. Ejemplos de estas últimas son las plataformas 4, 5, 8, 15, 19 y 29.
5.2. Representación del nivel 79 Figura 5.4: Plataformas simplificadas del rectángulo en el nivel 5 de la competición del año 2013. Aunque este sistema pueda parecer complejo, el centro del rectángulo es la información más accesible que tenemos del mismo. Además, saber qué formas son admisibles en cada plataforma nos será muy útil más adelante, cuando tengamos que generar movimientos o decidir qué acción tomar. Sin embargo, hay muchas de las plataformas que hemos generado que son adyacentes y que permiten que el rectángulo se mueva de una a otra con las acciones MOVE_LEFT o MOVE_RIGHT, si admite una forma común en ambas plataformas. En consecuencia, y dado que durante la planificación contar con un número más reducido de plataformas es más eficiente, introducimos el concepto de plataforma simplificada. Una plataforma simplificada no es más que la unión de plataformas adyacentes. Las plataformas simplificadas del nivel de la Figura 5.3 aparecen en la Figura 5.4. 5.2.2. Generación de movimientos Como ya comentamos en la sección 3.3.1, los movimientos que pueden realizar el círculo y el rectángulo son diferentes porque tienen características únicas. Mientras que el círculo puede saltar mediante la acción JUMP, el rectángulo no posee esa aptitud. Sin embargo, el rectángulo puede cambiar su forma manteniendo constante su área. A continuación, vamos a definir los tipos de movimiento del rectángulo, que serán
5.2. Representación del nivel 80 los que permitan pasar de una plataforma a otra o alcanzar algún diamante, y que no deben ser confundidos con las acciones. Las acciones son atómicas y se toman en cada llamada al método Update, mientras que los movimientos representan estrategias de más alto nivel, que se pueden completar realizando una secuencia de acciones, y que juntos forman el plan completo. Los tipos de movimiento del rectángulo son: NOMOVE, ADJACENT, FALL, DROP, TILT, MONOSIDEDROP, BIGHOLEADJ, BIGHOLEDROP y HIGHTILT. En los siguientes apartados se detalla cada uno de ellos. Esta sección es la más importante del capítulo, y el resto de ellas se siguen de manera natural una vez se identifican los diferentes tipos de movimientos. Movimientos NOMOVE Comenzamos con el tipo de movimiento más sencillo, el NOMOVE. Al igual que en el caso del círculo (ver sección 4.2.1), los movimientos NOMOVE representan la situación en la que el rectángulo puede alcanzar un diamante que está a la altura de una plataforma. Se procede de la misma manera: se evalúa en cada punto de cada plataforma si el rectángulo, en cada una de sus tres formas, interseca con la discretización de alguno de los diamantes. Al contrario que con el círculo, donde había que tener precaución sobre si era más conveniente tomar una discretización interior (Figura 4.1) o exterior (Figura 4.2) para calcular las intersecciones, en este caso, la forma rectangular hace que la discretización del rectángulo coincida con el propio rectángulo y por tanto no nos referiremos a ella a no ser que sea estrictamente necesario. Sin embargo, la discretización del diamante de la Figura 3.2 sí nos ocasionaba problemas de precisión. Hay algunos niveles, como el de la Figura 5.5 de la competición del año 2016, en el cual no se generaba un movimiento de tipo NOMOVE porque el rectángulo no puede alcanzar la discretización del diamante, pero sí que puede alcanzar el vértice inferior del diamante. Esta es una de las limitaciones que surgen de discretizar el entorno y que provocan una pérdida de precisión que, en este caso, nos resulta problemática. A pesar de ello, es posible solucionarlo, a costa, claro, de aumentar el coste computacional. Como la representación del nivel se realiza antes de que se inicie la cuenta del tiempo y no supone un empeoramiento apreciable en el rendimiento, decidimos realizar una comprobación adicional. Cuando se evalúan las intersecciones del rectángulo en forma vertical, comprobamos si la parte superior del rectángulo interseca con el diamante (no con su discretización). Esto tampoco es complicado ya que esa condición es equivalente a que la distancia L1, es decir, la distancia Manhattan, entre los píxeles del borde superior del rectángulo y el centro del diamante sea menor que la mitad de la altura del diamante. Nótese que el diamante no es otra cosa que una bola sobre la métrica L1. Esta medida consigue solventar el problema.
5.2. Representación del nivel 81 Figura 5.5: Fragmento del nivel 10 de la competición del año 2016 que muestra un diamante (morado) que puede ser alcanzado por el rectángulo, pero su discretización (amarilla) no puede ser alcanzada. Figura 5.6: Nivel 10 de la competición del año 2013. Movimientos DROP Este tipo de movimiento se crea por la existencia de un patrón común en los niveles de los años anteriores. El patrón se puede ver en la Figura 5.6 y consiste en una estructura en la que hay dos plataformas a la misma altura con un hueco de tamaño pequeño entre ellas. El tamaño del hueco es suficientemente pequeño para que el rectángulo pueda pasar de una plataforma a otra cuando está en forma horizontal y suficientemente grande para que el rectángulo pueda dejarse caer cuando está en forma vertical. Por tanto, el movimiento añade la posibilidad de que el rectángulo se deje caer por el hueco entre las plataformas.
5.2. Representación del nivel 82 Figura 5.7: Secuencia del movimiento DROP. Figura 5.8: Plataformas ficticias y movimientos DROP del nivel 10 de la competición del año 2013. Aunque en esta fase únicamente estamos considerando la existencia de una conexión entre las plataformas superiores y una plataforma inferior, describimos el movimiento que tenemos en mente que realice el rectángulo. Queremos que se sitúe en forma horizontal con su centro alineado con el centro del hueco y con velocidad cero y entonces pase a forma vertical, dejándose caer por el hueco (ver Figura 5.7). Recomendamos acceder a una animación mediante el siguiente enlace. Para modelizar este tipo de movimiento nos ha sido de gran utilidad considerar lo que hemos llamado plataformas ficticias, que son aquellas que hacen las veces de puente imaginario entre las dos plataformas a la misma altura en una estructura de tipo DROP. Son las plataformas de color naranja de la Figura 5.8. De esta forma, la plataforma destino de un movimiento DROP es la primera plataforma, real o ficticia, en la que se proyecta el punto medio del hueco del DROP. Por tanto, en la Figura 5.8 hay tres movimientos de tipo DROP: de la plataforma ficticia 1 a la plataforma ficticia 2, de la plataforma ficticia 2 a la plataforma ficticia 3 y de la plataforma ficticia 3 a la plataforma real 4. Finalmente, durante el movimiento de caída, hasta que se llega a una plataforma (real o ficticia), se evalúa si el rectángulo interseca alguno de los diamantes. Los alcanzados se añaden al conjunto de diamantes capturados durante el movimiento.
5.2. Representación del nivel 89 Figura 5.14: Orientación del rectángulo respecto a su posición inicial en función del ángulo θ(t). y será 0 cuando la acción tomada sea siempre NO_ACTION (lo que recupera el caso de movimiento uniforme en el eje de abscisas del círculo), o ±|a|, si la acción tomada es siempre MOVE_LEFT o siempre MOVE_RIGHT, siendo |a|el módulo de la aceleración asociada a dichas acciones. Como vemos, si bien las caídas del rectángulo son más complejas que las del círculo, en la práctica únicamente vamos a simular el triple de trayectorias, una para cada acción que se toma durante el vuelo. Además, las ecuaciones son igual de sencillas o complejas que en el otro caso. Sin embargo, la segunda diferencia que antes anticipábamos involucra un problema de modelización bastante más delicado. En una caída, cuando el centro de masas del rectángulo abandona la plataforma, el rectángulo empieza a girar sobre sí mismo. Se recomienda acceder al enlace para visualizar una animación de lo que sucede. Se puede comprobar que el rectángulo rota a la vez que se desplaza. Esto no es distinto a lo que sucedía con el círculo, pero en ese caso el espacio físico que ocupaba el círculo en el nivel estaba únicamente determinado por la posición de su centro. En el caso del rectángulo, además de la posición de su centro, que está perfectamente determinada por las ecuaciones anteriores, hay que conocer la orientación del rectángulo o la posición de sus vértices. A simple vista, no parece evidente cuál es la evolución de la orientación del rectángulo a lo largo del tiempo, es decir, cuál es la posición angular de sus vértices respecto al centro del rectángulo (ver Figura 5.14). Tras realizar diferentes pruebas, llegamos a dos conclusiones: la velocidad angular del rectángulo es constante y cuanto mayor es la velocidad inicial horizontal, menor es la velocidad angular. Por tanto, conjeturamos que la relación entre la velocidad angular y la velocidad horizontal inicial es inversamente proporcional, es decir, θ′(t) = C vα x para todo tiempo, con Cyαconstantes positivas por determinar. Para realizar una regresión que nos permitiera aproximar los valores de Cyαrealizamos una serie de experimentos para un conjunto de velocidades iniciales horizontales fijas. Comparamos visualmente la trayectoria real de los cuatro vértices del rectángulo
5.2. Representación del nivel 90 Velocidad inicial vx Mejor valor de βencontrado 100 1.25 200 0.5 300 0.3125 400 0.28 Tabla 5.1: Relación de los valores de vxy el mejor valor de βasociado. con la simulación de la trayectoria de los vértices en función de un parámetro βy elegimos el valor de βque haga que las trayectorias reales y simuladas coincidan (o estén lo más próximas posibles). Esta simulación consiste en situar para cada instante de tiempo el centro del rectángulo en la posición dada por las ecuaciones del movimiento y los vértices en la circunferencia de diámetro la diagonal del rectángulo y de tal forma que el ángulo entre la posición inicial del vértice y la actual sea exactamente θ(t) = βt, donde βes el parámetro que variamos. Si el ángulo que forma inicialmente uno de los vértices con la base es θ0= arc tg h wdonde hes la altura y wes la anchura, no es complicado deducir por trigonometría básica que la posición de dicho vértice a lo largo del tiempo es (x(t) = x0+vxt+at2 2±rcos(θ0−θ(t)) y(t) = y0+vyt−gt2 2±rsin(θ0−θ(t)) donde res la mitad de la diagonal, es decir, r=1 2√h2+w2y el signo del seno y el coseno depende del vértice en cuestión. En la tabla 5.1 se encuentran los mejores valores de βpara cada velocidad, es decir, aquellos para los que las trayectorias reales y simuladas de los vértices son muy parecidas. A modo de ejemplo, en el siguiente enlace mostramos la comparación entre la trayectoria simulada de los vértices y la trayectoria real del rectángulo para una velocidad inicial vx= 200 y el mejor valor de βencontrado. Se puede observar que la aproximación no es perfecta, pero sí suficientemente buena. Atendiendo a la tabla 5.1, podemos realizar la ya anunciada regresión, obteniendo que la función potencia que mejor aproxima los datos es θ′(t) = β(vx) = 204,35 v1,12 x . La gráfica de la función junto a los puntos de regresión se encuentran en la Figura 5.15. Tomando esa función, podemos simular la trayectoria del centro del rectángulo y de sus vértices. A partir de aquí, todo es igual que para el círculo: se discretiza el tiempo y en cada instante se comprueba si algún obstáculo interseca con el rectángulo. Si es así, se comprueba si el impacto se produce con uno de los lados o con un vértice. Si se produce con el vértice que tenga una menor altura en ese momento, entonces el movimiento termina porque se asume que se aterriza en una plataforma. Si se produce con cualquiera de los otros tres vértices se actualizan las velocidades y se sigue simulando. Por ejemplo, cuando la colisión se produce con el vértice derecho, entonces la velocidad horizontal se cambia de signo y se divide entre dos y la velocidad vertical se divide entre tres.
5.2. Representación del nivel 91 Figura 5.15: Representación de la función β(vx)junto a los puntos con los cuales se realiza la regresión. Es importante destacar que, a partir del primer rebote, la velocidad angular pasa a ser siempre 0, pues resulta muy complicado actualizarla correctamente. Esta simplificación no ofrece malos resultados, ya que es muy infrecuente que se necesite de un movimiento que rebote al menos dos veces. Todas estas decisiones sobre cómo actualizar las velocidades para seguir simulando tras una colisión han sido determinadas empíricamente. Si se impacta con uno de los lados del rectángulo, entonces se descarta el movimiento porque eso significa que ha colisionado contra una esquina de un obstáculo y la trayectoria resultante es muy complicada de predecir. Por último, al igual que hiciéramos con el círculo, debemos prescindir de las caídas que requieran de una velocidad horizontal inicial que es imposible de alcanzar. En la sección 4.2.1 calculamos cuál era el espacio necesario para, partiendo en reposo, lograr una velocidad vxdada. Por tanto, para evaluar si es factible realizar las caídas, simplemente hay que comprobar que hay suficiente espacio en la plataforma simplificada para alcanzar la velocidad deseada. Movimientos BIGHOLEADJ Los movimientos BIGHOLEADJ son, en cierta forma, una mezcla entre los movimientos ADJACENT, FALL y TILT. Supongamos que nos encontramos con el patrón de la Figura 5.16, que llamaremos BIGHOLE (agujero grande). Se trata de dos plataformas a la misma altura, pero el espacio que hay entre ellas es demasiado grande como para que se genere una plataforma ficticia y sus movimientos DROP y ADJACENT asociados. Esto es intencionado, debido a que el rectángulo en su forma horizontal no es capaz de pasar de uno de los lados al otro, aunque coja mucha velocidad.
5.2. Representación del nivel 92 Figura 5.16: Patrón de la estructura BIGHOLE. Nótese que la longitud del hueco es más de la mitad de la anchura del rectángulo en forma horizontal y no se puede repetir la secuencia de la Figura 5.7. Además, la simulación de las caídas hace que el punto de contacto entre el rectángulo y el obstáculo sea en uno de los lados del primero y, en una situación general, querremos descartarlo. Sin embargo, en esta situación, es la única forma de conectar las plataformas. Por eso, decidimos añadir este tipo de movimientos, que en ejecución serán parecidos a un FALL con la forma vertical y un TILT, que haga que el rectángulo se voltee y aterrice en la plataforma de destino en forma horizontal. Se puede acceder a una animación de los movimientos BIGHOLEADJ mediante el siguiente enlace. Movimientos BIGHOLEDROP Los movimientos BIGHOLEDROP son el análogo de los movimientos DROP para el patrón de estructura BIGHOLE, de forma similar a como los movimientos BIGHOLEADJ son el análogo de los movimientos ADJACENT. Sin embargo, estos movimientos son mucho más complicados de solventar. Dado que el hueco es demasiado grande, no sirve la misma estrategia que para los movimientos DROP, que consistía en colocar al rectángulo horizontal encima del hueco, apoyado en las dos plataformas de los lados (Figura 5.7). En esta ocasión, no hay una manera consistente de colocar al rectángulo en esta posición, lo que obliga a encontrar otra estrategia. Al enfrentarnos nosotros mismos a la estructura BIGHOLE, no encontrábamos ninguna manera intuitiva de conseguir caer por el hueco. Por eso, decidimos que la mejor manera de solucionar estos movimientos era que el rectángulo aprendiera a ejecutarlos. Así, diseñamos el nivel de la Figura 5.17. Durante las pruebas, nos dimos cuenta de que, por nuestra discretización, los huecos por los que resultaba difícil caer eran los que tenían una anchura de 14 o 15 cuadrados de 8×8píxeles del juego (la anchura máxima del rectángulo son unos 24-25 cuadrados). Si tenían una anchura menor, podíamos construir una plataforma ficticia y efectuar un DROP. Si tenían una anchura mayor, el rectángulo detectaba
5.2. Representación del nivel 93 Figura 5.17: Nivel utilizado para el aprendizaje de los movimientos BIGHOLEDROP. que podía hacer un movimiento de tipo FALL sin mayores complicaciones. Así, entrenamos por separado ambas anchuras (modificando la anchura del hueco del nivel de la Figura 5.17), ya que preveíamos (acertadamente) que las estrategias serían diferentes. Para el entrenamiento, optamos por la técnica de Q-Learning, al igual que habíamos hecho para el círculo (sección 4.3.3). En la representación del estado, consideramos la distancia horizontal y vertical del centro del rectángulo a la esquina de la plataforma actual en la que está el hueco (llamamos a estos atributos distance_x ydistance_y, respectivamente), la velocidad horizontal del rectángulo (current_velocity), la altura del rectángulo (height) y la anchura del hueco (hole_width). En la tabla 5.2, se muestran detalles de cómo se calculan y miden cada uno de estos atributos, así como un valor que lo ejemplifica para la configuración de la Figura 5.18, en la que la anchura del hueco es 14 y las distancias se miden con respecto a la esquina de color morado. Con todo, la función que queremos maximizar es que distance_y sea menor o igual que 0, lo que significará que el centro del rectángulo está por debajo de la altura de la plataforma, luego este tiene al menos dos de sus vértices por debajo de la altura de la plataforma y, por tanto, caerá por el hueco. A los estados que cumplan esta propiedad se les asignará una recompensan de 500 y a los que no la cumplan, una recompensa de -1, para que el agente aprenda a caer en el menor tiempo posible. La forma en la que se eligen las acciones, cómo se actualizan los valores de la tabla Q y los valores concretos de los parámetros α,γyεson los mismos que los la sección 4.3.3, donde ya introdujimos la técnica del Q-Learning. Realizamos una serie de simplificaciones para acelerar el entrenamiento: En primer lugar, solamente consideramos las distancias menores o iguales que
5.2. Representación del nivel 94 Atributo Cómo se calcula Positivo si Negativo si Valor en el ejemplo Distance_x Medida en cuadrados de 8×8píxeles desde la esquina El centro del rectángulo se encuentra a la derecha de la esquina El centro del rectángulo se encuentra a la izquierda de la esquina -5 Distance_y Medida en cuadrados de 8×8píxeles desde la esquina El centro del rectángulo se encuentra encima de la esquina El centro del rectángulo se encuentra debajo de la esquina 6 Current_velocity Se redondea la velocidad real al múltiplo de 10 más cercano El centro del rectángulo se mueve hacia la derecha El centro del rectángulo se mueve hacia la izquierda 20 Height Se divide la altura real entre 16 y se trunca el resultado Siempre Nunca 6 Hole_width Medido en cuadrados de 8×8píxeles desde la esquina Siempre Nunca 14 Tabla 5.2: Detalles relativos al cálculo del estado durante el entrenamiento de los movimientos BIGHOLEDROP, así como el valor resultante para la configuración de la Figura 5.18. Figura 5.18: Configuración de ejemplo para un BIGHOLEDROP de anchura 14. Se muestran los cuadrados de 8×8píxeles que hay entre el centro del rectángulo y la esquina de la plataforma actual en la que está el hueco, que aparece de color morado. 5 cuadrados de 8×8píxeles. Si el rectángulo se encontraba más alejado, lo acercábamos, haciendo que llegara a una distancia de 5 cuadrados con una
5.2. Representación del nivel 95 velocidad baja y en forma de cuadrado. Esto ayudaba a que comenzara siempre en la misma posición, y es la estrategia que luego seguiríamos para ejecutar un movimiento BIGHOLEDROP1. Por otro lado, si el rectángulo estuviera en la parte derecha del hueco (y no a la izquierda como en la Figura 5.18), podríamos realizar una simetría del estado de manera similar a como hacíamos en la sección 4.3.3. Esto quiere decir que, el estado que asociaríamos, y por tanto el que consultaríamos en la tabla Q, tendría cambiadas de signo la distancia horizontal (distance_x) y la velocidad horizontal (current_velocity), y cambiaríamos la acción MOVE_LEFT por MOVE_RIGHT y viceversa. De esta manera, reducimos a la mitad el número de estados a entrenar. Además, consideramos solamente los estados en los que el centro del cuadrado está encima de la esquina, es decir, distance_y ≥0, ya que si el centro está por debajo de la esquina, significa que hay al menos 2 vértices del rectángulo que ya han atravesado el hueco, de modo que el rectángulo caerá por su propio peso si no ejecuta ninguna acción. Finalmente, asignamos un tiempo límite de 15 segundos al nivel con el hueco de 15 cuadrados y 20 segundos al nivel con el hueco de 14 cuadrados (que es un movimiento más complicado de ejecutar). Esto provocaba que el nivel acabara rápidamente si el rectángulo se quedaba estancado en el hueco o no progresaba, acelerando así el tiempo entre ejecuciones. Además, le incentivaba a aprender a caer lo más rápido posible por el hueco. Solamente actualizábamos la tabla Q si el nivel terminaba, ya fuera porque el rectángulo caía y cogía el diamante o porque se le acababa el tiempo límite. Tras entrenar con estas características, realizamos una prueba para ver el porcentaje de éxito resultante. La implementación resultante de este aprendizaje tenía limitaciones, y no siempre consigue caer por el hueco, sino que muchas veces sigue quedándose estancado, como en la Figura 5.19. Parte de la razón por la que sufrimos estas limitaciones es debido a que el juego no proporciona en ningún momento la orientación que tiene el rectángulo (inclinación respecto al eje horizontal), sino simplemente su posición, velocidad y altura. Dado que no podemos incluir esta orientación en el estado, las configuraciones de la Figura 5.20, suponiendo que el rectángulo lleva una misma velocidad (nula) en ambas, son 1La única diferencia sería que, aunque el rectángulo acabaría con velocidad baja cuando llegue a una distancia de 5 cuadrados, antes de llegar a esa posición iría lo más rápido posible para emplear menos tiempo.
5.2. Representación del nivel 96 Figura 5.19: Configuración en la que el rectángulo se ha quedado estancado intentando realizar un BIGHOLEDROP, siendo incapaz de cambiar de estado. Figura 5.20: Configuraciones diferentes a las que se les asocia el mismo estado. Suponiendo una velocidad horizontal nula, la configuración izquierda consigue caer por el hueco, mientras que la derecha se queda estancada. indistinguibles. Es decir, se les asocia el mismo estado, que es: Distance_x→5 Distance_y→6 Current_velocity →0 Height →6 Hole_width →15 Sin embargo, suponiendo una velocidad horizontal nula, la configuración izquierda consigue caer por el hueco, mientras que la derecha se queda estancada. En consecuencia, no se puede determinar si este estado es deseable o no, ni cuál es la mejor acción a realizar. Aun así, nuestro agente logra caer por el hueco un 26 % de las veces si la anchura del hueco es 14 cuadrados y un 62 % de las veces si es de 15 cuadrados (lógicamente es mucho más sencillo quedar atascado cuando el hueco es más estrecho). Sin embargo, dado que no podemos garantizar que este sea un movimiento que se realice siempre con precisión, activamos su bit risky = true. Recordando lo explicado en la sección 3.3.2 y en la sección 5.2.2, tener este bit activo quiere decir que se intentará evitar realizar esta clase de movimientos, siempre y cuando se encuentre otro plan que coja al menos el mismo número de diamantes. Esto puede verse, por ejemplo, en la Figura 5.21, en la que el plan que se elige es más largo que el que realiza un
5.2. Representación del nivel 97 Figura 5.21: Nivel en el que el plan que se toma, formado por un movimiento BIGHOLEADJ (representado con un punto), un movimiento FALL (marcado con una línea continua) y un movimiento MONOSIDEDROP (dibujado como una línea discontinua), no es el más corto posible porque evita el tener que realizar un movimiento BIGHOLEDROP. solo movimiento de tipo BIGHOLEDROP para caer directamente a la plataforma inferior. Como ya vimos en los movimientos HIGHTILT, priorizamos la consistencia sobre la velocidad. 5.2.3. Filtrado de movimientos De manera similar a lo que sucedía con el círculo, la fase de generación de movimientos produce una gran cantidad de movimientos, siendo algunos de ellos equivalentes. Para reducir los costes computacionales de la posterior búsqueda, es necesario restringirnos a un subconjunto de movimientos que garantice que se puedan recoger todos los diamantes alcanzables y que haya conectividad entre las plataformas. Mientras que en el caso del círculo la redundancia de movimientos se producía, en mayor medida, porque dos movimientos del mismo tipo con parámetros distintos eran equivalentes, en el caso del rectángulo la duplicidad también afecta notablemente a movimientos de tipos diferentes. En esta sección, explicaremos los criterios que seguimos para guardar aquellos más convenientes. Al igual que hacíamos con el círculo, inicialmente descartamos aquellos nuevos movimientos que no nos sirvan para cambiar de plataforma o alcanzar algún diamante. Estos serán los NOMOVE que no recojan diamantes, ya que los demás tipos de movimientos llevan asociado un cambio de plataforma. Si el nuevo movimiento supera este primer filtro, se compara con todos los movimientos ya añadidos para evaluar si puede sustituir a uno (o varios) de los anteriores.
5.2. Representación del nivel 98 Figura 5.22: Estructura de tipo DROP donde hay que prescindir del movimiento FALL espurio (verde) frente a los movimientos ADJACENT (rojos). El primer caso que trataremos es aquel en el que los movimientos comparados no tienen plataformas de partida o aterrizaje iguales. Aunque pudiera parecer que es bueno conservar ambos movimientos, lo cierto es que esto no siempre es así. Supongamos que nos encontramos una estructura de tipo DROP, como la de la Figura 5.22. Ya hemos visto que se generarán movimientos de tipo ADJACENT que conecten la plataforma ficticia con las plataformas reales a su izquierda y su derecha (los movimientos rojos). Lo cierto es que también se pueden generar movimientos de tipo FALL espurios entre las dos plataformas reales y que son indeseados (movimiento verde). En la fase de ejecución, si tenemos movernos entre las plataformas reales, preferiremos hacerlo simplemente deslizando el rectángulo en forma horizontal antes que realizando una caída con las a veces impredecibles colisiones que puedan surgir. Por tanto, cuando se compara un movimiento de tipo ADJACENT y otro de tipo FALL, hay que evaluar si existe otro movimiento de tipo ADJACENT que conforme una situación como la de la Figura 5.22, en cuyo caso se eliminará el movimiento de tipo FALL, conservando los dos de tipo ADJACENT. Nótese que el movimiento ADJACENT de la izquierda tiene como plataforma destino la ficticia (mientras que el movimiento de tipo FALL tiene como destino la de la derecha) y el movimiento de tipo ADJACENT de la derecha tiene como origen la plataforma ficticia (mientras que el movimiento de tipo FALL tiene como origen la de la izquierda). Algo similar sucede con movimientos de tipo FALL y DROP, como se aprecia en la Figura 5.23. Por conveniencia, la plataforma origen del movimiento DROP es la ficticia y se pueden generar movimientos de tipo FALL indeseados que ofrezcan la misma conectividad que un movimiento DROP. Sin embargo, los movimientos de tipo DROP son mucho más estables, más seguros de ejecutar y su resultado no varía al perturbar levemente las condiciones iniciales. En consecuencia, y siguiendo el mismo criterio que en el caso anterior, prescindiríamos del movimiento FALL espurio (verde), conservando los movimientos de tipo ADJACENT (rojo) y DROP (amarillo).
5.4. Ejecución del plan 105 Figura 5.26: Nivel 5 de la competición del rectángulo del año 2013. Figura 5.27: Rectángulo atascado al realizar el movimiento TILT. Lo que vamos a realizar es un bucle en el que vamos decrementando la altura h del rectángulo desde su máximo hasta una unidad más de la altura del cuadrado. Para cada valor de h, simulamos si el rectángulo, realizando el TILT con altura h, colisiona con algún obstáculo. Para entender la simulación, es conveniente observar la Figura 5.28 (cuando el escalón está a la derecha, el procedimiento es simétrico). En la figura, podemos observar la trayectoria del rectángulo a lo largo del tiempo. El rectángulo tiene altura h, que es el parámetro que estamos decrementando y que queremos optimizar. Como su área Aes constante, la base está determinada y tiene longitud fija w=A/h. Si la altura del escalón es a, entonces el radio de la circunferencia descrita por el vértice superior izquierdo del rectángulo es r1=h−a. Análogamente, el radio de la circunferencia descrita por el vértice superior derecho es r2=pr2 1+w2. Con esto, si fijamos el origen de coordenadas en el vértice del escalón, la posición inicial de los vértices superiores izquierdo y derecho son respectivamente Q(0) = (r1cos(θ1), r1sin(θ1)) yP(0) = (r2cos(θ2), r2sin(θ2)) donde θ1=π/2y θ2=arctan(h/w). Es inmediato verificar que la trayectoria que recorren los vértices se puede describir por las curvas P(θ) = (r1cos(θ1+θ), r1sin(θ1+θ)), θ ∈(0, π/2) Q(θ) = (r2cos(θ2+θ), r2sin(θ2+θ)), θ ∈(0, π/2).
5.4. Ejecución del plan 106 Figura 5.28: Análisis de las colisiones de los movimientos TILT variando la altura. Tras estos cálculos, únicamente hay que comprobar, para una discretización de θ, si los píxeles en los que se encuentran P(θ)yQ(θ)tienen tipo distinto de OBSTACLE y PLATFORM, es decir, si la trayectoria colisiona o no con algún objeto. Con este proceso, conseguimos nuestro objetivo de calcular la altura máxima que puede tener el rectángulo para realizar un movimiento de tipo TILT sin quedarse atascado. Si esta altura no es la altura máxima que puede tener el rectángulo, no coincidirá con la altura de ninguna de las tres formas básicas de la Figura 5.1. Por tanto, para integrar este caso a la situación general, formalmente se debería haber hablado durante toda esta sección de “mejor altura” o “altura objetivo”, para referirnos a la altura de la mejor forma o la forma objetivo. 5.4.3. Acción que más acerca al rectángulo a la posición del movimiento En el apartado anterior, explicamos cómo se tratan las formas, cuál es la política que hay que llevar para pasar de una a otra, y cómo solucionamos la problemática de los movimientos de tipo TILT, evitando así que el rectángulo quede atascado. Nuestro objetivo ahora es conseguir que el rectángulo consiga desplazarse hacia una posición dentro de la misma plataforma simplificada y que llegue con una velocidad determinada, olvidando los cambios de forma, ya que eso lo podemos solventar aplicando lo explicado en el apartado anterior. La estrategia es muy similar al caso del círculo. Si recordamos, en la sección 4.3.3 expusimos dos alternativas para escoger la acción que más acercaba al rectángulo a una posición y velocidad dada. Una era un sistema de reglas que tenía en cuenta la velocidad actual y la posición actual y, mediante las ecuaciones del movimiento,
5.4. Ejecución del plan 107 calculábamos puntos de interés que llamábamos punto de frenado y punto de aceleración. Estudiando el signo de la velocidad y discutiendo los casos en función de qué puntos estaban a la izquierda o a la derecha llegábamos a un sistema de reglas que nos permitía tomar la acción (en el caso del círculo ROLL_RIGHT o ROLL_LEFT) que más acercaba al círculo a su posición y velocidad objetivo. La otra alternativa era que el propio círculo aprendiera la acción que debía tomar mediante un algoritmo de aprendizaje por refuerzo, concretamente, mediante Qlearning. Para el rectángulo, hemos optado por utilizar únicamente el sistema de reglas. Esto se debe a que las reglas son prácticamente las mismas a las del círculo. Únicamente hay que tener la precaución de cambiar las acciones asociadas al desplazamiento del círculo (ROLL_RIGHT y ROLL_LEFT) por las análogas para el desplazamiento del rectángulo (MOVE_RIGHT y MOVE_LEFT). Asimismo, las constantes de aceleración no son iguales para el círculo que para el rectángulo, pero simplemente hay que calcular estas aceleraciones del rectángulo con otro experimento. En esencia, todo se reduce a traducir lo que hicimos para el círculo en la sección 4.3.3 y creemos que no merece la pena volver a detallarlo todo de nuevo. Simplemente apuntamos que este sistema de reglas trataba de ir todo lo rápido que pudiera en cada momento y frenar lo más tarde posible, con el objetivo de ahorrar tiempo. Elegir el sistema de reglas evita tener que entrenar al agente una vez más, ya que no nos vale la tabla Q aprendida por el círculo, pues esta se ajustaba a la aceleración propia del círculo, que ya hemos dicho que es diferente de la del rectángulo. Pero es que, además de esta reducción de tiempo y esfuerzo, adelantamos (se verá en el capítulo 7) que el círculo que utiliza aprendizaje por refuerzo obtiene peores resultados que el que utiliza un sistema de reglas, por lo que creemos que la mejor decisión es no implementar las dos versiones del rectángulo. Para el rectángulo, en ocasiones no es tan determinante llegar al punto objetivo con una velocidad concreta, como lo era para el círculo. Depende del tipo de movimiento: ∗En los movimientos de los tipos DROP, NOMOVE, FALL, ADJACENT, HIGHTILT y BIGHOLEDROP, sí es importante llegar con una velocidad concreta. Para estos movimientos, el mismo sistema de reglas que utilizábamos para el círculo ofrece buenos resultados. •Para los movimientos de tipo DROP, la velocidad objetivo es siempre 0, ya que, para comenzar el movimiento, el rectángulo debe estar en forma horizontal, en reposo, alineado con el centro del hueco (ver tercera imagen de la secuencia de la Figura 5.7). •Para los movimientos de tipo NOMOVE, la velocidad objetivo también es siempre 0, ya que, cuando alcanzamos un diamante con un NOMOVE, lo queremos hacer con velocidad baja, porque no podemos saber de antemano si el siguiente objetivo estará a la derecha o la izquierda.
5.4. Ejecución del plan 108 •Los movimientos de tipo FALL han sido simulados partiendo con una determinada velocidad horizontal inicial y, si no cumplimos esa precondición, es muy probable que el resultado de la ejecución diste mucho de lo simulado. •Para los movimientos de tipo ADJACENT, que recordemos conectan plataformas reales y ficticias, hemos comprobado empíricamente que las velocidades altas pueden llegar a ser problemáticas por bugs en el juego. Además, como estos movimientos de tipo ADJACENT pertenecen a estructuras de tipo DROP, suelen preceder en los planes a movimientos de tipo DROP, que tienen velocidad objetivo 0. En consecuencia, es razonable que la velocidad objetivo de los movimientos de tipo ADJACENT sea también pequeña. Hemos considerado, tras la realización de varias pruebas con distintas velocidades, que 50, la décima parte de la velocidad máxima alcanzable, es un valor adecuado de velocidad objetivo de los movimientos de tipo ADJACENT. •Para los movimientos HIGHTILT, recordamos que se necesitaba coger la máxima velocidad posible, que ya se había calculado en la etapa de planificación. Ya que estos son movimientos que hemos catalogado como arriesgados, queremos maximizar las posibilidades de realizarlos con éxito, para lo que debemos llegar con la velocidad objetivo que se les asocia. •Los movimientos BIGHOLEDROP, debido a la implementación que hemos elegido, son parecidos a los movimientos ADJACENT. Dado que hemos optado por utilizar aprendizaje por refuerzo para resolver estos movimientos, y este aprendizaje siempre comenzaba con el rectángulo a una distancia de 5 cuadrados con velocidad muy baja y en forma de cuadrado, ya que esto reducía significativamente la cantidad de estados que se debían entrenar, queremos replicar esas condiciones. Por eso, nos interesa llegar al punto que se encuentra a una distancia de 5 cuadrados con, digamos, velocidad 20, con la que el rectángulo tiene tiempo de sobra para calibrar. Con una velocidad que fuera mucho mayor, el rectángulo no tendría espacio para frenar, y muy probablemente se quedaría estancado en el hueco. ∗Por otro lado, en los movimientos de tipo TILT, BIGHOLEADJ y MONOSIDEDROP, no es crítico llegar con una velocidad determinada. Por tanto, no es necesario un sistema tan sofisticado para asegurarse de que se llega con una velocidad concreta al punto de inicio del movimiento. Simplemente habrá que realizar la acción que más acerque al rectángulo a la posición objetivo, es decir, si el punto objetivo está a la derecha de la posición actual del rectángulo, entonces se tomará la acción MOVE_RIGHT y, en caso contrario, la acción MOVE_LEFT. No va a ser relevante la velocidad que lleve el rectángulo cuando se encuentre en la posición objetivo, pero sí que es de interés que
5.4. Ejecución del plan 109 la velocidad no sea excesivamente grande. Para controlar que la velocidad no se dispare, cuando el módulo de la velocidad es mayor que 2503, tomamos la acción NOACTION para mantener la velocidad. •Para los movimientos de tipo TILT, la velocidad con la que se debe llegar al escalón no es clara, siempre que sea suficientemente grande. Recordamos que los movimientos de tipo TILT pretendían voltear al rectángulo como se aprecia en la Figura 5.11 o en la animación del siguiente enlace. •Para los movimientos BIGHOLEADJ, pretendemos que suceda lo que muestra la animación del siguiente enlace. Como se puede intuir de la animación, perturbaciones de la velocidad no afectarían al resultado final del movimiento. •Finalmente, para los movimientos MONOSIDEDROP, la velocidad tampoco es determinante. Queremos que el rectángulo se comporte como en la animación del siguiente enlace. Al igual que para los movimientos BIGHOLEADJ, el movimiento se efectuará de la misma forma, aunque se llegue con velocidades diferentes. Esto concluye la sección de cómo se elige la acción que más acerca al rectángulo a la posición del movimiento. En la siguiente sección, asumiremos que el rectángulo ya tiene la forma deseada y la posición y velocidad necesarias para iniciar el movimiento, y describiremos las acciones que toma mientras lo ejecuta. 5.4.4. Acción asociada al tipo de movimiento En esta sección, explicamos las acciones que toma el rectángulo desde el comienzo del movimiento. Para ello, debe estar en la posición objetivo con la forma objetivo y la velocidad objetivo (si esta es relevante). Podemos clasificar los movimientos en 3 categorías: movimientos que no realizan ninguna acción, movimientos que realizan siempre la misma acción y movimientos que toman varias acciones diferentes. Movimientos que no realizan ninguna acción En esta categoría, se encuentran los movimientos NOMOVE y los movimientos ADJACENT, que terminan nada más comienzan. Esto se debe a que, en el caso de los NOMOVE, el rectángulo debería coger los diamantes asociados al movimiento si se encuentra en la posición correcta con la forma adecuada, mientras que, en los ADJACENT, el rectángulo cambia de plataforma en la siguiente actualización del 3Como referencia, la velocidad máxima que alcanzaba el círculo era del orden de 200, por lo que 250 no es, en ningún caso, una velocidad pequeña.
5.4. Ejecución del plan 110 estado. En ninguno de los dos casos hay tiempo para realizar ninguna acción. Movimientos que toman siempre la misma acción En esta categoría, se encuentran varios de los movimientos del rectángulo, a los que les basta con tomar siempre la misma acción mientras se ejecutan para completarse. Los describimos a continuación: Movimientos FALL Los movimientos FALL tienen asociada una acción que realizar durante el aire, tal y como se explicó en la sección 5.2.2. Ya anticipamos que, aunque los movimientos FALL deberían incluirse en la categoría de movimientos que toman varias acciones diferentes, consideramos que la simplificación de siempre tomar la misma acción es capaz de generar los movimientos adecuados en todos los niveles, lo que han corroborado todas las pruebas que hemos realizado. En consecuencia, durante un movimiento FALL siempre se toma una de las acciones NO_ACTION, MOVE_LEFT o MOVE_RIGHT. Movimientos TILT Para los movimientos TILT, una vez se llega a la esquina sobre la que el rectángulo debe voltearse (segunda imagen de la figura 5.11), es necesario que el rectángulo continúe ejecutando la acción de desplazamiento lateral, de modo que siga haciendo fuerza con la esperanza de voltearse. Para ello, tenemos una variable que denominamos has_finished_tilt a la que se le da el valor false cuando el rectángulo se encuentra a menos de 3 cuadrados de la posición objetivo, de tal manera que, mientras esa variable tenga el valor false, mantenga su acción actual. Tras varias pruebas, consideramos que liberar el valor de la variable una vez el rectángulo se aleja 4 cuadrados del punto de giro daba resultados satisfactorios. Se puede ver una animación de la ejecución de los movimientos de tipo TILT accediendo al siguiente enlace. Movimientos HIGHTILT En los movimientos HIGHTILT, una vez se acerca a la esquina sobre la que se debe voltear, el rectángulo necesita mantener la acción que esté ejecutando (ya sea MOVE_LEFT, como en el ejemplo de la figura 5.12, o MOVE_RIGHT si la plataforma a la que se pretende subir está a la derecha). Esto ya sucedía en los movimientos TILT, pero en los movimientos HIGHTILT es más importante, lo que nos hizo dejar más margen antes de liberar la variable has_finished_tilt del rectángulo, teniendo que encontrarse a una distancia de 10 cuadrados en lugar de 4, antes de considerar que ha terminado el movimiento. Esto se debe a que, como se puede apreciar en la animación del siguiente enlace, el rectángulo puede alejarse mucho al impactar
5.4. Ejecución del plan 111 contra la esquina. Como ya dijimos en la sección 5.2.2, en muchas ocasiones, el rectángulo no logra subir en el primer intento, y suele quedarse en la posición de la figura 5.12, pero sin moverse, pues la variable has_finished_tilt sigue estando a false. En este caso, hemos de esperar a que se llame al sistema de recuperación, que explicaremos más adelante, de forma que lo aleje de la esquina y se vuelva a empezar el proceso de coger carrerilla. Movimientos BIGHOLEADJ Los movimientos BIGHOLEADJ son similares a los anteriores. Si no ejecutáramos ninguna acción, el rectángulo impactaría contra el otro lado del hueco, con lo que perdería mucho momento lineal y acabaría cayendo, o, aún peor, se quedaría estancado. Esto puede solucionarse si se mantiene la acción que ha tomado para acelerar, de forma que acabe volteándose sobre la esquina de la plataforma de llegada, como se puede observar en la animación del siguiente enlace. En el ejemplo de la figura 5.16, esto corresponde con la acción MOVE_RIGHT, mientras que si el hueco estuviera a la izquierda del rectángulo, sería la acción MOVE_LEFT. Una vez el centro del rectángulo se encuentra en la plataforma de llegada, el movimiento termina (pues el rectángulo se estabilizará por su propio peso y velocidad horizontal). Movimientos que toman varias acciones diferentes En esta categoría, se encuentran los movimientos que toman varias acciones diferentes mientras se ejecutan. Estos son los movimientos más complejos que es capaz de realizar el rectángulo, que son aquellos movimientos que tratan de caer por un hueco. Movimientos DROP Los movimientos DROP requieren más sincronización y precisión que los movimientos mencionados hasta ahora. Una vez nos encontramos en la posición de la tercera imagen de la secuencia de la figura 5.7, el objetivo es ponerse en posición vertical (cuarta imagen de la figura) para caer por el hueco. La primera dificultad que presenta esto es que, como explicaremos más adelante, antes de que el rectángulo elija la acción MORPH_UP para crecer, realizamos una comprobación para verificar que este dispone de espacio suficiente para hacerlo. En el caso de los movimientos DROP, muchas veces esta comprobación cancelaba la acción de crecer e impedía que el rectángulo se pusiese suficientemente vertical como para atravesar el hueco. En consecuencia, tuvimos que crear una variable has_finished_drop que imposibilitara la interrupción del crecimiento del rectángulo. Esta variable se desactiva una vez el rectángulo ha alcanzado su altura máxima. Sin embargo, como se puede observar en la figura 5.8, no basta con caer por el hueco
5.4. Ejecución del plan 112 Figura 5.29: Configuración en la que el rectángulo no ha conseguido ejecutar el movimiento MONOSIDEDROP. y esperar a aterrizar en la plataforma de llegada, ya que esta puede ser ficticia y la atravesaríamos si mantuviéramos la forma vertical. Por ese motivo, decidimos que, en cuanto el rectángulo atravesara el hueco, se intentara hacer horizontal lo antes posible (mediante la acción MORPH_DOWN). De esta manera, el rectángulo aterrizará siempre sobre la plataforma de llegada de manera horizontal. Esto permite que dicha plataforma de llegada pueda ser formalmente ficticia, aunque los puntos reales de apoyo serán las plataformas reales adyacentes, como en el caso de la figura 5.8. Para visualizar el comportamiento de volverse horizontal lo antes posible, junto a la secuencia conjunta de acciones que componen un movimiento de tipo DROP, recomendamos ver la animación del siguiente enlace. Movimientos MONOSIDEDROP Los movimientos MONOSIDEDROP son una combinación de varios de los movimientos anteriores. Aunque el centro del rectángulo llegue al punto medio del hueco de la figura 5.9 (supongamos que se trata del hueco de la izquierda), puede suceder que el vértice inferior derecho todavía siga en la plataforma, especialmente en niveles como el de la figura, donde el hueco es estrecho y no hay mucho espacio para crecer. Por tanto, si no realizáramos ninguna acción, el rectángulo no caería y permanecería apoyado contra la pared, como se muestra en la figura 5.29. Para solucionar este problema, nos aprovechamos de que al otro lado del hueco hay una pared, por lo que podemos mantener la acción MOVE_LEFT (si el hueco estuviera a la derecha de la plataforma de partida, se mantendría la acción MOVE_RIGHT) para asegurarnos de que los cuatro vértices del rectángulo abandonan la plataforma y el rectángulo cae con éxito por el hueco. Podemos ver un ejemplo del comportamiento anterior en la animación del siguiente enlace. Podría parecer entonces que basta con mantener la misma acción y estos movimientos se realizarían siempre correctamente. Sin embargo, ¿qué sucede si la plataforma de destino del movimiento es ficticia? Con esta estrategia, es muy posible que el rec-
5.4. Ejecución del plan 113 tángulo atravesara esta plataforma y cayera más de lo deseado. Al igual que sucedía con los movimientos DROP, es conveniente realizar la acción MORPH_DOWN para adoptar la forma horizontal lo antes posible, siempre que haya espacio suficiente para realizar dicha acción. En resumen, si el centro del rectángulo está por encima del hueco, realizamos la acción que nos hará caer, ya sea MOVE_LEFT o MOVE_RIGHT. Si, por el contrario, el centro del rectángulo está por debajo del hueco, realizamos la acción MORPH_DOWN, como si se tratara de un DROP. Movimientos BIGHOLEDROP Los movimientos BIGHOLEDROP son los movimientos más complicados del rectángulo. Tras la discusión que realizamos en la sección 5.2.2, debería ser evidente por qué pertenecen a esta categoría. El comportamiento de los movimientos BIGHOLEDROP varía de ejecución en ejecución como resultado del entrenamiento. Encontramos que, tras probar varias veces cada nivel, el rectángulo era capaz de seguir estrategias diferentes. Por ejemplo, en este enlace se puede ver una forma de realizar el movimiento, mientras que en este segundo enlace y en este tercer enlace se ven otras maneras diferentes. En consecuencia, la estrategia a seguir es la aprendida por el rectángulo en el entrenamiento y no depende de unas reglas que hayamos implementado nosotros, luego es más difícil de interpretar. Esto concluye la explicación de las acciones que toma el rectángulo en función del tipo de movimiento. En la siguiente sección, explicamos algunas consideraciones adicionales que se tienen en cuenta durante la ejecución del agente. 5.4.5. Comentarios adicionales sobre la ejecución del plan En esta última sección, destacamos otros aspectos que hemos considerado durante el desarrollo del agente, y que han permitido obtener mejores resultados en determinadas situaciones. Sistema de recuperación Comenzamos con uno de las características más importantes de nuestro agente. El comportamiento del rectángulo es bastante impredecible, y las acciones que puede tomar están muchas veces limitadas. Por ejemplo, salvo que el rectángulo tenga algún lado aproximadamente paralelo al suelo, las acciones MORPH_UP y MORPH_DOWN no tienen ningún efecto. Esto quiere decir que, si por ejemplo el rectángulo efectúa un movimiento de tipo FALL, gira durante el aire y acaba inclinado y apoyado sobre una pared, no va a poder cambiar de forma hasta que no se
5.4. Ejecución del plan 114 Figura 5.30: Configuración en la que el rectángulo piensa que está horizontal e intenta realizar la acción de ir a la derecha. Al no caber, su acción no tiene ningún efecto. ponga otra vez “recto”. Por ejemplo, en la situación de la figura 5.29, el rectángulo no sería capaz de realizar las acciones MORPH_UP y MORPH_DOWN, pero en la de la figura 5.9 sí. Sin embargo, como ya mencionamos en la sección 5.2.2, el juego no proporciona en ningún momento la orientación o inclinación del rectángulo. En consecuencia, nuestro rectángulo no tiene manera de saber que se encuentra en una situación en la que no puede crecer o decrecer, y que debe moverse para solucionarlo. Dado que nuestro algoritmo de ejecución intenta ponerse en la mejor forma posible antes de acercarse al punto del movimiento, esta característica del juego es muy problemática, y, sin el sistema de recuperación, nos dejaría estancados en la mayoría de niveles. Para solucionarlo, implementamos un sistema mediante el cual el agente comprueba en cada actualización del estado si alguno de los parámetros que tiene (posición horizontal, posición vertical, velocidad horizontal, velocidad vertical y altura) ha cambiado con respecto a la actualización anterior. Si el estado no varía durante 30 actualizaciones (equivalente a aproximadamente 3 segundos), es porque el rectángulo está intentando realizar una acción que no tiene ningún efecto. Esto puede ser por intentar variar su forma en la situación anterior o por intentar ir a la izquierda o a la derecha cuando se está dando contra una pared. Esto último puede pasar, por ejemplo, en situaciones como la de la figura 5.30. En la situación de la figura, el rectángulo piensa que ya ha adoptado una forma completamente horizontal, debido a la discretización que realizamos. Sin embargo, todavía no es lo suficientemente bajo como para caber por el hueco, por lo que se queda estancado intentando moverse a la derecha. Nuestro sistema de recuperación, al detectar estas situaciones, comienza a tomar acciones aleatorias, actualizándolas cada 200 ms. Debido a lo que hemos explicado en la discusión anterior, no sabemos cuál de estas acciones es la que debemos realizar
6.1. Introducción y retos derivados de la cooperación 121 Figura 6.1: Nivel 1 de la competición cooperativa del año 2013, en el que los diamantes solamente son alcanzables si el círculo salta sobre el rectángulo, el rectángulo crece hasta estar completamente vertical y el círculo vuelve a saltar. Figura 6.2: Nivel 3 de la competición cooperativa del año 2017, en el que el rectángulo es el único que puede alcanzar el diamante de la derecha porque el hueco es demasiado estrecho para el círculo. Sin embargo, el rectángulo no puede subir por sí mismo a la plataforma porque está demasiado alta, y necesita ayuda del círculo para lograrlo. de ellas, o, al menos, a la mayoría. En cuanto a la elaboración del plan, lo primero que debemos reseñar es que hay que construir un plan doble, ya que cada agente necesitará un plan individualizado. En segundo lugar, se debe tener en cuenta cuándo se pueden realizar los movimientos para cambiar de plataforma o alcanzar un diamante. Por ejemplo, en el nivel de la Figura 6.2, el rectángulo no podrá tener en su plan un movimiento en el que se apoye en el círculo y se voltee para subir a la plataforma en la que se encuentra el diamante de la derecha si el círculo no está en la plataforma inferior. De igual
6.1. Introducción y retos derivados de la cooperación 122 Figura 6.3: Nivel 8 de la competición cooperativa del año 2020, en el que el rectángulo es el único que puede alcanzar el diamante, ya que el círculo rebota contra los obstáculos verdes y negros. Sin embargo, el rectángulo no puede llegar por sí mismo a la posición del diamante y, para lograrlo, el círculo debe saltar en el momento adecuado para impulsar al rectángulo mientras este último cae. Figura 6.4: Nivel 9 de la competición cooperativa del año 2013, en el que el rectángulo debe transportar al círculo encima suya hasta el diamante de la derecha, que solamente puede ser alcanzado por el círculo. Nótese que el círculo no puede rodar por la plataforma amarilla porque la atraviesa. forma, en el nivel de la Figura 6.4, el círculo no podrá tener planificada una caída para situarse sobre el rectángulo hasta que el rectángulo este sobre la plataforma amarilla. Todo lo anterior impone ciertas restricciones espaciales que se deben cumplir a la hora de expandir los nodos en la búsqueda. Asimismo, el plan debe ser idealmente óptimo en tiempo. Para ello se debe exprimir al máximo la división de tareas, en la que cada agente puede coger un diamante distinto, pero priorizando siempre que los
6.1. Introducción y retos derivados de la cooperación 123 Figura 6.5: Nivel 6 de la competición cooperativa del año 2016, en el que el diamante dentro del obstáculo amarillo solamente puede ser alcanzado por el círculo. Figura 6.6: Nivel 4 de la competición cooperativa del año 2020, en el que el diamante solamente puede ser alcanzado por el rectángulo. Para ello necesita la colaboración del círculo porque no es capaz de subir de forma independiente a la plataforma, que está demasiado alta. planes alcancen todos los diamantes, luego el orden en el que se cogen y qué agente los alcanza es determinante para completar los niveles (ver Figura 6.7). En este aspecto, debemos tener precauciones a la hora de dar soluciones subóptimas, ya que la cooperación es un cuello de botella de los planes, porque puede tener bloqueado a un agente en una plataforma hasta que el otro finaliza parte de su plan y realicen una acción de cooperación. Por último, la ejecución del plan no es precisamente la parte más sencilla de todo el proceso. Los agentes deben mostrar una gran coordinación para tomar acciones combinadas. Que los agentes no se dejen espacio para realizar las acciones, que el rectángulo no pueda mantener el equilibrio cuando está en forma vertical y el círculo
6.2. Representación del nivel 124 Figura 6.7: Nivel 1 de la competición cooperativa del año 2016, en el que el plan óptimo de alto nivel es: en primer lugar, que el círculo se suba encima del rectángulo para alcanzar el diamante que se encuentra en la zona superior derecha, y que después se dividan las tareas, de forma que el círculo coja el diamante de la esquina superior izquierda y el rectángulo el de la izquierda. Para esto último el rectángulo necesita la ayuda del círculo para subir a la plataforma. Nótese que ninguno de los dos agentes puede coger el otro diamante. se sitúa sobre él o que los agentes quieran ir en direcciones contrarias y choquen, son una pequeña muestra de los problemas a los que se tienen que enfrentar el círculo y el rectángulo. Confiamos en que todo lo anterior haya prevenido al lector de que el problema al que nos enfrentamos es muy complejo. La cooperación multiplica la dificultad, ya de por sí alta, del entorno físico de Geometry Friends y lo hace un banco de pruebas muy interesante para la implementación de técnicas de IA. En las siguientes secciones daremos una explicación detallada de nuestra propuesta para resolver los retos anteriormente expuestos. Como veremos más adelante, somos capaces de completar casi la totalidad de los niveles cooperativos de los años anteriores, hito al que no se habían acercado ninguna de las implementaciones propuestas anteriormente. 6.2. Representación del nivel Para resolver los niveles cooperativos, partiremos de lo realizado para los agentes individuales, empezando con la identificación de plataformas y tratando después la generación de movimientos y su filtrado. Teniendo eso en mente, necesitamos pensar qué representación adicional vamos a necesitar para resolver las situaciones colaborativas que hemos descrito en la sección anterior.
6.2. Representación del nivel 125 6.2.1. Plataformas cooperativas La colaboración más básica, y la primera en la que nos vamos a centrar, es aquella en la que el círculo utiliza de plataforma al rectángulo, con el fin de alcanzar diamantes o plataformas que se encuentren muy altos. Para ello, recordamos que tanto el círculo como el rectángulo habían identificado sus correspondientes plataformas (que en general son diferentes), y las usaban para detectar qué movimientos permitían moverse de una a otra. Esta información puede ser compartida de forma bidireccional entre ambos agentes mediante un sistema de mensajes que ofrece la interfaz del juego. En definitiva, si queremos utilizar al rectángulo de plataforma y detectar qué movimientos son posibles para el círculo cuando se encuentra sobre el rectángulo, la solución más evidente es considerar plataformas ficticias en los lugares donde se podría situar el rectángulo y ver qué elementos se pueden alcanzar desde ahí. De esta forma, al igual que en el desarrollo del rectángulo considerábamos plataformas ficticias en lugares donde el agente podía apoyarse bajo ciertas condiciones (en aquel caso, era que la forma fuera horizontal y hubiese un hueco no demasiado grande entre dos plataformas), decidimos generar plataformas ficticias para el círculo y reutilizar la estrategia que ya seguimos anteriormente. Sin embargo, durante la generación de estas plataformas, nos encontramos con varios elementos a tener en cuenta. En primer lugar, las plataformas del rectángulo debían estar ya generadas, pues es a partir de ellas de donde se crearán las ficticias del círculo. Es decir, solamente tiene sentido considerar aquellos lugares en los que sabemos que el rectángulo puede apoyarse. Además, el círculo se situará a diferentes alturas según la forma que adopte el rectángulo. Por tanto, decidimos crear tantas plataformas como formas básicas (totalmente horizontal, totalmente vertical y cuadrado) admisibles tuviera el rectángulo en esa plataforma. Finalmente, antes de generar la plataforma ficticia, comprobamos que el círculo realmente puede apoyarse en esa posición (supuesto que el rectángulo está debajo) y no choca con ningún obstáculo. Todo esto puede vislumbrarse en la figura 6.8, un nivel dividido en cuatro regiones, donde las plataformas ficticias del círculo en cada una de ellas aparecen de color rosa. Como puede observarse en el nivel de la imagen, el rectángulo tiene una única plataforma simplificada (que solo mira adyacencia independientemente de las formas admisibles del rectángulo), pero tiene múltiples plataformas no simplificadas (que tienen en cuenta las formas admisibles del rectángulo). En la zona de la plataforma marcada de color violeta, el rectángulo solo cabe en forma horizontal (ya que colisiona con el obstáculo amarillo), por lo que solamente se genera esa plataforma ficticia. Por otro lado, en la parte recuadrada de color rojo, el rectángulo puede estar en cualquiera de las tres formas, pero el círculo colisiona con el obstáculo superior si se posicionara encima del rectángulo estando este en posición vertical, por lo que esa plataforma ficticia no se genera. Lo mismo sucede en la parte de color marrón, en
6.2. Representación del nivel 126 Figura 6.8: Nivel en el que la única plataforma simplificada del rectángulo se ha dividido en cuatro regiones en las que se han generado diferentes plataformas ficticias del círculo. la que, de estar sobre el rectángulo, el círculo colisionaría con algún obstáculo que no puede atravesar, salvo que este estuviera en forma vertical (pues el rectángulo sí puede atravesar el obstáculo verde). Por último, en la zona de color cian, se generan las tres plataformas ficticias sin problema. Nótese que las plataformas del último caso tienen diferente anchura en función de la forma del rectángulo a partir de la cual se han generado. Esto se debe a que las plataformas del rectángulo indican dónde puede posicionarse el centro del mismo. De esta forma, aunque el círculo podría estar más a la derecha de lo que indica la plataforma ficticia asociada a la forma horizontal del rectángulo (si se apoyara sobre la parte derecha del rectángulo), la generación que realizamos no es tan extensa. Hubo un momento en el que consideramos extender manualmente las plataformas ficticias generadas para que representaran realmente dónde podía colocarse el círculo sin necesidad de estar sobre el centro del rectángulo, pero, de cara a la ejecución, suponía muchas más complicaciones innecesarias. La aproximación que elegimos, que es la que hemos detallado, aunque no es perfecta, proporciona muy buenos resultados, como ya veremos en la sección 7.4. Si no realizáramos ninguna modificación adicional, las plataformas ficticias que generaríamos tendrían un gran problema, y es que el círculo no sabría cómo pasar adecuadamente de una altura a otra. Con esto, queremos referirnos a que, si el círculo se encuentra encima del centro del rectángulo, que está, por ejemplo, con forma de cuadrado, es obvio que puede acceder a las plataformas ficticias que tiene encima y debajo haciendo que el rectángulo ejecute la acción MORPH_UP o MORPH_DOWN, respectivamente. Es decir, puede cambiar entre determinadas plataformas ficticias sin tener que realizar ningún movimiento. Este fenómeno es similar al que teníamos en el rectángulo con las plataformas no sim-
6.2. Representación del nivel 127 Figura 6.9: Nivel en el que cada plataforma no simplificada del rectángulo, separadas por líneas rojas verticales, genera sus propias plataformas ficticias del círculo, no uniéndose a pesar de que son adyacentes. plificadas: podíamos pasar de una a otra simplemente adoptando la forma adecuada, independientemente de la velocidad que tuviéramos y de manera bidireccional. En consecuencia, decidimos que el círculo también iba a tener asociadas plataformas simplificadas. Así, si la plataforma es real, es decir, el círculo se encuentra encima de un obstáculo, la plataforma simplificada será la misma que la no simplificada; pero, si la plataforma es ficticia, la simplificada agruparía todas las ficticias a las que se pudiera llegar sin más que cambiar la forma del rectángulo. La agrupación de estas plataformas ficticias en plataformas simplificadas no es tan inmediata como pueda parecer. La primera idea que tuvimos fue agrupar aquellas plataformas ficticias que hubieran sido generadas a partir de la misma plataforma no simplificada del rectángulo, pues son las que usamos para esta tarea. Sin embargo, esta primera aproximación dejaba mucho que mejorar, siendo lo más problemático el hecho de que no agrupara plataformas adyacentes, es decir, plataformas ficticias cuyas plataformas no simplificadas del rectángulo, a partir de las cuales se habían generado, estuvieran asociadas a la misma plataforma simplificada. Por ejemplo, en la figura 6.9, las plataformas generadas a partir de las no simplificadas 0 y 1 del rectángulo deberían pertenecer a la misma plataforma simplificada, ya que el rectángulo tan solo debe cambiar a forma vertical para poder moverse libremente entre ellas. Tras este primer e infructuoso intento, probamos a realizar lo mismo, pero agrupando plataformas que se hubieran generado a partir de la misma plataforma simplificada del rectángulo. Si bien esto solucionaba el problema anterior, tenía otras consecuencias aún peores. Si consideramos el nivel de la figura 6.10, podemos ver que las plataformas ficticias de la izquierda y de la derecha se agrupan, cuando claramente no hay manera de ir de una a otra (de hecho, el círculo ni siquiera es capaz de llegar a la parte derecha del nivel). Es decir, si bien antes agrupábamos menos plataformas
6.2. Representación del nivel 128 Figura 6.10: Nivel en el que se generan dos grupos de plataformas ficticias del círculo, pero generadas a partir de plataformas no simplificadas del rectángulo que pertenecen a la misma simplificada, por lo que se unirían incorrectamente. ficticias de las que queríamos, con esta segunda idea agrupábamos de más. La tercera opción que barajamos fue exigir que las plataformas que se agruparan tuvieran que estar conectadas horizontalmente. Esto quiere decir que solamente agruparíamos plataformas cuya proyección en el eje X tuviera intersección no vacía (o estuvieran conectadas a través de una cadena de plataformas ficticias). Esto no se hizo como alternativa al método anterior, sino que se incorporó como una restricción adicional. Si bien esta aproximación mejoraba en gran medida las plataformas resultantes, todavía agrupaba más plataformas de las apropiadas. Tras probar en muchos niveles, encontramos el nivel de la figura 6.11, en el que las dos plataformas ficticias de la izquierda se agrupaban incorrectamente, ya que el círculo no es capaz de moverse entre ellas incluso si el rectángulo cambia de forma, por no poder atravesar el obstáculo verde. Este problema es muy específico, pues se unen incorrectamente plataformas ficticias que se han generado a partir de la misma plataforma no simplificada del rectángulo, y ninguna de las tres aproximaciones que habíamos seguido lo había tenido en cuenta. Por último, dimos con una solución que resultó adecuada en todos los niveles de competiciones de años anteriores que probamos. Partiendo de la idea anterior, añadimos otra nueva comprobación que debía cumplirse para poder agrupar las plataformas. Dada una agrupación A(es decir, una futura plataforma simplificada), para añadir una nueva plataforma pa la agrupación, debía cumplirse que, entre la altura más baja de A(que correspondería a la altura de la plataforma más baja que contenga A) y la altura de p, no podía haber ninguna plataforma prdel círculo que fuera real y cuyos límites horizontales contuvieran los de p. Esto, escrito en términos
6.2. Representación del nivel 129 Figura 6.11: Nivel 8 de la competición de 2017, en el que las plataformas ficticias de la parte izquierda no deberían agruparse a pesar de haberse creado a partir de la misma plataforma, ya que el círculo no puede pasar de una a otra. matemáticos, quiere decir que pse puede añadir a Asi, y solo si, ∄prtal que pr.is_real, pr.righ_edge ≥p.right_edge, pr.left_edge ≤p.left_edge, Sign(pr.height −p.height) = Sign(A.min_height −pr.height), donde Sign(x) es la función signo (0 si xes 0 y |x|/x en caso contrario), por lo que, pensándolo con cuidado, la última condición expresa que la altura de la plataforma prestá entre la de py la más baja del conjunto A. Aunque aún se pueden crear niveles diseñados específicamente para que este sistema de agrupamiento falle, consideramos que eran situaciones demasiado concretas, que nunca se iban a dar en las competiciones reales, donde sí que agrupamos siempre de manera correcta. Como último comentario, hemos tratado de manera especial las plataformas ficticias del rectángulo. A partir de ellas, únicamente hemos creado la plataforma ficticia del círculo asociada a la forma horizontal, ya que la forma de cuadrado es demasiado inestable en cuanto el hueco es mínimamente ancho. Sabemos que esto puede limitar la ejecución en niveles específicos, pero, al no encontrar ninguno en competiciones de años anteriores, y teniendo en cuenta las limitaciones temporales para realizar la implementación de los agentes, decidimos omitirlo. Además, estas plataformas ficticias del círculo, generadas a partir de plataformas ficticias del rectángulo, no se agrupan con el resto, ya que no han sido generadas a partir de la misma plataforma simplificada del rectángulo. Aunque esto parece contradecir la idea original de las plataformas simplificadas del círculo, recordamos que en el rectángulo se hacía lo mismo, y teníamos movimientos específicos para
6.2. Representación del nivel 130 cambiar entre una plataforma ficticia y una real. Como ya veremos, hemos optado por continuar con esta filosofía y generar movimientos para el círculo para estas situaciones. Con esto, concluimos esta sección, de forma que en la siguiente hablaremos de los movimientos adicionales que hemos creado en nuestro desarrollo de técnicas cooperativas. 6.2.2. Generación de movimientos Si bien en la sección anterior nos hemos centrado en la cooperación consistente en que el círculo utilice al rectángulo de plataforma, lo cierto es que, para subir a una plataforma ficticia o para bajar de ella, únicamente se necesitan saltos y caídas, que ya generábamos. Aunque hemos tenido que realizar ciertas modificaciones que describiremos a continuación, adelantamos que la parte principal de esta sección se centra en los movimientos CIRCLETILT del rectángulo, generados para resolver situaciones como la de los niveles de las figura 6.6 y 6.7. Modificaciones a los movimientos del círculo En primer lugar, vamos a explicar los ajustes que hemos tenido que introducir a los movimientos del círculo. Dado que hemos creado plataformas ficticias para el círculo, sus movimientos ahora pueden detectar que aterrizan en una plataforma ficticia. El problema con esto es que, tal y como diseñamos la simulación de movimientos, el movimiento terminaría al llegar a la plataforma ficticia, cuando realmente, salvo que el rectángulo se encuentre justo en el lugar adecuado y con la forma adecuada, el círculo continuaría cayendo hasta aterrizar en una plataforma real. De esta manera, alteramos la simulación de movimientos, de forma que no terminara hasta que no se aterrizara en una plataforma real. Como resultado de la simulación, se devolvería una lista de movimientos, cada uno de ellos simulado hasta el instante en el que se aterrizaba en una plataforma, ya fuera ficticia o real. Así, cada posición y velocidad inicial ya no determinan unívocamente el movimiento, sino que generan una familia de ellos. Esto no es problemático en absoluto para nuestros agentes, ya que simplemente se considerarán como movimientos diferentes, que aterrizan en plataformas diferentes. Toda la simulación de movimientos también se realiza desde las plataformas ficticias, para capturar la posibilidad de que el círculo salte o caiga cuando esté sobre el rectángulo para alcanzar un diamante o moverse a una nueva plataforma. En estos casos, hay que tener la precaución de limitar la velocidad máxima horizontal que el círculo puede alcanzar, ya que el espacio disponible para acelerar cuando se encuentra sobre el rectángulo es escaso. Por lo demás, todo el proceso es el mismo.
6.3. Trazado de un plan a seguir 137 Figura 6.13: Nivel 1 de la competición del año 2016, en el que se indican los posibles movimientos de los agentes desde la situación inicial. ficticia rosa de la izquierda, subir sobre el rectángulo y el movimiento auxiliar de espera/cooperativo. Por su parte, el rectángulo solamente puede subir a la plataforma inmediatamente superior con un CIRCLETILT o generar un movimiento auxiliar de espera/cooperativo. De las ocho combinaciones de movimientos, solamente son válidas tres: que el círculo salte a la plataforma superior y el rectángulo espere en su plataforma; que el círculo salte sobre el rectángulo y este último elija el movimiento auxiliar; y que el rectángulo realice un CIRCLETILT, para lo que el círculo deberá elegir el movimiento auxiliar. Supongamos, por ejemplo, que se expande el primero de los nodos generados, en el cual los agentes se encontrarían en una situación como la imagen superior izquierda de la figura 6.14. Desde esa situación, la lista de movimientos del círculo es saltar a la plataforma superior, saltar sobre el rectángulo, saltar a la plataforma inferior, saltar a la plataforma ficticia rosa de la izquierda y el movimiento auxiliar. Por su parte, los movimientos del rectángulo vuelven a ser los mismos, pero esta vez nunca se podrá elegir el CIRCLETILT porque el círculo no se encuentra en la misma plataforma. Como el rectángulo solo puede elegir el movimiento auxiliar, el círculo ya no puede elegirlo y se vuelven a generar tres nodos (todos los saltos menos el que acaba en la plataforma ficticia de la izquierda porque el rectángulo no está en la plataforma adecuada), frente a los teóricos 5×2 = 10. Si se expandiera el segundo de los nodos, es decir, el círculo salta sobre el rectángulo, nos encontraríamos en una situación como en la de la imagen superior derecha de la figura 6.14. Al procesar la plataforma del círculo, se identificaría que puede alcanzar el diamante superior y después se procedería a expandir los nodos. El rectángu-
6.3. Trazado de un plan a seguir 138 Figura 6.14: Nodos generados a partir del inicial donde las líneas rosas representan plataformas ficticias del círculo. lo, aunque vuelve a tener dos movimientos, solamente puede elegir el movimiento auxiliar cooperativo porque el círculo está sobre él, y el círculo puede elegir entre caer a la plataforma inferior o saltar a la de altura intermedia, pero no puede elegir su movimiento auxiliar ni puede caer sobre la plataforma ficticia de la izquierda. Volvemos a reducir las ocho posibilidades iniciales a solamente dos. Por último, si se expandiera el último nodo, es decir, el círculo ayuda al rectángulo a realizar un CIRCLETILT, los agentes se encontrarían como en la situación de la imagen inferior de la figura 6.14. Entonces, al procesar la plataforma del rectángulo se identificaría que alcanza el diamante de la izquierda y después se procedería a expandir los nodos. Los posibles movimientos del rectángulo son una caída y un movimiento auxiliar y los del círculo son un salto a la plataforma de altura intermedia, un salto sobre el rectángulo, un salto a la plataforma ficticia de la derecha y un movimiento auxiliar de espera. De las ocho posibilidades únicamente son posibles cuatro: o bien que el rectángulo elija el movimiento auxiliar y el círculo aterrice sobre él o en la plataforma de altura intermedia, o bien que el rectángulo caiga y el círculo espere o salte a la plataforma de altura intermedia. En resumen, aunque el factor de ramificación teórico sea aproximadamente 8 en un nivel como el de la figura 6.13 (que es un nivel bastante estándar en cuanto a número de plataformas y conectividad), las restricciones impuestas a la hora de expandir nodos hacen que este factor de ramificación se reduzca a 3 en la práctica. En este nivel, en el que el plan es de los más largos porque tiene 5 pasos, en la práctica se expanden únicamente unos 35= 243 nodos frente a los aproximadamente
6.4. Ejecución del plan 139 85= 32.768 teóricos. 6.4. Ejecución del plan Para concluir la arquitectura de nuestros agentes cooperativos, vamos a explicar cómo deciden qué acciones tienen que tomar en cada momento para alcanzar todos los diamantes, basándonos en los sistemas ya implementados para los agentes individuales. Partimos del plan cooperativo, que se compone de dos planes, uno para cada agente. Como en el caso individual, lo primero que hace cada agente al llegar a una nueva plataforma es alcanzar todos los diamantes que se pueden coger con movimientos que aterrizan en esa misma plataforma. Salvo el caso en el que el agente es el círculo y la plataforma sobre la que está es ficticia, es decir, está sobre el rectángulo, todo lo demás es igual que cuando los agentes actuaban de forma individual. Resumidamente, cada agente identifica el movimiento más cercano que parte de esa plataforma y alcanza un diamante y, mediante los sistemas de reglas basados en las ecuaciones del movimiento, se dirige al punto con la velocidad apropiada como se explicó en las secciones 4.3 y 5.4. Por otro lado, cuando no tienen ningún diamante más que alcanzar en la plataforma en la que se encuentran, los agentes deben ejecutar el primer movimiento de su plan. Si este no es cooperativo, es decir, para el rectángulo no es un CIRCLETILT o un movimiento auxiliar y para el círculo no es un movimiento que aterrice o despegue sobre una plataforma ficticia o un movimiento auxiliar, todo trascurre como lo hacía en los casos individuales. En las siguientes secciones abordaremos los casos cooperativos y que constituyen las diferencias fundamentales con la fase de ejecución de los agentes individuales. 6.4.1. Ejecución de los movimientos de tipo CIRCLETILT En primer lugar, nos planteamos la ejecución de los movimientos de tipo CIRCLETILT. Para ello, asumimos que el círculo y el rectángulo se encuentran en la misma plataforma, que el primer paso del plan del rectángulo es un CIRCLETILT y que el primer paso del plan del círculo es un movimiento auxiliar que se interpreta como que el círculo tienen la obligación de ayudar al rectángulo. Si este no fuera el caso, el sistema de replanificación entraría en juego porque el plan no es correcto. El procedimiento para ejecutar estos movimientos es sencillo, teniendo en mente que buscamos imitar un comportamiento como el descrito en la animación del siguiente enlace. En primer lugar, se le indica al círculo que se dirija, mediante el sistema de reglas físico, al borde de la plataforma en el que se debe posicionar para hacer de punto de apoyo del rectángulo, al lado de la plataforma destino del rectángulo y con velocidad
6.4. Ejecución del plan 140 0. Mientras tanto, se le notifica al rectángulo que se dirija al extremo contrario de la plataforma (para que ambos agentes no se estorben y que tenga suficiente espacio para acelerar) y que espere a que el círculo le dé la señal de que está listo para realizar el movimiento. Cuando el círculo se sitúa en la posición apropiada, envía una señal al rectángulo, que, al recibirla, se dirige con velocidad máxima hacia el punto donde se encuentra el círculo y mantiene la acción hasta que aterriza en la plataforma destino. Adicionalmente, cuando el rectángulo está sobrevolando al círculo, este último salta para darle un pequeño impulso y acelerar el proceso. El único inconveniente que surge en estos movimientos es cuando el rectángulo se encuentra entre el extremo por donde se debe realizar el CIRCLETILT y la posición del círculo, ya que, en ese caso, ambos agentes deben intercambiar sus posiciones. Trataremos estos intercambios de posiciones en un contexto más general en la sección 6.4.4. 6.4.2. Ejecución de movimientos del círculo que aterrizan en el rectángulo El segundo reto cooperativo se da cuando el círculo debe aterrizar sobre una plataforma ficticia, es decir, debe aterrizar encima del rectángulo. Para ello, antes de iniciar el salto o la caída, el círculo debe esperar a recibir una señal informándole de que el rectángulo está listo para servirle de plataforma de aterrizaje, es decir, está en el lugar donde aterrizará el círculo. Lo que debe hacer el rectángulo es ir, mediante el sistema de reglas físico, a esa posición de aterrizaje, que ya se calculó durante la generación de movimientos, y situarse en la forma adecuada para recibir al círculo (se priorizaba la horizontal siempre que era posible por ser más estable). Cuando haya llegado a dicha posición con velocidad 0, activará una señal que le indicará al círculo que ya está listo para servirle de plataforma. Al recibir el círculo la señal, realiza el salto o caída de igual forma que lo haría en el caso individual. A este sistema sencillo, que se puede ver en funcionamiento en la animación del siguiente enlace, le añadimos varias optimizaciones que mejoran enormemente su rendimiento. Recálculo de la trayectoria del círculo Durante los saltos y caídas del círculo, permitíamos que la velocidad horizontal de partida fuera ligeramente distinta de la velocidad objetivo, siempre y cuando el movimiento acabara en la misma plataforma. Como estas pequeñas variaciones en la velocidad horizontal inicial hacían que el círculo aterrizara en un borde del rectángulo, desestabilizándolo, o incluso que aterrizara fuera del rectángulo, decidimos que el rectángulo recalculara la nueva posición de caída del círculo. Este cálculo utiliza el mismo sistema que en la generación de movimientos de saltos y caídas, con la ventaja de que la velocidad horizontal mientras el círculo está en el aire es exacta y nunca varía (salvo colisiones con obstáculos). Durante el vuelo del círculo, el rectángulo intercala llamadas al sistema físico de simulación de parábolas con acciones para
6.4. Ejecución del plan 141 dirigirse a la nueva posición de aterrizaje del círculo, que es cada vez más precisa. Sistema de consolidación del aterrizaje Debido a que el juego Geometry Friends se desarrolla en un entorno físico realista, cuando el círculo aterriza sobre el rectángulo, lo suele hacer con bastante velocidad vertical y se suelen producir pequeños rebotes. Si el rectángulo, inmediatamente después del aterrizaje del círculo, pasara a realizar su siguiente tarea, el círculo caería del rectángulo en la mayor parte las ocasiones. Por tanto, durante el segundo inmediatamente siguiente al primer impacto del círculo con el rectángulo, el rectángulo tiene como deber evitar que el círculo se caiga. Para lograrlo, se le indica que se dirija a la posición horizontal en la que tiene su centro el círculo, con lo que conseguimos alinear los centros de ambos personajes y permitimos que se consolide el aterrizaje. Se puede apreciar cómo el rectángulo recalcula la posición en la que el círculo va a aterrizar, cómo adapta su colocación y cómo espera que el círculo termine de aterrizar en la animación del siguiente enlace. Ajuste de la posición de espera del rectángulo y trayectorias alternativas del círculo Son muchas las ocasiones, como en el nivel de la figura 6.15, en las que la trayectoria del círculo para situarse sobre el rectángulo, colisiona con el propio rectángulo. Es decir, en el nivel de la figura, para alcanzar cualquiera de los diamantes de la parte superior del nivel, el círculo debe primero saltar y aterrizar sobre el rectángulo, pero el movimiento que tiene asignado para hacerlo es de tipo JUMPMOVE y tiene velocidad horizontal 0. Si el rectángulo se situara en la posición de aterrizaje del círculo, el círculo colisionaría con el rectángulo al saltar. Esto se debe a que, en la generación de movimientos del círculo, asumíamos que el rectángulo no se encontraba en ninguna parte del nivel y el círculo, si bien tenía la capacidad de aterrizar sobre él (en las plataformas ficticias), no tenía la limitación de tener que esquivarle en sus saltos y caídas. Para que todo funcione correctamente cuando el rectángulo interseca la trayectoria del círculo, el rectángulo evalúa si, situándose ligeramente a la izquierda o ligeramente a la derecha del punto de aterrizaje, sigue intersecando con la trayectoria del círculo. Evidentemente, no siempre va a poder situarse ligeramente a la izquierda o a la derecha porque, por ejemplo, en el nivel de la figura 6.15, no puede moverse a la izquierda ya que hay una pared. Sin embargo, son muy escasas las ocasiones en las que no puede situarse en ninguno de los dos lados. Una vez el rectángulo estuviera en su nueva posición, el círculo saltaría y, gracias a que se recalculan las trayectorias, el rectángulo acaba situándose en el punto de aterrizaje en el momento en el que se le necesita, como se aprecia en la animación del siguiente enlace.
6.4. Ejecución del plan 142 Figura 6.15: Nivel 8 de la competición del año 2013, en el que el rectángulo está en la trayectoria de salto del círculo para situarse sobre él. Cuando no conseguimos solucionar el problema situando al rectángulo ligeramente a la derecha o a la izquierda del punto de aterrizaje, tenemos que cambiar de estrategia. Lo que hacemos es volver a generar todos los movimientos desde la plataforma en la que se encuentra el círculo y filtramos aquellos que aterrizan en el rectángulo, pero considerando al rectángulo como un obstáculo fijo más. De entre todos ellos, elegimos el mejor movimiento que no interseca con el rectángulo pero aterriza sobre él, de acuerdo al filtrado habitual de parábolas. De encontrar un movimiento adecuado, se reemplaza el salto del plan por el nuevo movimiento. Este proceso es bastante costoso en tiempo porque supone recalcular muchas trayectorias, demorando algunos segundos la resolución del nivel. Sin embargo, este problema no es muy significativo, ya que las trayectorias se recalculan justo cuando se va a comenzar a ejecutar el movimiento, mientras los agentes aún están posicionándose. En consecuencia, y dado que son muy pocos los niveles en los que el problema no se soluciona haciendo que el rectángulo se aparte ligeramente, consideramos esta solución suficientemente buena para nuestros propósitos. 6.4.3. Ejecución de movimientos del círculo que parten del rectángulo En este apartado vamos a suponer que el círculo se encuentra sobre el rectángulo, ya ha aterrizado y también ha consolidado su posición. Se plantean dos posibilidades no excluyentes: el siguiente movimiento del círculo es para capturar un diamante o
6.4. Ejecución del plan 143 el siguiente movimiento le sirve al círculo para cambiar de plataforma. En cualquiera de los dos casos, el círculo debe situarse en una determinada posición dentro de la plataforma ficticia en la que se encuentra y alcanzar una determinada velocidad. Para ello, es el rectángulo el que debe transportar al círculo a su posición objetivo. Por tanto, para realizar ese reto, simplemente se le indica al rectángulo que su posición objetivo es la posición desde la que parte el siguiente movimiento del círculo y su velocidad objetivo es 0. Por su parte, el círculo, para evitar caer del rectángulo mientras es transportado, tiene como objetivo mantenerse en el centro del rectángulo. Eso es sencillo lograrlo, ya que basta indicarle que se dirija a esa posición y que lo haga con velocidad nula (velocidad relativa a la velocidad del rectángulo). Este sistema tan sencillo es sorprendentemente muy efectivo y permite al rectángulo ir tan rápido como pueda para llegar lo antes posible y sin preocuparse de si el círculo cae o no, porque es el propio círculo el que se encarga de mantenerse sobre el rectángulo. En lugar de dirigirse al punto objetivo, el rectángulo se sitúa ligeramente a la izquierda o a la derecha para que el círculo aproveche toda la anchura del rectángulo como plataforma y tenga espacio para acelerar. Cuando ha estabilizado su posición y ha adoptado la forma apropiada, lanza una señal al círculo para que este deje de preocuparse por caer del rectángulo y proceda a realizar el movimiento que tenía planificado. El círculo, actuando como lo haría en el caso individual, salta o cae según proceda. La animación del siguiente enlace muestra el comportamiento descrito. En ese momento se plantean 2 alternativas: o bien la plataforma de aterrizaje del círculo es real o bien es ficticia, es decir, salta del rectángulo para volver a aterrizar en él. Este segundo caso ya lo hemos tratado en la sección 6.4.2 y el rectángulo simplemente recalcula la posición de aterrizaje del círculo y se dirige a ella. El primero de los casos es que la plataforma donde el círculo tiene previsto aterrizar sea real. En este caso también hay dos alternativas, que esta plataforma se encuentre más arriba o más abajo de la posición del rectángulo. Si se encuentra más arriba, y en previsión de un salto impreciso por las complicaciones de la física del juego, el rectángulo está prevenido y se dirige a la posición donde el círculo caería si no consigue completar el salto. Esta posición se recalcula continuamente con llamadas al sistema de simulación de trayectorias parabólicas. Un ejemplo de un salto no exitoso en el que el rectángulo previene una caída y ahorra tiempo se puede ver en la animación del siguiente enlace. Si la altura de la plataforma de aterrizaje del círculo es inferior a la posición del rectángulo, entonces el rectángulo podría estorbar al círculo e impedirle bajar si no le indicamos lo contrario. Por tanto, se calcula la posición horizontal en la que el círculo se encontrará cuando esté a la altura del rectángulo (nuevamente con la simulación de las trayectorias parabólicas), y se le indica al rectángulo que se situé ligeramente a la izquierda o a la derecha de tal manera que no colisione con el círculo. El comportamiento de nuestros agentes en esta situación es el que se muestra en la animación del siguiente enlace.
6.4. Ejecución del plan 144 Figura 6.16: Nivel 9 de la competición cooperativa del año 2015, en el que los agentes no están ordenados igual que sus puntos objetivos. El punto objetivo del círculo (amarillo) está a la derecha del punto objetivo del rectángulo (verde), pero el círculo no está a la derecha del rectángulo. 6.4.4. Intercambios de posición Una situación aparentemente sencilla y que nos ha supuesto un quebradero de cabeza durante el desarrollo de los agentes cooperativos viene dada por los intercambios de posición. Cuando los agentes se encuentran en la misma plataforma pero no se encuentran ordenados respecto a los puntos objetivos donde desean ir (ver figura 6.16), deben intercambiar sus posiciones para estar en el orden correcto. Aunque en el nivel de la figura parece evidente que el círculo debe saltar al rectángulo en el centro del nivel, esta situación no es fácilmente generalizable. En algunas ocasiones, no hay espacio suficiente para que el círculo salte por encima del rectángulo, y no es sencillo identificar en qué parte de la plataforma es posible hacer el intercambio. Para realizar los intercambios optamos por un sistema alternativo. Los agentes se dirigirán el uno hacia el otro, con el rectángulo en forma vertical. Con ello pretendemos que el círculo sirva de pivote para el rectángulo y le permita voltearse e intercambiar posiciones con el círculo. Podemos ver una demostración del sistema de intercambio de posiciones en la animación del siguiente enlace. Sin embargo, este método tiene sus limitaciones cuando los agentes cuentan con poco espacio para realizar el intercambio porque hay obstáculos cerca. En ocasiones, los agentes se quedan atascados y no podrían continuar si no fuera por el sistema de recuperación que presentamos a continuación.
6.5. Visualización y explicabilidad de la cooperación 145 6.4.5. Sistema de recuperación De igual manera que hiciéramos con el rectángulo, hemos implementado un sistema que identifica cuándo los personajes están atascados y toma acciones aleatorias para salir de ese estado. Concretamente, se evalúa si los agentes están suficientemente próximos y permanecen en la misma posición durante un periodo de tiempo mayor que 3 segundos. De darse ese caso, los agentes comienzan a tomar acciones aleatorias que mantienen durante 300 ms. Para el círculo, la probabilidad de realizar un salto (una medida algo más drástica e imprevisible que rodar a izquierda o derecha) es de solamente un 10 %, mientras que las otras dos acciones tienen ambas una probabilidad del 45 %. Una pequeña optimización que mejora la actuación de los agentes en algunos niveles y no les perjudica en ninguno es incrementar el tiempo que se mantiene la acción aleatoria en 100 ms cada vez que los agentes vuelven a quedar atascados. De esta manera, si los agentes quedan recurrentemente atascados, las acciones aleatorias se tomarán durante más tiempo y hemos comprobado empíricamente que es más probable que salgan del estado de bloqueo, especialmente en situaciones en las que, aunque consigan separarse, es fácil que vuelvan a quedar bloqueados. Esto finaliza las explicaciones relativas a la ejecución de movimientos por parte de los agentes y la coordinación. En la siguiente sección, expondremos un sistema de explicabilidad que permite a los usuarios ajenos al proyecto entender las decisiones de los agentes. 6.5. Visualización y explicabilidad de la cooperación Una vez ya hemos desarrollado en profundidad el funcionamiento completo de nuestros agentes cooperativos, queremos detenernos para abordar el problema de la explicabilidad. Como desarrolladores, nosotros muchas veces sabemos qué es lo que está haciendo cada agente en cada momento o cuáles son sus subojetivos a corto plazo, pero, para una persona ajena al proyecto, hemos identificado que existen problemas para comprender las decisiones que toman los agentes. Por ese motivo, y con ayuda del depurador visual que viene incorporado con el juego, hemos desarrollado un sistema de explicabilidad que permita entender la motivación del agente para realizar las acciones o movimientos a distintos niveles. Este problema de comprensión no se da únicamente con los agentes cooperativos, sino que también afecta, aunque en menor medida, a los agentes individuales. Por ello, y por las limitaciones temporales, nos hemos restringido a desarrollar el sistema de explicabilidad exclusivamente para los agentes cooperativos. Sin embargo, los agentes individuales también muestran cierta información por pantalla, aunque esta
6.5. Visualización y explicabilidad de la cooperación 146 está menos ordenada y puede ser quizás menos comprensible para un usuario ajeno al proyecto, ya que es la que utilizábamos como desarrolladores para depurar el código. Aun así, consideramos que es suficiente para interpretar las acciones tomadas por los agentes individuales, ya que estas son muy intuitivas la mayor parte de las veces. Para desarrollar el sistema de explicabilidad cooperativo, lo primero que debemos hacer es presentar de manera oficial al sistema de depuración visual, y apostillamos lo de oficial, ya que, en el fondo, ha estado presente en muchas de las figuras que han aparecido en la memoria hasta el momento. Este sistema nos ha posibilitado la elaboración de gran cantidad de las figuras de imágenes del juego durante su ejecución, y sobre las que hemos podido añadir parábolas, texto, píxeles u otras trayectorias e información. Para poder mostrarlo y ocultarlo, el usuario de la aplicación debe pulsar la tecla F1 durante la ejecución de los niveles. En la sección 3.2, vimos las funciones que el juego Geometry Friends ofrece a los agentes en forma de interfaz para interaccionar con él, como, por ejemplo, los métodos Update oGetAction. En ese momento, obviamos deliberadamente el método GetDebugInformation, que comunica al juego la información que debe imprimir en el depurador visual por pantalla. Lo que devuelve periódicamente este método es una lista de objetos de tipo DebugInformation que pueden ser tanto un nuevo lienzo sobre el que pintar como un círculo, un rectángulo, una línea o incluso texto. Existen funciones para crear cada uno de estos objetos, establecer su tamaño y posición dentro del lienzo, su color y, en el caso del texto, el mensaje. Con estas herramientas, hemos creado la interfaz visual de explicabilidad, pero debemos advertir que el depurador visual que ofrece el juego presenta un problema que limita en gran medida la cantidad de información que se muestra en pantalla. A medida que se añaden más objetos que pintar sobre el lienzo en la lista devuelta por GetDebugInformation, el rendimiento de la aplicación se resiente notablemente, los agentes se mueven de forma entrecortada, y su precisión decae. Por tanto, es preciso encontrar cierto equilibrio entre la cantidad de información que se muestra por pantalla y el rendimiento de la aplicación. El aspecto de la interfaz de explicabilidad es el que se muestra en la figura 6.17. Aunque pueda parecer recargado, advertimos que se puede eliminar cierta información que no se desee mostrar de manera muy sencilla, con tan solo comentar unas líneas de código que están claramente identificadas. A lo largo de la explicación, iremos ocultando o mostrando ciertas partes de la interfaz para focalizarnos en la parte que exponemos. En primer lugar, podemos observar que la interfaz visual se divide fundamentalmente en tres partes. En la parte izquierda, se muestra la información relativa al círculo (sobre un fondo de color amarillo claro), en la derecha, la información del rectángulo (sobre un fondo de color verde claro), y, dentro del nivel, la información de plataformas, puntos de interés, trayectorias y movimientos del plan, entre otros. Hacemos notar que el sistema proporcionado por el juego para mostrar información