Abstract
Synthesizing programmatic strategies—AI agents whose logic is encoded in human-readable code—is a significant challenge due to the non-differentiable nature of programs and the sparsity of win/loss signals. We introduce Bilevel Synthesis (Bi-S), a framework that searches concurrently in the space of programs and game features. By using features as "stepping stones," Bi-S provides a dense guidance signal that helps search algorithms navigate the flat plateaus of the optimization landscape. Our results in MicroRTS show that Bi-S synthesized strategies significantly outperform state-of-the-art human-coded agents and existing synthesis baselines.
Introduction
In the pursuit of interpretable and powerful AI, programmatic strategies offer a compelling alternative to "black box" neural networks. However, synthesizing these programs is notoriously difficult. The search space is discrete and non-differentiable, and the standard feedback—a win or loss—is often too sparse to guide optimization. A minor code change might not immediately change the game outcome, leaving search algorithms "lost" on vast plateaus where every direction seems equally unproductive. While some approaches use strong pre-existing "oracles" for guidance, these are not always available, and a "representation gap" often prevents the program language from accurately mimicking complex oracle behavior.
Methodology: Bilevel Synthesis (Bi-S)
The proposed Bilevel Synthesis (Bi-S) framework addresses the search plateau problem by decomposing the task into two interconnected layers:
- Feature Space Search: This upper layer searches for "target features"—quantifiable game states like "build 10 workers and 2 barracks." It employs a Combinatorial Multi-Armed Bandit (CMAB) approach, specifically Naive Sampling, to identify feature combinations likely to lead to victory.
- Program Space Search: The lower layer uses Simulated Annealing (SA) to find a program within a Domain-Specific Language (DSL) that achieves these target features.
The critical innovation lies in how these layers interact. When the program search encounters two different programs that both result in a loss, it breaks the tie by preferring the program that gets closer to the target features. This provides a dense, informative signal even when the primary win/loss utility is silent. Additionally, the authors introduced Bi-S+, which utilizes Transfer Learning by maintaining a library of programs discovered on smaller maps to initialize searches on larger, more complex maps.
Experimental Evaluation
The framework was evaluated in MicroRTS, a competitive real-time strategy environment. Testing was conducted across three maps of increasing scale: 24x24, 32x32, and 64x64. Bi-S was compared against a "Competition Set" of top human-coded agents (COAC, Mayari) and state-of-the-art synthesis baselines like Sketch-SA.
Results
The results demonstrate the effectiveness of the bilevel approach. In round-robin tournaments against 22 other agents, variants of Bi-S combined with Iterated Best Response (IBR) and Fictitious Play (FP) secured the top positions on the leaderboard.
Key findings include:
- Superior Performance: Synthesized strategies achieved a total win rate of 0.89, surpassing the previous top human-coded agents, COAC (0.77) and Mayari (0.74).
- Search Efficiency: Bi-S reached higher win rates faster than standard Simulated Annealing, proving that feature-based guidance effectively navigates search plateaus.
- Knowledge Transfer: Bi-S+ showed that programmatic knowledge is modular; strategies for resource management on small maps provide excellent starting points for complex strategies on larger maps.
Conclusion and Future Work
Bilevel Synthesis successfully bridges the gap between high-level strategic goals and low-level code implementation. By treating game features as heuristics, it avoids the pitfalls of sparse rewards in program synthesis. While currently reliant on predefined feature functions, future work aims to automate feature discovery using Game Description Languages (GDL), potentially enabling entirely autonomous strategy synthesis from first principles.
Summary updated