Introduction
In the realm of artificial intelligence for games, the transition from classic board games like Chess or Go to Real-Time Strategy (RTS) games represents a massive leap in complexity. While Chess offers a branching factor of approximately 35, RTS games such as StarCraft or $μ$RTS present "exponential action spaces." In these environments, a player must simultaneously issue commands to dozens or hundreds of units, leading to a combinatorial explosion of possible moves. This paper, originally presented at IJCAI-20, provides a comprehensive survey and a new conceptual framework to unify the disparate algorithms designed to navigate these vast search spaces.
The Challenge of Combinatorial Action Spaces
The core difficulty in RTS planning is the sheer number of combinations. If a player controls 50 units and each unit has only 4 possible actions, the total number of joint actions is $4^{50}$—a figure that dwarfs the number of atoms in the observable universe. Standard search algorithms, such as Minimax or vanilla Monte Carlo Tree Search (MCTS), are computationally incapable of exploring even a fraction of this space within the millisecond constraints of real-time play. Consequently, AI research has focused on various forms of abstraction and pruning to find "good enough" moves efficiently.
The GEX Framework: A Unifying Perspective
The primary contribution of this work is the introduction of General Combinatorial Search for Exponential Spaces (GEX). GEX is a unifying framework that demonstrates how seemingly different algorithms are actually variations of the same underlying template. By mapping existing methods into GEX, the author shows that by simply adjusting parameters—such as the sampling policy, the opponent model, or the evaluation function—one can derive most state-of-the-art RTS planning algorithms.
Taxonomy of Search Strategies
The paper categorizes existing solutions into three main architectural buckets based on how they abstract the action space:
1. Uniform Action Abstractions
These methods rely on "scripts"—pre-defined, high-level behaviors (e.g., "Attack-Closest" or "Kite-Opponent"). Instead of searching every possible coordinate, the AI chooses between a few scripts for each unit.
- Portfolio Greedy Search (PGS): This algorithm iteratively refines the script assigned to one unit at a time, seeking to improve the overall "portfolio" of actions through local optimization.
- Stratified Strategy Selection (SSS): To further reduce complexity, SSS groups similar units together (e.g., all healthy archers) and assigns the entire group a single script.
2. Regular Action Spaces
Rather than using scripts, these methods treat action selection as a sampling problem.
- NaïveMCTS: This approach treats the joint action selection for all units as a multi-armed bandit problem. It utilizes "Naïve Sampling" to explore combinations that appear promising based on the average reward of individual unit actions, allowing for more fine-grained control than script-based methods.
3. Asymmetric Action Abstractions
- A3N: A hybrid approach that allows the search to be "regular" (fine-grained) for a small subset of important units while using restrictive scripts for the remainder of the army. This focuses computational power where it matters most.
Key Theoretical and Empirical Insights
Beyond the unification of algorithms, the paper highlights several critical insights derived from the literature:
- The Serialization Trick: Although RTS moves are simultaneous, researchers often model them as sequential (Player 1 moves, then Player 2 moves). The paper explains how this logic can be embedded within the transition function to simplify the mathematical modeling of the game without losing the essence of simultaneous play.
- The PGS Pathology and NGS: A notable finding in RTS research is that if PGS attempts to optimize both the player's and the opponent's moves simultaneously, it can perform worse than if it assumed a fixed opponent. This "pathology" led to the development of Nested-Greedy Search (NGS), which fixes the issue by nesting the optimization process.
- Discovery of Hybrid Algorithms: By placing all algorithms into the GEX matrix, the author identifies "empty cells"—combinations of techniques that have not yet been explored. For instance, while we have Stratified Greedy Search (SSS), a "Stratified NaïveMCTS" remains an open area for future implementation.
Conclusion
The GEX framework serves as both a map of the current landscape and a roadmap for the future. Empirical results across $μ$RTS and StarCraft suggest that asymmetric search (A3N) and evolved scripts are currently the most effective tools for handling exponential action spaces. However, the true value of this unifying perspective lies in its call to action: by identifying the gaps in our current algorithmic toolkit, it paves the way for the next generation of real-time strategy AI.
Summary updated