Creación de bots para Ms-Pacman basados en gramáticas evolutivas

Creaci´on de bots para Ms-Pacman basados en gram´aticas evolutivas Trabajo Fin de Grado H´ector Laria Mantec´on Jorge S´anchez Cremades Jos´e Miguel Tajuelo Garrig´os Jorge Vieira Luna dirigido por Carlos Cervigon R¨uckauer Antonio A. S´anchez-Ruiz Departamento de Ingenier´ıa del Software e Inteligencia Artificial Facultad de Inform´atica Universidad Complutense de Madrid Junio de 2017 ii Agradecimientos Queremos agradecer en primer lugar a nuestras familias, parejas, amigos y compa˜neros por su gran apoyo e inter´es durante la realizaci´on de este proyecto. Adem´as, estamos especialmente agradecidos por acogernos como tutores, as´ı como ayudarnos con su trabajo, su paciencia y su dedicaci´on a Carlos Cervigon R¨uckauer y a Antonio A. S´anchez-Ruiz, que nos han orientado tanto a la hora de realizar y estructurar el Trabajo de Fin de Grado de forma que fuera lo menos ca´otico posible y llegase a buen puerto, a costa de infinitas revisiones, correcciones y tiempo. Tambi´en agradecerles su trabajo y dedicaci´on a Philipp Rohlfshagen, Simon Lucas y David Robles, creadores del fant´astico framework que usamos para Pac-Man, con los que hemos tenido oportunidad de establecer contacto. Es una suerte disponer de proyectos como el suyo, que a´un a d´ıa de hoy sigue generando competiciones que motivan a gente como nosotros a investigar y desarrollar. Por supuesto no podemos olvidar a Jos´e Luis Risco Mart´ın, Jos´e Manuel Colmenar Verdugo y Josu´e Pag´an Ortiz, creadores y desarrolladores del framework JECO, sin el cual no habr´ıa sido posible este trabajo. Y por ´ultimo y no menos importante, queremos expresar nuestro agradecimiento a la Universidad Complutense de Madrid, a la Facultad de Inform´atica y en especial a sus profesores, gracias a los cuales hemos tenido la oportunidad de aprender las bases necesarias para llegar hasta aqu´ı y poder realizar un trabajo en el que hemos tenido la oportunidad y la necesidad de entremezclar conocimientos de un mont´on de facetas de la inform´atica. iii iv Resumen Desde el nacimiento de los videojuegos la inteligencia artificial ha ido de la mano de estos, ya sea aplicando t´ecnicas para el comportamiento de personajes, estrategias de los enemigos, trazado de rutas, etc. Queremos experimentar en nuestro trabajo con la evoluci´on gramatical (una variante de la programaci´on gen´etica) para evolucionar bots cuyo comportamiento se genera desde la derivaci´on de reglas gramaticales, y ver qu´e resultados da a la hora de aprender a jugar. Para ello hemos experimentado evolucionando un bot para el juego Ms. Pac-Man vs Ghosts, un famoso arcade que posee varios subobjetivos como sobrevivir el mayor tiempo posible, comer la mayor cantidad de p´ıldoras, comer tantos fantasmas como se pueda o pasarse tantos niveles como se pueda antes de que nos coja un fantasma. Concretamente hemos experimentado y mostramos resultados para controladores basados primero en gram´aticas que proporcionaban secuencias de movimientos, generando conceptualmente un aut´omata, mejor´andolos luego introduciendo s´ımbolos condicionales. Tras eso abandonamos los aut´omatas y las secuencias de acciones repetidas en bucle por ´arboles de decisi´on, los cuales generamos con varias gram´aticas diferentes, con acciones de bajo, medio y alto nivel respectivamente. Para todas ellas analizamos sus resultados y sacamos conclusiones. Experimentamos tambi´en con diversas mejoras a la evoluci´on gramatical, como son: Optimizaci´on multi-objetivo: Por lo ´util de poder modificar el comportamiento del bot con simplemente cambiar las funciones de evaluaci´on del algoritmo, para alcanzar subobjetivos que consideramos m´as importantes en una determinada situaci´on, y combinarlos entre s´ı. Operadores de cruce y mutaci´on especializados, como cruce LHS y mutaci´on neutral, que mejoren el rendimiento del algoritmo en tiempo y resultados. En definitiva, en este trabajo mostraremos que el enfoque basado en evoluci´on gramatical tiene muchas posibilidades de mejora y consigue buenos resultados a la hora de desarrollar bots que aprendan a jugar a videojuegos. Para Pac-Man obtienen puntuaciones muy altas y completan varios niveles, superando incluso a los bots hechos a mano u otros bots evolutivos conocidos. v Palabras clave Pac-Man, Ms. Pac-Man vs Ghosts, Inteligencia Artificial, Programaci´on Evolutiva, Programaci´on Gen´etica, Evoluci´on Gramatical, Multi-objetivo, ´ Arboles de Decisi´on. vi Abstract Ever since the birth of video-games we have seen artificial intelligence techniques applied to them: Character behaviour, enemy strategies, path-finding, etc. We want to explore the possibilities of Grammatical Evolution (a Genetic Programming variant) to evolve game strategies generated from the derivation of defined grammar rules. For this purpose, we experimented with the evolution of a bot for Ms. Pac-Man, a well-known game which can have many sub-goals, like surviving the most time possible, eating the most pills, killing as many ghosts as it can, or go through a lot of levels before dying to the ghosts. We have experimented and will show results for controllers based firstly in grammars that generated a sequence of movements, later including conditions in this sequence. After that we switched from the repetition of sequences to decision trees, which we have generated using different grammars with low, mid and high level actions. For each of them we show results and obtain conclusions. We will also test some upgrades to grammatical evolution, like: Multi-objective optimization: Given the complexity of the algorithms used and the usefulness of being able to modify the artificial intelligence behaviour swiftly, by simply changing the evaluator functions depending on what goals we want to achieve. Specialized cross and mutation operators, like LHS cross-over and neutral mutation. In the end we will show that a grammatical evolution approach has a lot of room to improve its efficiency, gets very good results when faced with obtaining controllers for video games, getting high scores for Pac-Man, as well as passing many levels, overcoming hand-made bots and others that have used evolutionary techniques previously. Keywords Pac-Man, Ms. Pac-Man vs Ghosts, Artificial Intelligence, Evolutionary Computation, Genetic Programming, Grammatical Evolution, Multi-objective, Decision Trees. vii viii ´ Indice general Agradecimientos III Resumen V Abstract VII 1. Introducci´on 1 1.1. Motivaci´on ................................... 1 1.2. Objetivos .................................... 2 1.3. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Introduction 5 2.1. Motivation ................................... 5 2.2. Objectives.................................... 5 2.3. Documentstructure .............................. 6 3. Programaci´on evolutiva 9 3.1. Algoritmos evolutivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2. Programaci´on gen´etica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3. Gram´aticas independientes del contexto . . . . . . . . . . . . . . . . . . . 15 3.4. Evoluci´on gramatical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.5. Algoritmos Evolutivos Multiobjetivo . . . . . . . . . . . . . . . . . . . . . 19 3.5.1. JECO .................................. 21 4. Ms. Pac-Man 23 4.1. Descripci´on del juego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2. Arquitectura para crear bots . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3. Competiciones ................................. 25 5. Bots basados en secuencias de acciones 27 5.1. Integraci´on de Ms. Pac-Man y JECO . . . . . . . . . . . . . . . . . . . . . 27 5.2. Ideageneral................................... 28 5.3. Unprimerbot ................................. 29 5.4. Incorporando condicionales y acciones de alto nivel . . . . . . . . . . . . . 30 ix xvi ´ Indice de tablas 5.1. Fenotipo y puntos del primer bot de secuencias de acciones. . . . . . . . . 30 5.2. Acciones y condiciones de alto nivel desarrolladas. . . . . . . . . . . . . . 30 5.3. Fenotipo y puntos de los siguientes bots con condicionales y acciones de altonivel. .................................... 31 6.1. Par´ametros utilizados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2. Pac-Man de bajo nivel contra varios controladores de fantasmas. 1000 ejecuciones. ................................... 53 6.3. Pac-Man de medio nivel contra diversos fantasmas. 1000 ejecuciones. . . . 54 6.4. Pac-Man de alto nivel contra diversos fantasmas. 1000 ejecuciones. . . . . 55 7.1. Estad´ısticas del n´umero de codones utilizados para generar el fenotipo de los individuos de una poblaci´on de 100 individuos. Longitud m´axima del genotipo:100codones.............................. 60 7.2. Estad´ısticas del n´umero de codones utilizados para generar el fenotipo de los individuos de una poblaci´on de 100 individuos. Longitud m´axima del genotipo:50codones............................... 61 9.1. Par´ametrosusados................................ 82 9.2. Pac-Man vs Ghost controllers’ comparison. 1000 games. . . . . . . . . . . 85 9.3. Pac-Man vs Ghost controllers’ comparison including Multi-Objective. 1000 games....................................... 86 10.1.Parametersused................................. 88 xvii xviii Cap´ıtulo 1 Introducci´on 1.1. Motivaci´on Desde el nacimiento del mundo de los videojuegos siempre ha sido necesario utilizar en ellos t´ecnicas de inteligencia artificial: para encontrar caminos ´optimos entre dos puntos, evitar obst´aculos, adaptar comportamientos de personajes u objetos, etc. Adem´as, una de las dificultades de la inteligencia artificial, el requerimiento de un sistema de percepci´on fiable, se resuelve con gran facilidad en los videojuegos simplemente leyendo informaci´on del estado del juego. A su vez los videojuegos son la plataforma perfecta para desarrollar, probar y mejorar diversas t´ecnicas de aprendizaje, dado que son entornos controlados, en los que se pueden realizar multitud de experimentos con gran rapidez, a la vez que permiten definir diferentes problemas con facilidad, tanto en estructura como en dificultad. Hemos elegido Pac-Man por disponer de una versi´on con una interfaz f´acil de creaci´on de controladores, poder comparar nuestros resultados con otros existentes (ya que se realizan competiciones), y la relativa sencillez del c´odigo y el juego en s´ı mismo frente a la complejidad que conlleva implementar un controlador que juegue bien utilizando t´ecnicas de inteligencia artificial. Los controladores, o “bots”, simulan un jugador humano tratando de lograr los objetivos del juego. Para ello determinan que movimientos o acciones han de hacerse en cada momento de la partida, mediante t´ecnicas de algoritmia muy diversas. Nuestro objetivo es experimentar en este sentido, intentando generar bots que se comporten de manera intuitivamente razonable, y que sean capaces de obtener puntuaciones y resultados inalcanzables para jugadores amateur. Para ello, tras decidir centrarnos en el campo de la programaci´on evolutiva, hemos optado por generar dichos bots mediante el uso de gram´aticas evolutivas. Esta decisi´on se debe a dos razones de peso. La primera, las facilidades que ofrecen a la hora de resolver problemas que requieran la generaci´on de bloques de c´odigo, al ser el lenguaje en el que est´e codificado f´acilmente definible por una gram´atica. La segunda, la relativa escasez de material a´un al respecto, sobretodo tratando de aplicar mejoras como multi-objetivo o mutaci´on neutral. 1 2Cap ´ ıtulo 1. Introducci´on 1.2. Objetivos El objetivo general de nuestro trabajo se centra en desarrollar una plataforma donde poder evaluar la viabilidad y el ´exito del uso de gram´aticas evolutivas para tomar decisiones en tiempo real, explorando diversas mejoras posibles conocidas en evoluci´on gramatical. En concreto evaluaremos su efectividad creando un bot capaz de jugar al popular arcade Ms. Pac-Man y analizando los resultados en forma del comportamiento del bot, puntos obtenidos u otras variables. Un compendio de objetivos concretos, como punto de partida y que han surgido a lo largo del trabajo son los siguientes: Integraci´on del juego Ms. Pac-Man con un framework que permita el uso de gram´aticas evolutivas (JECO), para as´ı permitir a nuestro bot tomar decisiones utilizando evoluci´on gramatical. Creaci´on de un traductor de ´arboles de derivaci´on expresados como cadenas de caracteres, generadas mediante evoluci´on gramatical, a ´arboles t´ıpicos de nodos terminales y no terminales interpretados como ´arboles de decisi´on, capaces de representar movimientos o llamadas a funciones proporcionadas por la implementaci´on de Pac-Man, que permitan consultas al estado del juego en las gram´aticas que desarrollemos. Prueba y evaluaci´on de diferentes gram´aticas, con espacios de soluciones de complejidad variable, as´ı como con m´as o menos conocimiento experto agregado a la toma de decisiones. Experimentaci´on con diversas t´ecnicas que potencialmente pueden mejorar el rendimiento de las gram´aticas evolutivas, como fitness multi-objetivo, operadores de cruce (LHS) y mutaci´on especializadas (mutaci´on neutral). 1.3. Estructura de la memoria La estructura de la memoria consta de los siguientes cap´ıtulos. Cap´ıtulo 1 y Cap´ıtulo 2: Introducci´on. En estos cap´ıtulos, escritos en espa˜nol e ingl´es respectivamente, se expone la motivaci´on de nuestro trabajo, sus objetivos y la estructura que sigue este documento. Cap´ıtulo 3: Programaci´on evolutiva. En este cap´ıtulo describimos las principales t´ecnicas relacionadas con la evoluci´on de programas que usamos en el trabajo y el estado del arte de las mismas. Cap´ıtulo 4: Ms. Pac-Man. 1.3. Estructura de la memoria 3 En este cap´ıtulo describimos el juego en el que se basa el trabajo, el framework del juego que utilizamos, la arquitectura de controladores en la que se basa y comentamos las competiciones en las que se ha usado con anterioridad. Cap´ıtulo 5: Bots basados en secuencias de acciones En este cap´ıtulo detallamos nuestros primeros experimentos usando evoluci´on gramatical con el objetivo de producir programas simples representados como cadenas de acciones prefijadas y las limitaciones que posee este sistema. Cap´ıtulo 6: Bots basados en ´arboles de decisi´on. En este cap´ıtulo describimos en detalle el paso realizado para representar los programas evolucionados como ´arboles en los que se integran evaluaciones condicionales. Explicamos las gram´aticas desarrolladas y los resultados obtenidos. As´ı mismo, tambi´en incluimos las mejoras implementadas al algoritmo de evoluci´on gramatical para obtener mejores resultados. Cap´ıtulo 7: Estudios, optimizaciones y mejoras. En este cap´ıtulo mostramos diferentes estad´ısticas y estudios sobre los algoritmos utilizados, as´ı como algunas optimizaciones de los frameworks usados y explicamos las implementaci´ones adicionales que hemos realizado para el trabajo. Cap´ıtulo 8: Herramienta gr´afica de experimentaci´on. En este cap´ıtulo describimos la interfaz gr´afica de nuestro programa desarrollado para poder realizar este trabajo. Cap´ıtulo 9: Conclusiones. En este cap´ıtulo, redactado en espa˜nol e ingl´es, mostramos las conclusiones obtenidas sobre nuestro trabajo y qu´e trabajo futuro puede hacerse sobre lo ya realizado. Cap´ıtulo 11: Contribuciones. En este cap´ıtulo se explican de manera resumida las contribuciones particulares de cada integrante del grupo. 4Cap ´ ıtulo 1. Introducci´on Cap´ıtulo 2 Introduction 2.1. Motivation Since the birth of video-games it has always been necessary to use Artificial Intelligence techniques on them: For path-finding, obstacle avoiding, NPC behaviour and such. Also, one of the problems of Artificial Intelligence, the requirement of trustworthy samples, is very easy to solve in video-games, with mere calls to game state providers. Video-games are the perfect platform to develop and test various learning techniques since they provide controlled environments, in which is very easy to run massive amounts of experiments in a very short period of time. It is also very easy to specify problems in games, both in structure and difficulty. We have chosen Pac-Man because we found a very simple and easy interface to make controllers, we would be able to compare ourselves to previous ones (since there are competitions) and the relative simplicity of the code and the game itself compared to the complex task of developing a bot that plays nicely using Artificial Intelligence techniques. The controllers, or “bots”, emulate a human player trying to achieve the game goals. For this task, the bot determines which movement or action has to be done every time Pac-Man can move, which can be done with many different algorithmic approaches. Our primary objective is to experiment in this area, trying to generate bots that obtain high scores and results that would normally be unreachable for human players. We have opted for Grammar Evolution as our bot architecture. There are two reasons for this: Firstly, it is very easy to define behaviour for a game like Pac-Man in a grammar. Second, there hasn’t been much work related to grammatical evolution, especially trying some upgrades to the architecture like multiobjective oriented evaluation and operators like neutral mutation. 2.2. Objectives The main goal of our project will be developing a framework where we can test how good the use of grammatical evolution can be when faced with making real-time 5 6Cap ´ ıtulo 2. Introduction decisions, exploring some upgrades to the architecture. We will test its effectiveness developing a bot that can play Pac-Man, and will analyse the results in various terms, namely score, levels reached or other variables. A list of agreed detailed objectives to develop during the project are the following: Integration of the Ms. Pac-Man game with a framework that allowed for grammatical evolution techniques (JECO), so that our bot could use grammars. The development of a parser from derivation trees encoded as strings, originated with grammatical evolution, to a decision tree of terminal and not terminals that could encode game function calls and actions. Testing and evaluation of various grammars with different search space complexity, and various degrees of expert knowledge aggregated. Experimenting with various upgrades for grammatical evolution, like multi-objective fitness and specialized operators like LHS crossover or neutral mutation. 2.3. Document structure The structure of this document consists of the following chapters. Chapter 1 and Chapter 2: Introduction. In this chapters, written in Spanish and English respectively, we explain our motivation, the objectives we aimed for with this work and the structure of it. Chapter 3: Evolutionary Computation. In this chapter we introduce the main techniques used to evolve the programs we use in the work, as well as a description of the current state of the art. Chapter 4: Ms. Pac-Man. In this chapter we present the game we have used, its framework and its controller architecture, and we comment the competitions in which it has been used. Chapter 5: Sequence-of-actions based bots. In this chapter we describe our early experiments using Grammatical Evolution in order to produce simple programs, represented as strings of fixed actions. We also point out the limitations of this system. Chapter 6: Decision Trees based bots. In this chapter we detail the step towards representing evolved programs as trees in which we integrate conditional evaluations. Developed grammars and results obtained are also explained. Moreover, we include improvements to the grammatical evolution algorithm. 2.3. Document structure 7 Chapter 7: Studies and optimizations. In this chapter we cover some statistics and studies we made about the algorithms used and the different optimizations we performed on the frameworks, in addition to additional techniques implemented for completeness. Chapter 8: Graphic interface. In this chapter we showcase the graphic interface developed for interactive visualization and a swifter progress. Chapter 9: Conclusions. In this chapter, written in English and Spanish, we discuss the conclusions of our project and possible future work. Chapter 11: Contributions. In this chapter we summarize the contributions of each member of the group to the project. 14 Cap ´ ıtulo 3. Programaci´on evolutiva La programaci´on gen´etica no est´a exenta de problemas y uno muy com´un es el Bloating. Al realizar la operaci´on de cruce, el ´arbol de los nuevos individuos generados pueden tener un tama˜no excesivamente grande y que puede ir a m´as dado que este puede ser cruzado en generaciones posteriores (llegando a tener individuos con ´arboles extremadamente largos esparcidos por la poblaci´on). Adem´as, esto genera la aparici´on de intrones, grupos de nodos en el genotipo que generan trozos de c´odigo que no aportan nada a la funcionalidad del c´odigo generado y que intensifican la formaci´on de Bloating. ... if ( distFantasmaMasCercano > 20) { if ( distFantasmaMasCercano < 10) { // Secci ´on de programa que nunca llegar ´a a ejecutarse } } ... Figura 3.5: Ejemplo de intr´on. Hay varios m´etodos para intentar solventar el problema del Bloating: Naive: se empeora el fitness precalculado de todos los individuos en la siguiente cantidad Valor de empeoramiento del fitness = kempeoramiento ∗tamano del ´arbol donde kempeoramiento es una constante previamente elegida. De este modo, los individuos con valores de fitness similares pero con un genotipo m´as largo son penalizados frente a los individuos con genotipos m´as cortos. Tarpeian: trata de eliminar individuos que excedan la extensi´on media de la poblaci´on en base a una probabilidad. Si un individuo con longitud de genotipo superior a la media ha sido elegido para su eliminaci´on se le asigna el valor del peor fitness posible de tal forma que en la siguiente generaci´on este individuo tenga muy pocas probabilidades de ser seleccionado y se elimine. Covariant Parsimony Pressure: [32] funciona igual que el metodo Naive pero empleando un valor de kempeoramiento calculado en cada generaci´on mediante una f´ormula que tiene en cuenta caracter´ısticas de los genotipos de la poblaci´on, como su longitud media. La programaci´on gen´etica ya ha sido utilizada para la evoluci´on de un controlador del famoso juego Pac-Man. Koza [21] utiliz´o la programaci´on gen´etica para evolucionar el c´odigo del controlador del personaje principal de Pac-Man de una versi´on personalizada del juego. Para ello emple´o dos tipos de operadores, operadores de alto nivel para la obtenci´on de informaci´on del juego (Distance-to-Pill,If-Less-Than-or-Equal) y operadores de acci´on (Advance-to-Food). Con estos operadores el algoritmo construye y evoluciona 3.3. Gram´aticas independientes del contexto 15 el genotipo de los individuos gui´andose por la funci´on de fitness, que es b´asicamente el n´umero total de puntos obtenidos por el Pac-Man antes de morir (obteniendo el fenotipo del individuo y ejecutandolo en el juego). Koza obtuvo resultados muy prometedores con este m´etodo. Alhejali y Lucas [8] realizan una implementaci´on muy parecida a la de Koza pero usando operadores de un nivel m´as alto y abstracto (isInDanger(),toSafety(), ...) aunque obtuvieron resultados bastante similares. Sin embargo, Brandstetter y Ahmadi [11] optan por el uso de operadores de acci´on de bajo nivel (Up, Down, Left, Right), obteniendo muy buenos resultados y realizando una comparativa con otros controladores evolucionados mediante programaci´on gen´etica (incluyendo los previamente nombrados). En la comparativa se aprecian mejores resultados con los operadores de bajo nivel que con los operadores de alto nivel o m´as abstractos. 3.3. Gram´aticas independientes del contexto Una gram´atica independiente del contexto (en adelante GIC o gram´atica) es una cuaterna formada por un conjunto de s´ımbolos no terminales, un conjunto de s´ımbolos terminales, un conjunto de reglas de producci´on (tambi´en denominadas expresiones) y un s´ımbolo inicial. Mediante estos s´ımbolos y reglas la gram´atica es capaz de generar un lenguaje independiente del contexto[20][10]. Backus-Naur Form (BNF) es una notaci´on formal para representar gram´aticas independientes del contexto la cual es f´acilmente interpretable por el ser humano. Una BNF se compone de s´ımbolos terminales y no terminales (escritos entre <>). Estos s´ımbolos no terminales pueden ser expandidos por una serie de producciones las cuales a su vez contienen un conjunto de s´ımbolos no terminales o un terminal. La mayor´ıa de lenguajes inform´aticos, por ejemplo, tienen una representaci´on escrita en formato BNF [16]. Figura 3.6: Ejemplo de BNF. Para obtener una derivaci´on (una secuencia de caracteres perteneciente al lenguaje que representa la BNF) se parte del s´ımbolo inicial. A partir de aqu´ı se repite recursivamente el siguiente proceso: se procesan todos los s´ımbolos no terminales contenidos en la producci´on elegida. Para cada s´ımbolo no terminal sin procesar se realiza el mismo proceso, se elige una producci´on perteneciente al mismo y se vuelve a realizar este proceso de forma recursiva hasta llegar a un s´ımbolo terminal, momento en el que el s´ımbolo no terminal se da por procesado y se pasa a procesar el siguiente s´ımbolo no terminal sin haber sido completamente procesado. El proceso termina cuando todos los s´ımbolos no terminales han sido procesados. 16 Cap ´ ıtulo 3. Programaci´on evolutiva Figura 3.7: BNF que representa sumas de d´ıgitos. Para procesar y utilizar una BNF se usa un lector de BNFs que recorre y extrae informaci´on de la misma, como los s´ımbolos y terminales que la componen. 3.4. Evoluci´on gramatical Evoluci´on gramatical (Grammatical Evolution en ingl´es) es un tipo de algoritmo evolutivo basado en la programaci´on gen´etica que permite generar autom´aticamente producciones o programas con el objetivo de encontrar el ´optimo que realice una acci´on o resuelva un problema. A diferencia de la programaci´on gen´etica, donde se utiliza un ´arbol para codificar el genotipo, en la evoluci´on gramatical se usa un array de enteros como genotipo y una gram´atica independiente del contexto en notaci´on Backus-Naur Form (BNF) para la generaci´on del fenotipo. Estos n´umeros enteros que componen el array del genotipo se denominan codones y dictan qu´e producci´on perteneciente a una regla de la gram´atica se escoge a la hora de generar el fenotipo. Un ejemplo de genotipo formado por 5 codones tendr´ıa la forma: 37, 12, 5, 42, 1. El rango de valores que pueden tomar los codones se determina de antemano. Para determinar la producci´on a procesar del s´ımbolo no terminal siendo expandido se utiliza la siguiente f´ormula: Producci´on a escoger = cod´on m´od (node producciones para el s´ımbolo a derivar) (3.1) donde m´od es la funci´on de m´odulo entero. Esta f´ormula devuelve un n´umero que es la posici´on de la producci´on a seleccionar del s´ımbolo no terminal que est´a siendo expandido [27]. Se puede ver un ejemplo en la Figura 3.8. Esta f´ormula se aplica en orden a los s´ımbolos no terminales hasta que todos hayan sido procesados, es decir, se hayan alcanzado en todos un s´ımbolo terminal. A veces esto no se consigue con un ´unico recorrido del genotipo, por lo que se realiza lo que se conoce como wrapping, que consiste en volver a empezar a leer el genotipo desde el principio y seguir expandiendo las reglas todav´ıa sin expandir (ver Figura 3.9). El n´umero de veces que se permite realizar wrapping por individuo se determina de antemano y si, tras realizar wrapping este n´umero de veces no se ha conseguido derivar todos los s´ımbolos, el individuo es descartado. La estructura de partida de las tambi´en llamadas gram´aticas evolutivas es muy similar a la de los algoritmos gen´eticos comunes. 1. Generar una poblaci´on aleatoria. 2. Evaluar la poblaci´on usando una funci´on de fitness. 3.4. Evoluci´on gramatical 17 Figura 3.8: Ejemplo del proceso que se realizar´ıa para transformar el genotipo mostrado anteriormente al fenotipo que representa. 3. Cruzar la poblaci´on mediante el operador de cruce elegido. 4. Mutar la poblaci´on mediante el operador de mutaci´on elegido. 5. Repetir desde el punto dos hasta que se alcance el n´umero de generaciones. Sin embargo, el uso de operadores cl´asicos de cruce y mutaci´on produce resultados poco ´optimos debido a que genera poblaciones muy ca´oticas, un peque˜no cambio en un cod´on del genotipo puede producir un programa completamente diferente y sin relaci´on con el anterior dificultando en gran medida la convergencia de la poblaci´on hacia el ´optimo. Es por esta raz´on por la cual distintos operadores se han dise˜nado espec´ıficamente para su uso en gram´aticas evolutivas. La mayor´ıa de las investigaciones se centran en los m´etodos de cruce debido a que son bastante destructivos (el fenotipo del hijo de dos padres suelen no tener ninguna relaci´on con el fenotipo de sus padres lo que dificulta una evoluci´on convergente). No es f´acil dar con un nuevo m´etodo que mejore o no empeore el cruce monopunto, como es el caso del cruce homog´eneo [29], pero hay algunos operadores de cruce que s´ı mejoran considerablemente el cruce monopunto e intentan minimizar el comportamiento destructivo que tiene el cruce en los algoritmos gen´eticos, como es el caso de LHS replacement crossover [19]. Este operador de cruce trata de cruzar dos individuos moviendo producciones enteras y no secuencias de codones arbitrarias. Para ello selecciona un cod´on aleatorio del genotipo y busca el s´ımbolo que ha de ser expandido por ese cod´on a la hora de generar el fenotipo. Desde ese cod´on se cogen tantos codones como sea necesario para expandir completamente el s´ımbolo (llegar a un s´ımbolo terminal). Es este conjunto de codones el que es insertado en el genotipo del otro individuo y viceversa. Este proceso se puede ver 18 Cap ´ ıtulo 3. Programaci´on evolutiva Figura 3.9: Conversi´on de un genotipo (cromosoma) a su fenotipo a trav´es del m´etodo descrito anteriormente y utilizando la gram´atica dada [12]. como un “cortar-pegar” de trozos del fenotipo de un individuo en el fenotipo del otro individuo obteniendo hijos que poseen un fenotipo relacionado al del padre. Los operadores de mutaci´on pueden afectar de manera notable al fenotipo del individuo si se muta un cod´on que expande un s´ımbolo no terminal. As´ı mismo puede generar mutaciones sin efecto si se genera un nuevo cod´on que tenga el mismo m´odulo que el anterior. Se suelen utilizar los operadores de mutaci´on cl´asicos. A´un as´ı, nuevos operadores de mutaci´on han sido dise˜nados centr´andose en gram´aticas evolutivas, como por ejemplo la mutaci´on neutral [25]. Este operador pretender dar mayor diversidad a la poblaci´on, para ello muta aleatoriamente codones d´andoles un nuevo valor que produzca el mismo m´odulo que el anterior al generar el fenotipo. Este cambio no afecta directamente al fenotipo (se mantiene igual) pero en las siguientes generaciones en las que el genotipo puede haber cambiado esta mutaci´on neutral si puede tener efecto. Se puede utilizar en conjunto con otro operador de mutaci´on que s´ı produzca cambios en el fenotipo, por ejemplo la mutaci´on bit a bit. Adem´as de los operadores tambi´en se pueden encontrar cambios en la codificaci´on del genotipo [24] o adaptaciones de distintos tipos de algoritmos gen´eticos a algoritmos de evoluci´on gramatical con el fin de hacer esta misma m´as eficiente y efectiva, como es el caso de la evoluci´on diferencial. La evoluci´on diferencial es un algoritmo gen´etico el cual genera una poblaci´on auxiliar adicional y realiza el cruce entre elementos 3.5. Algoritmos Evolutivos Multiobjetivo 19 de la poblaci´on auxiliar y la poblaci´on principal. El operador de mutaci´on en vez de generar cambios aleatorios utiliza individuos de la poblaci´on y los combina mediante una f´ormula matem´atica creando un nuevo individuo. El uso de este algoritmo aplicado a un genotipo-fenotipo del algoritmo de evoluci´on gramatical da lugar al algoritmo denominado evoluci´on diferencial gramatical [28]. Otro m´etodo t´ıpicamente usado es el Grammatical Swarm Evolution el cual es una mezcla de la evoluci´on gramatical y Particle Swarm Optimization (optimizaci´on por enjambre de part´ıculas o PSO) [30] [17]. PSO es un algoritmo que intenta explorar todo el espacio de soluciones y as´ı encontrar el m´aximo/m´ınimo global y no estancarse en m´aximos/m´ınimos locales. Para eso trata la poblaci´on de individuos como part´ıculas en un “mapa” (espacio de soluciones) representadas mediante una “posici´on” (estado actual) que cambia en cada generaci´on dependiendo de la “velocidad” de la part´ıcula. Esta “velocidad” se calcula en cada generaci´on mediante una f´ormula matem´atica que utiliza distintas variables como la “posici´on” de la mejor part´ıcula actual (´optimo local) en el “mapa”. Al igual que la programaci´on gen´etica, las gram´aticas gvolutivas tambi´en han sido usadas previamente para la evoluci´on de controladores de Pac-Man. Galv´an-L´opez [15] us´o una estrategia similar a la utilizada por Koza (en su implementaci´on mediante programaci´on gen´etica) usando funciones de alto nivel para los operadores de movimiento (ANG - Avoid Nearest Ghost) y para los operadores que obtienen informaci´on del estado del juego (avgDistBetGhosts). Usaron una gram´atica compuesta por declaraciones if-else para la elecci´on del operador de movimiento adecuado bas´andose en ciertas caracter´ısticas del estado actual del juego. Con esta implementaci´on obtuvieron resultado similares a los controladores obtenidos mediante programaci´on gen´etica y con la ventaja que la gram´atica utilizada se puede cambiar con facilidad (a˜nadiendo o quitando reglas) y obteniendo de este modo distintos comportamientos adaptados a las nuevas funciones disponibles. Liberatore [22] propuso otra implementaci´on interesante pero esta vez para el controlador de los fantasmas, utilizando gram´aticas evolutivas y Flocking Strategies para obtener comportamientos y estrategias basados en una inteligencia de colmena. 3.5. Algoritmos Evolutivos Multiobjetivo Todas las distintas ramas de algoritmos evolutivos que hemos presentado anteriormente comparten la caracter´ıstica de que est´an enfocados a optimizar un ´unico objetivo en la funci´on de fitness. Sin embargo, a veces aparecen problemas en los que se buscan soluciones que optimicen m´as de una variable y se les denomina problemas multiobjetivo. Si por cada objetivo a optimizar se crea una funci´on fitness para determinar c´omo de bueno es el individuo respecto a ese objetivo entonces se busca: Optimizar{fi(X)| ∀i= 1,...,node objetivos} donde fies la funci´on i-´esima de fitness. 20 Cap ´ ıtulo 3. Programaci´on evolutiva Por ejemplo, un algoritmo evolutivo que determine d´onde invertir en bolsa podr´ıa tener dos objetivos, maximizar las ganancias de la inversi´on y minimizar el riesgo de p´erdidas. La dificultad de un algoritmo multiobjetivo es determinar el ´optimo global, es decir, el individuo que optimiza de la mejor forma todos los objetivos. La soluci´on al ejemplo anterior no es trivial ni ´unica, pues el algoritmo puede dictar una inversi´on que optimice el beneficio obtenido pero con un alto riesgo de p´erdidas as´ı como una inversi´on segura pero que genera muy pocos beneficios. Se suele emplear la definici´on de ´optimo en un contexto multiobjetivo dada por Vilfredo Pareto, denominado ´optimo de Pareto. Se dice que una soluci´on Y domina (es mejor) a otra X si es igual o mejor en todos los objetivos y es estrictamente mejor en al menos un objetivo [9]. fi(y)≤fi(x),(∀i= 1,...,node objetivos})∧ ∃fi(y)< fj(x) Figura 3.10: ´ Optimo de Pareto para un problema de minimizaci´on. Normalmente (como en el ejemplo anterior de inversi´on en bolsa) existen varios ´optimos de Pareto, es decir, un conjunto de soluciones que dominan al resto pero que entre ellas no se dominan. A este conjunto de soluciones se le denomina frente de Pareto (ver Figura 3.11). Figura 3.11: Frente de Pareto de un conjunto de soluciones para un problema de minimizaci´on. C es una soluci´on dominada por A y B, ambas pertenecientes al frente de Pareto [13]. A la hora de implementar un algoritmo multiobjetivo podemos elegir entre diferentes 3.5. Algoritmos Evolutivos Multiobjetivo 21 m´etodos. El m´as sencillo, y que no altera los esquemas cl´asicos de los algoritmos evolutivos, es el denominado multiobjetivo mediante funciones agregativas que consiste en la creaci´on de una funci´on fitness fcomo una combinaci´on lineal de funciones en donde cada una representa un objetivo a optimizar. f(x) = θ1f1(x) + θ2f2(x) + · · · +θnfn(x) donde θison coeficientes utilizados para dar m´as o menos peso a cada funci´on. El principal problema de este enfoque a problemas multiobjetivo es la dificultad para encontrar los pesos adecuados. Un m´etodo muy utilizado es el desarrollado por Deb, et al. denominado NSGAII (Non-dominated Sorting Genetic Algorithm) el cual ofrece buenos resultados pero es bastante exigente computacionalmente, sobretodo para poblaciones grandes [14]. El m´etodo consiste en la identificaci´on de los distintos frentes de Pareto de la poblaci´on en la generaci´on actual. Para ello se identifican los individuos pertenecientes al frente de Pareto de la poblaci´on y se les asigna rango uno, nuevamente se vuelve a identificar el frente de Pareto de la poblaci´on sin tener en cuenta los individuos que pertenecen al frente de Pareto ya identificado y se les asigna rango dos y se realiza este proceso hasta que todos los individuo de la poblaci´on tienen asignado un frente de Pareto al que pertenecen. Para los individuos de cada frente de Pareto se calcula una serie de valores denominados distancias de saturaci´on respecto a los distintos objetivos. Usando estas distancias de saturaci´on la selecci´on se realiza mediante el m´etodo de torneo, se escogen dos elementos aleatorios de la poblaci´on y se selecciona el que pertenezca al menor frente de Pareto (rango m´as bajo). Si ambos individuos pertenecen al mismo frente de Pareto entonces se escoge el que tenga mayor distancia de saturaci´on. 3.5.1. JECO Como punto de partida para abordar el uso de gram´aticas evolutivas hemos decidido emplear el framework JECO [33] (Java Evolutionary Computation Library). Inicialmente se valoraron otras opciones como GEVA [18], reutilizar c´odigo nuestro o partir de cero. JECO (Java Evolutionary COmputation) es un framework de inteligencia artificial orientado a la computaci´on evolutiva, creado por Jos´e Luis Risco Mart´ın y Jos´e Manuel Colmenar Verdugo, con la colaboraci´on posterior de Josu´e Pag´an Ortiz. Soporta muchas t´ecnicas de programaci´on evolutiva, entre las que nos interesaron las gram´aticas evolutivas simples y multiobjetivo (utilizando el algoritmo NSGA-II descrito anteriormente y que utilizaremos en nuestro trabajo), con soporte para el uso de varios hilos de procesamiento. 22 Cap ´ ıtulo 3. Programaci´on evolutiva Cap´ıtulo 4 Ms. Pac-Man Ms. Pac-Man es un juego antol´ogico desde su aparici´on en los arcades en el a˜no 1981. Desde entonces han sido muchas las variantes de este cl´asico y sus diversos usos (recreacional, investigaci´on, competici´on). La versi´on del juego que vamos a utilizar, “Ms. Pac-Man Vs. Ghosts” [5] [34], est´a implementada por Philipp Rohlfshagen, basada en implementaciones previas de Simon Lucas y David Robles, los tres de la universidad de Essex, Reino Unido. 4.1. Descripci´on del juego Las variantes del juego difieren mucho en cuanto a objetivos de juego y recompensas por los mismos, as´ı como reglas a seguir. A continuaci´on describimos la versi´on del juego que usamos en este trabajo. 23 30 Cap ´ ıtulo 5. Bots basados en secuencias de acciones A continuaci´on se muestra el resultado de uno de los primeros experimentos realizados, con tama˜no de poblaci´on 100, 50 generaciones, una evaluaci´on por individuo, selecci´on por Torneo Binario, cruce monopunto con 60 % de probabilidad de cruce e Integer Flip Mutation con 10 % de probabilidad de mutaci´on. El controlador de fantasmas era Starter Ghosts (nuestro bot a´un no ten´ıa ninguna oportunidad contra Legacy). Fenotipo Puntos (avg) LLDLDRLD 2480 Tabla 5.1: Fenotipo y puntos del primer bot de secuencias de acciones. 5.4. Incorporando condicionales y acciones de alto nivel Para dotar al aut´omata de capacidad de decisi´on que tuviera en cuenta el estado del juego en el que se encontraba el bot, incluimos s´ımbolos condicionales, que siempre iban precedidos del s´ımbolo “?”. A su vez este s´ımbolo siempre iba precedido de un car´acter que representaba la condici´on a evaluar. Si una condici´on evaluada resultaba cierta, se realizaba la acci´on que defin´ıa el car´acter ubicado a continuaci´on del de la condici´on. Si no, se omit´ıa. La versi´on final dispon´ıa de evaluaciones y acciones de alto nivel especificados por la cadena de instrucciones del aut´omata, cuyo alfabeto era el siguiente: Char Tipo de s´ımbolo Comportamiento P condicional Condicional de fantasma no comestible cerca B condicional Condicional de fantasma comible cerca H acci´on Huir E acci´on Comer pill W acci´on Comer powerpill F acci´on Comer fantasma Tabla 5.2: Acciones y condiciones de alto nivel desarrolladas. La gram´atica dise˜nada para hacer uso de este lenguaje, ten´ıa la siguiente forma: <expr > ::= ? <cond > <expr > | <action > <expr > | <action > <cond > ::= P | B <action > ::= H | E | W | F Listing 5.2: Gram´atica con acciones de alto nivel. 5.4.1. Fenotipos producidos En bots producidos por esta implementaci´on a veces se aprecia un atisbo de primera inteligencia muy primitiva, as´ı como los habituales intrones o fragmentos de programa in´utiles. 5.4. Incorporando condicionales y acciones de alto nivel 31 Los siguientes fenotipos fueron obtenidos tras experimentos con tama˜no de poblaci´on 100, 50 generaciones, una evaluaci´on por individuo, selecci´on por Torneo Binario, cruce monopunto con 60 % de probabilidad de cruce e Integer Flip Mutation con 10 % de probabilidad de mutaci´on. Los fantasmas siguen siendo Starter Ghosts en esta etapa, dados los malos resultados obtenidos contra fantasmas Legacy. Fenotipo Puntos (avg) E?P?PH 6580 ?B?PE?BHEHE 7000 Tabla 5.3: Fenotipo y puntos de los siguientes bots con condicionales y acciones de alto nivel. Como ejemplo, la traducci´on a pseudoc´odigo del primer programa ser´ıa lo siguiente: MIENTRAS ( true ) Ir hacia la pill m´as cercana SI ( fantasma no comible cerca ) ENTONCES SI ( fantasma no comible cerca ) ENTONCES Huir del fantasma no comible m´as cercano FIN SI FIN SI FIN MIENTRAS Listing 5.3: Pseudoc´odigo correspondiente al programa E?P?PH Que se traduce en ir siempre hacia la pill m´as cercana, salvo que haya un fantasma no comible cerca de Pac-Man, en cuyo caso se aleja de ´el. Se aprecia una doble evaluaci´on consecutiva de lo mismo que no aporta nada: Un problema t´ıpico en programaci´on gen´etica. Resulta destacable el descubrimiento por parte de los bots generados mediante este sistema de la variable “Global Reversal”, que en cada movimiento asigna a los fantasmas una probabilidad aleatoria muy baja de darse todos la vuelta. Los fenotipos consistentes en comer pills y huir cuando haya un fantasma cerca, producen una estrategia en la que el bot de Pac-Man huye a la vez que agrupa la mayor´ıa de fantasmas detr´as de ´el. Cuando ocurre el susodicho Global Reversal, los fantasmas cambian su direcci´on a la opuesta, y dado que no pueden cambiarla de nuevo salvo que ocurra otro Global Reversal y las distancias son calculadas teniendo esta limitaci´on en cuenta, todos pasan a estar “lejos” de Pac-Man y este puede comer pills con seguridad. 32 Cap ´ ıtulo 5. Bots basados en secuencias de acciones Figura 5.3: Global Reversal de los fantasmas. 5.5. Limitaciones Tal como esper´abamos, el empleo de este ingenuo aut´omata tiene varias limitaciones. El funcionamiento de nuestros condicionales permit´ıa una sola condici´on, es decir, no nos permit´ıan evaluar varias premisas (usando operadores l´ogicos binarios y/o unarios) salvo mediante el encadenamiento de condicionales (if). Tampoco ten´ıamos la posibilidad de emplear una segunda acci´on que solo se ejecutase en caso de no cumplirse el condicional, a modo “else”. Adem´as, solo se realizaba una acci´on en el consecuente, en lugar de poder realizar una serie de acciones. Otra limitaci´on era la imposibilidad de construir estrategias con continuidad temporal debido a la ejecuci´on de la cadena de instrucciones de forma lineal, dado que esta era ´unica para toda la ejecuci´on y simplemente se volv´ıa a empezar por el principio tras llegar al final. Adem´as, este funcionamiento en forma de bucle que repite la misma secuencia de acciones pod´ıa provocar muy f´acilmente la ejecuci´on de una acci´on sin sentido en el contexto en el que el juego se encontraba en determinado momento. Previamente decidimos comprobar si era posible adaptar el aut´omata con el que cont´abamos en ese momento de forma que se solventase los problemas descritos. Para dicha prueba, introdujimos un nuevo estado de huida (similar a un estado trampa, pero con una v´ıa de salida), en el que se entraba en caso de encontrarse alg´un fantasma (comestible) por debajo de un radio de peligro (ver Figura 5.4). En este estado de huida se codificaba un comportamiento, en alto nivel y ajeno al funcionamiento normal del aut´omata, en el que permanec´ıa hasta que Pac-Man estuviera fuera de la distancia de peligro. Tras estar fuera de peligro, el bot sal´ıa del estado de huida y segu´ıa ejecutando la cadena de instrucciones dada por el aut´omata en el punto en el que se encontraba antes de entrar al estado de huida. 5.5. Limitaciones 33 Figura 5.4: Ejemplo de aut´omata que usa el estado ”huida”. A trav´es de esta prueba comprobamos que la escalabilidad del aut´omata no era realista, ya que supon´ıa la codificaci´on de eventos cada vez m´as complejos de gestionar debido a la aparici´on de conflictos con los ya introducidos a la hora de controlar las transiciones. Llegados a este punto y con esos problemas, consider´abamos seriamente la posibilidad de realizar una nueva implementaci´on alejada del sistema de aut´omatas de movimientos concatenados. 34 Cap ´ ıtulo 5. Bots basados en secuencias de acciones Cap´ıtulo 6 Bots basados en ´arboles de decisi´on 6.1. Idea general Un ´arbol de decisi´on es un tipo especial de ´arbol utilizado en el ´area de inteligencia artificial cuyos nodos internos representan condiciones a evaluar y sus nodos hoja representan las acciones a realizar, resultados, soluciones, etc. El recorrido de un ´arbol de decisi´on es sencillo, se empieza por el nodo ra´ız y se eval´ua su condici´on, dependiendo del resultado de esta evaluaci´on se elige el siguiente nodo (hijo del nodo evaluado) que ser´a evaluado y as´ı sucesivamente hasta que se encuentre un nodo hoja. Figura 6.1: ´ Arbol de decisi´on para determinar si un individuo es enemigo o aliado. 35 36 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on Los ´arboles de decisi´on suelen emplearse ampliamente en ´areas donde sean necesarias decisiones deterministas automatizadas como finanzas, estad´ıstica, videojuegos, aprendizaje autom´atico, etc. Son f´aciles de entender y muy r´apidos de procesar una vez construidos [2]. En esta fase optamos por seguir un nuevo enfoque mediante inteligencia artificial reactiva. Esto significa evaluar en cada turno un ´arbol de decisi´on (partiendo siempre desde la ra´ız), comprobando una serie de condiciones del estado de la partida, y a partir de ellas determinar una ´unica acci´on a realizar. La decisi´on de seguir este enfoque persigue que nuestros bots resultantes tengan un comportamiento con continuidad dentro de una misma situaci´on pero a la vez sean capaz de adaptarse a cambios repentinos en el estado del juego. Por ejemplo,a partir del c´odigo: if ( getDistanceToClosestNonEdibleGhost >= 4 ){ getDirectionToClosestEdibleGhost } else { getDirectionAwayFromClosestNonEdibleGhost } Listing 6.1: Ejemplo de c´odigo construir´ıamos el siguiente ´arbol: Figura 6.2: ´ Arbol contruido a partir de ejemplo de c´odigo. La ejecuci´on de este ´arbol consistir´ıa en, turno a turno, evaluar desde el nodo ra´ız: primero, comprobar si la distancia al fantasma no comible m´as cercano es menor o igual que 4. En caso de que sea as´ı, eval´ua la rama izquierda recursivamente, y al ser esta un nodo hoja ejecuta la acci´on determinada por este, en este caso acercarse al fantasma comible m´as cercano. En caso de la que condici´on no se cumpla, se ejecutar´a de forma an´aloga la rama derecha, trat´andose de un nodo hoja con la acci´on que genera un movimiento de huida del fantasma m´as cercano. 6.1. Idea general 37 6.1.1. Parsing de fenotipo a ´arbol Para integrar ´arboles de decisi´on procedimos a hacer cambios en la representaci´on del fenotipo. Concretamente, a partir de cada fenotipo generado por el algoritmo evolutivo (una cadena de texto), generamos un ´arbol de decisi´on. El ´arbol generado mediante dicho metodo de parse organiza condicionales (con sus respectivos consecuentes) y acciones (que producen movimientos) de la forma m´as intuitiva posible. La estructuraci´on de dichos elementos dentro del ´arbol se realiza de la siguiente forma: Dicho ´arbol contiene las diferentes funciones para consultar el estado de juego (los nodos no terminales) y para decidir movimientos (nodos terminales) como enumerados, obteni´endose cada movimiento evaluando recursivamente el ´arbol. A la hora de realizar el cambio estructural de fenotipo, optamos por realizar un Acciones Los nodos terminales realizan una acci´on, que puede ser: Movimientos simples (direccionales) Movimientos basados en informaci´on del juego. Por ejemplo, “el movimiento que aleja m´as a Pac-Man del fantasma m´as cercano” Condicionales Los condicionales contienen una lista de par´ametros booleanos (los cuales hemos denominado condiciones) y otra lista que indica qu´e operadores booleanos binarios operan dichos par´ametros. En caso de que el condicional se trate de un if, contendr´a un nodo hijo con un consecuente, y en caso de ser un else, dos. Una condici´on puede ser de dos tipos. El primero, una consulta booleana del estado de juego. El segundo, el resultado de aplicar un operador num´erico a una consulta num´erica del estado de juego y un n´umero generado por la gram´atica. Un ejemplo de consulta num´erica del estado del juego seria la distancia al fantasma comible m´as cercano, y uno de una consulta booleana seria comprobar si Pac-Man se encuentra en una intersecci´on. Finalmente, una condici´on puede encontrarse negada. 6.1.2. Adaptador de ´arbol a movimiento de Pac-Man Para poder ejecutar partidas con estos ´arboles de decisi´on, necesitamos implementar un nuevo controlador de Pac-Man. Este controlador contiene el ´arbol de derivaci´on, actuando como wrapper, de forma que con cada solicitud de movimiento realizada al controlador, este eval´ua el ´arbol de forma recursiva, hasta encontrar una acci´on (un nodo terminal que devuelva un movimiento) y que cumple todos sus condicionales (nodos no terminales) previos. 38 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on N´otese que la evaluaci´on de dichos condicionales supone la evaluaci´on de numerosos par´ametros booleanos y enteros evaluados entre s´ı. Estos par´ametros son obtenidos directamente de consultas al estado de la partida. Finalmente se obtiene un movimiento, bien generado por la acci´on de un nodo terminal a trav´es de la llamada a una determinada funci´on interna del juego Ms. Pac-Man vs Ghosts, bien realizando un movimiento simple direccional. 6.2. Gram´aticas desarrolladas Todas nuestras gram´aticas producen c´odigos basados en inteligencias artificiales reactivas, es decir, a cada turno de movimiento (denominado internamente como tick) se eval´uan una serie de condiciones del estado del tablero para producir un ´unico movimiento de forma no ambigua. Las gram´aticas dise˜nadas usan una estructura de anidamientos de declaraciones if-else que posteriormente un parser1convertir´a a un ´arbol de decisi´on. Este ´arbol de decisi´on tendr´a una traducci´on directa de las funciones escritas en la gram´atica a funciones interpretables por el bot (escritas en Java) que ser´an ejecutadas en el proceso de evaluaci´on. A la hora de desarrollar gram´aticas las dividimos en tres categor´ıas dependiendo del tipo de acciones que pueden producir: Bajo nivel: son gram´aticas cuyos nodos terminales, aquellos que dicen al bot de Pac-Man qu´e movimiento hacer en cada tick del juego, se constituyen ´unicamente de las funciones Up, Down, Left, Right que son una codificaci´on directa de las teclas de movimiento que dispondr´ıa un humano al jugar el juego. Medio nivel: en lugar de las funciones b´asicas de movimiento (Up, Down, ...), disponen de funciones de un nivel medio, entendi´endose nivel medio como funciones que dictan una acci´on directa, como puede ser comerse la pill m´as cercana, huir del fantasma m´as cercano, ir a por la power pill m´as cercana, etc. Alto nivel: se diferencian de las de medio nivel en que sus funciones terminales son muy abstractas y no se puede determinar directamente qu´e direcci´on o comportamiento tomar´a el bot, estas funciones son del estilo de comer, huir, atacar, ... funciones que se entienden cu´al es su objetivo pero que pueden realizarse de distintas maneras. 6.2.1. Par´ametros del experimento realizado Todos los resultados de esta secci´on han sido obtenidos empleando los mismos operadores, par´ametros y probabilidad con la que se emplean los operadores del algoritmo evolutivo para permitir una comparaci´on objetiva del rendimiento empleando diferentes gram´aticas. Estos par´ametros son: 1Un parser es una herramienta que mediante el uso de una gram´atica transforma texto escrito en el lenguaje representado por la gram´atica a una representaci´on interpretable por otro sistema [6]. 6.2. Gram´aticas desarrolladas 39 Porcentaje Poblaci´on 100 - Generaciones 100 - Evaluaciones por individuo 30 - Longitud cromosoma 100 - L´ımite superior cod´on2256 - M´etodo de selecci´on Torneo Binario3M´etodo de cruce LHS 60 M´etodo de mutaci´on Integer Flip 10 Mutaci´on Neutral S´ı - Elitismo S´ı 5 Tabla 6.1: Par´ametros utilizados. 6.2.2. Gram´atica de bajo nivel Con la gram´atica de bajo nivel pretendemos que el bot tenga un comportamiento basado en est´ımulos muy espec´ıficos y utilizando solo los operadores de movimiento de los que un jugador humano dispone (moveup, moveDown, moveRight, moveLeft). Como son operadores de bajo nivel que no disponen de informaci´on del juego (pill m´as cercana, posici´on de fantasmas, etc), la gram´atica necesita contener una gran cantidad de funciones que devuelvan informaci´on del estado actual del juego: getDistanceToClosestNonEdibleGhost: Devuelve la distancia al fantasma peligroso m´as cercano. getDistanceToClosestNonEdibleGhostUp, Down, Left, Right: Distancia al fantasma peligroso m´as cercano a la posici´on del bot en la direcci´on dada. getDistanceToClosestEdibleGhost: Devuelve la distancia al fantasma comestible m´as cercano. getDistanceToClosestEdibleGhostUp, Down, Left, Right: Distancia al fantasma comestible m´as cercano a la posici´on del bot en la direcci´on dada. getNumberOfActivePowerPills: Devuelve la cantidad de power pills que se encuentran actualmente en el tablero. getDistanceToClosestPill: Distancia a la pill (tambi´en considerando las power pills) m´as cercana independientemente de la orientaci´on del bot. getDistanceToClosestPillUp, Down, Left Right: Devuelve la pill m´as cercana al bot en la direcci´on especificada. 2valor m´aximo que puede tomar 3o NSGA II si se est´a empleando multiobjetivo 46 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on Resultados Figura 6.4: Gr´afica que muestra las primeras 100 generaciones de dos ejecuciones distintas contra los controladores de fantasmas Random yLegacy usando la gram´atica de medio nivel. Funci´on fitness: 1000000 - puntos obtenidos. Las conclusiones obtenidas son: La velocidad de ejecuci´on del algoritmo evolutivo ha sido significativamente m´as r´apida que la de bajo nivel, de forma que la ejecuci´on se realiza en apenas unos minutos. Los resultados obtenidos en puntos son bastante superiores a los obtenidos con la gram´atica de bajo nivel, como se aprecia en la Tabla 6.3. El c´odigo generado por el mejor individuo (fenotipo) es muy corto, generalmente consiste de un solo if-else que contiene cada uno una ´unica funci´on. Creemos que la longitud del c´odigo est´a directamente relacionada al comportamiento que poseen los mejores individuos y que es obtenido de forma recurrente. Al principio y si no hay fantasmas cercanos el bot solo realiza movimientos neutros (continuar en la misma direcci´on), qued´andose atascado en una esquina del mismo modo que lo hace el bot “Camper” de la gram´atica de nivel bajo. Pero si un fantasma se acerca lo suficiente el bot pasa a un modo agresivo dirigi´endose a la power pill m´as cercana, comi´endosela y cazando a tantos fantasmas como puede. Este comportamiento lo repite con todas las power pills hasta que se queda sin ellas, pasando a un estado de movimiento neutral y siendo eliminado por los fantasmas sin pasar nunca del primer nivel del juego. Este comportamiento es debido 6.2. Gram´aticas desarrolladas 47 a una caracter´ıstica del juego que provoca una explosi´on en la puntuaci´on al comer fantasmas seguidos. Esto se debe a que durante el tiempo que dura el efecto de una power pill cada fantasma comido da una serie de puntos, este valor es duplicado si se come otro fantasma y el nuevo valor es a su vez duplicado si otro fantasma es consumido. Esto permite obtener una gran cantidad de puntos provocando que el fitness de ese individuo destaque Como se puede apreciar, la gram´atica de bajo nivel siempre lleva a un comportamiento de bot “Camper” y la gram´atica de medio nivel a un comportamiento de bot “Cazador”. Estos comportamientos vienen dados principalmente por los puntos que se obtienen al jugar, por lo que investigamos el uso de una gram´atica de alto nivel y comparamos los resultados obtenidos con la gram´atica de medio nivel. As´ı mismo estudiamos distintas funciones fitness y comprobamos si con estas nuevas funciones conseguimos mejores comportamientos. if (getDistanceToClosestNonEdibleGhost > 10) { if (getDistanceToClosestNonEdibleGhost < 20) { getDirectionTowardsClosestPowerPill } else { getDirectionTowardsClosestPill } } else { getDirectionAwayFromClosestNonEdibleGhost } Listing 6.6: Mejor individuo producido usando la gram´atica de medio nivel para evolucionar contra Random Ghosts. if (getDistanceToClosestNonEdibleGhost >= 5) { getDirectionTowardsClosestPill } else { getDirectionAwayFromClosestNonEdibleGhost } Listing 6.7: Mejor individuo producido usando la gram´atica de medio nivel para evolucionar contra Legacy Ghosts. 6.2.4. Gram´atica de alto nivel Tras los resultados obtenidos con las gram´aticas anteriores, decidimos estudiar hasta qu´e punto ser´ıa posible mejorarlos mediante el empleo de una gram´atica de alto nivel, empleando un n´umero reducido de funciones de alto nivel, proporcion´andole de esta forma conocimiento experto. 48 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on Nuevas funciones de alto nivel escapeHL Genera un movimiento de huida hacia la power pill mas cercana si puede alcanzarla antes que el fantasma m´as cercano. Si no llega a tiempo o bien no quedan power pills, genera un movimiento de huida del fantasma m´as cercano en la direcci´on que m´as le aleje de ´el. attackHL Genera un movimiento hacia el fantasma m´as comible cercano siempre que este pueda ser alcanzado por otro fantasma no comible antes. Si no hay fantasmas comibles, genera un movimiento igual a la ´ultima direcci´on en la que se movi´o. seekFoodHL Genera un movimiento hacia la pill m´as cercana (o si no quedan pills, la power pill m´as cercana) siempre y cuando sea alcanzable por Pac-Man antes que por un fantasma. Si no llega a tiempo, mueve en la ´ultima direcci´on en la que lo hizo el turno anterior. Notaci´on BNF <grammar > ::= <selection -statement > <selection -statement > ::= if( <condition > ){ <statement > } else{ <statement > } | if( <condition > ){ <statement > } <statement > ::= <terminal -func > | <selection -statement> <terminal -func > ::= escapeHL | attackHL | seekFoodHL <condition > ::= <number -func > <number - operator > <number > <number-func> ::= getDistanceToClosestNonEdibleGhost | getDistanceToClosestEdibleGhost <number - operator > ::= == | != | < | > | <= | >= <number > ::= 5 | 10 | 15 | 20 | 25 | 30 | 40 | 50 | 60 | 75 | 80 | 90 Listing 6.8: Gram´atica de alto nivel. 6.2. Gram´aticas desarrolladas 49 Resultados Debido al conocimiento experto que poseen las funciones, la gram´atica utilizada solo contiene como operadores de acci´on las tres funciones de alto nivel comentadas, dos operadores de obtenci´on de informaci´on del tablero (getDistanceToClosestNonEdibleGhost ygetDistanceToClosestEdibleGhost) debido a que recurrentemente han sido las m´as utilizadas, el comportamiento de los mejores bots obtenidos con las gram´aticas anteriores se basan ´unicamente en ellas para la toma de decisiones. Figura 6.5: Gr´afica que muestra las primeras 100 generaciones de dos ejecuciones distintas contra los controladores de fantasmas Random yLegacy usando la gram´atica de alto nivel. Funci´on fitness: 1000000 −puntosobtenidos. Las conclusiones obtenidas al evolucionar el bot usando esta gram´atica fueron: La velocidad de ejecuci´on del algoritmo es a´un m´as r´apida que con la gram´atica de medio nivel, de forma que la ejecuci´on se realiza en apenas unos segundos. El c´odigo generado habitualmente se parece mucho al obtenido mediante la gram´atica de medio nivel: Un if-else con una inecuaci´on num´erica que generalmente tiene en cuenta el fantasma m´as cercano. La m´as notable diferencia es que las acciones de medio nivel como getDirectionAwayFromClosestNonEdibleGhost, se ven sustituidas por su correspondiente directa de alto nivel, como escapeHL. if (getDistanceToClosestNonEdibleGhost >= 5) { getDirectionTowardsClosestPill } else { getDirectionAwayFromClosestNonEdibleGhost } 50 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on Listing 6.9: C´odigo del mejor individuo obtenido en una poblaci´on evolucionada con la gram´atica de medio nivel. if (getDistanceToClosestNonEdibleGhost <= 5) { escapeHL } else { seekFoodHL } Listing 6.10: C´odigo del mejor individuo obtenido en una poblaci´on evolucionada con la gram´atica de alto nivel. Obtiene buenos resultados muy r´apidamente (como se aprecia en la Tabla 6.2) comparada con la gram´atica de medio nivel (Figura 6.6). Esto se debe probablemente al reducido espacio de b´usqueda de soluciones al ser una gram´atica tan compacta. Sin embargo y como se analiz´o en nuestro art´ıculo (Apartado 9.2), la evoluci´on utilizando la gram´atica de alto nivel se estanca en un ´optimo local y es superada por la de medio nivel que obtiene mejores resultados, como se puede apreciar en la Figura 6.6. La de medio nivel consigue algunos puntos m´as en promedio con 100 generaciones. Todo esto nos indica que para tareas en las que es importante obtener buenos resultados de forma r´apida, conviene favorecer gram´aticas de alto nivel, mientras que si buscamos los mejores resultados posibles a cambio de un tiempo de evoluci´on largo, conviene usar gram´aticas de medio nivel. if (getDistanceToClosestNonEdibleGhost <= 5) { escapeHL } else { seekFoodHL } Listing 6.11: Ejemplo de bot producido al evolucionar usando la gram´atica de alto nivel (mismo resultado entrenando tanto contra Random Ghosts como Legacy Ghosts). 6.2.5. Comparativa gr´afica de niveles Al comparar las cincuenta primeras generaciones de una misma poblaci´on evolucionada con las gram´aticas de bajo, medio y alto nivel (Figura 6.6) observamos como la de bajo nivel se queda muy por encima de las gram´aticas de medio y alto nivel (se est´a minimizando por lo que es peor). Entre los fitness obtenidos con las gram´aticas de medio y alto nivel se ve como la de medio nivel obtiene significativamente mejor resultado que la de alto nivel contra el controlador Random. Sin embargo, contra el controlador Legacy no hay una gran diferencia, la gram´atica de alto nivel se mantiene ligeramente por debajo de la gram´atica de medio nivel pero se aprecia como la de medio nivel se va aproximando al fitness obtenido por la de alto nivel conforme pasan las generaciones. 6.2. Gram´aticas desarrolladas 51 Figura 6.6: Gr´afica comparativa del fitness del mejor individuo en las 50 primeras generaciones de la evoluci´on de una misma poblaci´on usando las gram´aticas de bajo, medio y alto nivel contra dos controladores de fantasmas distintos (menos es mejor). No obstante si observamos la Figura 6.7, se muestra las cien primeras generaciones vemos como efectivamente la gram´atica de medio nivel consigue sobrepasar a la gram´atica de alto nivel y obtener mejores resultados. En la mayor´ıa de las ejecuciones hemos observado que la gram´atica de alto nivel consigue minimizar el fitness r´apidamente en las primeras generaciones pero se estanca relativamente pronto y no mejora en las subsecuentes generaciones. Sin embargo, la gram´atica de medio nivel muestra una minimizaci´on del fitness m´as lenta pero continua, sin estancarse r´apidamente, consiguiendo mejores resultados en evoluciones largas. Esto sugiere que para evoluciones en las que se busque obtener un r´apido resultado o que no se disponga de una capacidad computacional suficiente para ejecutar el algoritmo durante varias generaciones en un tiempo asequible, se use la gram´atica de alto nivel. Si por el contrario se dispone de los recursos para poder ejecutar el algoritmo durante una mayor cantidad de generaciones, es recomendable, utilizar la gram´atica de medio nivel ya que obtendr´a mejores resultados. 52 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on Figura 6.7: Gr´afica comparativa del fitness del mejor individuo en las 100 primeras generaciones de la evoluci´on de una misma poblaci´on usando las gram´aticas de medio y alto nivel contra dos controladores de fantasmas distintos (menos es mejor). 6.2. Gram´aticas desarrolladas 53 Pac-Man Fantasmas puntuacion niveles ticks del juego max avg std max avg std max avg std Bajo nivel Random 900 151 117 1 0.071 0.257 5094 2151 972.1 Legacy 120 120 0 0 0 0 600 425 34.5 Tabla 6.2: Pac-Man de bajo nivel contra varios controladores de fantasmas. 1000 ejecuciones. 54 Cap ´ ıtulo 6. Bots basados en ´arboles de decisi´on Pac-Man Fantasmas Puntuaci´on Niveles Ticks del juego max avg std max avg std max avg std Medio nivel Random 64600 48558 10780 18 15 3.4 24000 21579 4470 Legacy 15960 6358 2883 3 0.9 0.7 4973 1916 730 Tabla 6.3: Pac-Man de medio nivel contra diversos fantasmas. 1000 ejecuciones. 6.2. Gram´aticas desarrolladas 55 Pac-Man Fantasmas Puntuaci´on Nivel Ticks del juego max avg std max avg std max avg std Alto nivel Random 55480 32704 13237 18 10.4 4.3 24000 17457 6784 Legacy 20040 5972 2832 4 1 0.6 8364 2026 1020 Tabla 6.4: Pac-Man de alto nivel contra diversos fantasmas. 1000 ejecuciones. 62 Cap ´ ıtulo 7. Estudios, optimizaciones y mejoras fantasmas, por lo que es eliminado por los fantasmas y no es habitual que complete el nivel uno. if( getDistanceToClosestEdibleGhost <= 20 ){ getDirectionTowardsClosestPowerPill } Listing 7.1: Mejor individuo obtenido mediante esta funci´on fitness. Pills {1000 - media de pills consumidas}:Fitness que tiene como objetivo comer el m´aximo n´umero de pills posibles, sin importar la puntuaci´on obtenida ni el nivel, aunque este ´ultimo est´a directamente relacionado con comer pills. Al mejor individuo que suele producir le hemos denominado bot “Glot´on”. Este bot se centra ´unicamente en comer pills normales pero, si se siente amenazado por un fantasma cercano, se dirige hacia una power pill, la consume y sigue comiendo pills normales (pero no caza a los fantasmas). Cuando no dispone de m´as power pills a las que dirigirse y un fantasma se acerca, este sigue comiendo pills normales y es comido por los fantasmas. Este bot suele perder en el nivel dos o en el nivel uno cuando quedan pocas pills por comer. El c´odigo producido es el ant´onimo del producido por el fitness de Puntuaci´on. if( getDistanceToClosestNonEdibleGhost >= 25 ){ getDirectionTowardsClosestPill } else{ getDirectionTowardsClosestPowerPill } Listing 7.2: Mejor individuo obtenido mediante esta funci´on fitness. Niveles {10 - m´aximo nivel alcanzado}: El objetivo de este fitness es pasarse el mayor n´umero de niveles sin importar la puntuaci´on, las pills comidas, el tiempo utilizado, etc por lo que los mejores individuos son los que han llegado al nivel m´as avanzado. Este bot nos sorprendi´o dado que aprovecha el fallo del juego que provoca que no sea detectado por algunos controladores de fantasmas como Starter Ghosts, si se coloca en una cierta posici´on del laberinto. Este xploit lo conoc´ıamos pero nunca se hab´ıa producido en el nivel tres, sin embargo este bot consigue realizarlo en todos los niveles llegando a superar2el juego. Se trata del bot “Camper” pero con un comportamiento mejorado. Nos dimos cuenta de que este comportamiento es alcanzable con las funciones getDistanceToClosestJunction{Up, 2La versi´on actual del juego soporta un n´umero ilimitado de niveles pero dispones de un tiempo m´aximo de juego (24000 ticks). El juego es detenido si se consume el tiempo total, independientemente del nivel en el que te encuentres. Dado que la versi´on actual del juego hace que se avance de nivel autom´aticamente al estar 4000 ticks en el mismo nivel el n´umero m´aximo de niveles al que se puede llegar usando el fallo del juego (estanc´andose en una parte del laberinto sin moverse hasta que se avanza de nivel por tiempo) es de 24000/4000 = 6 niveles. 7.5. Optimizaci´on Multiobjetivo 63 Down, Right, Left}. Si eliminamos dichas funciones de la gram´atica de medio nivel entonces se produce un bot “Camper” que no supera el nivel cuatro. Observamos que el bot se especializa dependiendo del objetivo de la funci´on fitness como es de esperar. No obstante contra controladores de fantasmas especialmente bien dise˜nados como Legacy la diversidad de comportamientos decrece, ya que en Pac-Man la mayor´ıa de objetivos est´an relacionados (por ejemplo, para pasarse niveles Pac-Man ha de comerse todas las pills si le es imposible “atascar” a los fantasmas y ganar el nivel por agotar el tiempo). En cualquier caso decidimos explorar una estrategia multiobjetivo con la intenci´on de conseguir un comportamiento acorde a lo que se deber´ıa esperar de un jugador amateur, avanzar el m´aximo n´umero de niveles consiguiendo la mayor cantidad posible de puntos, comportamiento que no conseguimos usando una funci´on fitness con un ´unico objetivo en consideraci´on contra todos los tipos de fantasmas. 7.5. Optimizaci´on Multiobjetivo Para intentar solventar el problema de especializaci´on que se est´a produciendo contra algunos tipos de fantasmas decidimos implementar una estrategia multiobjetivo en el algoritmo. Existen varios m´etodos de implementaci´on de estrategias multiobjetivo y por la primera que nos decantamos fue una estrategia mediante funciones agregativas. Decidimos usar esta estrategia en primer lugar porque no altera el algoritmo de gram´aticas evolutivas que estamos usando actualmente. Consiste en la implementaci´on de una funci´on fitness (como hasta ahora) pero que consta de una combinaci´on lineal de funciones o par´ametros que cada una determina la val´ıa de un individuo en un determinado aspecto. 7.5.1. Funciones Agregativas La primera funci´on agregativa mediante este m´etodo fue la uni´on de las anteriores funciones fitness de comer el m´aximo n´umero de pills y alcanzar el mayor nivel. La uni´on directa de las funciones como una combinaci´on lineal del estilo f= node pills + nivel m´aximo alcanzado no es posible por la diferencia de escala de los objetivos (el n´umero de pill comidas va a ser siempre m´as grande que el nivel m´aximo alcanzado por lo que ese objetivo no tiene impacto visible en el fitness del individuo) por lo que el uso de unos pesos wiser´an necesarios para que ambas funciones tengan la misma importancia en la combinaci´on lineal. Dada la funci´on f=w0∗node pills + w1∗nivel m´aximo alcanzado 64 Cap ´ ıtulo 7. Estudios, optimizaciones y mejoras tuvimos que experimentar varias versiones con distintos valores de los pesos hasta conseguir un balance adecuado. La versi´on final de la funci´on fue f= node pills + 10 ∗nivel m´aximo alcanzado donde w0= 0 y w1= 10. Los resultados no fueron los esperados y normalmente se obten´ıa un comportamiento de bot “Glot´on” en los mejores casos pero se vio un incremento en la longitud media de los programas (fenotipo) evolucionados. El mismo proceso se realiz´o con la uni´on de las funciones fitness de conseguir puntos y avanzar de niveles f= 0,1∗node puntos obtenidos + nivel m´aximo alcanzado donde w0= 0,1 y w1= 1 pero se obtuvo un bot “Camper” pero con un c´odigo menos eficiente y llegando hasta el cuarto nivel de media. if( getDistanceToClosestJunctionLeft >= 60 ){ getDirectionTowardsClosestPill } else{ if( getDistanceToClosestEdibleGhostUp > 75 ){ if( getClosestEdibleGhostDistanceToClosestJunctionLeft < ,→30 ){ if( getDistanceToClosestNonEdibleGhost <= 50 ){ getDirectionTowardsClosestEdibleGhost } else{ getDirectionTowardsClosestEdibleGhost } } else{ if( getDistanceToClosestNonEdibleGhost <= 10 ){ if( getClosestEdibleGhostDistanceToClosest ,→JunctionDown <= 5 ){ getDirectionAwayFromClosestNonEdibleGhost } else{ getDirectionTowardsClosestPowerPill } } } } else{ getDirectionTowardsClosestPill } } Listing 7.3: C´odigo del bot Camper obtenido mediante funciones agregativas. 7.5. Optimizaci´on Multiobjetivo 65 Nuevamente no obtenemos los resultados esperados y el proceso de creaci´on de combinaciones lineales es experimental, poco preciso y tedioso, as´ı que nos decidimos a realizar una implementaci´on avanzada de la estrategia multiobjetivo mediante el uso del algoritmo NSGA-II el cual usa la definici´on de ´optimo de Pareto y frente de Pareto en su algoritmo para determinar los mejores individuos en los objetivos a optimizar. 7.5.2. NSGA-II JECO dispon´ıa de una implementaci´on del algoritmo NSGA-II que nos sirvi´o como base para desarrollar la implementaci´on de la estrategia multiobjetivo mediante NSGAII. Los cambios realizados en JECO a nivel de c´odigo se explicar´an en el apartado 7.8.2). Hemos desarrollado una serie de funciones fitness por cada objetivo que deseemos optimizar. Hemos intentado representar los objetivos t´ıpicos que un jugador humano amateur intenta conseguir. Naive fitness Puntuaci´on directa obtenida en juego, en la que se tienen en cuenta pills,power pills y fantasmas comidos. Cuantos m´as puntos mejor fitness obtenido (minimizaci´on). f= 1000000 −puntuaci´on media Ghosts eaten N´umero de fantasmas comidos. Cuantos m´as fantasmas consumidos mejor fitness tendr´a el individuo. f= 1000 −fantasmas comidos Levels completed N´umero de niveles completados. A mayor nivel alcanzado mejo fitness del individuo. f= 100 −´ultimo nivel alcanzado Points without ghost multiplier La puntuaci´on total obtenida pero sin emplear el multiplicador de puntos que utiliza Pac-Man al comer varios fantasmas seguidos. f= 100000 −(n´umero de pills consumidas ∗puntos por pill consumida) +(n´umero de power pills consumidas ∗puntos por power pill consumida) +(n´umero de fantasmas consumidos * puntos por fantasma consumida) 7.5.3. Resultados Desafortunadamente, la inclusi´on de multiobjetivo no parece marcar una diferencia notable. Si por ejemplo usamos los fitness Naive yLevels completed no se obtienen mejores bots que los mismos fitness por separado. Esto se debe a que los objetivos que se pueden crear para el juego dependen directa o indirectamente de la puntuaci´on, por lo que no se crea diversidad de comportamiento en nuestros programas. Lo que nos 66 Cap ´ ıtulo 7. Estudios, optimizaciones y mejoras lleva a pensar que funcionar´ıa mucho mejor cuando los objetivos no est´an directamente relacionados. Los resultados muestran que si forzamos el objetivo de alcanzar m´as niveles, los programas obtenidos alcanzan puntuaciones similares ya que Pac-Man avanza niveles comiendo todas las pills del laberinto, y por tanto consiguiendo puntuaciones m´as altas. Lo mismo pasa al contrario, si nos centramos en conseguir puntos, Pac-Man completar´a todos los niveles que le sea posible porque se centra en comerse todas las pills. De cualquier forma siempre tenemos una ventaja clara usando multiobjetivo; en vez de definir un comportamiento monol´ıtico podemos crear un dise˜no m´as modular, m´as f´acilmente, a˜nadiendo subobjetivos adicionales a los ya escogidos. Como por ejemplo comer pills y mantenerse lo m´as alejado posible de los fantasmas, lo que le hace sobrevivir m´as tiempo. 7.6. Mutaci´on neutral La Mutaci´on Neutral es un operador espec´ıfico para gram´aticas evolutivas [26] que pretende proporcionar m´as diversidad a la poblaci´on realizando una mutaci´on que no afecta al fenotipo. Esto es posible en gram´aticas evolutivas, ya que si modificamos un cod´on del fenotipo de un individuo sum´andole un m´ultiplo del n´umero de producciones de la regla que determin´o esa parte del fenotipo, el fenotipo resultante es el mismo. Por ejemplo, si tenemos un s´ımbolo no terminal expandible a trav´es de cuatro reglas de producci´on a los codones mutados se les suma a su valor actual un m´ultiplo de cuatro (dado que hay cuatro reglas de producci´on) por lo que al generar el fenotipo y realizar el m´odulo al cod´on este devolver´a el mismo n´umero que antes de la mutaci´on, produciendo el mismo fenotipo. Aunque se mantiene el mismo fenotipo del individuo, se gana una mayor diversidad, ya que en evaluaciones posteriores el genotipo de este individuo ha podido ser modificado a trav´es del operador de cruce o un operador de mutaci´on adicional que s´ı produzca cambios (como Mutaci´on bit a bit) y este cambio en el cod´on ya no tiene por qu´e producir el mismo m´odulo y modificar´a el fenotipo. Un ejemplo de mutaci´on neutral podr´ıa ser el siguiente: <S> ::= <B> | <C> | <D> <B> ::= b | a <C> ::= c | a <D> ::= d | a Listing 7.4: Gram´atica e individuo de ejemplo para aplicar mutaci´on neutral Codones del individuo: 864375... Primero usar´ıamos el cod´on 8 para expandir S. El n´umero de producciones posibles para Ses 3. As´ı pues, har´ıamos 8 m´od 3 = 2, optar´ıamos por expandir usando D. Lo interesante es que para 11, 14, 17, y en definitiva la suma de 3 al cod´on el n´umero de veces que queramos, obtenemos el mismo resultado. Por lo tanto podemos hacer la siguiente suma al valor del cod´on: 7.7. Multithread 67 cod´on = cod´on + (n∗n´umero producciones posibles para el no terminal a expandir) donde nes un valor entero arbitrario mayor que 1. As´ı se mantiene la selecci´on de producciones intacta (y por lo tanto el fenotipo del individuo, el ´arbol), mientras que el genotipo (el propio cod´on) s´ı var´ıa. El mismo proceso se realizar´ıa ahora para ver si expandimos Dcon doa, y lo mismo vuelve a ser aplicable, permiti´endonos en definitiva mutar todos los codones utilizados del individuo con garant´ıa de no modificar su fenotipo. 7.7. Multithread Al empezar a desarrollar el segundo bot tambi´en pudimos aprovechar otra funcionalidad de JECO que consiste en paralelizar la etapa m´as pesada del algoritmo (evaluaci´on) en los distintos procesadores del ordenador. As´ı, las etapas donde se ejecutan los operadores de selecci´on, cruce y mutaci´on se hacen en el mismo hilo de procesamiento, ya que estas etapas son m´as llevaderas, con alg´un operador ejecut´andose por ejemplo un 10 % de las veces en la iteraci´on. Y seguidamente cuando llegamos a la etapa de evaluaci´on, podemos dividir la tarea entre tanto n´ucleos como haya disponibles para ejecutar el juego 1, 10, 20 o incluso m´as veces para paliar la aleatoriedad de los fantasmas, y eso para cada individuo de la poblaci´on. Gracias a esta t´ecnica nos hemos podido permitir poblaciones m´as grandes y mayor n´umero de generaciones en las evoluciones sin que los tiempos para completarlas sean desorbitados. 7.8. Optimizaciones secundarias de JECO El framework JECO nos es de mucha ayuda, pero ha habido ciertos momentos en los que se necesitaban ciertos ajustes o carec´ıa de ciertas funcionalidades que nos hac´ıan falta, por lo que las hemos tenido que implementar a mano. Las m´as importantes son: 7.8.1. Creaci´on de las clases para cada funci´on fitness Se implement´o un patr´on de dise˜no Command para estructurar la creaci´on de funciones de fitness. As´ı todas las funciones, aunque dispares, tienen un punto com´un que funciona de acuerdo a lo esperado. 7.8.2. Wrapper de funciones fitness para su uso en multiobjetivo Gracias al patr´on Command para las clases de las funciones de fitness se pudo implementar una factor´ıa de clases fitness y un envoltorio (FitnessWrapper). A esta clase se le pasan las funciones creadas f´acilmente desde ObjectiveFactory cuando se quieren 68 Cap ´ ıtulo 7. Estudios, optimizaciones y mejoras cambiar objetivos, incluso en tiempo de ejecuci´on. Despu´es, FitnessWrapper es llamado cada vez que se eval´ua el algoritmo en las sucesivas generaciones, justo despu´es de ejecutar Pac-Man para pasarle las estad´ısticas de la partida. 7.8.3. Modificaci´on de la mutaci´on La mutaci´on por defecto en JECO se realiza ´unicamente sobre los individuos que son resultantes de un cruce. Mezclar cruce y mutaci´on de esta manera no nos ha dado buenos resultados, y lo hemos sustituido por una aproximaci´on m´as com´un en los algoritmos gen´eticos: primero se aplica el operador de cruce a los elementos seleccionados de la poblaci´on anterior, y despu´es se aplica el operador de mutaci´on a toda esa nueva poblaci´on de elementos seleccionados e hijos generados por el operador de cruce. De esta manera garantizamos la independencia de operadores, ya que de lo contrario, tener una probabilidad de cruce muy baja implicaba que el operador de mutaci´on se aplicase con una probabilidad distinta y solo a ciertos elementos. 7.8.4. Modificaci´on de la ´elite JECO utiliza un m´etodo particular a la hora de mantener la ´elite en la poblaci´on. En cada generaci´on y despu´es de haber realizado la selecci´on, cruce y mutaci´on en los individuos pertinentes JECO un´ıa la poblaci´on antigua y la nueva poblaci´on, constituida por los elementos seleccionados y los hijos creados a trav´es de aplicar el operador de cruce, creando una uni´on de poblaciones ordenada de mejor a peor fitness. De este nuevo conjunto se extrae el n´umero de individuos m´aximo que pueden haber en una poblaci´on. Este m´etodo no aporta diversidad a la poblaci´on dado que se usa toda la poblaci´on de la anterior generaci´on (sin alterar) y la nueva poblaci´on para generar la poblaci´on final que ser´a utilizada en la siguiente generaci´on, haciendo que muchos individuos de la anterior generaci´on se conserven en la nueva generaci´on (y normalmente a lo largo de muchas generaciones m´as) conduciendo la b´usqueda r´apidamente a un ´optimo local del cual es dif´ıcil de salir por falta de diversidad. Optamos por deshacernos de esta implementaci´on y desarrollamos un elitismo cl´asico (ver Figura 7.5), donde un subconjunto de los mejores individuos de la poblaci´on antigua (determinado por un par´ametro denominado porcentaje de elitismo) se incluyen en la nueva generaci´on, sustituyendo un porcentaje id´entico de peores individuos en la nueva poblaci´on. As´ı aportando mayor diversidad y permitiendo que la b´usqueda no se estanque tan r´apido en un ´optimo local, incluso pudiendo salir de ´el. 7.9. Batch Executor Debido que empleamos controladores de fantasmas no deterministas, necesitamos ejecutar varias partidas con un mismo controlador de Pac-Man para obtener resultados estad´ısticamente correctos de su rendimiento. Puesto que aumentar el n´umero de partidas que juega un mismo individuo en la evaluaci´on del algoritmo evolutivo supone un 7.9. Batch Executor 69 Figura 7.5: A la izquierda gr´afica de la evoluci´on de la poblaci´on con el nuevo m´etodo de elitismo. A la derecha gr´afica usando el m´etodo de elitismo de JECO usado anteriormente. La l´ınea gris muestra la media del fitness de la poblaci´on. impacto significativo en el tiempo de ejecuci´on de este, optamos por ejecutar un n´umero conservador de partidas (unas 30, como queda reflejado en el par´ametro Evaluaciones por individuo de la Tabla 6.1). Una vez terminada la ejecuci´on del algoritmo evolutivo, extraemos el c´odigo del mejor individuo producido. Despu´es empleamos este c´odigo para jugar mil partidas contra el controlador de fantasma deseado. Gracias a este procedimiento podemos obtener datos precisos manteniendo tiempos de entrenamiento razonables. Requerimos esta reevaluaci´on mas precisa del bot debido a la gran aleatoriedad del comportamiento de controladores de los fantasmas. Cabe destacar el hecho de que a partir de 1000 partidas no se produce ninguna mejora en la precisi´on de los datos obtenidos. 70 Cap ´ ıtulo 7. Estudios, optimizaciones y mejoras Cap´ıtulo 8 Herramienta gr´afica de experimentaci´on Necesitamos una interfaz gr´afica (GUI) para la ejecuci´on continua de algoritmos. Con ligeras variaciones, pero siempre presentando los resultados de forma inmediata y eficaz. El patr´on que mejor se nos ajusta es Feature, Search and Browse [36], porque podemos tener tanto los par´ametros como el resultado de su ejecuci´on a la vista, al mismo tiempo. 8.1. Necesidad de este tipo de herramientas Una caracter´ıstica de los algoritmos gen´eticos es que son muy sensibles a la configuraci´on inicial, cambiando ligeramente un par´ametro puede llevar a generar demasiado ruido y que el algoritmo se quede muy lejos de converger. De hecho, los rangos efectivos de cada operador var´ıan ampliamente entre ellos, incluso siendo de la misma fase del algoritmo (p. ej. dos m´etodos de mutaci´on). Por ese motivo es necesario realizar un gran n´umero de experimentos comprobando qu´e par´ametros funcionan mejor. Para agilizar este proceso hemos desarrollado una herramienta que permite visualizar el comportamiento del algoritmo durante la fase de aprendizaje y de ese modo abortar ejecuciones que no funcionan, sin tener que esperar a que acaben. Pudiendo tambi´en analizar su resultado posteriormente, habiendo acabado el algoritmo completamente o no. 71 78 Cap ´ ıtulo 8. Herramienta gr´afica de experimentaci´on 8.3.2. Pesta˜nas Tenemos varias presentaciones al mismo nivel, por lo que se han dispuesto diferentes pesta˜nas para cambiar entre ellas. Este dise˜no no es limitante, permitiendo incluso analizar resultados del entrenamiento anterior mientras se est´a realizando un nuevo entrenamiento. Figura 8.15: Pesta˜na Progress. Dos objetivos siendo optimizados a la vez. 8.3.3. Tiempo estimado Este panel tambi´en cuenta con una barra de progreso que aparece durante la ejecuci´on y desaparece al terminar. Indica adem´as el tiempo estimado restante en una etiqueta sobre la barra. Esta barra tambi´en cuenta con un bot´on Cancel para detener la ejecuci´on del algoritmo en cualquier punto del entrenamiento, pudiendo hacer an´alisis de la evoluci´on y ejecuciones del mejor individuo hasta el momento de la parada. 8.4. Panel del mejor individuo 79 Figura 8.16: Barra de progreso con tiempo (segundos) al ejecutarse un entrenamiento. 8.4. Panel del mejor individuo En cuanto el algoritmo termina de entrenar aqu´ı podemos ver el fenotipo correspondiente al mejor individuo. Figura 8.17: Pesta˜na Derivation. C´odigo del mejor individuo evolucionado. 8.5. Panel de juego Permite ejecutar y analizar visualmente una partida del juego Ms. Pac-Man a partir de un fenotipo dado. El bot´on Copy best here copia el programa del mejor individuo generado por el algoritmo a la ventana de edici´on, para despu´es ejecutarlo directamente en Pac-Man con el bot´on Run code o editarlo antes de ejecutar, si se desea. Los controles contienen adem´as un slider que permite ajustar la velocidad de la partida dentro de un rango razonable. 80 Cap ´ ıtulo 8. Herramienta gr´afica de experimentaci´on Figura 8.18: Pesta˜na Game. A la izquierda Pac-Man jugando, a la derecha el c´odigo del controlador que se est´a ejecutando. Cap´ıtulo 9 Conclusiones 9.1. Conclusiones A lo largo del desarrollo del Trabajo de Fin de Grado hemos pasado por numerosas versiones con distintos enfoques aplicados a la generaci´on de bot de Ms. Pac-Man a trav´es de gram´aticas evolutivas. Primero de todo, mediante la generaci´on de aut´omatas que ejecutaban cadenas de acciones (que posteriormente fue ampliado con acciones de m´as alto nivel y condicionales muy simples), que, si bien no alcanz´o resultados destacablemente positivos, si logr´o encontrar una brecha en las reglas del juego que le permit´ıa conseguir completar niveles muy f´acilmente contra fantasmas no muy inteligentes. Despu´es, orientamos nuestra gram´atica a la generaci´on de controladores reactivos, sustituyendo tambi´en las anteriores cadenas de acciones por un ´arbol de decisi´on. Este cambio supuso una mejora significativa, permiti´endonos dise˜nar gram´aticas de distintos niveles de abstracci´on. A continuaci´on, realizamos una serie de estudios (de la presi´on selectiva, del uso de codones y de funciones de fitness) que nos llevaron a incluir numerosas mejoras con el fin de mejorar tanto los resultados obtenidos por el algoritmo evolutivo (cruce LHS, Mutaci´on Neutral, optimizaci´on multiobjetivo y numerosos cambios menores en el framework JECO), como la comodidad de empleo de la herramienta (multithread). Todas estas mejoras centradas en el algoritmo evolutivo han tenido la suficiente repercusi´on en el rendimiento de los bots generados como para formar parte de los par´ametros con los que alcanzamos mejores resultados. Finalmente, tras un profundo an´alisis de todas las diferentes pruebas que hemos realizado durante el transcurso de Trabajo de Fin de Grado, podemos concluir con una serie de hechos. Primero de todo, obtenemos los mejores resultados, tanto para cualquier gram´atica como para cualquier controlador de fantasmas adversario, utilizando los par´ametros del algoritmo evolutivo de la Tabla 9.1. 1o NSGA II si se est´a empleando multiobjetivo 81 82 Cap ´ ıtulo 9. Conclusiones Porcentaje M´etodo de selecci´on Torneo Binario 1M´etodo de cruce LHS 60 M´etodo de mutaci´on Integer Flip 10 Mutaci´on Neutral S´ı - Elitismo S´ı 5 Tabla 9.1: Par´ametros usados. Segundo, tal como se aprecia se en la Figura 9.1, los bots consiguen mejores resultados en evoluciones con pocas generaciones, 50 en el caso de la gr´afica, cuanto mayor es la abstracci´on de la gram´atica aplicada. No obstante, los bots generados usando la gram´atica de medio nivel consiguen superar a los de alto nivel con muchas generaciones (por ejemplo 100), al tener mayor potencial, como se explica m´as adelante en la Tabla 9.2. Figura 9.1: Fitness con un solo objetivo. Tercero, tal como se aprecia en la Tabla 9.2, los bots generados usando tanto la gram´atica de medio nivel como la de alto nivel superan los controladores de Pac-Man base as´ı como otros bots generados por gram´aticas evolutivas, como por ejemplo el generado por la universidad UCD de Dubl´ın [15]. Esto ocurre tanto enfrent´andose al controlador Random Ghosts como al de Legacy Ghosts. Uno de los factores que nos permiten obtener mejores resultados que el bot de UCD Dublin [15] (especialmente interesante al estar tambi´en basado en gram´aticas evolutivas) consiste en que su bot emplea funciones demasiado espec´ıficas, las cuales acaban 9.2. Difusi´on 83 limitando el comportamiento del bot, siendo una de ellas por ejemplo esperar a que los fantasmas se acerquen siempre que se encuentre al lado de una power pill. Otro de los factores es el uso de numerosos par´ametros para evaluar sus funciones condicionales. Por ejemplo, su bot utiliza una ventana alrededor de Pac-Man, dentro de la cual eval´ua condiciones como encontrar fantasmas dentro de esta. Para emplear dicha ventana, emplea dos par´ametros ancho y alto. Por otro lado, nuestras funciones condicionales obtienen directamente la distancia de la ruta a determinados elementos, pudiendo operar esta distancia con distintos operadores num´ericos sobre valores tambi´en num´ericos. Por ´ultimo, si bien el empleo de la optimizaci´on multiobjetivo supone una mejora significativa en ejecuciones del algoritmo evolutivo relativamente cortas (al evitar estancamiento en los numerosos m´ınimos locales), no produce una diferencia suficientemente significativa en los bots generados mediante ejecuciones suficientemente largas. Esto es apreciable en la Tabla 9.3 (donde las sigles MO se refieren a los bots que emplean la Optimizaci´on Multiobjetivo), y sucede as´ı en el caso concreto de Ms. Pac-Man vs Ghost debido a la relaci´on directa entre los distintos fitness que hemos perseguido en multiobjetivo (fantasmas comidos, niveles completados y puntos alcanzados sin el multiplicador de puntos al comer fantasmas) con la puntuaci´on (fitness perseguido previo a la optimizaci´on multiobjetivo), siendo esta una composici´on de los fitness anteriores. 9.2. Difusi´on Considerando el impacto que puede tener el proyecto que hemos realizado, hemos decidido publicarlo [7] como c´odigo abierto y bajo licencia GPL [4] en la plataforma GitHub. Esto lo hicimos con la esperanza de poder ser de ayuda a cualquier proyecto relacionado con el campo de la evoluci´on gramatical o la inteligencia artificial aplicada a videojuegos. Finalmente, una vez hab´ıamos obtenido y analizado los resultados del proyecto, decidimos llevarlo un paso mas all´a y publicar un art´ıculo cient´ıfico sobre ´el. Este, titulado “A Pac-Man bot based on Grammatical Evolution”, se centra en la implementaci´on final (arboles de decisi´on) y el uso de gram´aticas de medio y alto nivel, mencionando brevemente la mejora de optimizaci´on multiobjetivo. En estos momentos el art´ıculo ha sido enviado al CoSECiVi 2017 (Congreso de la Sociedad Espa˜nola para las Ciencias del Videojuego) y se encuentra pendiente de revisi´on por pares. 9.3. Trabajo futuro Aunque estamos satisfechos con el alcance de nuestro trabajo y sus resultados, nos habr´ıa gustado experimentar y comprobar otras t´ecnicas no incluidas por falta de tiempo. Son las que se describen a continuaci´on. 84 Cap ´ ıtulo 9. Conclusiones 9.3.1. ´ Arboles de comportamiento Una de las posibles t´ecnicas a aplicar son los ´arboles de comportamiento (Behaviour trees). El uso de ´arboles de comportamiento habr´ıa supuesto incluir en nuestras gram´aticas bucles en los formatos t´ıpicos (while, for, do-while, ...). Esto supone que para encontrar un terminal que devuelva un movimiento en nuestro ´arbol de decisi´on, ya no se parte siempre desde la ra´ız, sino que puede tener que continuarse en un punto definido por las solicitudes de movimiento previas. Esta t´ecnica en principio posibilita, o facilita la producci´on de estrategias m´as espec´ıficas, que requieran continuidad. Sin ´arboles de comportamiento tambi´en pueden conseguirse, pero el conjunto de condiciones a evaluar para llegar a dichas estrategias y soportar varias a la vez puede hacerse enorme, y llegar a dichas soluciones en un espacio de b´usqueda tan grande/complejo es extremadamente poco factible en t´erminos de potencia computacional. 9.3.2. Bloques de comportamiento Nos gustar´ıa usar una t´ecnica basada en ´arboles que ya se ha visto en diferentes trabajos sobre ´arboles de comportamiento [23] [31]. Esta t´ecnica consiste en entrenar bots en tareas espec´ıficas como huir, comer pills, comer fantasmas, etc. Una vez hecho eso construir ´arboles de decisi´on a partir de estas tareas (sub´arboles), contruyendo as´ı comportamientos complejos a partir de otros m´as simples. Adem´as de que las comparaciones con multiobjetivo ser´ıan bastante interesantes debido a la similitud de estas tareas con los multiobjetivos. 9.3.3. NEAT Otra t´ecnica prometedora ser´ıa la aplicaci´on de redes neuronales debido a su amplio espectro y gran capacidad de generalizaci´on. Como inputs tendr´ıamos las mismas funciones de las que hacen uso las gram´aticas para conocer el estado del juego y como output nos dar´ıa un movimiento que ejecutar´ıa Pac-Man. El problema radicar´ıa en la arquitectura de la red, por lo que para dar con la ´optima y siguiendo con el esp´ıritu evolucionista, usar´ıamos el algoritmo NEAT [35] (NeuroEvolution of Augmenting Topologies). Este algoritmo se vale de t´ecnicas de Programaci´on Evolutiva para evolucionar y proteger las topolog´ıas de las redes neuronales que genera hasta que est´an lo suficientemente entrenadas para resolver con ´exito un problema concreto. La ventaja adicional es que se podr´ıa integrar dentro del framework JECO con m´ınimo esfuerzo, m´as all´a de la implementaci´on del mismo. 9.3. Trabajo futuro 85 Pac-Man Ghosts score level time (game ticks) max avg std max avg std max avg std Random Random 1380 501 213 1 0.036 0.186 5635 1943 887.5 NearestPill 18910 4471 2654 5 1 0.9 7216 1795 1018 UCD Dublin bot [15] 11640 4288 - - - - - - - Low-level 900 151 117 1 0.071 0.257 5094 2151 972.1 Medium-level 64600 48558 10780 18 15 3.4 24000 21579 4470 High-level 55480 32704 13237 18 10.4 4.3 24000 17457 6784 Random Legacy 1840 197 107 0 0 0 877 465 61.3 NearestPill 7190 3531 638 1 0.4 0.5 1881 1152 143.7 UCD Dublin bot [15] 12350 3945 - - - - - - - Low-level 120 120 0 0 0 0 600 425 34.5 Medium-level 15960 6358 2883 3 0.9 0.7 4973 1916 730 High-level 20040 5972 2832 4 1 0.6 8364 2026 1020 Tabla 9.2: Pac-Man vs Ghost controllers’ comparison. 1000 games. 86 Cap ´ ıtulo 9. Conclusiones Pac-Man Ghosts score level time (game ticks) max avg std max avg std max avg std Medium-level 9.2 Random 64600 48558 10780 18 15 3.4 24000 21579 4470 Medium-level (MO) 62050 46922 1243 18 15 4 24000 20868 5094.5 High-level 9.2 55480 32704 13237 18 10.4 4.3 24000 17457 6784 High-level (MO) 57370 32441 12712 17 10 4.1 24000 17536 6604.7 Medium-level 9.2 Legacy 15960 6358 2883 3 0.9 0.7 4973 1916 730 Medium-level (MO) 18020 6229 2832 3 0.9 0.7 5041 1905 725 High-level 9.2 20040 5972 2832 4 1 0.6 8364 2026 1020 High-level (MO) 20040 5972 2832 4 1 0.6 8364 2026 1020 Tabla 9.3: Pac-Man vs Ghost controllers’ comparison including Multi-Objective. 1000 games. Cap´ıtulo 10 Conclusions 10.1. Conclusions All along this undergraduate thesis we have iterated through numerous versions with different approaches, all applied to the generation of our bot for Ms. Pac-Man with grammatical evolution. First of all, with the automaton approach, the bot executed sequences of actions (which was later improved with high level actions and very simple conditional evaluations), even if its results weren’t so good score-wise, achieved to develop a tactic that allowed it to progress many levels against the most silly ghosts. After that we oriented our grammars to follow a reactive approach, changing our previous sequences of actions for decision trees. This change was a significant breakthrough, that allowed us to design grammars with different levels of abstraction. Next, we did a series of studies (of selective pressure, codon usage, and fitness functions) which lead us numerous improvements in a try to obtain better results, both in algorithm efficacy (LHS cross-over, neutral mutation, multi-objective optimization, and multiple minor changes to the JECO framework), and the friendliness of our tool (multithreading). All this upgrades had enough repercussion in the bot performance as to include them in the parameters of execution for the best results we show. Finally, after analysing all the tests we did, we could conclude various things. First of all, we obtain the best results, for any grammar and against any ghost controller, using the parameters from Table 10.1 for the evolutionary algorithm. Second, as Figure 9.1 shows, the bots obtain better results, when using only a few generations (for example 50), as the more abstract the used grammar is. However, when using more generations (for example 100), the bots using the medium-level grammar obtain the best results, due to its higher potential, as shown later at Table 9.2. 1or NSGA II if multi-objective is being used 87 94 Cap ´ ıtulo 11. Contribuciones individuales cruce y mutaci´on con el fin de detectar la mejor combinaci´on. Este estudio no aport´o nada significativo debido a la similaridad de los resultados obtenidos pero pudimos ver que todas las gr´aficas obtenidas mostraban un comportamiento poco convergente y, por recomendaci´on de nuestro profesor Carlos, decidimos implementar nuevos operadores de cruce y mutaci´on. La implementaci´on del cruce LHS la realic´e a partir de un art´ıculo investigado. La implementaci´on como tal no fue dif´ıcil pero el estudio de resultados y la b´usqueda de posibles errores fue un poco m´as laborioso. Durante este estudio descubr´ı que gran parte de los codones del genotipo de los individuos no eran utilizados a la hora de generar el fenotipo y realic´e otro estudio sobre el uso de los codones descubriendo que, en efecto, normalmente s´olo un 10 % de los codones era utilizado a la hora de generar los distintos fenotipos. Por ´ultimo, realice un peque˜no cambio en la implementaci´on multiobjetivo de JECO el cual no utilizaba en su totalidad el algoritmo NSGA-II, utilizando una mezcla entre el NSGA-II y otro denominado MOGA. El cambio supuso el uso ´unico y correcto del algoritmo NSGA-II. Ha sido un placer trabajar al lado de mis compa˜neros y les agradezco su ayuda y comprensi´on durante mi estancia Erasmus+ que no me permiti´o ayudarles al cien por cien. Aun as´ı siempre ha habido un gran compa˜nerismo entre nosotros y todos han estado dispuestos a ayudar a otro en cualquier momento. Tambi´en cabe destacar la realizaci´on de un art´ıculo acad´emico en conjunto y que con otro grupo no hubiese sido posible. 11.3. Jos´e Miguel Tajuelo Garrig´os Durante el verano previo al proyecto acordamos intentar codificar un bot de PacMan cada uno de los integrantes del proyecto, para poder extraer algunas ideas del experimento. Una vez ya iniciado el Trabajo de Fin de Grado, ayude a mis compa˜neros a decidir qu´e framework usar, analizando y realizando pruebas con GEVA, hasta optar final por descartar y emplear JECO en su lugar. Una vez que Jorge Vieira logr´o integrar Ms. Pac-Man vs. Ghosts, le ayude a implementar el primer bot experimental que ejecutaba cadenas de caracteres, centr´andome principalmente en el dise˜no de un mecanismo de condicionales (y su implementaci´on), optimizaciones y mejoras de algunas funciones (como la mejora de una funci´on de huida b´asica), y traza de algunos errores y comportamientos an´omalos (como la necesidad de un reseteo del punto de entrada al comienzo de cada vida). En la segunda fase del proyecto realice la implementaci´on de ´arboles de decisi´on, empleando enumerados para los s´ımbolos de la gram´atica (lo simplifica mucho la tarea de a˜nadir nuevas funciones que consulten el estado y acciones), con condicionales con operadores num´ericos y booleanos, y con una funci´on de evaluaci´on recursiva. Adem´as, implementa un traductor (parser) que construye estos ´arboles a partir de un string con el c´odigo. Adem´as, ayude a H´ector con un m´etodo que pasase el ´arbol a string de forma legible para cualquier usuario (en forma de c´odigo convencional), adem´as de implementar m´etodo que “limpie” el string de c´odigo embellecido (o no) a un string si parseable. 11.4. Jorge Vieira Luna 95 Una vez completada la implementaci´on de ´arboles de decisi´on, a˜nad´ı, al igual que el resto de mis compa˜neros, algunos s´ımbolos para tener, requiriendo implementaci´on de nuevas funciones internas en el c´odigo de Ms. Pac-Man vs. Ghosts, as´ı como ayudar a Jorge Vieira a mejorar la eficiencia de las funciones que m´as tiempo consumen. Despu´es, tambi´en revise que todas las funciones implementadas hasta ese momento realizasen el comportamiento esperado, y no hubiera ning´un error imposible de trazar, descubriendo algunas erratas, funciones que no realizaban lo esperado y algunos fallos de eficiencia. Entre ellas se encuentra el c´alculo de distancias a fantasmas no comibles, que supuso su implementaci´on, ya que en lugar de calcular la distancia teniendo en cuenta la imposibilidad de los fantasmas de darse la vuelta, la calculaba aplic´andole err´oneamente ese handicap a Pac-Man. Por otro lado, tambi´en a˜nadi´o un nuevo fitness basado en el n´umero de niveles completados. Tambi´en cabe destacar que realic´e un estudio completo sobre la presi´on selectiva y el impacto de esta en nuestro proyecto. Simult´aneamente ayude a H´ector con distintos aspectos de la Interfaz Gr´afica. Primero de todo, realice el dise˜no e implementaci´on del selector de objetivos a perseguir, partiendo del concepto de una ventana emergente (para evitar saturar el panel de ajustes del experimento) en la que poder seleccionar y deseleccionar elementos de una lista. Esto lo logre creando personalizada una lista (de interfaz gr´afica) que sobreescribe parte de sus m´etodos. Tambi´en realice una reorganizaci´on experimental de los elementos del panel de ajustes, revirtiendo los cambios al final. Tambi´en realic´e, con la ayuda de H´ector, numerosos cambios internos para permitir el escalado de la pantalla del juego para una visualizaci´on m´as clara. Finalmente, para la obtenci´on de datos concretos sobre el rendimiento del proyecto, ayude a H´ector con el tratamiento de datos obtenido a partir de tanto la ejecuci´on normal como la ejecuci´on del Batch Executor. 11.4. Jorge Vieira Luna Cuando tuvimos claro el proyecto lo primero fue buscar junto a los compa˜neros los frameworks que ´ıbamos a usar, tanto para Pac-Man como para JECO. Decantarse por “Ms. Pac-Man Vs. Ghost” para Pac-Man fue f´acil: Ha habido varias versiones, pero la ´unica que se mantiene actualizada y para la que se hacen competiciones a d´ıa de hoy es esa. El framework de gram´aticas evolutivas en cambio no estaba tan claro. Primero probamos bastante GEVA, tal vez por ser de los m´as famosos, pero personalmente no me gust´o nada la estructura del c´odigo con vistas a integrarlo con Pac-Man. Sin embargo tras leer y trastear con el c´odigo de JECO para mi estaba claro, con JECO ser´ıa mucho m´as f´acil, as´ı que fu´ı partidario de JECO que es lo que usamos al final. Hemos tenido sus m´as y sus menos con ´el, pero personalmente yo y creo que mis compa˜neros estamos bastante contentos con la decisi´on. Una vez que tuvimos los frameworks me ocup´e de la integraci´on entre ambos, para conseguir una primera versi´on que fuera capaz de jugar utilizando gram´aticas, aunque fueran extremadamente primitivas. Pese a lo rudimentario y lo malo de los resultados 96 Cap ´ ıtulo 11. Contribuciones individuales iniciales, fue emocionante ver que Pac-Man se mov´ıa de una manera que no hab´ıa especificado directamente nadie, sino que hab´ıa determinado ´el como la mejor. La integraci´on supuso b´asicamente que JECO lanzara un Pac-Man para evaluar cada uno de los ´arboles de derivaci´on que produc´ıa pasados a formato string, Pac-Man le devolviera los puntos y JECO los interpretara como fitness. Como ya hab´ıa que empezar a valorar qu´e gram´aticas y mejoras eran mejor que otras, dise˜n´e un sistema de logs de fitness tambi´en bastante rudimentario, mientras se habilit´o multithread y la GUI iba tomando forma en gran parte gracias a H´ector. Luego me puse a tratar de mejorar la eficacia de este primer sistema rudimentario, sobretodo con la ayuda de Jos´e Miguel, para conseguir darle forma de aut´omata que tuviera en cuenta ciertos factores del estado del juego, e incluso conseguimos integrar con ´el evaluaciones condicionales. Tras esto decidimos “ponernos serios” e implementar ´arboles de decisi´on en condiciones, pudiendo introducir s´ımbolos en la gram´atica que representaran llamadas a funciones de consulta del estado de juego, y en funci´on del resultado optar por una rama u otra del ´arbol. Fue interesante pensar el dise˜no de implementaci´on con H´ector y Jos´e Miguel, y posteriormente ayudar un poco a Jos´e Miguel en la implementaci´on final. Una vez tuvimos los andamios de la estructura definitiva ya implementados, me puse a crear funciones de Pac-Man con los compa˜neros para que la gram´atica pudiera consultarlas y obtener informaci´on del juego o movimientos directos. Siguiendo con las mejoras estructurales, cree un sistema que recopilaba informaci´on diversa de cada partida jugada, de forma que la funci´on de fitness recibe un objeto con ella y puede tener en cuenta lo que le interese para evaluar. Este fue el comienzo de lo que luego ser´ıa el multi-objetivo. Tambi´en implement´e un log mucho m´as interesante que el rudimentario inicial, que guardaba mucha m´as informaci´on de las ejecuciones realizadas desde JECO y sus mejores resultados, en formato csv. Dicho log luego incluir´ıa incluso una comunicaci´on con git utilizando la librer´ıa JGit, que permitir´ıa registrar el commit con el que se realiz´o la ejecuci´on, para no mezclar resultados de una y otra versi´on del proyecto. Por ´ultimo mencionar la implementaci´on de Neutral Mutation, un operador de mutaci´on espec´ıfico para gram´aticas evolutivas que ayuda a dar diversidad a la poblaci´on. Faltan un mont´on de cosas menos significativas que fueron ocurriendo entre todo esto, pero en definitiva: Un mont´on de trabajo tanto en l´ıneas c´odigo como en investigaci´on, debates de implementaci´on, trabajo en equipo y un proyecto que al menos a mi me ha resultado muy interesante y me ha hecho aprender much´ısimo sobre inteligencia artificial, programaci´on gen´etica y gram´aticas evolutivas, y conocer m´as a tres muy buenos compa˜neros con los que ha sido un placer trabajar. Bibliograf´ıa [1] Computational Intelligence & Games conference. URL http://cig16.image.ece. ntua.gr/. [2] Decision trees, part i: How decision trees work. URL http://www.aihorizon.com/ essays/generalai/decision_trees.htm. [3] Jflap. URL http://www.jflap.org/. [4] Pac-Man license. URL https://github.com/hecoding/Pac-Man/LICENSE.txt. [5] Ms. Pac-Man Vs. Ghosts tournament. URL http://www.pacmanvghosts.co.uk/. [6] What is a Parser? techopedia. URL https://www.techopedia.com/definition/ 3854/parser. [7] Pac-man. URL https://github.com/hecoding/Pac-Man. [8] Atif M Alhejali and Simon M Lucas. Evolving diverse ms. pac-man playing agents using genetic programming. In Computational Intelligence (UKCI), 2010 UK Workshop on, pages 1–6. IEEE, 2010. [9] Lourdes Araujo and Cervig´on Carlos. Algoritmos evolutivos: un enfoque pr´actico. RA-MA S.A. Editorial y Publicaciones, 2009. ISBN 9788478979110. URL https: //books.google.es/books?id=XEDVcQAACAAJ. [10] Holger Billhardt. Gram´aticas independientes del contexto. URL http://www.ia. urjc.es/grupo/docencia/automatas_itis/apuntes/capitulo10.pdf. Universidad Rey Juan Carlos. [11] Matthias F Brandstetter and Samad Ahmadi. Reactive control of ms. pac man using information retrieval based on genetic programming. In Computational Intelligence and Games (CIG), 2012 IEEE Conference on, pages 250–256. IEEE, 2012. [12] Jos´e Manuel Colmenar. Fundamentos de la evoluci´on gramatical. URL http://web. fdi.ucm.es/posgrado/conferencias/JoseManuelColmenar-slides.pdf. Universidad Rey Juan Carlos. 97 98 BIBLIOGRAF´ IA [13] Wikimedia Commons. Front pareto, 2017. URL https://upload.wikimedia.org/ wikipedia/commons/b/b7/Front_pareto.svg. [14] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182–197, 2002. [15] Edgar Galv´an-L´opez, John Mark Swafford, Michael O’Neill, and Anthony Brabazon. Evolving a ms. pacman controller using grammatical evolution. In European Conference on the Applications of Evolutionary Computation, pages 161–170. Springer, 2010. [16] Lars Marius Garshol. Bnf and ebnf: What are they and how do they work. URL http://www.garshol.priv.no/download/text/bnf.html. [17] Nuria G´omez, Luis F Mingo, Jesus Bobadilla, Francisco Serradilla, and Jose A Calvo Manzano. Particle swarm optimization models applied to neural networks using the r language. WSEAS Transactions on Systems, 9(2):192–202, 2010. [18] Jerome Guibert. A library in java for using grammatical evolution. URL https: //github.com/geronimo-iia/geva. [19] Robin Harper and Alan Blair. A structure preserving crossover in grammatical evolution. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, volume 3, pages 2537–2544. IEEE, 2005. [20] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages and computation. Pearson Addison Wesley, 2007. [21] J.R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. A Bradford book. Bradford, 1992. ISBN 9780262111706. URL https://books.google.es/books?id=Bhtxo60BV0EC. [22] Federico Liberatore, Antonio M. Mora, Pedro A. Castillo, and Juan Juli´an Merelo Guerv´os. Evolving Evil: Optimizing Flocking Strategies Through Genetic Algorithms for the Ghost Team in the Game of Ms. Pac-Man, pages 313–324. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. ISBN 978-3-662-45523-4. doi: 10.1007/978-3-662-45523-4 26. [23] Chong-U Lim, Robin Baumgarten, and Simon Colton. Evolving behaviour trees for the commercial game defcon. In European Conference on the Applications of Evolutionary Computation, pages 100–110. Springer, 2010. [24] Nuno Louren¸co, Francisco B Pereira, and Ernesto Costa. Unveiling the properties of structured grammatical evolution. Genetic Programming and Evolvable Machines, 17(3):251–289, 2016. BIBLIOGRAF´ IA 99 [25] Christian Oesch and Dietmar Maringer. A Neutral Mutation Operator in Grammatical Evolution, pages 439–449. Springer International Publishing, Cham, 2015. ISBN 978-3-319-11313-5. doi: 10.1007/978-3-319-11313-5 39. URL http://dx.doi.org/ 10.1007/978-3-319-11313-5_39. [26] Christian Oesch and Dietmar Maringer. A neutral mutation operator in grammatical evolution. In Intelligent Systems’ 2014, pages 439–449. Springer, 2015. [27] M. O’Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Genetic Programming. Springer US, 2012. ISBN 9781461504474. URL https://books.google.es/books?id=R6EACAAAQBAJ. [28] Michael O’Neill and Anthony Brabazon. Grammatical differential evolution. In IC-AI, pages 231–236, 2006. [29] Michael O’neill, Conor Ryan, Maarten Keijzer, and Mike Cattolico. Crossover in grammatical evolution. Genetic Programming and Evolvable Machines, 4(1):67– 93, March 2003. ISSN 1389-2576. doi: 10.1023/A:1021877127167. URL http: //dx.doi.org/10.1023/A:1021877127167. [30] Michael O’Neill and Anthony Brabazon. Grammatical swarm. In Genetic and Evolutionary Computation–GECCO 2004, pages 163–174. Springer, 2004. [31] Diego Perez, Miguel Nicolau, Michael O’Neill, and Anthony Brabazon. Evolving behaviour trees for the mario ai competition using grammatical evolution. Applications of evolutionary computation, pages 123–132, 2011. [32] Riccardo Poli and Nicholas F McPhee. Covariant parsimony pressure in genetic programming. Technical report, Technical Report CES-480, Department of Computing and Electronic Systems, University of Essex, 2008. [33] Jos´e Luis Risco. Java evolutionary computation library. URL https://github. com/jlrisco/jeco. [34] David Robles. Pacman vs ghosts simulator. URL https://github.com/ davidrobles/pacman-vs-ghosts. [35] Kenneth O Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary computation, 10(2):99–127, 2002. [36] Jenifer Tidwell. Designing interfaces: Patterns for effective interaction design. .O’Reilly Media, Inc.”, 2010. [37] Edward PK Tsang, Jin Li, Sheri Markose, Hakan Er, Abdel Salhi, and Giulia Iori. Eddie in financial decision making. Journal of Management and Economics, 4(4): 1–13, 2000. 100 BIBLIOGRAF´ IA [38] L Darrell Whitley et al. The genitor algorithm and selection pressure: Why rankbased allocation of reproductive trials is best. In ICGA, volume 89, pages 116–123, 1989.