Puppet Search: Enhancing Scripted Behavior by Look-Ahead Search with Applications to Real-Time Strategy Games

Real-Time Strategy (RTS) games have shown to be very resilient to standard  adversarial tree search techniques. Recently, a few approaches to tackle their complexity have emerged that use game state or move abstractions, or both. Unfortunately, the supporting experiments were either limited to simpler RTS environments (uRTS, SparCraft) or lack testing against state-of-the-art game playing agents. Here, we propose Puppet Search, a new adversarial search framework based on scripts that can expose choice points to a look-ahead search procedure. Selecting a combination of a script and decisions for its choice points represents a move to be applied next. Such moves can be executed in the actual game, thus letting the script play, or in an abstract representation of the game state which can be used by an adversarial tree search algorithm. Puppet Search returns a principal variation of scripts and choices to be executed by the agent for a given time span. We implemented the algorithm in a complete StarCraft bot. Experiments show that it matches or outperforms all of the individual scripts that it uses when playing against state-of-the-art bots from the 2014 AIIDE StarCraft competition.

• Publication year

  2021

• Venue

  Artificial Intelligence and Interactive Digital Entertainment Conference

• Publication date

  2021-06-24

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1609/aiide.v11i1.12779
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Using Lanchester Attrition Laws for Combat Prediction in StarCraft

  2021cited by this paper
• Game-Tree Search over High-Level Game States in RTS Games

  2014influential reference
• Global State Evaluation in StarCraft

  2014cited by this paper
• Hierarchical Adversarial Search Applied to Real-Time Strategy Games

  2014cited by this paper
• Introducing Hierarchical Adversarial Search, a Scalable Search Procedure for Real-Time Strategy Games

  2014cited by this paper
• The Combinatorial Multi-Armed Bandit Problem and Its Application to Real-Time Strategy Games

  2013cited by this paper
• A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft

  2013cited by this paper
• Portfolio greedy search and simulation for large-scale combat in starcraft

  2013cited by this paper
• Fast Heuristic Search for RTS Game Combat Scenarios

  2012cited by this paper
• A Bayesian model for opening prediction in RTS games with application to StarCraft

  2011cited by this paper
• Build Order Optimization in StarCraft

  2011cited by this paper
• A Particle Model for State Estimation in Real-Time Strategy Games

  2011cited by this paper
• A Bayesian Model for Plan Recognition in RTS Games Applied to StarCraft

  2011cited by this paper
• A data mining approach to strategy prediction

  2009cited by this paper
• Learning from Demonstration and Case-Based Planning for Real-Time Strategy Games

  2008cited by this paper
• Bandit Based Monte-Carlo Planning

  2006influential reference
• Heuristic Search Applied to Abstract Combat Games

  2005cited by this paper
• A New Hashing Method with Application for Game Playing

  1990cited by this paper

• A Survey of Non-Learning-Based Abstractions for Sequential Decision-Making

  2025influential citation
• Elastic Monte Carlo Tree Search

  2023cites this paper
• Elastic Monte Carlo Tree Search with State Abstraction for Strategy Game Playing

  2022cites this paper
• Algorithm Selection in Zero-Sum Computer Games

  2021cites this paper
• Improving Monte Carlo Tree Search Policies in StarCraft via Probabilistic Models Learned from Replay Data

  2021cites this paper
• Single Believe State Generation for Handling Partial Observability with MCTS in StarCraft

  2021cites this paper
• Monte Carlo Tree Search: a review of recent modifications and applications

  2021cites this paper
• Generating Diverse and Competitive Play-Styles for Strategy Games

  2021cites this paper
• Adaptive Online Opponent Game Policy Modeling with Association Rule Mining

  2021cites this paper
• Improving the Performance of MCTS-Based µRTS Agents Through Move Pruning

  2020influential citation
• Parametric action pre-selection for MCTS in real-time strategy games

  2020cites this paper
• Online Adversarial Planning in μRTS : A Survey

  2019cites this paper
• Search, Abstractions and Learning in Real-Time Strategy Games

  2019influential citation
• Real-time Strategy Game Tactical Recommendation Based on Bayesian Network

  2019cites this paper
• Search, Abstractions and Learning in Real-Time Strategy Games

  2019cites this paper
• Evolving Game State Evaluation Functions for a Hybrid Planning Approach

  2019cites this paper
• Algorithms or Actions? A Study in Large-Scale Reinforcement Learning

  2018cites this paper
• A Review of Computational Intelligence for StarCraft AI

  2018cites this paper
• Artificial Intelligence Techniques on Real-time Strategy Games

  2018cites this paper
• Adaptation of Alpha-Beta Search Algorithm for Real-Time Strategy Game

  2018cites this paper
• Tabular Reinforcement Learning in Real-Time Strategy Games via Options

  2018influential citation
• Improving Collectible Card Game AI with Heuristic Search and Machine Learning Techniques

  2017cites this paper
• State-of-the-Art and Open Challenges in RTS Game-AI and Starcraft

  2017cites this paper
• Combining Strategic Learning and Tactical Search in Real-Time Strategy Games

  2017cites this paper
• Combining Scripted Behavior with Game Tree Search for Stronger, More Robust Game AI

  2017cites this paper
• Game Tree Search Based on Nondeterministic Action Scripts in Real-Time Strategy Games

  2017cites this paper
• Improving hearthstone AI by learning high-level rollout policies and bucketing chance node events

  2017cites this paper
• Evaluating real-time strategy game states using convolutional neural networks

  2016cites this paper
• Heuristic Search Techniques for Real-Time Strategy Games

  2016cites this paper
• State and Action Abstraction for Search and Reinforcement Learning Algorithms

  year unknowncites this paper