Unit Selection Based On Fuzzy Integral And NSGA-? In StarCraft

StarCraft is a very famous real-time strategy(RTS)game exploited by Blizzard Entertainment.The artificial intelligence research around StarCraft has been conducted for many years,including strategic planning,multi-agent control,opponent modeling,and prediction.An important research problem of strategic planning is unit selection,that is,if the formation of the attack team of the enemy is known,how to choose a suitable group of units from the existing units to form one or several teams to defeat the enemy's army,thus increasing the chance of winning the whole game.The units of StarCraft are mutually check and balance,and there is a fog of war in the actual game process,players cannot see the troops sent by the enemy in advance and cannot accurately judge the enemy's attack time.Therefore,the unit selection problem in StarCraft is still a very big challenge,there is no universal algorithm that can directly solve this problem.This article considers solving the static unit selection problem in an ideal situation,when the player can see the unit composition of the enemy's offensive team.In the actual game,the number of each unit will change.If the player encounters the same enemy team multiple times,we need to select multiple winning teams to provide players with multiple choices,thereby increasing a chance to win in the end.We list the main contributions as follows:(1)We improve the order-based fuzzy integral by adding the normalized term of team size to the fuzzy integral,the normalized order-based fuzzy integral can better evaluate the relative combat effectiveness of a given team of StarCraft,and we use genetic algorithm(GA)to learn the fuzzy measure of fuzzy integral from the replay data of StarCraft;(2)We consider the unit selection problem of StarCraft as a multi-objective optimization problem(MOP)with two objectives,and design a unit selection algorithm using the normalized order-based fuzzy integral and Elitist Non-dominated Sorting Genetic Algorithm(NSGA-?).The algorithm we proposed is also the first algorithm to give a clear solution in the field of unit selection in StarCraft;(3)Experiments with SparCraft are conducted.The experimental results show that the unit selection algorithm proposed in this paper can select ordinary units in StarCraft with high accuracy,most of the armies formed by the selected units can defeat a given enemy army,and the size of the formed army does not exceed the size of the enemy team.