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