On-Line Case-Based Plan Adaptation for Real-Time Strategy Games.

Neha Sugandh, Santiago Ontañón, Ashwin RamAAAI 2008 · OpenReview

Abstract

Traditional artificial intelligence techniques do not perform well in applications such as real-time strategy games because of the extensive search spaces which need to be explored. In addition, this exploration must be carried out on-line during performance time; it cannot be precomputed. We have developed on-line case-based planning techniques that are effective in such domains. In this paper, we extend our earlier work using ideas from traditional planning to inform the real-time adaptation of plans. In our framework, when a plan is retrieved, a plan dependency graph is inferred to capture the relations between actions in the plan. The plan is then adapted in real-time using its plan dependency graph. This allows the system to create and adapt plans in an efficient and effective manner while performing the task. The approach is evaluated using WARGUS, a well-known real-time strategy game.

Introduction

Real-Time Strategy (RTS) games like Warcraft or StarCraft present significant challenges for AI due to massive search spaces, hidden information, and the requirement for millisecond decision-making. While Case-Based Planning (CBP)—reusing successful past strategies—is a promising alternative to search-based AI, it faces a major hurdle: adaptation. A plan recorded in one game rarely fits the specific state of a new game perfectly. Traditional adaptation techniques are often too slow or too rigid. This paper introduces a domain-independent, search-free adaptation method that functions on-the-fly as the game state changes.

Methodology

The authors implemented their approach within the Darmok system. The core innovation is the use of a Plan Dependency Graph (PDG) to manage structural plan adaptation.

The Darmok system architecture, showing behavior acquisition and execution cycles.

The system operates in two main phases:

  1. Behavior Acquisition: Expert human play "traces" are recorded, annotated with goals, and stored as cases in a library.
  2. Structural Adaptation:
    • Pruning: When a plan is retrieved, a PDG maps action dependencies. If a success condition is already met (e.g., a player already has a "Barracks"), the system prunes the redundant action and its support steps via graph traversal.
  3. Insertion: If an action fails due to an unmet precondition (e.g., "not enough gold"), the system inserts a new "satisfying goal." The CBP cycle then retrieves a behavior for this specific sub-goal, effectively interleaving adaptation with execution.

Experimental Setup

The system was evaluated using WARGUS, an open-source clone of Warcraft II. The case library consisted of 7 expert demonstration traces. Testing was conducted on strategically complex maps like "Nowhere to run nowhere to hide" (NWTR) and "Garden of War" (GoW), which require specific tactics like tunneling through forests.

Key Results

The quantitative results demonstrate that adaptation is a "force multiplier" for CBP, especially as the variety of expert knowledge increases.

Comparison of win rates with and without plan adaptation across different numbers of expert traces.

Key findings include:

  • Multi-Trace Scaling: With 6 traces, the win rate doubled from 9 (no adaptation) to 18 (with adaptation). With 7 traces, the win rate jumped from 10% to 50%.
  • Search-Free Efficiency: By treating adaptation as a graph traversal problem, the system remained fast enough for real-time play without causing game lag.
  • The "Tie-in" Effect: Adaptation is most critical when mixing behaviors from different experts, as it resolves the gaps and redundancies common in multi-source plans.

Conclusion

The Darmok system successfully demonstrates that search-free graph analysis can effectively adapt plans in real-time domains. Future work will focus on adapting abstract goals before they are fully expanded and exploring formal methods for merging multiple plans into a single optimal strategy.

Summary updated

Abstract

On-Line Case-Based Plan Adaptation for Real-Time Strategy Games Neha Sugandh, Santiago Ontañón, Ashwin Ram Traditional artificial intelligence techniques do not perform well in applications such as real-time strategy games because of the extensive search spaces which need to be explored. In addition, this exploration must be carried out on-line during performance time; it cannot be precomputed. We have developed on-line case-based planning techniques that are effective in such domains. In this paper, we extend our earlier work using ideas from traditional planning to inform the real-time adaptation of plans. In our framework, when a plan is retrieved, a plan dependency graph is inferred to capture the relations between actions in the plan. The plan is then adapted in real-time using its plan dependency graph. This allows the system to create and adapt plans in an efficient and effective manner while performing the task. The approach is evaluated using WARGUS , a well-known real-time strategy game. Subjects: 3.1 Case-Based Reasoning; 1.11 Planning Submitted: Apr 15, 2008 This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.
BibTeX
@inproceedings{sugandh2008line,
  author = {Neha Sugandh and Santiago Ontañón and Ashwin Ram},
  title = {{On-Line Case-Based Plan Adaptation for Real-Time Strategy Games.}},
  booktitle = {AAAI},
  year = {2008},
  url = {https://openreview.net/forum?id=IsqIJfK55mG},
}
Figure