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
  • Graduation date
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • 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.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
  • Supervisor / co-supervisor and their department(s)
  • Examining committee members and their departments
    • Munoz-Avila, Hector (Computer Science & Engineering, Lehigh University)
    • Dick, Scott (Engineering)
    • Bulitko, Vadim (Computing Science)
    • Muller, Martin (Computing Science)