Programmatic Strategies for Real-Time Strategy Games

Julian R. H. Mariño, Rubens O. Moraes, Tassiana C. Oliveira, Cláudio Toledo, Levi H. S. Lelis

Introduction

In the development of Artificial Intelligence (AI) for Real-Time Strategy (RTS) games, a persistent tension exists between performance and interpretability. While deep reinforcement learning models like AlphaStar achieve superhuman performance, they often operate as "black boxes" requiring immense computational resources. Conversely, hand-coded scripts are interpretable and efficient but difficult to scale and maintain.

Researchers from Brazil and Canada have proposed a middle ground: LS2 (Local Search and Language Simplifier). Presented at AAAI-21, LS2 automatically synthesizes programmatic scripts to play RTS games. These scripts are high-performing, human-readable, and computationally lightweight, offering a viable alternative for commercial game development.

The LS2 Framework

LS2 addresses the challenge of program synthesis by combining a novel language simplification technique with a self-play local search.

Lasi: The Language Simplifier

The search space for potential programs is vast. To make synthesis tractable, LS2 employs Lasi, a Language Simplifier. Lasi reduces the "vocabulary" of the Domain-Specific Language (DSL) by analyzing a "trace" of a successful game. It identifies the minimal set of commands and boolean conditions required to replicate the observed behavior, effectively treating the problem as a Set Cover Problem.

Local Search with Self-Play

Following simplification, the system utilizes a local search algorithm. Starting from a random script, it iteratively applies mutations to the code. These variants compete against the current best version in a self-play loop. If a mutation demonstrates superior performance, it replaces the current champion. The resulting scripts are written in $\mu$Language, a DSL designed for the $\mu$RTS environment.

Parse tree representation of a programmatic strategy in the DSL.

Experimental Evaluation

The system was evaluated using $\mu$RTS, a minimalist environment for AI research, across four distinct maps:

  • Standard Maps: $8 \times 8$ and $24 \times 24$.
  • Resource Wall Map: $9 \times 8$.
  • Micro-management Map: $18 \times 8$ (combat-only).

To establish a competitive baseline, the researchers conducted a user study where four professional programmers wrote scripts for these specific maps using the same DSL.

Results and Analysis

The experimental results demonstrate the efficacy of the LS2 approach across various scenarios.

Win rate comparison across different map sizes and configurations, showing LS2's performance relative to baselines and human programmers.

Key Findings:

  • Superiority of Simplification: LS2 significantly outperformed versions of the algorithm that omitted the Lasi simplification step (68.6% vs 54.7% average win rate across all maps).
  • Outperforming Human Experts: In the $8 \times 8$ and $24 \times 24$ maps, LS2-synthesized scripts achieved higher win rates than those written by professional programmers.
  • Competitive Efficiency: LS2 performed comparably to state-of-the-art search algorithms like GNS. However, unlike search-based methods, LS2's output is a readable script that executes with negligible CPU overhead during gameplay.
  • Emergent Strategies: Interestingly, LS2 occasionally synthesized scripts with seemingly redundant commands that inadvertently optimized the game's internal pathfinding—a nuance missed by human programmers.

Conclusion

LS2 represents a significant step toward automated, interpretable AI for complex games. By simplifying the language of strategy, it enables the efficient synthesis of specialized scripts that rival both human expertise and computationally intensive search algorithms. Future work may explore more advanced search techniques, such as Genetic Programming, to further navigate the simplified program space.

Summary updated

Abstract

Search-based systems have shown to be effective for planning in zero-sum games. However, search-based approaches have important disadvantages. First, the decisions of search algorithms are mostly non-interpretable, which is problematic in domains where predictability and trust are desired such as commercial games. Second, the computational complexity of search-based algorithms might limit their applicability, especially in contexts where resources are shared among other tasks such as graphic rendering. In this work we introduce a system for synthesizing programmatic strategies for a real-time strategy (RTS) game. In contrast with search algorithms, programmatic strategies are more amenable to explanations and tend to be efficient, once the program is synthesized. Our system uses a novel algorithm for simplifying domain-specific languages (DSLs) and a local search algorithm that synthesizes programs with self play. We performed a user study where we enlisted four professional programmers to develop programmatic strategies for mRTS, a minimalist RTS game. Our results show that the programs synthesized by our approach can outperform search algorithms and be competitive with programs written by the programmers.
BibTeX
@inproceedings{marino2021programmatic,
  author = {Julian R. H. Mariño and Rubens O. Moraes and Tassiana C. Oliveira and Cláudio Toledo and Levi H. S. Lelis},
  title = {{Programmatic Strategies for Real-Time Strategy Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i1.16114},
}
Figure