Asymmetric Action Abstractions for Planning in Real-Time Strategy Games

Rubens O. Moraes, Mario A. Nascimento, Levi H. S. LelisJAIR 2022 · DOI · OpenReview

TL;DR

Planning in Real-Time Strategy (RTS) games is notoriously difficult due to the "combinatorial explosion" of possible actions. This paper introduces Asymmetric Action Abstractions, a method that allows AI agents to focus their limited computational "attention" by searching for fine-grained strategies for a few key units while using simple scripts for the rest. The resulting algorithms, particularly A3N, significantly outperform state-of-the-art uniform search methods across various map sizes.

What Problem Does This Paper Address?

In an RTS game like StarCraft or $\mu$RTS, a player might control dozens of units simultaneously. If each unit has 10 possible actions and you control 10 units, there are $10^{10}$ possible joint actions every single frame. Standard search algorithms (like Minimax or MCTS) cannot handle this state space within the typical 100ms time limit allowed for planning.

To cope, researchers use action abstractions. Traditionally, these are "uniform": every unit is restricted to a small set of high-level scripts (e.g., "Worker Rush" or "Light Rush"). While this makes the search manageable, it’s a blunt instrument. It prevents the AI from discovering clever, micro-managed maneuvers—like pulling back a single damaged unit while the rest of the army continues to fight. The challenge is finding a middle ground between searching the "unabstracted" (too big) and "uniformly abstracted" (too simple) game trees.

Methods

The authors propose Asymmetric Action Abstractions. The core idea is to divide units into two groups:

  1. Restricted Units: These follow a set of predefined scripts (high abstraction).
  2. Unrestricted Units: The algorithm considers all legal actions for these units (no abstraction).

By keeping the number of unrestricted units small, the search remains computationally feasible while allowing for high-precision "micro" play where it matters most.

The paper introduces four new algorithms:

  • GAB (Greedy Alpha-Beta) & SAB (Stratified Alpha-Beta): These are two-step searchers. They first perform a hill-climbing search in a uniformly abstracted space. If they find a local maximum before time runs out, they "zoom in" and perform a second search (using Alpha-Beta pruning) specifically for the unrestricted units.
  • A2N & A3N: These are variants of NaïveMCTS, which uses combinatorial multi-armed bandits. A3N specifically samples actions from the asymmetrically abstracted tree, allowing the MCTS to explore fine-grained unit movements that uniform MCTS would ignore.

The authors also tested nine different selection strategies to decide which units should be unrestricted, such as "Closest to Enemy," "Lowest Hit Points," or "Farthest from Centroid."

Datasets

The algorithms were evaluated using $\mu$RTS, an open-source RTS designed for AI research.

  • Maps: 10 different maps ranging from tiny (8x8) to large (64x64).
  • Opponents: The agents were tested against a suite of state-of-the-art RTS bots, including Guided-NaïveMCTS (GNS), Adversarial HTN (AHT), and various hard-coded script bots.

Key Insights and Ideas

  • Attention as a Resource: The paper treats search effort as a finite resource. Asymmetric abstraction is essentially an "attention mechanism" for game tree search.
  • The "Micro" Advantage: The most successful selection strategy for A3N was "Farthest from Centroid" or "Closest to Enemy." This confirms that giving the AI "finer control" over units in combat or units isolated from the main group yields the highest strategic returns.
  • Bridging the Scale Gap: Unabstracted search (searching every possible move) works well on 8x8 maps but fails on 64x64. Uniformly abstracted search works on large maps but is too "dumb" for small ones. Asymmetric search is the first approach to perform competitively across all map sizes.

Key Results

  • A3N is the New Benchmark: A3N achieved the highest overall winning rate (77.4%) against all other search-based methods.
  • Outperforming Baselines: GAB and SAB consistently beat their uniform counterparts (Portfolio Greedy Search and Stratified Strategy Selection). For example, GAB won 81% of its matches against its uniform baseline, PGS.
  • Two Steps are Better Than One: The two-step approach (searching the simple space first, then the complex space) proved vital. Algorithms that tried to search the asymmetric space in a single step (like GAS and SAS) performed significantly worse.

Limitations and Future Work

  • Fixed Number of Units: The study mostly used a fixed number ($N$) of unrestricted units. In a real game, the "optimal" number of units to micro-manage might change dynamically based on the current game state.
  • Opponent Modeling: GAB and SAB assume the opponent will follow a fixed script during the second search step. This makes the agent potentially exploitable by a human or an AI that can deviate from those scripts.
  • Computational Overhead: While more efficient than unabstracted search, selecting unrestricted units and managing the two-step search adds overhead. Future work could explore using neural networks to predict which units deserve "attention" more efficiently.

Summary updated

BibTeX
@article{moraes2022asymmetric,
  author = {Rubens O. Moraes and Mario A. Nascimento and Levi H. S. Lelis},
  title = {{Asymmetric Action Abstractions for Planning in Real-Time Strategy Games}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.13769},
}

Loading related content...

Figure