Stratified Strategy Selection for Unit Control in Real-Time Strategy Games

Levi H. S. Lelis

Abstract

Controlling dozens of individual units in Real-Time Strategy (RTS) games presents a massive computational challenge due to an astronomical branching factor. This paper introduces Stratified Strategy Selection (SSS), an algorithm that reduces search complexity by grouping similar units into types and assigning them shared behavioral scripts. We further propose SSS+, an adaptive variant that uses meta-reasoning to dynamically adjust the granularity of these types based on available computation time. Evaluated in the SparCraft simulator, SSS and SSS+ significantly outperform state-of-the-art portfolio search methods in large-scale combat scenarios, achieving win rates over 90% in complex battles.

Introduction

In RTS games like StarCraft, micromanagement—the precise control of individual units—is crucial for victory but computationally prohibitive for AI. Standard search algorithms like Monte Carlo Tree Search fail to explore the vast state space within millisecond time limits. While portfolio-based approaches—searching over sets of high-level scripts—improve efficiency, they still scale poorly as unit counts increase. This work addresses the gap by introducing abstraction through unit stratification.

Methodology: Stratification and Meta-Reasoning

The core of SSS is a Type System that partitions units into groups (e.g., "wounded Dragoons"). Instead of searching for a script for every unit, SSS searches for a script for every type, reducing the search space from $O(|\Sigma|^{|U|})$ to $O(|\Sigma|^{|T|})$.

SSS+ enhances this by monitoring its own running time. If the search is too slow, it merges types to simplify the problem; if time permits, it splits types for finer control. This ensures the agent always produces a move within the game's strict time constraints. Additionally, the authors developed PGS+, an evaluation function that uses simulations to better account for non-aggressive positioning tactics like clustering.

SSS+ dynamically adjusts type system granularity to manage running time across decision points, ensuring real-time performance.

Experimental Evaluation

Experiments were conducted in the SparCraft simulator across various unit compositions and scales, ranging from 4 vs 4 to 56 vs 56. SSS and SSS+ were compared against Portfolio Greedy Search (PGS) and Portfolio Online Evolution (POE).

As shown in the win rate tables below, SSS and SSS+ consistently dominate in large-scale battles. In a complex scenario with 56 units (14 of each of 4 types), SSS+ achieved a 95% win rate against POE. In contrast, basic SSS struggled in these diverse scenarios due to fixed complexity, winning only 16% of matches when time-outs occurred. SSS+ successfully mitigated this by dynamically simplifying its type system to fit the time limit.

Win rate comparisons across various unit compositions and scales. SSS and SSS+ show significant performance gains as the number of units and types increase.

Conclusion

Stratified Strategy Selection provides a scalable solution for high-unit-count RTS combat. By leveraging group-level abstractions and time-aware meta-reasoning, SSS+ maintains high strategic quality under strict computational budgets. Future work will explore more complex physics and partial information environments.

Summary updated

Abstract

In this paper we introduce Stratified Strategy Selection (SSS), a novel search algorithm for micromanaging units in real-time strategy (RTS) games. SSS uses a type system to partition the player's units into types and assumes that units of the same type must follow the same strategy. SSS searches in the state space induced by the type system to select, from a pool of options, a strategy for each unit. Empirical results on a simulator of an RTS game shows that SSS employing either fixed or adaptive type systems is able to substantially outperform state-of-the-art search-based algorithms in combat scenarios with up to 100 units.
BibTeX
@inproceedings{lelis2017stratified,
  author = {Levi H. S. Lelis},
  title = {{Stratified Strategy Selection for Unit Control in Real-Time Strategy Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/522},
}

Loading related content...

Figure