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