Combat Models for RTS Games.

Alberto Uriarte, Santiago OntañónIEEE Trans. Games 2016 · OpenReview

TL;DR

This paper introduces three novel "combat models" for simulating battles in Real-Time Strategy (RTS) games, addressing the challenge of unavailable forward models needed for game-tree search algorithms like MCTS. These models can be learned from replay data and, when integrated into an MCTS framework, significantly improve tactical decision-making in games like StarCraft.

What Problem Does This Paper Address?

Many AI agents for complex games like Real-Time Strategy (RTS) games rely on "forward models" or simulators to predict the outcome of actions. These models are crucial for game-tree search algorithms, such as Monte Carlo Tree Search (MCTS), which explore possible game futures. However, in games like StarCraft, precise, readily available forward models for combat are difficult to create due to the complexity of unit interactions, damage calculations, and game mechanics. This paper tackles this problem by proposing and evaluating new, learnable combat models that can effectively simulate battles in RTS games, making them usable within MCTS for tactical decision-making.

Methods

The authors propose three new combat models:

  • TS-Lanchester²: This model is based on Lanchester's Square Law, a classic attrition model, but adapted for heterogeneous armies (different unit types). It incorporates a target selection policy to determine which specific units are eliminated, aiming for a more accurate final state prediction than basic Lanchester models.
  • Sustained DPF Model: An extension of a previous model, this approach accounts for different unit attack types (e.g., ground vs. air) and calculates the time required for each army to destroy the other. It assumes sustained damage output, which is a simplification.
  • Decreasing DPF Model: This is a more fine-grained model that addresses the Sustained model's limitation by reducing an army's damage output as units are destroyed. It simulates combat by iteratively determining the time to kill individual units based on a target selection policy.

Crucially, the paper also details how the parameters for these models (effective Damage Per Frame (DPF) and target selection policies) can be learned from game replays, a significant contribution for domains where game rules are not fully known or easily accessible.

Datasets

The primary dataset used was extracted from 600 StarCraft replays, resulting in 140,797 combat records. For evaluation purposes, a subset of 6,066 combats that ended with one army destroyed was used. Additionally, a SPARCRAFT-compatible subset of 4,558 combats was generated to allow comparison with the SPARCRAFT simulator. The authors also mention using replays from professional human players.

Key Insights and Ideas

  • Learnable Combat Models are Viable: The ability to learn combat model parameters (DPF and target selection) directly from replay data is a major breakthrough, enabling the application of these models even without explicit game knowledge.
  • Target Selection is Crucial: The performance of combat models, especially for predicting final states, is highly sensitive to the target selection policy. Learned policies (like Borda Count) significantly outperform random selection.
  • Abstraction is Key for MCTS: High-level abstractions of the game state (grouping units by type and region) drastically reduce the branching factor in MCTS, making it feasible to search complex RTS games.
  • TS-Lanchester² and Decreasing Models Excel: Among the proposed models, TS-Lanchester² and the Decreasing DPF model showed superior performance in both winner prediction and final state prediction accuracy.
  • Static DPF Can Be Strong: In many cases, using static DPF values (derived from game data) yielded better results than learned DPFs, suggesting that explicit game knowledge, when available, is valuable.

Key Results

  • Winner Prediction Accuracy: The proposed combat models achieved higher winner prediction accuracy (up to 94.10% for TS-Lanchester² static) compared to SPARCRAFT's scripted behaviors (around 84-88%).
  • Final State Prediction Accuracy: The best proposed model (TS-Lanchester² static with Borda Count) achieved significantly higher average similarity (around 0.91) to actual combat outcomes than SPARCRAFT (around 0.85).
  • Computational Efficiency: The proposed models were significantly faster than SPARCRAFT, being 19 to 145 times faster, making them suitable for the large number of simulations required by MCTS.
  • MCTS Performance: When integrated into an MCTS framework for controlling military units in StarCraft, the Decreasing DPF model achieved the best win rate (75%) against the built-in Terran AI, outperforming other models and baselines.

Limitations and Future Work

  • Fog of War: The experiments were conducted with fog of war deactivated, limiting the applicability to scenarios with full observability. Future work aims to address partial observability.
  • Game Pausing: The MCTS search was performed by pausing the game. Future work plans to explore splitting computation time across game frames for more continuous play.
  • Heterogeneous Armies: Predicting combats between heterogeneous armies proved challenging, with a significant drop in accuracy.
  • On-line Learning: The current models are trained off-line. Future work will explore on-line learning techniques to adapt combat models to specific adversaries during gameplay.
  • Uncertainty: The models do not explicitly handle uncertainty in combat outcomes.
  • Other Tasks: The MCTS framework focused solely on military unit control, excluding other crucial RTS tasks like resource gathering and unit production.

Summary updated

Abstract

Game tree search algorithms, such as Monte Carlo Tree Search (MCTS), require access to a forward model (or "simulator") of the game at hand. However, in some games such forward model is not readily available. This paper presents three forward models for two-player attrition games, which we call "combat models", and show how they can be used to simulate combat in RTS games. We also show how these combat models can be learned from replay data. We use StarCraft as our application domain. We report experiments comparing our combat models predicting a combat output and their impact when used for tactical decisions during a real game.
BibTeX
@article{uriarte2016combat,
  author = {Alberto Uriarte and Santiago Ontañón},
  title = {{Combat Models for RTS Games.}},
  journal = {IEEE Trans. Games2018},
  year = {2016},
  url = {https://openreview.net/forum?id=MPU6ERIs0_X},
}
Figure