Data-driven Production Constrained Build-order Optimization In StarCraft

Computer games have become an important and active area in artificial intelligence(AI)research since they not only provide a suitable platform for technological evaluation but also elicit a new line of research i.e.game AI,therefore driving the AI research development.StarCraft is a well-known real-time strategy game released by Blizzard Entertainment and has engaged with AI research over years that includes strategic decision making,intelligent agent control,opponent modeling,prediction and so on.The opening build-order belongs to strategic decision making which is often required in the early stage of the StarCraft game.Given a specific build-order plan,players take actions to produce different types and numbers of units and structures,upgrade skills,search technologies or perform other actions so as to obtain a dominant position in the early phase of a game.The goal we set is to maximize the number of buildings and units in the production process and we hope to obtain different types and quantities of combat units in order to defend the base or execute other tasks.It is named as a Production Constrained Build-order Optimization Problem(PC-BO)in StarCraft,Focusing on this problem,the main works and novelties are as follows:(1)The production constraint is an uncertain constraint which is relevant to the number of units produced by players' opponents in the gameplay and other game factors.To address the challenge of formulating a precise PC-BO,we resort to a data-driven approach to the optimization problem that exploits game replay files to facilitate the unit calculation in StarCraft.The approach is motivated by widely available replay files that are uploaded by various game players in the world.The replay files record players' interactions in the gameplay e.g.the building actions,the building times,the unit production of the player and his opponents and the types of the units.(2)Solving the PC-BO problem requires evaluating a large number of build-orders and running these build-orders in StarCraft directly needs a lot of computation time.So we implement a StarCraft building simulator for evaluating the build-orders which is generated during the solving process.(3)We adopt an improved genetic algorithm called genetic simulated annealing algorithm(GASA)to solve the optimization problem with data-driven constraints.To further improve the performance of GASA,we use the game players' build-orders to participate the generation process of initial population.Experimental results show the effectiveness of this method.