Generación automática de contenidos para videojuegos mediante técnicas evolutivas

Generación automática de contenidos para videojuegos mediante técnicas evolutivas TRABAJO FIN DE GRADO Ingeniería de Computadores/Ingeniería del Software Dirigido por Carlos Cervigón Ruckauer Samuel Lapuente Jiménez Álvaro Lázaro Sevilla Departamento de Ingeniería del Software e Inteligencia Artificial Facultad de Informática Universidad Complutense de Madrid Junio 2017 Documento maquetado con T EXiS v.1.0+. Generación automática de contenidos para videojuegos mediante técnicas evolutivas Memoria de Trabajo de Fin de Grado Samuel Lapuente Jiménez Álvaro Lázaro Sevilla Dirigido por Carlos Cervigón Ruckauer Departamento de Ingeniería del Software e Inteligencia Artificial Facultad de Informática Universidad Complutense de Madrid Junio 2017 A mi compañero y amigo Álvaro, por aguantarme en todo momento y realizar la mayor parte del trabajo. A mi compañero y amigo Samuel, por aguantarme en todo momento y realizar la mayor parte del trabajo. Agradecimientos Primero, queremos agradecer a nuestras familias por aguantar estos años de esta travesía por el desierto que, al fin, acaban. Agradecer a la cafetería, a Andrés, a Sánchez y a Richy por manternos con vida un poco más a base de comida, café y cerveza. A los laboratorios, que aunque no tienen Github instalado y de los que nos han echado N + 1 veces, nos han permitido juntarnos y conseguir acabar este proyecto. A StackOverflow, lugar de reunión de eruditos de la programación y fuente inagotable de conocimiento. Ahora pongámonos serios, queremos agradecer a nuestro Director, Carlos, por todas las reuniones, información, correcciones y ayudas que nos ha prestado a lo largo del año. También queremos agradecerle que aceptara este TFG propuesto y se uniese a nosotros en esta divertida aventura. Por último, agradaceros a vosotros, queridos lectores, el que estéis echando un ojo a este trabajo, esperamos que lo disfrutéis. ix Índice Agradecimientos ix Resumen x Palabras clave xii Siglas xiii Abstract xiv Keywords xv 1. Introducción 1 1.1. Motivación ............................ 1 1.2. Objetivos ............................. 2 1.3. Estructura............................. 3 1.4. Motivation............................. 5 1.5. Goals ............................... 6 xvi Índice xvii 1.6. Structure ............................. 7 2. Trabajo relacionado 10 2.1. Generación Procedural . . . . . . . . . . . . . . . . . . . . . . 10 2.2. Técnicas Evolutivas . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3. Inteligencia Artificial . . . . . . . . . . . . . . . . . . . . . . . 16 2.4. Nuestra aportación . . . . . . . . . . . . . . . . . . . . . . . . 17 3. Computación evolutiva y Programación genética 19 3.1. Computación evolutiva . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1. Antecedentes biológicos . . . . . . . . . . . . . . . . . 19 3.1.2. Representación . . . . . . . . . . . . . . . . . . . . . . 20 3.1.3. Operadores genéticos . . . . . . . . . . . . . . . . . . . 21 3.1.4. Función de Fitness . . . . . . . . . . . . . . . . . . . . 26 3.1.5. Mejoras en el algoritmo evolutivo . . . . . . . . . . . . 26 3.2. Programación genética . . . . . . . . . . . . . . . . . . . . . . 26 3.2.1. Representación . . . . . . . . . . . . . . . . . . . . . . 27 3.2.2. Métodos de inicialización . . . . . . . . . . . . . . . . 28 3.2.3. Operadores ........................ 28 3.2.4. Mejoras en el algoritmo evolutivo . . . . . . . . . . . . 32 3.2.5. Ejemplos ......................... 33 4. Técnicas para la generación de mazmorras 36 Índice xviii 4.1. Ideainicial ............................ 36 4.2. Generación de mazmorras mediante algoritmos genéticos . . . 37 4.2.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.2. Decisiones de implementación . . . . . . . . . . . . . . 37 4.2.3. Evaluación de las mazmorras: Visión general . . . . . . 40 4.2.4. Evaluación de las mazmorras: Detalle . . . . . . . . . 42 4.2.5. Operadores del Algoritmo Genético . . . . . . . . . . . 45 4.2.6. La implementación en detalle . . . . . . . . . . . . . . 50 4.2.7. Individuos obtenidos . . . . . . . . . . . . . . . . . . . 52 4.3. Interfaz de usuario . . . . . . . . . . . . . . . . . . . . . . . . 55 5. Técnicas para la generación de la inteligencia artificial 58 5.1. Ideainicial ............................ 58 5.2. Decisiones de implementación . . . . . . . . . . . . . . . . . . 59 5.3. Función de evaluación . . . . . . . . . . . . . . . . . . . . . . 62 5.3.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . 63 5.3.2. Primera aproximación . . . . . . . . . . . . . . . . . . 63 5.3.3. Segunda aproximación . . . . . . . . . . . . . . . . . . 66 5.3.4. Tercera aproximación . . . . . . . . . . . . . . . . . . 70 5.3.5. Aproximación final . . . . . . . . . . . . . . . . . . . . 71 5.4. Operadores ............................ 75 5.4.1. Inicializador de la población . . . . . . . . . . . . . . . 75 Índice xix 5.4.2. Métodos de selección . . . . . . . . . . . . . . . . . . . 75 5.4.3. Operador de cruce . . . . . . . . . . . . . . . . . . . . 76 5.4.4. Operadores de mutación . . . . . . . . . . . . . . . . . 76 5.4.5. Eliminación de intrones . . . . . . . . . . . . . . . . . 76 5.5. Paralelización del fitness . . . . . . . . . . . . . . . . . . . . . 77 5.6. Interfaz de usuario . . . . . . . . . . . . . . . . . . . . . . . . 78 5.7. Resultados............................. 79 6. Framework de pruebas 86 7. Videojuego 89 7.1. Imágenes del videojuego . . . . . . . . . . . . . . . . . . . . . 90 8. Trabajo individual 94 9. Conclusiones y trabajo futuro 99 9.1. Conclusiones en la generación de mazmorras . . . . . . . . . . 99 9.2. Conclusiones en la generación de inteligencias artificiales . . . 100 9.3. Conclusiones generales . . . . . . . . . . . . . . . . . . . . . . 100 9.4. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.5. Conclusions in dungeon generation: . . . . . . . . . . . . . . . 102 9.6. Conclusions in artificial intelligence generation: . . . . . . . . 102 9.7. General conclusions: . . . . . . . . . . . . . . . . . . . . . . . 103 Índice xx 9.8. Futurework: ...........................103 Bibliografía 107 Índice de figuras 2.1. Escenario creado mediante Generación Procedural . . . . . . 11 2.2. Emulador de Space Invaders ................... 14 2.3. Ejemplo de máquina de estados y decisiones . . . . . . . . . . 18 3.1. Pasos en un algoritmo evolutivo . . . . . . . . . . . . . . . . . 21 3.2. Ejemplo de selección por ruleta . . . . . . . . . . . . . . . . . 23 3.3. Ejemplo de selección estocástica . . . . . . . . . . . . . . . . . 23 3.4. Ejemplo de cruce monopunto . . . . . . . . . . . . . . . . . . 25 3.5. Ejemplo de mutación . . . . . . . . . . . . . . . . . . . . . . . 25 3.6. Crucemonopunto......................... 29 3.7. Mutación de árbol . . . . . . . . . . . . . . . . . . . . . . . . 30 3.8. Mutación de funcion . . . . . . . . . . . . . . . . . . . . . . . 31 3.9. Mutación terminal . . . . . . . . . . . . . . . . . . . . . . . . 31 3.10. Mutación por permutación . . . . . . . . . . . . . . . . . . . . 32 3.11. Ejemplo de árbol de un individuo . . . . . . . . . . . . . . . . 34 3.12. Ejemplo hormiga usando estrategia en zig zag . . . . . . . . . 35 xxi Índice de figuras xxii 4.1. Diferentes implementaciones del Grafo . . . . . . . . . . . . . 38 4.2. Adyacencia nodos . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3. Conexiones entre salas . . . . . . . . . . . . . . . . . . . . . . 43 4.4. Cortes subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.5. Unión subgrafos . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.6. Mutación de arista . . . . . . . . . . . . . . . . . . . . . . . . 49 4.7. Mutación de nodo . . . . . . . . . . . . . . . . . . . . . . . . 49 4.8. Mutación de sala . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.9. Ejemplo de mazmorra 1 . . . . . . . . . . . . . . . . . . . . . 53 4.10. Ejemplo de mazmorra 2 . . . . . . . . . . . . . . . . . . . . . 54 4.11. Visor de funciones . . . . . . . . . . . . . . . . . . . . . . . . 55 4.12. Visor de mazmorras . . . . . . . . . . . . . . . . . . . . . . . 56 4.13.Visordesalas........................... 56 5.1. Ejemploárbol........................... 62 5.2. Diagramadeflujo......................... 64 5.3. Evaluaciónmapa ......................... 66 5.4. Mapa1 .............................. 67 5.5. Mapa2 .............................. 68 5.6. Mapa3 .............................. 69 5.7. Mapa4 .............................. 69 5.8. Mapa5 .............................. 70 Índice de figuras xxiii 5.9. Ejemplo de intrones . . . . . . . . . . . . . . . . . . . . . . . 77 5.10. Visualización GUI de la parte de la IA . . . . . . . . . . . . . 78 5.11. Árboles de patrulla y ataque . . . . . . . . . . . . . . . . . . . 79 5.12. Gráfica de evaluación . . . . . . . . . . . . . . . . . . . . . . . 80 5.13. Gráfica de evaluación sin elitismo . . . . . . . . . . . . . . . . 81 5.14. Ejemplo de estrategia defensiva . . . . . . . . . . . . . . . . . 82 5.15. Ejemplo de estrategia típica rogue-like . . . . . . . . . . . . . 84 6.1. Ventana de parametrización del framework . . . . . . . . . . . 88 7.1. Pantalla de inicio . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.2. Ejemplo de una sala de la mazmorra . . . . . . . . . . . . . . 91 7.3. Ejemplo de otra sala de la mazmorra . . . . . . . . . . . . . . 91 7.4. Ejemplo de sala con la llave . . . . . . . . . . . . . . . . . . . 92 7.5. Ejemplo de sala con el portal de fin . . . . . . . . . . . . . . . 92 7.6. Ejemplodepausa......................... 93 Índice de Tablas 4.1. Costes implementaciones Grafo . . . . . . . . . . . . . . . . . 39 4.2. Lista de adyacencia nodos . . . . . . . . . . . . . . . . . . . . 40 5.1. Lista de parámetros IA . . . . . . . . . . . . . . . . . . . . . 75 xxiv Capítulo 1 Introducción Lo último que uno sabe es por dónde empezar. Blaise Pascal, Matemático y filósofo francés. 1.1. Motivación A la hora de crear un videojuego, la mayoría de contenidos se generan de forma manual. Los escenarios, el comportamiento de los elementos controlados por el ordenador o la historia acostumbran a ser fijos. La distribución de los elementos de un mismo escenario, el comportamiento de un mismo enemigo o el argumento es siempre igual aunque se juegue varias veces. En los últimos años han comenzado a utilizarse técnicas de generación automática de contenidos en la programación de videojuegos. Particularmente, nosotros vamos a diferenciar entre las técnicas utilizadas para la generación de escenarios y las utilizadas para la IA de los enemigos. Destaca la Generación Procedural como método de generación automática de contenido en un videojuego, basada en el uso de algoritmos. Estos contenidos pueden ser desde los escenarios hasta otros más complejos como las armas o los objetos que se pueden encontrar. En los últimos años, está extendiéndose su uso sobre todo en la generación automática de escenarios. Ejemplos de esto último pueden encontrarse en videojuegos como No 1 1.6. Structure 8 Chapter 3. Evolution programming and genetic programming In this chapter the main concepts of genetic programming are detailed. Chapter 4. Dungeon generation techniques In this chapter we explain deeper the techniques used for the dungeon genetic generation algorithms. Chapter 5. Artificial intelligence generation techniques In this chapter we explain the procedure and tests que have to do in order to develop the AI. Chapter 6. Framework In this chapter we detail the framework we have developed using SFML which we used for testing the AIs. This framework can be extended for other types of genetic program problems. Chapter 7. Video game In this chapter we explain the final video game developed with this techniques. Chapter 8. Individual work In this chapter it is detailed the individual work each one of us has done during this project. 1.6. Structure 9 Chapter 9. Conclusions and future work In this chapter our final conclusions are exposed as well as the possibilities of expanding it. Tools In this chapter we describe briefly the tools we have used for developing this project. Bibliography Finally, we enumerate all the bibliographic references we have taken while we have worked on this project. This bibliography includes books, articles, web pages and other papers. Capítulo 2 Trabajo relacionado Me gusta y me fascina el trabajo. Podría estar sentado horas y horas mirando a otros cómo trabajan. Jerome K. Jerome, Humorista inglés. Para analizar el estado del arte de este proyecto, tenemos que tener en cuenta 3 aspectos fundamentales: La generación procedural de contenido para videojuegos. La generación de contenido para videojuegos mediante algoritmos evolutivos. Las diferentes implementaciones de IAs existentes. 2.1. Generación Procedural Generación procedural es el método de creación de contenidos a través de algoritmos, en oposición a un método de creación manual, y se aplica tanto en simulaciones gráficas por computadora como en videojuegos, instalaciones, programación y en música. Los fractales son un ejemplo de animación mediante generación procedural: funciones matemáticas gráficas repetidas hasta el infinito. El sonido digital también se puede generar 10 2.1. Generación Procedural 11 de forma procedural, un uso que se ha desarrollado mucho para la música electrónica. En videojuegos e instalaciones la generación procedural se utiliza en función de que el contenido se genere en la computadora que los contiene, en tiempo real, y no de manera previa y renderizado en paquetes gráficos predefinidos. Se utiliza principalmente para la generación de ambientes y mapas, aunque también se aplica para IA y jugabilidad. Se utiliza para generar de manera rápida y detallada espacios infinitos y patrones de singularidad en objetos, simulaciones y personajes. También se utiliza para la creación de sistemas de partículas para agua, fuego y gases; o para generar un sinfín de actores digitales únicos y diferentes como reemplazo de extras. Sin embargo, no se suele utilizar para el contenido final, el cual en general se muestra ya preestablecido. En (Gamasutra, 2014) se muestra una técnica para generar mazmorras aleatorias. Los pasos para ello son: Figura 2.1: Escenario creado mediante Generación Procedural Generar una serie de salas con una determinada anchura y altura y colocarlas aleatoriamente dentro de un círculo. 2.2. Técnicas Evolutivas 12 Separar las diferentes salas aplicando físicas de colisión, hasta que no se superpongan. Después, para escoger qué salas son las principales, se tendrán en cuenta aquellas que estén por encima de 1.25 en el ratio ancho/alto. Tomar los puntos medios de las salas principales y aplicarles el Procedimiento de Delaunay (Departamento de Matemática Aplicada, 2015) para obtener un grafo a partir de los triángulos obtenidos. A partir del grafo, se debe obtener el árbol de expansión mínimo (Algorithms y more, 2012). Esto hará que todas las habitaciones principales sean accesibles, pero que no estén conectadas directamente. Finalmente, se añaden los pasillos a la mazmorra. Si los nodos están cerca horizontalmente, se añade una línea horizontal. Lo mismo para los nodos cercanos verticalmente. Si no es así, se añaden dos líneas que formen una L. 2.2. Técnicas Evolutivas Existen proyectos que, mediante gramáticas evolutivas, generan historias de fondo que aportan consistencia a la experiencia de juego, con la intención de evitar que éstas deban ser ideadas por desarrolladores de forma manual (García-Ortega y García-Sanchez, 2014). Existen herramientas que permiten utilizar algoritmos genéticos para generar mazmorras en base a unos parámetros de diseño (Font, Izquierdo, Manrique y Togelius, 2016), que tienen que venir definidos previamente. En este sentido cabe reseñar el ejemplo explicado en (Togelius, Preuss, Beume, Wessing, Hagelbäck, Yannakakis y Grappiolo, 2013), que cuenta cómo se pueden desarrollar funciones heurísticas que miden propiedades de los mapas y comprueban si afectan a la experiencia de juego. Se diseñaron dos representaciones diferentes de mapas, una para un juego de estrategia genérico y otro para el videojuego Starcraft. Mediante este método se puede automatizar completamente la generación de mapas o como herramienta de apoyo para diseñadores humanos. Otro ejemplo más es el referido en (Pérez, Togelius, Samothrakis, Rohlfshagen y Lucas, 2013) que analiza 3 subcomponentes diferentes en el proceso de generación de mapas y propone soluciones a todos ellos. Los mapas 2.2. Técnicas Evolutivas 13 se representan mediante 2 conceptos distintos, la geometría y la disposición del contenido. La geometría se lleva a cabo tanto en el exterior como en el interior conectando segmentos de mapas pre-hechos para formar mapas más grandes y completos. La disposición del contenido a través del mapa se determina mediante el uso de características de la geometría como el uso de una Red de Producción de Patrones de Composición. Por último están las preferencias del jugador para diseño del contenido, que se capturan y se utilizan en un marco de sistema recomendador. Todas las soluciones se combinan y se prueban en el videojuego de acción y disparos Angry Bots (Unity, 2011) y se evalúan en un experimento a gran escala. Existe un precedente de uso de AGs para evolucionar el comportamiento de los bots -enemigos jugadores controlados por el ordenadoren un videojuego más o menos actual, concretamente el Unreal Tournament 2004 (Bullen y Katchabaw, 2004).Los resultados demostraron una mejora considerable en el rendimiento de los bots evolucionados, con respecto al grupo de control. En otra ocasión se usó programación genética para la evolución de estrategias defensivas. En (Jackson, 2005) se utiliza la programación genética para evolucionar estrategias en un simple juego que emula los invasores del espacio 2.2. Figura 2.2: Emulador de Space Invaders 2.2. Técnicas Evolutivas 14 Para la función de evaluación se realizaron un conjunto de pruebas. En cada una, el defensor se colocaba en la parte inferior del mapa, mientras que los oponentes se colocaban en cualquiera de las filas superiores, desplazándose inicialmente en una dirección elegida al azar. Después, irían descendiendo de izquierda a derecha, bajando cuando llegasen a los límites laterales del tablero y lanzando bombas de vez en cuando. Se utilizaron los operadores genéticos más comunes. Se demostró que mediante programación genética es posible desarrollar estrategias de defensa para hacer frente a juegos de una determinada dificultad. Esas estrategias incorporan muchos de los aspectos de la evasión, la búsqueda y la conducta de orientación que se encuentran en jugadores humanos. Se define un conjunto de elementos terminales: T={IZQUIERDA, DERECHA, F UEGO, DISTY, DISTX} y un conjunto de funciones: O={IF, EQ, P ROGN2, P ROGN3} Después de un proceso evolutivo se obtienen soluciones representadas de la siguiente forma: (IF (EQ(DISTYDISTX)) (P ROGN3(F UEGOIZQUIERDADISTX)) (P ROGN2(IZQUIERDAIZQUIERDA))) El significado de esa expresión es el siguiente: Si la distancia en Y es igual que la distancia en X, se ejecuta P ROGN3(F UEGO IZQUIERDA DISTX), que disparará, avanzará a la izquierda y calculará la distancia horizontal hasta el defensor. 2.3. Inteligencia Artificial 15 Si no es igual, se ejecuta P ROGN2(IZQUIERDA IZQUIERDA), que avanzará dos casillas hacia la izquierda. Por otro lado, combinando el uso de algoritmos genéticos con Grafos tenemos el problema del coloreamiento mínimo de un grafo (Universidad de Oviedo, 1997). Se han de utilizar el menor número de colores cumpliéndose la restricción siguiente: Dos nodos adyacentes no pueden tener el mismo color. Se trata de un problema NP-completo. No hay un método que asegure que se va a obtener el coloreamiento óptimo para todos los tipos de grafos que se presenten. Esto se debe a que con sólo añadir alguna arista o nodo a un grafo dado, la solución cambia radicalmente. En este problema, un individuo es una permutación de todos los nodos del grafo. La población de individuos se selecciona mediante el método de la Ruleta. Dada la facilidad para evaluar si hay que añadir un color extra o no, los individuos suelen ser bastante buenos. Dada una permutación de nodos de un grafo, hay que colorear dicho grafo recorriendo en orden los nodos, asignándoles a cada uno el primer color que puede tener cumpliendo las restricciones. La función de Fitness busca obtener el mínimo número de colores necesarios para el coloreamiento completo del grafo. Para la reproducción de los individuos se puede utilizar cruce monopunto, mientras que la mutación se puede cambiar de orden dos nodos del individuo. 2.3. Inteligencia Artificial En un videojuego, se define la inteligencia artificial -IAcomo la simulación de inteligencia -comportamiento, modo de actuar, etc.- de los PNJs y que normalmente incluirá algo relacionado con los siguientes aspectos: Conseguir comportamientos muy básicos en los PNJs -coger un elemento, golpear, etcMoverse a través de unos escenarios en los que pueden aparecer obstáculos. Tomar decisiones para saber qué acciones realizar y en qué orden. 2.3. Inteligencia Artificial 16 Hay diversas maneras de implementación de estas IAs (Alcalá): Algoritmos minimax: se utiliza normalmente en juegos de tablero como el Ajedrez o las damas. Está basado en la prueba de todas las posibilidades de jugada de cada jugador. Se puede optimizar utilizando la poda alfa-beta. Algoritmos de búsqueda de camino (Dijkstra, A*). Búsqueda del camino más corto para llegar de un punto A a otro punto B. A* es una combinación de recorridos de tipo primero en anchura con primero en profundidad y garantiza encontrar siempre el camino óptimo. Dijkstra, por su parte, determina en un grafo valorado el camino más corto para llegar desde un vértice a todos los demás del grafo. Agentes inteligentes: se aplica cuando los PNJs perciben mediante sensores la existencia de algún elemento extraño en el entorno -pared, esquina donde hay que girar, un enemigoy actúa consecuentemente -dándose la vuelta, girando, pasando a modo ataquecon la mejor acción posible, gracias a unos actuadores que le indican cómo debe hacerlo. Dos tipos: •Reactivo: actúa promovido por un cambio en el entorno (Guardián de algún tesoro). •Proactivo: decide actuar antes de que se produzcan los sucesos (Jefe final de un juego). Máquinas de estados finitos: entidad abstracta que está formada por diferentes estados y las transiciones que se producen entre ellos. Estas transiciones están producidas por cambios que se van produciendo en el entorno. Según el estado en se encuentre, se pueden llevar a cabo una serie de acciones. Redes neuronales: están inspiradas en el comportamiento de las neuronas y conexiones del cerebro humano, tratando de crear programas capaces de solucionar problemas difíciles, actuando como haría un humano. Necesitan entrenamiento con muchos ejemplos. Algoritmos evolutivos y Programación genética: Son sistemas muy robustos que resuelven problemas de optimización, donde los individuos más capaces son los que finalmente sobreviven, tras aplicarles una serie de transformaciones. 2.4. Nuestra aportación 17 2.4. Nuestra aportación Nuestro proyecto pretende analizar el rendimiento de los AGs, y determinar si es viable usarlos como mecanismo de generación automática de elementos de un juego sin necesidad de un diseño previo, así como estudiar la calidad de los elementos generados y la dificultad que puede conllevar establecer unos buenos parámetros para estos algoritmos. En la parte de generación de los mapas hemos optado por representar cada individuo mediante un grafo que representa el esqueleto de nuestra mazmorra. Se aplica un algoritmo evolutivo para transformar una de las CCs del grafo hasta obtener una mazmorra satisfactoria. Dada la pequeña cantidad de proyectos y documentación en relación a la generación automática de IAs en videojuegos, nuestro proyecto trata de hacer un análisis sobre la posibilidad de aplicar técnicas evolutivas en este aspecto. De forma análoga al proyecto MADE (García-Ortega y García-Sanchez, 2014), intentaremos automatizar los procesos de desarrollo de elementos principales de un videojuego, centrándonos en analizar aspectos clave, como la calidad de los elementos generados y el tiempo que conlleva generarlos. En este sentido, hay que tener en cuenta la generación de 2 árboles diferentes (patrulla y ataque) y las transiciones entre estados de uno y otro árbol, siendo en cierta manera cada uno de los estados un árbol diferente (exploración y ataque, como comentábamos antes) 2.3. Figura 2.3: Ejemplo de máquina de estados y decisiones 3.1. Computación evolutiva 24 Figura 3.4: Ejemplo de cruce monopunto 3.1.3.3. Operadores de mutación Los operadores de mutación que se utilizarán en este proyecto serán explicados en cada una de las secciones siguientes, porque serán diferentes según se trate de la parte de generación de mazmorras o de la IA 3.5. Figura 3.5: Ejemplo de mutación 3.2. Programación genética 25 3.1.4. Función de Fitness En computación evolutiva, el concepto de Fitness se asocia a la capacidad que tiene un individuo de sobrevivir y reproducirse. Para evaluar esa capacidad se asigna un valor a cada individuo que determinará su aptitud. Lo que se pretende con esto es que, con el paso de las generaciones, sean los individuos con mejor Fitness los que sobrevivan. 3.1.5. Mejoras en el algoritmo evolutivo 3.1.5.1. Elitismo Se selecciona, en un pequeño porcentaje, a los mejores individuos de cada generación, permitiéndoles pasar intactos a la generación siguiente. 3.1.5.2. Contractividad Proceso utilizado en los AGs que consiste en, si en una generación los individuos no mejoran lo suficiente, no se tiene en cuenta. Este proceso se hace un número finito de veces y, si en ese tiempo no se ha mejorado, se detiene el algoritmo, ya que podemos suponer que la mejora ha alcanzado su punto de convergencia. 3.2. Programación genética La programación genética es una técnica evolutiva en la cual los individuos representan expresiones codificadas en forma de árbol. John Koza es considerado el padre de la programación genética (Koza, 1992). Él definió un AG de la siguiente manera: “Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural 3.2. Programación genética 26 una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud.” 3.2.1. Representación Cada individuo de la población se representa en forma de árbol con las siguientes características: Los nodos internos del árbol representan las funciones, que son las operaciones que se llevan a cabo. Estas operaciones pueden ser condicionales o la ejecución de otras operaciones en secuencia. Las hojas del árbol representan símbolos terminales, que son las acciones que se pueden ejecutar cuando indiquen las operaciones. Estos elementos terminales pueden ser del tipo avanzar, girar o disparar. Estos árboles representan expresiones que combinan elementos terminales y no terminales Para llevar a cabo un problema de programación genética se deben seguir estos pasos: Identificar los elementos terminales, es decir, los elementos por los cuales el árbol no se seguirá expandiendo. Identificar bien las funciones que vamos a necesitar y el número de elementos en los que aplicará (aridad). Reconocer la función de adaptación que vamos a necesitar. Establecer los parámetros del algoritmo. Determinar bajo qué criterios consideraremos que deberá terminar la ejecución del algoritmo. 3.2. Programación genética 27 3.2.2. Métodos de inicialización Existen varios métodos para inicializar los individuos de la población cuando el genotipo de los individuos es un árbol. Creciente: Puede haber cualquier tipo de nodo en cualquier profundidad sin superar la profundidad máxima. Completa: Se fija una profundidad máxima del árbol y se van generando nodos no terminales hasta que se alcanza la profundidad máxima momento en el que solo se seleccionan nodos terminales. Ramped & half: Se genera la mitad de la población con el método completo, es decir, profundidad máxima y la otra mitad con el método creciente. En la mitad de la población que se genera con el método de inicialización creciente constan de una profundidad máxima y mínima. L & L (método propio): Para este método se escoge una profundidad mínima y una máxima. Hasta la mínima se usa el método de inicialización completa y una vez se ha alcanzado la profundidad mínima, desde esa hasta la máxima, el método creciente. Decidimos implementar este método porque es un método híbrido y favorece una población variada en tamaños. 3.2.3. Operadores Al igual que en la computación evolutiva general, los operadores que se usan en programación genética son los de selección, cruce y mutación. Particularmente, hemos utilizado los siguientes: 3.2.3.1. Operadores de selección Selección por ruleta: a cada individuo se le asigna una parte proporcional en base a su aptitud y a un número aleatorio calculado para cada individuo. La suma de todas las aptitudes debe ser 1. Selección estocástica: similar a la selección por ruleta, con la diferencia de que se genera un sólo número aleatorio para toda la población. 3.2. Programación genética 28 Selección por ranking: se ordena a los individuos en orden decreciente según su Fitness. En base a esa ordenación, se le otorga un valor a cada uno que será lo que determine su elección o no. Selección por torneo: se hace competir a los individuos, según su Fitness y un factor aleatorio. En base al resultado obtenido, los mejores tendrán más posibilidades de ser elegidos. 3.2.3.2. Operadores de cruce 1. Cruce simple: se seleccionan dos nodos distintos de la raíz en dos árboles. Se cortan por esos puntos y se intercambian los subárboles como se indica en 3.6. endenumerate Figura 3.6: Cruce monopunto 3.2.3.3. Operadores de mutación a)Mutación de árbol: se selecciona un nodo y se sustituye por un subárbol generado aleatoriamente. Ver 3.7. b)Mutación de función: se selecciona un nodo que represente un operador de función y se sustituye por otro que corresponda a 3.2. Programación genética 29 otra función con la misma aridad, es decir, que tenga el mismo número de hijos. Ver 3.8. c)Mutación de terminal: se selecciona un nodo que represente un terminal y se sustituye por otro. Ver 3.9. d)Mutación combinada: se elige aleatoriamente qué tipo de mutación de las tres anteriores se va a utilizar y se aplica. e)Mutación por permutación: consiste en intercambiar los hijos de un padre. Esta mutación decidimos no introducirla ya que, después de varias pruebas con las mencionadas anteriormente, constatamos que no iba a suponer ninguna mejora. Ver 3.10. Figura 3.7: Mutación de árbol 3.2. Programación genética 30 Figura 3.8: Mutación de funcion Figura 3.9: Mutación terminal 3.2. Programación genética 31 Figura 3.10: Mutación por permutación 3.2.3.4. Función de evaluación -FitnessLa función de fitness calcula la aptitud de un individuo en base al resultado con que éste resuelve el problema. Se tienen que evaluar las operaciones que figuran en su árbol y compararlas con los valores óptimos. Se deberá calcular su aptitud dependiendo de si el óptimo es un valor concreto, o si el problema debe maximizar o minimizar. 3.2.4. Mejoras en el algoritmo evolutivo 3.2.4.1. Control del bloating Cuando el genotipo de los individuos se basa en una estructura de datos que puede expandirse de forma infinita, como por ejemplo un árbol, se limita su crecimiento para evitar individuos excesivamente grandes. Cuando los individuos crecen en exceso, sin que ello suponga una mejora significativa del fitness, se utilizan muchas técnicas para controlar ese crecimiento: a) Penalizar a los individuos muy grandes en la función de fitness. 3.2. Programación genética 32 b) Establecer límites al tamaño de los individuos. c) Evaluar a varios individuos y, en caso de aptitud similar, escoger a los más pequeños. d) Evitar cruces que produzcan hijos peores que los padres. Algunos de los métodos de control de bloating son Penalización bien fundamentada o Tarpeian. 3.2.4.2. Intrones Debido a la representación en forma de árbol de los individuos, en ocasiones pueden aparecer ramas con expresiones redundantes. Estas expresiones provocan que los individuos contengan información irrelevante que puede ser eliminada o sustituida por expresiones más simples. Un caso típico en programación genética son aquellos nodos de decisión -equivalente a una sentencia if then elseen la que ambas ramas conducen a ejecutar las mismas acciones. Este tipo de expresiones redundantes se denominan intrones. La detección de intrones depende siempre del problema concreto que se pretende resolver, ya que es un problema asociado directamente a la semántica y el contexto de los individuos. Las mismas expresiones pueden ser consideradas intrones para un problema concreto y no serlo para otro. 3.2.5. Ejemplos Un ejemplo para ilustrar lo que es la programación genética es el problema de “la hormiga artificial sobre el rastro de Santa Fe” (Araujo y Cervigón, 2009) (Koza, 1992). Hay que diseñar una hormiga artificial que sea capaz de encontrar toda la comida situada en un tablero de 32x32 casillas, empezando desde la casilla situada en la esquina superior izquierda. Hacen falta operaciones que permitan avanzar, girar en ambas direcciones o comer. Por tanto, se pueden utilizar las siguientes funciones y los siguientes terminales: TERMINALES = Avanza, Derecha, Izquierda; donde Avanza hace que la hormiga avance una casilla en la dirección en que esté mirando en ese momento, y Derecha e Izquierda giran 90oen la dirección correspondiente. 3.2. Programación genética 33 FUNCIONES = SIC(a, b), PROGN2(a, b), PROGN3(a, b, c); donde SIC(a, b) ejecuta la orden asi detecta comida delante y b en otro caso, y ambos PROGN evalúan sus argumentos en orden devolviendo el último de ellos. Un posible individuo y el correspondiente árbol que lo representa sería: P ROGN3(Derecha, P ROGN2(Avanza, Avanza), P ROGN2(Izquierda, Avanza)) En la figura 3.11 puede verse el árbol de este individuo. Figura 3.11: Ejemplo de árbol de un individuo Para medir la aptitud de los individuos en este problema se puede utilizar la cantidad de comida consumida por la hormiga en un intervalo de tiempo determinado. Se considera que cada operación de avance o giro consume una unidad de tiempo. Para probar a los distintos individuos se propuso un modelo de rastro llamado “rastro de Santa Fe” y tiene un rastro irregular, porque hay algunos huecos de una o dos posiciones que también pueden estar en las esquinas. En la figura 3.12 se muestra un ejemplo de ejecución (en negro) sobre dicho rastro en el cual se ve que la hormiga ha seguido una estrategia de tipo zig zag. 4.2. Generación de mazmorras mediante algoritmos genéticos 40 cofres y demás elementos decorativos. Esto se llevaría a cabo tras haber generado un grafo suficientemente bueno. Sin embargo, nos presentaban un problema fundamental para el correcto funcionamiento del AG, la función de evaluación, esto es, ¿cuán bueno es un grafo? Debido a la complejidad de la implementación, tuvimos que descartar la idea inicial de que la función de evaluación la realizara una red neuronal previamente entrenada con ejemplos a mano. Optamos entonces por crear una función de fitness que tuviese un funcionamiento similar, evaluando cada grafo en función de diversos aspectos clave, cada uno de ellos con un peso que podríamos variar hasta dar con una ponderación adecuada. Ahora bien, ¿cuáles son estos aspectos clave? Ésta era la siguiente pregunta a responder. En primer lugar, nos dimos cuenta de que debido a la aleatoriedad de los grafos, éstos podrían tener varias CCs diferentes, e igual una de ellas era suficiente para nosotros como mazmorra completa. Así pues, la primera decisión que tomamos fue que la nota o “medida de calidad” de un grafo completo sería la mejor nota de cualquiera de sus CCs. Quedaba entonces por determinar los aspectos clave para evaluar las CCs. El objetivo era generar una mazmorra que, sin ser excesivamente grande, resultase divertida. Para este punto, decidimos que la mazmorra tuviese ciertas salas clave, en concreto, una sala inicial, de la que parte el jugador, una sala final, a la que debe llegar, y una sala con una llave, que permitirá al jugador pasar al siguiente nivel desde la sala final. De esta forma, se proporciona un objetivo al jugador para explorar la mazmorra. Durante dicha exploración, el jugador debería encontrarse obstáculos que superar (enemigos) y recompensas por haber explorado (cofres). Conseguimos esto sencillamente generando para cada sala un número aleatorio de estos dos elementos. Sin embargo, este enfoque presentaba unos problemas que tuvimos que resolver y se explicarán más adelante. Tras un profundo análisis, consideramos que había 5 puntos importantes que eran interesantes para nuestros mapas o mazmorras. La distancia entre las salas clave: si las tres salas clave están demasiado juntas, el jugador no tendrá la necesidad de explorar la mazmorra. El tamaño de la mazmorra: si la mazmorra es muy pequeña resultaría aburrida; por el contrario, si es demasiado grande, podría resultar injugable. 4.2. Generación de mazmorras mediante algoritmos genéticos 41 La conexión entre salas: si las salas están demasiado interconectadas, al jugador le cuesta mucho más crear un mapa mental de la mazmorra. La dispersión de enemigos y cofres: al ser situados de forma aleatoria, podría resultar que en una zona de la mazmorra se acumulasen muchos enemigos o cofres. El tamaño de las salas: se favorece que las salas tengan una forma rectangular (apaisada), de manera que representarlas en una pantalla sea más estético. Este parámetro es el menos relevante. 4.2.4. Evaluación de las mazmorras: Detalle A continuación explicamos cómo valoramos cada uno de esos aspectos. 4.2.4.1. Distancia entre salas clave El recorrido natural del jugador debería ser ir desde la sala inicial hasta la que contenga la llave, y luego encontrar la sala final para pasar al siguiente nivel. Por este motivo, decidimos maximizar la distancia (en salas o nodos) desde el origen hasta la sala de la llave y desde la sala de la llave hasta la sala final. Para el cálculo de la distancia, realizamos un recorrido en anchura (BFS) sobre el grafo. Para que una CC pueda puntuar en este aspecto, es necesario que contenga las tres salas clave. Favorecer mazmorras que solo tuviesen dos de ellas podría desembocar en individuos a los que les faltase una de las salas clave, lo cual no es permisible. DistanciaSalasClave =distancia(SalaInicio, SalaLlave)+ +distancia(SalaLlave, SalaF in) 4.2.4.2. Tamaño de la mazmorra El tamaño de la mazmorra no es más que el número de salas que tiene la CC. Determinar si este era un aspecto que debíamos maximizar o minimizar no fue sencillo. Si maximizamos, corríamos el riesgo de generar mazmorras demasiado grandes y si minimizamos, sucedería lo contrario. Decidimos que lo mejor sería minimizar este aspecto, y en combinación con la distancia entre salas clave, se produciría un “tira y afloja” en el que un aspecto favorecería mazmorras con muchas salas, 4.2. Generación de mazmorras mediante algoritmos genéticos 42 mientras que el otro potenciaría aquellas más pequeñas. Si estos dos parámetros se ajustaban correctamente, podríamos generar mazmorras con un número adecuado de salas (entre 15 y 30, según nuestro criterio). 4.2.4.3. Conexión entre salas Para evitar mazmorras demasiado complejas debíamos minimizar la interconexión entre salas. A priori puede parecer que minimizar este aspecto conllevaría favorecer aquellas mazmorras que tuviesen pocas salas, pero al valorar la distancia entre salas clave como algo positivo lo que este factor favorece es la generación de mazmorras con varias salas interconectadas, pero de forma mínima 4.3. Figura 4.3: Conexiones entre salas La forma de minimizar la interconexión es penalizar aquellas CCs en donde las salas tengan demasiadas entradas. En otras palabras, se pretende minimizar el grado de los nodos del grafo. MediaGrado = n P i=1 grado(i) n Donde nes el número de salas que tiene la CC y grado(i) es el número de aristas que tiene la sala i. 4.2. Generación de mazmorras mediante algoritmos genéticos 43 4.2.4.4. Dispersión de enemigos y cofres Este parámetro sin duda debía ser maximizado ya que lo que se buscaba era que estos elementos del juego estuviesen muy repartidos. Para un elemento del juego, por ejemplo cofres, el parámetro de dispersión se establece como la distancia media (en salas) que separa a cada cofre del resto. Esta distancia se calcula para cada cofre de la CC y luego se realiza la media total. Más formalmente: Dispersion(e) = ne P i=1 ne P k=1 distancia(i,k) n−1 n Donde ees un elemento del juego (enemigos o cofres) y nees la cantidad de dicho elemento en la CC. La función distancia(i, k) devuelve la distancia en salas entre el elemento iy el elemento k, si ambos están dentro de la misma sala la función vale 0. 4.2.4.5. Tamańo de las salas Para favorecer las salas de forma apaisada, se debía maximizar el ratio entre ancho y alto de las salas. Para ello, se calcula la media de ancho y alto de todas las salas de la CC. Luego se calcula el ratio, simplemente dividiendo estos dos valores. Por último, se le resta 1. Si el ratio entre ancho y alto de una CC es menor que 1, implica que, de media, sus salas son más altas que anchas, luego este parámetro será negativo y penalizará en la función de fitness. De forma contraria, si el ratio es mayor que 1, el valor sumará. Si es igual a 1, es decir, salas normalmente cuadradas, el parámetro no penaliza, pero tampoco suma al fitness. RatioSalas =mediaAncho mediaAlto −1 4.2.4.6. La función de fitness La función que determinaría entonces cuán buena es una mazmorra sería la que sigue: F itness =Maximizado −Minimizado Maximizado =DistanciaSalasClave +Dispersion(cofres)+ 4.2. Generación de mazmorras mediante algoritmos genéticos 44 +Dispersion(enemigos) + RatioSalas Minimizado =NumeroSalas ∗0,4 + MediaGrado Multiplicamos por 0.4 el número de salas de la CC para que evitar que se penalicen de más las mazmorras grandes, ya que tras algunas pruebas, restar el número directamente provocaba que las mazmorras resultantes fueran demasiado pequeñas. 4.2.5. Operadores del Algoritmo Genético Ya hemos determinado cuál es la estructura de los individuos dentro del AG, así como la forma de evaluar cada uno de ellos. Falta entonces explicar otro de los aspectos fundamentales de la programación evolutiva: los operadores de selección, cruce y mutación. Como ya se ha explicado anteriormente, variando entre diferentes métodos se modifica la forma en la que una población de individuos evoluciona. En concreto, nosotros decidimos implementar y probar las posibles combinaciones de los siguientes métodos. 4.2.5.1. Métodos de selección Con distintos operadores de selección, se determina qué individuos pasarán a la fase de cruce, es decir, se eligen los individuos que podrían ser progenitores de nuevos individuos que conformarán la siguiente generación. Puede parecer lógico optar por un método de selección que siempre elige a los mejores individuos de cada generación, sin embargo, al hacer esto se puede estar reduciendo significativamente el espacio de soluciones posibles que el AE pueda alcanzar. En ocasiones puede suceder que la combinación entre un buen individuo y otro no tan bueno ocasione la creación de un nuevo individuo que supere al mejor individuo obtenido. Distintos métodos de selección afectan de forma diferente a las poblaciones que se obtienen. Un método de selección que favorezca mucho a los mejores individuos provoca un aumento en la presión selectiva y a su vez se puede producir una evolución en avalancha o una convergencia prematura a causa de la falta de diversidad. La presión selectiva se define como la aptitud máxima entre la aptitud media de una población. Si la presión selectiva es muy alta, se pueden producir superindividuos que reducen el espacio de búsqueda del problema, si es muy baja, es 4.2. Generación de mazmorras mediante algoritmos genéticos 45 indicativo de una falta de diversidad en la población. Lo ideal, es que la presión selectiva sea baja durante las primeras generaciones, y vaya aumentando conforme los individuos evolucionan. Dicho esto, los operadores probados en la generación de mapas han sido: Selección por Ruleta: los individuos son seleccionados de forma proporcional a su aptitud. En un segmento de longitud 1, se divide de forma que a los individuos mejor adaptados les corresponde mayor porcentaje. Selección Estocástica: Mediante este método un individuo puede ser seleccionado múltiples veces, así como no ser seleccionado ninguna. Selección por Torneo: Se seleccionan individuos en grupos de 3 y se van escogiendo los que mejor adaptación tengan, hasta completar la población. Selección por Ranking: Se ordena en orden decreciente a los individuos según su fitness o adaptación. 4.2.5.2. Métodos de cruce En el caso particular de los grafos, es difícil aplicar operadores de cruce complejos que realmente aporten algo nuevo en la generación de nuevos individuos. Por el momento, hemos probado con: Cruce monopunto: se elige un número aleatorio entre 1 y N-2, siendo N el número total de nodos del grafo. Esto genera dos subgrafos diferentes que serán combinados con los subgrafos del otro progenitor. 4.2. Generación de mazmorras mediante algoritmos genéticos 46 Figura 4.4: Cortes subgrafos Como se ve en la figura 4.4, los puntos de corte de los progenitores pueden ser distintos. Al cortar, se generan dos subgrafos, que serán idénticos al grafo original, pero del cual se ha eliminado una parte de los nodos, y las aristas que conectan con dichos nodos. Estos subgrafos se generan siguiendo el orden de los índices. Los mayores del índice de corte serán un subgrafo y los menores, otro. Una vez obtenidos estos subgrafos, se combinan los subgrafos obtenidos de A, con los obtenidos de B, consiguiendo de esta forma nuevos individuos. 4.2. Generación de mazmorras mediante algoritmos genéticos 47 Figura 4.5: Unión subgrafos Sin embargo, no es suficiente con unir los subgrafos de A y B; es necesario que entre estos subgrafos se hagan nuevas conexiones, sino se perderían aristas en cada cruce, consiguiendo eventualmente grafos totalmente inconexos. Para evitarlo, una vez unidos los subgrafos en uno solo, se elige un conjunto pequeño de las posibles aristas entre los nodos del subgrafo A y los de B y se añaden al nuevo grafo. Una vez se han añadido estas aristas aleatorias, se reescriben los índices para que el rango sea de nuevo de 0 a N-1 4.5. Cruce multipunto: el cruce multipunto se basa en varios cortes monopunto. Se eligen varios puntos de corte, y se combinan los diferentes subgrafos de A y B para conseguir los nuevos individuos. 4.2. Generación de mazmorras mediante algoritmos genéticos 48 4.2.5.3. Métodos de mutación De manera eventual e intentando imitar el fenómeno de la mutación aleatoria que sucede de forma natural, algunos individuos pueden modificar su estructura interna sin necesidad de combinarlo con otros. Éste es el operador de mutación. Hasta el momento, tenemos cuatro implementaciones de mutación para los grafos: Mutación de arista: se añade o se borra (50 % - 50 %) una arista aleatoria 4.6. Figura 4.6: Mutación de arista Mutación de nodo 4.7: se añade o se borra (50 % - 50 %) un nodo aleatorio. Figura 4.7: Mutación de nodo Mutación de sala: Se mueve de sitio una de las salas clave (inicio, llave o fin) de un nodo a otro 4.8. 4.2. Generación de mazmorras mediante algoritmos genéticos 49 Figura 4.8: Mutación de sala Mutación combinada: una mutación que combina las 3 anteriores como una sola. 4.2.6. La implementación en detalle Una vez vistos los conceptos teóricos del cromosoma, es necesario explicar cómo será internamente un individuo del AG en lenguaje C++. Para empezar, hemos decidido abstraer el concepto de Grafo del concepto Cromosoma. En lugar de que el Cromosoma en sí contenga los elementos propios de un grafo, hemos optado por encapsular el Grafo dentro del Cromosoma. Aun así, el Cromosoma mantiene las operaciones propias de un individuo: función de evaluación, control del bloating, guarda parámetros de adaptación, acumulada, etc. La función de evaluación se basa en realidad en pedir toda la información necesaria al Grafo que compone su genotipo, y realizar los cálculos en base a ella. Por su parte, el Grafo está construido según lo explicado anteriormente, con algunos pequeños detalles. Se mantiene una tabla hash donde se asocia un identificador de nodo unsigned int con su información asociada (tamaño de sala, node enemigos) Por otro lado, otra tabla hash 4.3. Interfaz de usuario 56 son colocados de forma aleatoria, pues su posición no está indicada ni es relevante en está fase del desarrollo. De esta forma, con una GUI sencilla podíamos ver toda la información de una ejecución completa del AG. Capítulo 5 Técnicas para la generación de la inteligencia artificial Las tres leyes de la robótica son: 1. Un robot no puede dañar a un ser humano ni, por inacción, permitir que un ser humano sufra daño. 2. Un robot debe obedecer las órdenes dadas por los seres humanos excepto cuando tales órdenes entren en conflicto con la Primera Ley. 3. Un robot debe proteger su propia existencia hasta donde esta protección no entre en conflicto con la Primera o Segunda Ley. Isaac Asimov, Bioquímico y escritor estadounidense. 5.1. Idea inicial Para la parte relativa a la inteligencia artificial se pensó inicialmente en utilizar gramáticas evolutivas. Después de un profundo estudio y un análisis de las ventajas y desventajas, decidimos decantarnos por la programación genética. Las razón principal es que al utilizar programación genética trabajamos directamente con una codificación de los individuos en forma de árbol. Esto es importante ya que facilita 57 5.2. Decisiones de implementación 58 mucho la adaptación al videojuego y separa lo máximo posible la implementación y uso del AE con la inclusión de la IA en el videojuego. Por tanto, nuestro algoritmo para la IA se basa en la evolución de árboles que representan las distintas decisiones que toman nuestros PNJs. Una vez habíamos decidido la tecnología, planteamos cómo íbamos a generar estas IAs para el videojuego. Decidimos que para cada PNJ íbamos a tener dos árboles: uno representa el árbol correspondiente al estado Patrulla, que consiste en que los PNJs se mueven por la sala intentando encontrar al jugador y el otro representa el árbol correspondiente al estado Ataque, en el cual los PNJs, una vez han encontrado al jugador, intentan acabar con él. De esta forma el enfoque utiliza programación genética con árboles diferentes dentro de cada estado de una máquina de estados. Es importante destacar que las IAs, a diferencia de las mazmorras, no se crean en tiempo de ejecución. Estas IAs se generan previamente y se añaden al videojuego. En nuestro caso concreto, se genera un número de IAs y en la ejecución del juego se asignan de forma aleatoria a cada PNJ. Esto nos facilitó el proceso ya que no debíamos preocuparnos por la eficiencia en tiempo. Lo que nos preocupaba únicamente era que las IAs fueran lo más realistas y divertidas posibles dentro de las limitaciones que teníamos. 5.2. Decisiones de implementación Una vez elegida la técnica y representación para soportar la IA, lo primero que tuvimos que decidir eran las operaciones o acciones a realizar por nuestros PNJs. Las IAs debían ser capaces de realizar acciones básicas, como moverse, girar o atacar, en función de decisiones que dependerían de su estado dentro del mapa. Con estas directrices, las acciones serían nodos hoja en el árbol, mientras que las decisiones serían nodos intermedios, que, en base a la condición que representen, determinarían cuál o cuáles de sus hijos deben ser ejecutados. La gramática del árbol se divide entonces entre una serie de operaciones terminales y otras operaciones de función. Las reglas son sencillas. Como forman un árbol, las operaciones de función hacen las veces de nodos no hoja y las operaciones de terminales hacen de nodos hoja. Las operaciones de función pueden tener dos o más hijos. Por el contrario, las operaciones terminales no pueden tener ningún hijo, ya que 5.2. Decisiones de implementación 59 son hoja. A continuación enumeramos todas las operaciones originales distinguiendo su tipo y explicando lo que implican en el juego. Las operaciones representadas con elementos terminales (nodos hoja) son: Avanzar: el PNJ avanza una casilla en la dirección en la que mira. Girar Izquierda: el PNJ gira 90oa la izquierda. Girar Derecha: el PNJ gira 90oa la derecha. Cambiar Estado: el PNJ cambia del árbol de Patrulla al de Ataque. Esta operación solo puede estar en el árbol de Patrulla. Bloquear N: el PNJ bloquea ataques en la dirección que mira durante Nticks del juego. Esta operación solo puede estar en el árbol de Ataque. Atacar: el PNJ ataca en la dirección que mira. Esta operación solo puede estar en el árbol de Ataque. Retroceder: el PNJ retrocede en la dirección contraria a la que mira manteniendo su orientación fija. Esta operación solo puede estar en el árbol de Ataque. Las operaciones correspondientes a funciones son: ProgN2: encadena dos operaciones. ProgN3: encadena tres operaciones. Si jugador: si hay un jugador está en la casilla adyacente al PNJ y en la dirección que mira, ejecuta la primera acción y en caso contrario ejecuta la segunda. Este terminal solo puede estar en el árbol de Patrulla. Si bloqueado: si delante hay una casilla bloqueada (un borde, un muro, ) realiza una acción, si no otra. Si jugador en rango: si el jugador está en rango de ataque, realiza una acción, si no, otra. Si jugador detectado: si el jugador está en rango de detección, realiza una acción, si no, otra. 5.2. Decisiones de implementación 60 Estas funciones toman la forma de un if-then-else, de tal forma que si se cumple la condición realizamos la operación del nodo derecho y si no, la del izquierdo. Después de muchas pruebas, como se detalla más adelante en el punto 5.3.5, decidimos que necesitábamos cambiar algunos de los nodos del árbol de ataque. Los nuevos nodos función del árbol de ataque quedaron en esto: ProgN2: encadena dos operaciones. ProgN3: encadena tres operaciones. Si bloqueado: si delante hay una casilla bloqueada (un borde, un muro) realiza una acción, si no otra. Si jugador en rango: si el jugador está en rango de ataque, realiza una acción, si no, otra. Vida IA: en función de la cantidad de vida del PNJ, realiza una acción u otra. Vida Jugador: en función de la cantidad de vida del jugador, realiza una acción u otra. Los nuevos nodos terminales quedaron así: Bloquear N: el PNJ bloquea ataques en la dirección que mira durante N ticks del juego. Atacar: el PNJ ataca en la dirección que mira. Acercar: el PNJ se acerca al jugador utilizando el algoritmo A*. Esto lo permitimos ya que decidimos que una vez el árbol de patrulla detecta al jugador, se conoce siempre la posición de este. Alejar: el PNJ retrocede en la dirección contraria a la que mira manteniendo su orientación fija Curar: durante cuatro turnos el PNJ no realizará ninguna acción y, una vez se hayan terminado, gana un punto de vida hasta el máximo. Un ejemplo de programa en formato de árbol sería el indicado en la figura 5.1. 5.3. Función de evaluación 61 Figura 5.1: Ejemplo árbol Y así sería el ejemplo de este mismo árbol como instrucciones: P ROGN2(SIBLOQ(GiraD, Avanza), SIJUGADOR(CambiaEstado, Avanza)) Estas operaciones las decidimos mantener en un Enumerado. Posteriormente, elaboramos una clase Nodo que representa una operación dentro del árbol de decisión de la IA. Esta clase Nodo contiene a su vez un hash map para poder acceder de forma constante al número de nodos hijos que puede tener una operación en el árbol. Para evitar que los árboles se volvieran demasiado largos, implementamos una función de control del bloating. En este caso concreto el control del bloating consiste en, una vez el árbol ha superado una profundidad máxima, podarlo y transformar todos los nodos situados en el nivel inferior en nodos terminales u hojas. 5.3. Función de evaluación La función de evaluación de las IAs ha sido, sin duda, la parte más desafiante de este proyecto. Nos hemos frustrado en ocasiones y realizado multitud de pruebas, como se destaca en las siguientes páginas. Comenzó siendo una suma de valores ponderados y ha acabado siendo algo más parecido a lo que utilizamos en las mazmorras, una suma de elementos a maximizar, sustrayendo de estos elementos que consideramos malos y que por tanto deberían ser minimizados. El principal problema ha sido el tiempo de ejecución que rondaba unas doce horas. 5.3. Función de evaluación 62 Eso nos ha dificultado mucho la posibilidad de realizar más pruebas y nos frenó bastante durante las primeras aproximaciones hasta que encontramos la solución. 5.3.1. Introducción La función de evaluación nos planteó una serie de preguntas a contestar que no eran sencillas. Teníamos varias dificultades añadidas de las cuales no hemos encontrado mucha información sobre el tema. En el tema de los videojuegos, como hemos podido leer en el estado del arte, sí que hay muchos estudios y técnicas desarrolladas para generar IAs que jueguen a videojuegos, desde juegos simples como el Space Invaders hasta más complejos como el Street Fighter (Capcom, 1987). La ventaja que tienen esos juegos sobre el nuestro es que son IAs que se van a enfrentar a otras IAs y los mapas son siempre conocidos o irrelevantes. Sin embargo, nuestra IA teóricamente debe enfrentarse a un humano que no tiene por qué seguir una estrategia siquiera similar. Además los mapas son aleatorios puesto que se generan en cada ejecución del juego. Nuestro objetivo es intentar conseguir unas IAs buenas para un videojuego de forma automática. Esto es importante ya que las IAs no deben ganar siempre. Deben parecer inteligentes - podría ser más óptimo avanzar pegando espadazos a diestro y siniestro, pero no parecería muy natural - y tienen que ser divertidas, ya que, si te ganan siempre, el juego perdería su componente principal que es divertir al jugador. 5.3.2. Primera aproximación Para conseguir una IA versátil decidimos crear una serie de mapas de prueba (6) y lanzar varias pruebas sobre cada uno de los mapas. Para cada prueba variamos la posición tanto del jugador como del PNJ. Para simular un jugador humano decidimos que era mejor que realizara actos aleatorios y no crearle nosotros un patrón de conducta o un árbol de decisión con el objetivo de evitar que nuestro algoritmo nos genere PNJs que sólo sepan jugar contra un tipo concreto de estrategia. De esta forma intentamos introducir el mayor grado de aleatoriedad a nuestro jugador con el objetivo de obtener un árbol de decisión capaz de enfrentarse a diferentes situaciones. Es por tanto una estrategia reactiva con la que se decide el movimiento o acción posible a partir del estado de juego actual, pero no tienen en cuenta las decisiones tomadas previamente. 5.3. Función de evaluación 63 También pensamos que lo mejor sería dividir este AE en dos árboles simulando dos estados de una máquina de estados. Estos estados serían Patrulla yAtaque. En el primero, el algoritmo se centra en premiar el mayor número de superficie observada y el tiempo que tarda el PNJ en encontrar al jugador. En el árbol de Ataque, se parte de la premisa de que sabemos la posición del jugador -o la casilla inmediatamente anterior-. Esta función de evaluación premia el atacar el mayor número de veces al jugador y recibir el menor número de golpes, siendo este último menos importante; el enemigo siempre preferirá morir él y el jugador a que escapen ambos. Para evaluar un individuo, calculamos la media de puntuaciones obtenida en cada uno de los mapas de prueba. Para cada mapa de prueba el individuo tiene un número de turnos para demostrar su nivel adaptación. En esta primera aproximación el individuo disponía de 100 turnos por mapa, siguiendo el diagrama de flujo indicado en la figura 5.2. Figura 5.2: Diagrama de flujo Una vez el individuo ha terminado de evaluarse en este mapa, se guardan unos valores que determinan lo bueno que es. Estos valores eran: 5.3. Función de evaluación 64 El número de casillas exploradas Turnos en el árbol de patrulla Golpes intentados Golpes recibidos Daño al jugador De estos valores, nos interesaba maximizar el número de casillas exploradas, el número de golpes intentados y el daño al jugador. Por el contrario, queríamos minimizar el número de turnos en patrulla y los golpes recibidos por el PNJ. Como la función de evaluación queríamos que estuviese entre cero y uno, generamos un array con los valores óptimos para cada elemento a considerar. Estos óptimos eran: [DimensionDelMapa, 0, 20, 0, 3] Y una vez teníamos un valor entre cero y uno para cada elemento, pasamos a ponderarlo para conseguir un único valor que nos indicaría el fitness. Los pesos eran los siguientes: [0.3, 0.2, 0.05, 0.1, 0.35] Una vez se ha realizado el proceso como se muestra en la figura 5.3 se calcula la media de todos los mapas, la cual nos daría la evaluación final del individuo. 5.3. Función de evaluación 65 Figura 5.3: Evaluación mapa 5.3.3. Segunda aproximación Después de esta nueva aproximación, decidimos modificar la función de evaluación para evitar el minimizar valores ya que siempre puntuaban al máximo si el individuo no hacía nada. Por ejemplo, si te quedas quieto, el jugador probablemente no irá a por ti y no recibirás heridas, o, si tu árbol de patrulla es simplemente cambiar al de ataque, los turnos eran mínimos, lo cual no nos parecía coherente. Finalmente decidimos que el árbol de patrulla iba a estar determinado por el tamaño del área explorada y el árbol de ataque por el número de golpes efectuados con éxito (aunque el jugador bloquee el golpe), el número de golpes bloqueados y el número de heridas infligidas al jugador. La simulación se lanza sobre seis mapas. En el primero sólo se coloca al jugador en una posición y es vacío. En los demás, están rellenos como se muestran en las figuras 5.4, 5.5, 5.6, 5.7 y 5.8 y se lanzan cinco veces distintas, colocando cada vez al jugador en una de las casillas marcadas. Como se puede apreciar en las imágenes, el objetivo era crear una serie de salas diferentes para que el individuo, al ser colocado de forma aleatoria en cada una de las evaluaciones, se enfrente a diferentes situaciones y ver cómo de bueno es ese árbol de decisión con salas dispares. 5.3. Función de evaluación 72 +Curaciones −GolpesF allados Como se puede observar en ambos bloques, apenas hay acciones que penalizar, por esto, decidimos aplicar un factor que penalizase de forma drástica todo el conjunto de acciones realizadas si no se alcanzaban ciertos hitos. El primer factor crucial para la patrulla es que la IA encuentre al jugador. Encontrar al jugador con el árbol de patrulla implica que se tiene que dar una secuencia de dos acciones. Primero, la IA debe haber ejecutado la acción SiDetectado y haber tomado la rama de Sí, lo que implica que en ese turno, el jugador está delante de la IA y esta lo ha visto. La segunda acción necesaria es que, tras haber detectado al jugador, las decisiones que tome la IA durante ese turno lleven a ejecutar un nodo CambiaEstado. A está secuencia de acciones lo denominamos el factor de patrulla, que tomará el valor 1 si se ha realizado y 0 en caso contrario. Si una IA no realiza estas dos acciones combinadas, puntuará 0. El segundo factor es el número de heridas que la IA ha conseguido infringir al jugador. Esto implica que una IA que no consigue herir al jugador también puntúe 0. Sin embargo, una IA que mate al jugador -conseguir herirlo 3 vecesmultiplicará por 3 su fitness. Por último, se tuvieron en cuenta dos factores análogos que evitaban la propagación de individuos demasiado pasivos que no se mueven. Los factores AndarAtaque y AndarPatrulla tomarán valor 0 si la IA no se ha movido en ataque o en patrulla respectivamente, y 1 en caso contrario. Esto provoca que IAs que no se muevan en ambos estados puntuen 0. F actorF inal =F actorAtaque ∗F actorP atrulla∗ ∗AndarAtaque ∗AndarP atrulla La conclusión es que un individuo debe realizar todas estas acciones para poder puntuar. Después de mucha investigación hemos concluido que esta función de fitness debe ser muy estricta para conseguir que los individuos hagan lo que tienen que hacer y una vez lo han hecho, se les puntúe acorde a la calidad de las acciones realizadas. Por ello, consideramos una condición necesaria aplicar elitismo en la evolución. El elitismo evita que se pierdan aquellos individuos con árboles que cumplen todos los hitos. Sin embargo, el elitismo por sí mismo no es suficiente para conseguir individuos que superen este corte tan estricto. Es condición indispensable que exista variedad en la población, lo que nos obligó a utilizar 5.3. Función de evaluación 73 grandes tamaños de población, de 50 o 100 individuos mínimo. El hecho de utilizar selección por torneo también ha afectado positivamente al control de la diversidad mediante análisis de la presión selectiva. Como se mencionó en la introducción de este apartado, la función de evaluación de la IAs obligaba a probar cada individuo sobre varios mapas, lo que consumía la mayor parte de nuestro tiempo a la hora de realizar pruebas. Conseguimos reducir de forma significativa -hasta 120 veces menosel tiempo que se tardaba en evaluar la población realizando dos simples mejoras. La primera y más básica es utilizar un conjunto de individuos marcados. Cada vez que un individuo sufre una modificación, bien sea por haber sido cruzado, mutado o se le haya cortado alguna rama debido al control de bloating, en lugar de ser evaluado, se marca para su posterior evaluación. Así, si un individuo pasa por un cruce y luego es mutado, sólo se evalúa una vez. De la misma forma, un individuo que atraviesa una generación sin sufrir cambios, no necesita ser reevaluado. Las segunda y más importante optimización es la paralelización de la evaluación del fitness. En lugar de probar a un individuo sobre cada uno de los mapas de forma secuencial, se ejecuta cada simulación de cada mapa por separado y se obtiene el fitness en cada uno de ellos. Con esto, la función de fitness demora como mucho el tiempo que tarda en simularse el más lento de los mapas, en lugar de la suma de todos ellos. Finalmente, la función de evaluación queda como sigue: Evaluacion =F actorF inal∗(P untuacionP atrulla+P untuacionAtaque) Estos parámetros significan lo siguiente: Para conseguir que la función de evaluación haya obtenido resultados importantes, además del cambio de algunas operaciones fueron fundamentales varias optimizaciones que realizamos. El principal problema que nos encontramos en la nueva función de evaluación es que debía ser muy exigente para evitar evolucionar individuos con malas estrategias. Debido a esto, consideramos una condición necesaria aplicar elitismo en la evolución. Debido a esta función restrictiva, también nos dimos cuenta que era necesario que la población fuera suficientemente grande ya que, sin variedad, no funcionaba bien. La necesidad de tener poblaciones grandes acrecentaba aún más nuestro problema de tiempos, que estaba del orden de los quince o veinte minutos por generación para poblaciones de 100 individuos. Por esta 5.4. Operadores 74 Variable Significado FactorAtaque Número de heridas infligidas FactorPatrulla 1 si ocurre siDetectado - CambiaEstado, 0 si no AndarAtaque 1 si anda en ataque, 0 en caso contrario AndarPatrulla 1 si anda en patrulla, 0 en caso contrario CasillasAndadasPatrulla Número de casillas andadas en patrulla CasillasExploradasPatrulla Número de casillas exploradas en patrulla Golpes Número de impactos sobre el jugador Bloqueos Número de ataques bloqueados Curaciones Número de curaciones con éxito GolpesFallados Número de ataques no impactados Tabla 5.1: Lista de parámetros IA razón decidimos paralelizar la función de evaluación de manera que para un individuo se evalúan simultáneamente todos los mapas. 5.4. Operadores 5.4.1. Inicializador de la población Para inicializar la población utilizamos el método LL. Nos decantamos por este ya que es el más completo de los tres. Con este método obtenemos una mezcla de árboles irregulares de diferentes profundidades creadas por el método creciente y árboles más regulares creados por el método completo. 5.4.2. Métodos de selección De los métodos de selección explicados anteriormente, hemos decidido utilizar la selección por Torneo ya que favorece la supervivencia de los mejores individuos. Otra de las razones de utilizar el método de torneo es que es el único de los implementados que tiene en cuenta el fitness de manera directa. todo esto es necesario porque, como hemos explicado anteriormente, la función de fitness es muy exigente. 5.4. Operadores 75 5.4.3. Operador de cruce El operador de cruce que hemos utilizado aquí es el monopunto o simple, ya que no consideramos que uno más complejo fuera a favorecer la mejoría de los individuos. 5.4.4. Operadores de mutación De los operadores de mutación y después de múltiples pruebas, decidimos decantarnos por la combinada. Observamos que al ser la que más variedad permitía, más favorecía a conseguir las acciones obligatorias que nuestros individuos deben llegar a realizar. 5.4.5. Eliminación de intrones La eliminación de intrones pretende corregir aquellos árboles en los que se encuentran expresiones redundantes. En programación genética, la existencia de intrones depende de la semántica que tenga el árbol y su contexto. En nuestro caso, muchos de los intrones se pueden detectar y simplificar surgen del hecho de que los árboles deben ser ejecutados durante un turno. Esto implica, por ejemplo, que si un nodo SiBloqueado devuelve NO, mientras la IA no ejecute una acción de giro o retroceso, seguirá bloqueada y el resto de nodos SiBloqueado también seguirán por la rama del NO. A continuación se explican cuáles han sido los intrones que hemos considerado: a) Nodo PROGN2 1) Acciones contrarias: Si un nodo PROGN2 tiene como hijos dos acciones que realizan acciones contrarias, como por ejemplo GiraIzquierda y GiraDerecha, se sustituye el nodo PROGN2 por un terminal aleatorio. 2) Primer hijo CambiarEstado: Dada la naturaleza del nodo CambiarEstado, que provoca el cambio instantáneo al árbol de ataque, el resto de hijos de PROGN2 no se ejecutarán, así que sustituimos el nodo PROGN2 directamente por un nodo CambiarEstado. b) Nodo PROGN3 1) Primer hijo CambiarEstado: Caso análogo al de PROGN2, sustituimos el nodo PROGN3 directamente por un nodo CambiarEstado. 5.5. Paralelización del fitness 76 c) Nodo tipo condicional 1) Ambos hijos terminales iguales: Si ambas opciones de un nodo de decisión son la misma, siendo estas acciones terminales, semánticamente dicho nodo es equivalente a cualquiera de sus hijos. 2) Hijo equivalente: Si un hijo de un nodo condicional es a su vez el mismo condicional, dicho hijo puede ser sustituido por la rama condicional en la que él mismo se encuentra. Figura 5.9: Ejemplo de intrones 5.5. Paralelización del fitness Para conseguir las mejoras que hemos mencionado y alcanzar la función de fitness final, fue fundamental paralelizar la evaluación de los individuos. Para poder hacer esto, decidimos crear un thread por cada mapa de evaluación, de tal forma que se podían evaluar todos los mapas y se tardaba en evaluar todos lo que tardase el mapa más largo. 5.6. Interfaz de usuario 77 5.6. Interfaz de usuario La GUI para la sección de IA es similar a la utilizada en la generación de mazmorras. Mantenemos el visor de gráficas para poder ver la evolución de los individuos. Para poder visualizar de forma clara cómo se comportan los individuos, decidimos crear un visor de la evaluación de los individuos. Con él podemos ver en tiempo real qué movimientos está llevando a cabo el individuo, así como las casillas que ha cubierto o la dirección hacia la que mira 5.10. Con el objetivo de facilitar también la visualización de los árboles de patrulla y ataque, creamos una ventana adicional 5.11 en la que se muestran los árboles del individuo que está siendo evaluado. Todas estas ventanas decidimos complementarlas con la posibilidad de manipular los atributos del AG, creando un framework usando SFML. Esto se detalla en el siguiente capítulo. Figura 5.10: Visualización GUI de la parte de la IA 5.7. Resultados 78 Figura 5.11: Árboles de patrulla y ataque 5.7. Resultados Como se puede apreciar en la imagen 5.12, la gráfica presenta una mejora clara generación tras generación, tanto en la tendencia de la media como en el mejor individuo. El mejor individuo de la generación -Mejor gen en la leyenday el mejor individuo absoluto coinciden perfectamente ya que para las IAs siempre activamos elitismo, por lo tanto el mejor nunca se descarta. 5.7. Resultados 79 Figura 5.12: Gráfica de evaluación Sin embargo, si no ponemos elitismo, se aprecia en la figura 5.13 que van variando el mejor y el de la mejor generación. Se obtienen individuos con menor fitness, tanto el mejor como el resto de la población. Por estas razones podemos concluir que el elitismo es un parámetro fundamental en la generación de las IAs. 5.7. Resultados 80 Figura 5.13: Gráfica de evaluación sin elitismo En la imagen 5.14 podemos apreciar una estrategia algo defensiva ya que tiende a bloquear y curarse bastante. Sin embargo, la que vimos anteriormente, en la figura 5.11 es una mucho más ofensiva. 5.7. Resultados 81 Figura 5.14: Ejemplo de estrategia defensiva Capítulo 7 Videojuego Mi trabajo es un juego, un juego muy serio. Maurits Cornelis Escher, Artista neerlandés. Aquí explicamos el desarrollo del videojuego como prueba de concepto. Hemos desarrollado un juego estilo rogue-like muy simple e introducido tanto la generación de mazmorras como las inteligencias articiales generadas. Este tipo de videojuegos consiste en explorar una mazmorra, eliminando enemigos y consiguiendo mejoras que te ayuden en el viaje. El juego que hemos implementado carece de historia y es estilo arcade. El jugador debe intentar superar el máximo número de niveles posibles en un intento. Los controles son muy sencillos. Con las teclas W-A-S-D nos movemos y con las teclas K y L atacamos y bloqueamos. Para abrir los cofres basta con atacarlos. Para moverse entre salas o recoger la llave, es suficiente con pasar por encima. Las mazmorras se generan cada vez que el jugador juega una partida o avanza una fase. Por el contrario las IAs son ?jas ya que los tiempos de ejecución no las hacían viables para que se generen en cada partida. Además, aunque los tiempos hubiesen sido viables, no son tan consistentes como las mazmorras y es arriesgado introducir IAs sin revisarlas previamente. En nuestro videojuego, el jugador debe explorar infinitos niveles de una mazmorra. Para pasar de un nivel al siguiente, debe llegar al portal que simboliza el fin del nivel. Para poder atravesarlo deberá haber encontrado antes una llave situada en algún lugar del nivel. Durante sus aventuras, el jugador irá explorando salas en 88 7.1. Imágenes del videojuego 89 las que habrá portales para moverse, enemigos que le dificultarán su viaje y cofres para ayudarle. Conforme elimina a sus enemigos, consigue bonus de los cofres, o avanza niveles, el jugador recibe puntos. No hemos implementado ningún tipo de historia por lo que el objetivo del juego es puramente arcade. De esta forma, hemos conseguido incluir las técnicas evolutivas para la generación de mapas y de inteligencias artificiales en un juego completo. 7.1. Imágenes del videojuego Figura 7.1: Pantalla de inicio 7.1. Imágenes del videojuego 90 Figura 7.2: Ejemplo de una sala de la mazmorra Figura 7.3: Ejemplo de otra sala de la mazmorra 7.1. Imágenes del videojuego 91 Figura 7.4: Ejemplo de sala con la llave Figura 7.5: Ejemplo de sala con el portal de fin 7.1. Imágenes del videojuego 92 Figura 7.6: Ejemplo de pausa Capítulo 8 Trabajo individual Una sola flecha puede ser destruida fácilmente pero un haz de flechas es indestructible. Gengis Kan, Khaqan mongol. Aquí nos gustaría destacar que todos hemos estado implicados en el proyecto y consideramos que sin el trabajo de todos nosotros y nuestro director, esto no habría sido posible. La propuesta del TFG y los detalles de cómo hemos ido avanzando cuando han salido problemas ha sido un trabajo común del equipo. Queremos destacar también que nos hemos ayudado mutuamente en la corrección de la memoria. Por tanto, aunque tengamos que especificar el trabajo individual, nos gustaría destacar que todo este proyecto es un trabajo común. Al ser un proyecto de tamaño considerable, intentamos dividirnos lo mejor posible el trabajo acorde a nuestros fuertes. Samuel Lapuente: Al tener más conocimientos y base sobre los mecanismos utilizados en videojuegos para simular inteligencia, fui el encargado principal del desarrollo del bloque de inteligencias artificiales. Fue tarea mía la realización de las ideas y decisiones tomadas previamente -y duranteasí como el principal encargado de programarlo. Para ello utilicé el la ventana que creó mi compañero 93 94 Álvaro y decidimos posteriormente convertirla en un framework para algoritmos genéticos. Como se ha podido apreciar anteriormente, el proceso para alcanzar la función de fitness definitiva no fue rápido y llevó no sólo bastante trabajo programando sino pensando y probando. Fue, sin ninguna duda, la parte más complicada de todo el TFG. Realizamos muchas más pruebas de las que hemos citado para evitar que toda la memoria se hablara de esto. Hasta llegar a alcanzar la propuesta final, estuve investigando ya no sólo en inteligencias artificiales para los videojuegos sino también en el supuesto concreto de los rogue-like. Como se ha podido leer en la segunda aproximación de la función de fitness del capítulo de la IA, generamos unos mapas de prueba sobre los que simular el comportamiento. Yo me encargué de inventar esos mapas. La parte más complicada y crítica del trabajo han sido ambas funciones de evaluación. La función del generador de mapas o mazmorras fue complicada pero la conseguimos solventar más rápidamente. Estuve presente y aporté ideas para conseguir esta función. Como he mencionado anteriormente, la de la inteligencia artificial no fue menos. De esta fuí yo el encargado principal pero recibí mucha ayuda de Álvaro para conseguir alcanzar la función definitiva. Al ser un TFG propuesto, la idea inicial la propusimos a nuestro director Álvaro y yo. El proceso para pulir esa idea fue un trabajo del grupo hasta lograr los resultados aquí expuestos. Comenzamos sin tener una idea definida de videojuego y con la intención de intentar generar también música e historia. Posteriormente, para la proof of concept del videojuego rogue-like, aporté ideas de diseño del mismo, como por ejemplo la vista de la cámara o el diseño del mismo. Esta prueba de concepto es un videojuego muy sencillo, sin historia ni grandes personalizaciones. Me encargué de buscar las texturas del videojuego ya que no somos expertos en ello y las que creé de prueba eran bastante malas. De buscar la música del juego así como los efectos de sonido me encargué yo. De la parte de la memoria me he encargado de redactar la sección de las inteligencias artificiales y, al igual que mis compañeros, de corregir y aportar en todas las demás secciones. En cuanto a la organización del grupo, mis compañeros decidieron que ejerciera las funciones de una especie de jefe de proyecto. Me encargué de crear el repositorio de github y gestionar algún 95 problema con commits y merges que surgieron. En la parte de la organización de la memoria intenté ir asignando alguna tarea por orden de prioridad; pero no fueron ni determinantes ni muy importantes ya que mis compañeros se supieron gestionar a la perfección el tiempo. Para la parte del código no necesitamos que nadie ejerciera las funciones de un jefe de proyecto ya que intentamos que la mayor parte del proceso fuera un trabajo común, ya fuera en la puesta de ideas o en el proceso de creación. Finalmente, me encargué de acabar la maquetación en que empezó Iván antes de dejar el trabajo. Álvaro Lázaro: Dada mi experiencia previa con el lenguaje C++, fui encargado de crear el esqueleto que utilizamos para los algoritmos genéticos, así como todo lo relacionado con el apartado de generación de mazmorras, sin embargo, he de destacar que el proceso creativo ha sido fruto de una puesta en común de ideas y muchas pruebas, habitualmente fallidas, hasta dar con una implementación y resultados acordes a nuestras expectativas. Debido a que fui el miembro del grupo que más uso había hecho de la librería SFML, me encargué de realizar las GUIs tanto en la parte de generación de mapas como en la de IA, con el objetivo de generar un framework que nos permitiera realizar pruebas y observar resultados fácilmente. Por la naturaleza de los algoritmos evolutivos, son necesarias muchas pruebas antes de encontrar una combinación de parámetros óptima. Por ello, he estado involucrado en todo el proceso de pruebas de ambos bloques principales, desde el testeo de las partes más simples hasta el de las funciones de fitness. Como se ha podido leer en los apartados previos, las funciones de fitness han sido partes fundamentales en ambos bloques. He investigado sobre ellas y aportado ideas en el proceso de desarrollo de las mismas y, en ocasiones, soluciones. Al haber implementado la parte de grafos, también he sido el responsable de redactar los detalles de la implementación y el capítulo sobre la generación de mapas. En lo referente a la implementación final del juego, he realizado una breve investigación sobre el desarrollo de videojuegos en SFML, además de aportar ideas sobre la estructura general del juego. 96 Para facilitar el uso de la programación genética en lo referente a las inteligencias artificiales, tuve que desarrollar algunos componentes visuales que tuviesen la funcionalidad necesaria para poder parametrizar el algoritmo evolutivo. Esto era necesario para realizar la conversión de este bloque a un framework de trabajo con el que poder investigar, ahora y en el futuro, diferentes combinaciones de operadores genéticos. He organizado el repositorio en el cual hemos desarrollado todos los proyectos que se han mencionado, especialmente lo referente a limpieza de proyectos obsoletos. En menor medida, de forma previa a la realización de este proyecto, he recopilado información sobre generación procedural y algunas aplicaciones de algoritmos genéticos sobre videojuegos. He tomado parte en la revisión de la presente memoria, si bien me gustaría destacar que ésta ha sido una tarea compartida por todos. Iván Quiros: A lo largo de todo el desarrollo del proyecto, he sido el encargado principal de buscar trabajos previos que pudieran ayudarnos en la realización de este proyecto. La búsqueda de videojuegos en los cuales alguno de sus contenidos hayan sido generados automáticamente (generación procedural, técnicas evolutivas), la recopilación de información acerca de cómo se generan las IAs en otros videojuegos, cómo se han combinado en anteriores trabajos el uso de Grafos con programación evolutiva o la búsqueda de información previa acerca del uso de Grafos para generar los mapas de un videojuego. He sido el encargado de redactar parte de la introducción, el capítulo sobre computación evolutiva y programación genética, parte del resumen de este trabajo y lo referente al trabajo relacionado, así como -al igual que mis compañerosde la corrección de las partes que creímos necesario. También me encargué de la parte referida a la bibliografía de esta memoria, gestionando que se presentase en el formato correcto, utilizando para ello la aplicación Mendeley. Por otra parte, me encargué de la parte de la maquetación de la memoria del proyecto utilizando L A TEX. El formato fue algo que consensuamos mis compañeros, nuestro director y yo para que la presentación quedase lo mejor posible. 97 Iván comenzó con nosotros este proyecto pero antes de acabar el curso decidió que no era para él y acabo dejándolo. Nos parecía importante mencionar su trabajo antes de dejarlo y no atribuirnos un mérito que no nos corresponde. Herramientas utilizadas Si la única herramienta que tiene es un martillo, pensará que cada problema que surge es un clavo. Mark Twain, Escritor y humorista estadounidense. Visual Studio Desde el comienzo del proyecto, tuvimos claro que realizaríamos el proyecto en lenguaje C++. Pese a ser un lenguaje más complejo, tiene la ventaja de ser más eficiente y muy utilizado para la implementación de videojuegos. Además, existen gran cantidad de librerías que pueden ser incluidas de forma fácil en un proyecto. Por este motivo, decidimos utilizar Visual Studio 2013 como IDE con la que desarrollar todo el proyecto. SFML SFML es una librería desarrollada para C++, especialmente utilizada en la creación de videojuegos 2D. Permite el uso de elementos gráficos de forma sencilla y cuenta con pequeños módulos para el manejo de sonidos y conexiones de red. Con ella hemos podido realizar tanto las interfaces gráficas (pese a no estar directamente diseñada para ello), como el juego final. 104 9.8. Future work: 105 Github Para realizar el trabajo de forma colaborativa, utilizamos un repositorio privado en la plataforma GitHub, lo que nos permite llevar un control de versiones del proyecto, dividirlo en ramas en función de la fase del desarrollo y mantenernos informados de los cambios que ha introducido cada miembro del grupo. Latex L A TEX es un sistema de preparación de documentos. Está orientado a la presentación de escritos que requieran de calidad profesional. Se compone de una serie de macros que ayudan a usar el lenguaje TEX (Wikipedia, TeX). Permite,a su vez, separar el contenido del formato del documento. En este trabajo, hemos utilizado L A TEX para la maquetación de la memoria. Mendeley Mendeley es una aplicación utilizada para llevar la gestión de las referencias bibliográficas. Permite añadir documentos gestionando la propia aplicación los datos de la referencia o añadir las referencias manualmente, teniendo que meter todos los datos de la referencia. Puede utilizarse para toda clase de artículos, además de para páginas web. También permite el uso de varios formatos de bibliografía diferentes, dependiendo de lo que se quiera mostrar en la referencia. Bibliografía Y así, del mucho leer y del poco dormir, se le secó el celebro de manera que vino a perder el juicio. El Ingenioso Hidalgo de Don Quijote de la Mancha AB, M. Minecraft. 2011. Disponible en https://minecraft. net/ (último acceso, Mayo, 2017). Alcalá, J. Inteligencia artificial en videojuegos. Laboratorio de Investigación y Desarrollo en Inteligencia Artificial, Departamento de Ciencias e Ingeniería de la Computación, ???? Algorithms ymore. árbol de expansión mínima: Algoritmo de kruskal. 2012. Disponible en https://jariasf.wordpress.com/2012/04/19/ arbol-de-expansion-minima-algoritmo-de-kruskal/ (último acceso, Mayo, 2017). Araujo, L. yCervigón, C. Algoritmos evolutivos: un enfoque práctico. RA-MA S.A, 2009. Bullen, T. yKatchabaw, M. Using genetic algorithms to evolve character behaviours in modern video games problem encoding population initialization evaluation selection evolution population replacement. 2004. Capcom. Street fighter. 1987. Disponible en http://www. streetfighter.com/ (último acceso, Mayo, 2017). Corporation, T. Space invaders. 1978. Disponible en http: //www.spaceinvaders.net/ (último acceso, Mayo, 2017). 106 Bibliografía 107 EcuRed, P. Lisp. 2016. Disponible en https://www.ecured. cu/Lisp (último acceso, Mayo, 2017). Matemática Aplicada y Estadística, U. D. d. Test de turing. 2004. Disponible en http://matap.dmae.upm. es/cienciaficcion/DIVULGACION/3/TestTuring.htm (último acceso, Mayo, 2017). Font, J. M.,Izquierdo, R.,Manrique, D. yTogelius, J. Constrained level generation through grammar-based evolutionary algorithms. 2016. Gamasutra. Procedural dungeon generation algorithm. 2014. Disponible en http://www.gamasutra.com/blogs/AAdonaac/ 20150903/252889/Procedural_Dungeon_Generation_ Algorithm.php (último acceso, Mayo, 2017). Games, E. Unreal tournament. 1999. Disponible en https:// www.epicgames.com/unrealtournament/ (último acceso, Mayo, 2017). Games, H. No man’s sky. 2016. Disponible en https://www. nomanssky.com/ (último acceso, Mayo, 2017). García-Ortega, R. yGarcía-Sanchez, P. My life as a sim: evolving unique and engaging life stories using virtual worlds. ALIFE 14, 2014. Guillén Torres, B. El verdadero padre de la inteligencia artificial. 2016. Disponible en https://www.bbvaopenmind.com/ el-verdadero-padre-de-la-inteligencia-artificial/ (último acceso, Mayo, 2017). Intriago, J. Algoritmo a estrella. 2014. Disponible en https://advanceintelligence.wordpress.com/ 2014/10/07/algoritmo-a-estrella/ (último acceso, Mayo, 2017). Jackson, D. Evolving defence strategies by genetic programming. EuroGP, 2005. Koza, J. R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992. Departamento de Matemática Aplicada, U. P. d. M. Triangulación de delaunay. 2015. Disponible en http://www.dma.fi.upm.es/recursos/ aplicaciones/geometria_computacional_y_grafos/web/ Bibliografía 108 triangulaciones/delaunay.html (último acceso, Mayo, 2017). Muńoz, M. Juegos roguelike: Historia y actualidad. 2014. Disponible en http://www.fsgamer.com/ juegos-roguelike-historia-y-actualidad-20140414. html (último acceso, Mayo, 2017). Namco. Pacman. 1980. Disponible en http://pacman.com/ (último acceso, Mayo, 2017). Universidad de Oviedo, C. d. i. a. Problema del coloreamiento de un grafo. 1997. Disponible en http://www.aic. uniovi.es/ssii/Tutorial/Grafos.html (último acceso, Mayo, 2017). Pérez, D.,Togelius, J.,Samothrakis, S.,Rohlfshagen, P. yLucas, S. Automated map generation for the physical travelling salesman problem. Evolutionary Computation, IEEE Transactions on, 2013. Software, G. Borderlands. 2009. Disponible en https:// borderlandsthegame.com/ (último acceso, Mayo, 2017). Togelius, J.,Preuss, M.,Beume, N.,Wessing, S.,Hagelbäck, J.,Yannakakis, G. N. yGrappiolo, C. Controllable procedural map generation via multiobjective evolution. Genetic Programming and Evolvable Machines, 2013. Toy, M.,Wichman, G. yArnold, K. Rogue. 1980. Unity. Angry bots. 2011. Wikipedia (TeX). Entrada: “TeX”. Disponible en https://es. wikipedia.org/wiki/TeX (último acceso, Mayo, 2017).