Resolución de laberintos en StarCraft empleando apredizaje por refuerzo

Abstract

Desde los orígenes de la informática se ha intentado dotar de mayor autonomía a los sistemas informáticos, desarrollando algoritmos capaces de aprender y adaptarse a los cambios en su entorno. En el campo de los videojuegos, esta inteligencia artificial (IA) suele quedar limitada a comportamientos previamente definidos por un diseñador, dando lugar a jugadores no humanos carentes de toda autonomía. Por otro lado, el aprendizaje automático y los algoritmos de aprendizaje por refuerzo son técnicas prometedoras que nos ofrecen la posibilidad de crear agentes que aprendan por sí mismos. Además, a pesar de que se están empezando a introducir en el desarrollo de videojuegos, aún no han sido ampliamente exploradas en este campo. En concreto, el algoritmo Q-Learning nos ofrece una buena base para desarrollar sistemas basados en este tipo de aprendizaje. En este proyecto intentaremos desarrollar una aplicación que mediante este algoritmo sea capaz de aprender a hacer ciertas actividades por sí mismo en el entorno del juego de estrategia en tiempo real (RTS, del inglés Real-Time Strategy Games) StarCraft. En concreto, lo emplearemos para la resolución de laberintos de forma autónoma, es decir, sin proporcionarle conocimiento previo al agente sobre la estructura del laberinto. Para ello iremos moviendo a una unidad del juego por un laberinto que podrá contener trampas, y mediante aprendizaje por refuerzo lograremos que dicha unidad sea capaz de encontrar la salida por sí misma. Mostraremos experimentos con distintas estrategias de aprendizaje, usando distintas recompensas, y al final explicaremos cuáles han funcionado mejor. Además desarrollaremos un framework reutilizable para este tipo de aprendizaje basado en el algoritmo Q-Learning, que emplearemos para resolver nuestro problema y podrá servir como base para futuros desarrollos.

From the beginnings of computer science it has been tried to give more autonomy to computer systems, developing algorithms able to learn and adapt themselves to the changes in their environment. In the area of videogames, this artificial intelligence (AI) is usually limited to behaviors that have been defined in advance by the designer, leading to non-player characters without autonomy. On the other hand, the machine learning and reinforcement learning algorithms are promising techniques, which give the opportunity to create agents who can learn by themselves. In addition, despite the fact that they are beginning to be introduced in the videogames development, they haven’t been widely explored in this area yet. Concretely, the Q-Learning algorithm gives us a good base to develop systems based on this learning model. With this project we will try to develop an application that, using the Q-Learning algorithm, will be able to learn several activities by itself in the environment of real-time strategy game (RTS) StarCraft. In particular, we will use it to solve maze on an autonomous way, in other words, without providing it with previous knowledge about the maze's structure. To accomplish it, we will be moving one game-unity inside a maze that may have enemies, and thanks to the reinforcement learning the game-unity will be able to find the maze's exit by itself. We will show experiments with different learning strategies, using diverse rewards, and at the end we will explain which of them worked better. Also we will develop a reusable framework for this kind of learning based on Q-Learning algorithm, which will be used to solve our problem and could be useful as a base to future developments.