Heuristic Search Techniques for Real-Time Strategy Games

• Author / Creator

  Churchill, David G

• Real-time strategy (RTS) video games are known for being one of the most complex and strategic games for humans to play. With a unique combination of strategic thinking and dexterous mouse movements, RTS games make for a very intense and exciting game-play experience. In recent years the games AI research community has been increasingly drawn to the field of RTS AI research due to its challenging sub-problems and harsh real-time computing constraints. With the rise of e-Sports and professional human RTS gaming, the games industry has become very interested in AI techniques for helping design, balance, and test such complex games. In this thesis we will introduce and motivate the main topics of RTS AI research, and identify which areas need the most improvement. We then describe the RTS AI research we have conducted, which consists of five major contributions. First, our depth-first branch and bound build-order search algorithm, which is capable of producing professional human-quality build-orders in real-time, and was the first heuristic search algorithm to be used on-line in a Starcraft AI competition setting. Second, our RTS combat simulation system: SparCraft, which contains three new algorithms for unit micromanagement (Alpha-Beta Considering Durations (ABCD), UCT Considering Durations (UCT-CD) and Portfolio Greedy Search), each outperforming the previous state-of-the-art. Third, Hierarchical Portfolio Search for games with large search spaces, which was implemented as the AI system for the online strategy game Prismata by Lunarch Studios. Fourth, UAlbertaBot: our Starcraft AI bot which won the 2013 AIIDE Starcraft AI competition. And fifth: our tournament managing software which is currently used in all three major Starcraft AI competitions.

• Subjects / Keywords

  • Monte-carlo tree search
  • Artificial intelligence
  • Starcraft
  • Real-time strategy games
  • Heuristic search

• Graduation date

  Fall 2016

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3HT2GN96

• 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.