A multi-objective genetic algorithm for simulating optimal fights in StarCraft II

摘要

The goal of this work is to develop a multi-objective genetic algorithm for simulating optimal fights between arbitrary units in the real-time strategy game StarCraft II. As there is no freely available application programming interface for controlling units in the game directly, this first requires an accurate simulation of the actual game mechanics. Next, based on the concept of artificial potential fields a general behavior model is developed which allows controlling units in an optimal way based on a number of real-valued parameters. The goal of each individual unit is to maximize their damage output while minimizing the amount of received damage. Finding parameter values that control the units of two opposing players in an optimal way with respect to these objectives can be formulated as a multi-objective continuous optimization problem. This problem is then solved by applying a genetic algorithm that optimizes the behavior of each unit of two opposing players in a competitive way. To evaluate the quality of a solution, only a finite number of solutions of the opponent can be used. Therefore, the current optima are repeatedly exchanged between both players and serve as input for the simulated encounter. By comparing the solutions of both players at the end of the optimization, it can be estimated if one of the two players has an advantage. Finally, in order to evaluate the effectiveness of the presented approach, a number of sample build orders, which correspond to the amount of units that have been produced until a certain point of time, serve as input for several optimization runs.