Download the full-sized PDF of Heuristic Search Techniques for Real-Time Strategy GamesDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Heuristic Search Techniques for Real-Time Strategy Games Open Access


Other title
artificial intelligence
heuristic search
real-time strategy games
monte-carlo tree search
Type of item
Degree grantor
University of Alberta
Author or creator
Churchill, David G
Supervisor and department
Buro, Michael (Computing Science)
Examining committee member and department
Bulitko, Vadim (Computing Science)
Muller, Martin (Computing Science)
Dick, Scott (Engineering)
Munoz-Avila, Hector (Computer Science & Engineering, Lehigh University)
Department of Computing Science

Date accepted
Graduation date
2016-06:Fall 2016
Doctor of Philosophy
Degree level
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.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 1758597
Last modified: 2016:11:16 15:03:25-07:00
Filename: thesis_pdfa.pdf
Original checksum: 4bdff2838ae6f11969fe393512229295
Activity of users you follow
User Activity Date