Show Me the Way! Bilevel Search for Synthesizing Programmatic Strategies

David S. Aleixo, Levi H. S. Lelis

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:

  1. 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.
  2. 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.
Example grammar and parse tree for a programmatic strategy in the domain-specific language.

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.

Winning rate over time for various synthesis methods across three MicroRTS maps. The top row shows Bi-S results, while the bottom row shows Bi-S+ with transfer learning.

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

Abstract

The synthesis of programmatic strategies requires one to search in large non-differentiable spaces of computer programs. Current search algorithms use self-play approaches to guide this search. The issue with these approaches is that the guiding function often provides a weak search signal. This is because self-play functions only measure how well a program performs against other programs. Thus, while small changes to a losing program might not transform it into a winning one, such changes might represent steps in the direction of a winning program. In this paper we introduce a bilevel search algorithm that searches concurrently in the space of programs and in a space of state features. Each iteration of the search in the space of features defines a set of target features that the search in the program space attempts to achieve (i.e., features one observes while following the strategy encoded in a program). We hypothesize the combination of a self-play function and a feature-based one provides a stronger search signal for synthesis. While both functions are used to guide the search in the program space, the self-play function is used to guide the search in the feature space, to allow for the selection of target features that are more likely to lead to winning programs. We evaluated our bilevel algorithm in MicroRTS, a real-time strategy game. Our results show that the bilevel search synthesizes stronger strategies than methods that search only in the program space. Also, the strategies our method synthesizes obtained the highest winning rate in a simulated tournament with several baseline agents, including the best agents from the two latest MicroRTS competitions.
BibTeX
@inproceedings{aleixo2023show,
  author = {David S. Aleixo and Levi H. S. Lelis},
  title = {{Show Me the Way! Bilevel Search for Synthesizing Programmatic Strategies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25626},
}

Loading related content...

Figure