Análisis de estrategias de construcción en videojuegos de estrategia en tiempo real

Abstract

Los videojuegos de estrategia en tiempo real (Real-Time Strategy, RTS) presentan nuevos retos en el área de la Inteligencia Artificial (Artificial Intelligence, AI). En este escenario, los investigadores han desarrollado una amplia variedad de algoritmos y agentes inteligentes para mejorar el rendimiento actual de ciertas tareas, como la búsqueda de caminos óptimos, la micro-gestión o la exploración de los mapas. En concreto, en juegos como Starcraft: Brood War, la creación de la competición anual AIIDE del juego ha impulsado la aparición de nuevos trabajos enfocados a la aplicación de algoritmos de IA para mejorar diversos aspectos del juego. En este trabajo presentamos un agente inteligente capaz de construir en lugares óptimos dentro de la base siguiendo una cierta estrategia. En primer lugar, obtenemos un conjunto de datos que contiene gran cantidad de repeticiones de jugadores no profesionales. Después, este conjunto de datos es filtrado por las acciones por minuto de los jugadores (Actions Per Minute, APM) y clasificado según las estrategias típicas de Starcraft. Luego, se extrae información sobre los órdenes de construcción del conjunto de datos resultante. En este contexto, diseñamos un Algoritmo Genético (Genetic Algorithm, GA) para generar lugares de construcción óptimos para una estrategia. Concretamente, el GA genera individuos a partir de acciones de construcción con restricciones, que son evaluadas por una función de fitness adaptada al problema. Después, mediante una selección por torneo se seleccionan las soluciones que generarán los nuevos descendientes. El método de combinación utilizado es una combinación uniforme proporcional al fitness de la solución. A la hora de mutar, el GA toma una de las siguientes alternativas: una tasa de mutación estática, fijada en un valor concreto, o una tasa de mutación dinámica, agregando un gen a las soluciones que será la tasa de mutación. Así mismo, se emplea elitismo para conservar la calidad de las soluciones generación tras generación. Todos los parámetros del GA son ajustados para obtener soluciones óptimas. Después, las mejores soluciones son utilizadas por el agente inteligente y probadas contra la inteligencia artificial por defecto del juego. Los resultados muestran que podemos escoger mejores estrategias de construcción para ciertos mapas y razas antes de que la propia partida comience.

The Real-Time Strategy videogames (RTS) present new challenges in the Artificial Intelligence (AI) area. In this scenario, researchers have developed a wide variety of algorithms and AI agents to improve the current performance of specific tasks, such as pathfinding,micromanagement or map exploration. Concretely, in games like Starcraft: Brood War, the creation of the AIIDE Starcraft annual competition has boosted the number of research papers discussing different aspects of the game. In this work we present an AI agent capable of constructing on optimal building placements inside a base following a certain strategy. First of all, we obtain a large dataset containing multiples replays from non-profesional players. This dataset is then filtered by the actions per minute (APM) of players and classified attending to typical Starcraft strategies. The resulting dataset is later on used to extract information about building orders. In this context, we design a Genetic Algorithm (GA) to generate optimal building placements for a strategy. In particular, the GA creates individuals from constrained building actions, that are evaluated by a problem adapted fitness function. Then, a tournament selection is done to select the solutions for creating new offsprings. The crossover method is a uniform combination proportional to the fitness score.When mutating, the GA takes one of two alternatives: a static mutation rate, fixing a value, or a dynamic one, adding a mutation rate gene to the each solution. Additionaly, elitism is used to preserve quality to the next generation. Every GA parameter is adjusted to obtain optimal solutions. Afterwards, the best solutions are utilized by the AI agent and tested again the default AI of the game. Results show that we can choose better building strategies for certain maps and races before the game itself begins.