Logo des Repositoriums

A Multi-objective Genetic Algorithm for Build Order Optimization in StarCraft II

dc.contributor.authorKöstler, Harald
dc.contributor.authorGmeiner, Björn
dc.description.abstractThis article presents a modified version of the multi-objective genetic algorithm NSGA II in order to find optimal opening strategies in the real-time strategy game StarCraft II. Based on an event-driven simulator capable of performing an accurate estimate of in-game build-times the quality of different build lists can be judged. These build lists are used as chromosomes within the genetic algorithm. Procedural constraints e.g. given by the Tech-Tree or other game mechanisms, are implicitly encoded into them. Typical goals are to find the build list producing most units of one or more certain types up to a certain time (Rush) or to produce one unit as early as possible (Tech-Push). Here, the number of entries in a build list varies and the objective values have in contrast to the search space a very small diversity. We introduce our game simulator including its graphical user interface, the modifications necessary to fit the genetic algorithm to our problem, test our algorithm on different Tech-Pushes and Rushes for all three races, and validate it with empirical data of expert StarCraft II players.
dc.relation.ispartofKI - Künstliche Intelligenz: Vol. 27, No. 3
dc.relation.ispartofseriesKI - Künstliche Intelligenz
dc.subjectGenetic algorithm
dc.subjectMulti-objective optimization
dc.subjectNSGA II
dc.subjectStarcraft II
dc.titleA Multi-objective Genetic Algorithm for Build Order Optimization in StarCraft II
dc.typeText/Journal Article