Design Adaptive AI for RTS Game by Learning Player's Build Order

Guillaume Lorthioir, Katsumi InoueIJCAI 2020 · DOI

Abstract

This paper proposes a hybrid approach to creating adaptive Real-Time Strategy (RTS) AI by combining economic simulation with Bayesian programming. By simulating a player's resource gathering in real-time, the AI can infer the opponent's "Build Order" (opening strategy) and use constrained optimization to select the most effective counter-strategy. This method addresses the high computational costs and brittleness of deep reinforcement learning by focusing on the fundamental resource constraints of the game environment.

Introduction

In Real-Time Strategy games like StarCraft, AI opponents often struggle to adapt to human unpredictability, frequently relying on "cheating" (e.g., full map vision) to remain competitive. The core challenge lies in Plan Recognition: identifying a player’s strategy behind the "fog of war." Predicting a "Build Order"—the specific sequence of buildings and units—is essential for high-level play, but the permutation space is massive. While models like AlphaStar achieve high performance, they require millions of dollars in compute and are often brittle to rule changes. This research explores a more efficient, physics-based approach to strategy inference.

The Proposed Pipeline

The authors propose a three-stage pipeline to infer and react to an opponent's strategy, moving from raw economic data to a finalized counter-plan.

The three-stage pipeline for strategy inference and adaptation, moving from economic simulation to the final AI build order.

1. Economic Simulation

Instead of pattern-matching from a static list, the AI runs a real-time simulation of the opponent's economy. By tracking worker counts, it calculates the maximum possible resources (Gas and Minerals) available at any given second. This generates a set of "mathematically possible" Build Orders ($BO_1, BO_2, BO_3$), effectively pruning the search space based on the game's "physics."

2. Filtering & Bayesian Inference

As the AI's units scout the map, they gain partial information. Any Build Order in the simulated set that contradicts these observations (e.g., seeing a building that wasn't predicted) is discarded. The remaining candidates are processed through a Bayesian model to determine which specific strategy the opponent is most likely following.

3. Constrained Optimization

Once the strategy is identified, the AI uses constrained optimization to select a counter-strategy ($BO_{AI}$). Crucially, this model considers the "switching cost"—evaluating whether it is more efficient to stay the course or spend resources to pivot the entire production line to a new strategy.

Methodology and Data

The research leverages the extensive library of StarCraft: Brood War replays, specifically utilizing the Weber and Mateas (2009) dataset for strategy prediction benchmarks.

The approach relies on Physics-Based Inference. Rather than treating strategy prediction as a pure pattern-matching problem, the authors treat it as a resource-constraint problem. If the math dictates that an opponent cannot afford a specific unit at a certain time, that possibility is ignored. The focus is primarily on the Early Game (the first ten minutes), where opening moves follow the most rigid patterns and are most decisive.

Key Results and Scalability

As a Doctoral Consortium presentation, the results are primarily architectural:

  • Methodological Integration: The authors successfully integrated economic equations into a strategy inference pipeline.
  • Efficiency: Unlike deep learning approaches, this simulation-based method is designed to run on standard consumer hardware.
  • Robustness: The reliance on fundamental game rules makes the system more resilient to balance updates compared to data-driven black-box models.

Limitations and Future Work

The final stage of the project—automated adaptation via constrained optimization—was theoretical at the time of publication. Future work involves full implementation in a live bot and exploring "heuristic search" to replace raw simulation, further increasing the speed of strategy identification. Finding a heuristic function that accurately reflects the "value" of a strategy in complex environments remains a primary challenge.

Summary updated

BibTeX
@inproceedings{lorthioir2020design,
  author = {Guillaume Lorthioir and Katsumi Inoue},
  title = {{Design Adaptive AI for RTS Game by Learning Player's Build Order}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/737},
}
Figure