Hierarchical Adversarial Search Applied to Real-Time Strategy Games

Authors

  • Marius Stanescu University of Alberta
  • Nicolas Barriga University of Alberta
  • Michael Buro University of Alberta

DOI:

https://doi.org/10.1609/aiide.v10i1.12714

Keywords:

Heuristic Search, Real-Time Strategy Games, Adversarial Search

Abstract

Real-Time Strategy (RTS) video games have proven to be a very challenging application area for artificial intelligence research. Existing AI solutionsare limited by vast state and action spaces and real-time constraints. Most implementations efficiently tackle various tactical or strategic sub-problems, but there is no single algorithm fast enough to be successfully applied to big problem sets (such as a complete instance of the StarCraft RTS game). This paper presents a hierarchical adversarial search framework which more closely models the human way of thinking --- much like the chain of command employed by the military. Each level implements a different abstraction --- from deciding how to win the game at the top of the hierarchy to individual unit orders at the bottom. We apply a 3-layer version of our model to SparCraft ---a StarCraft combat simulator --- and show that it outperforms state of the art algorithms such as Alpha-Beta, UCT, and Portfolio Search in large combat scenarios featuring multiple bases and up to 72 mobile units per player under real-time constraints of 40 ms per search episode.

Downloads

Published

2021-06-29

How to Cite

Stanescu, M., Barriga, N., & Buro, M. (2021). Hierarchical Adversarial Search Applied to Real-Time Strategy Games. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 10(1), 66-72. https://doi.org/10.1609/aiide.v10i1.12714