Search, Abstractions and Learning in Real-Time Strategy Games

• Author / Creator

  Barriga Richards, Nicolas A

• Real-time strategy (RTS) games are war simulation video games in which the players perform several simultaneous tasks like gathering and spending resources, building a base, and controlling units in combat against an enemy force. RTS games have recently drawn the interest of the game AI research community, due to its interesting sub-problems and the availability of professional human players. Large state and action space make standard adversarial search techniques impractical. Sampling the action space can lead to strong tactical performance on smaller scenarios, but doesn't scale to the sizes used on commercial RTS games. Using state and/or action abstractions contributes to solid strategic decision making, but tactical performance suffers, due to the necessary simplifications introduced by the abstractions. Combining both techniques is not straightforward, due to the real-time constraints involved. We first present Puppet Search, a search framework that employs scripts as action abstractions. It produces agents with strong strategic awareness, as well as adequate tactical performance. The tactical performance comes from incorporating sub-problem solutions, such as pathfinding and build order search, into the scripts. We then split the available computation time between this strategic search and NaiveMCTS, a strong tactical search algorithm that samples the low-level action space. This second search refines the output of the first one by reassigning actions to units engaged in combat with the opponent's units. Finally, we present a deep convolutional neural network (CNN) that can accurately predict Puppet Search output in a fraction of the time, thus leaving more time available for tactical search. Experiments in StarCraft: Brood War show that Puppet Search outperforms its component scripts, while in microRTS it also surpasses other state-of-the-art agents. Further experimental results show that the combined Puppet Search/NaiveMCTS algorithm achieves higher win-rates than either of its two independent components and other state-of-the-art microRTS agents. Finally, replacing Puppet Search with a CNN shows even higher performance. To the best of our knowledge, this is the first successful application of a convolutional network to play a full RTS game on standard sized game maps, as previous work has focused on sub-problems, such as combat, or on very small maps. We propose further work to focus on partial observability and CNNs for tactical decision-making. Finally, we explore possible utilization in other game genres and potential applications on the game development process itself, such as playtesting and game balancing.

• Subjects / Keywords

  • Real-Time Strategy games
  • Abstractions
  • Heuristic Search
  • Machine Learning

• Graduation date

  Fall 2017

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3GT5FV8T

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.