Comparing heuristic search methods for finding effective real-time strategy game plans

This paper compares genetic algorithms against bit-setting hill-climbers for generating competitive plans to beat an opponent in the initial stages of real-time strategy games. Specifically, we search for build-orders that generate the right mix of entities and attack orders and compare the algorithms´ performance against optimal plans from exhaustive search. Since multiple possible global optima exist, three hand-coded opponents that follow different strategies serve to provide a baseline for plan comparisons. Our results show that while our hill-climber takes three hours to produce optimal plans against our three hard-coded baselines, it only finds these plans six percent of the time. On the other hand, genetic algorithms routinely find the best plans against our baselines but take significantly longer. This work helps game artificial intelligence designers evaluate the strengths of these types of heuristic search algorithms and serves to inform our research on improving evolutionary approaches to real-time strategy game player design.