Fast Heuristic Search for RTS Game Combat Scenarios

By David Churchill, Abdallah Saffidine, Michael Buro. 2012

142 citations recorded by the source corpus.

Heuristic search has been very successful in abstract game domains such as Chess and Go. In video games, however, adoption has been slow due to the fact that state and move spaces are much larger, real-time constraints are harsher, and constraints on computational resources are tighter. In this paper we present a fast search method — Alpha-Beta search for durative moves— that can defeat commonly used AI scripts in RTS game combat scenarios of up to 8 vs. 8 units running on a single core in under 5ms per search episode. This performance is achieved by using standard search enhancements such as transposition tables and iterative deepening, and novel usage of combat AI scripts for sorting moves and state evaluation via playouts. We also present evidence that commonly used combat scripts are highly exploitable — opening the door for a promising line of research on opponent combat modelling.

Subfields: Artificial Intelligence, Economics and Econometrics, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Economics and Econometrics

In Sociology and Political Science

Citations in the corpus

TorchCraft: a Library for Machine Learning Research on Real-Time Strategy Games (2016, background): “Related work: Classical AI approaches normally involving planning and search [2, 15, 24, 7] are extremely challenged by the combinatorial action space and the complex dynamics of RTS games, making simulation (and thus Monte Carlo tree search) difficult [8, 22].”
Episodic Exploration for Deep Deterministic Policies: An Application to StarCraft Micromanagement Tasks (2016, background): “There has been work on Bayesian fusion of hand-designed inﬂuence maps [36], fast heuristic search (in a simpliﬁed simulator of battles without collisions) [5], and even evolutionary optimization [16].”
A Review of Real-Time Strategy Game AI (2014, methodology): “Furthermore, the game must carry out expensive calculations such as unit vision and collisions, and cannot be forced to skip ahead to just the " interesting " states, making it too slow for the purpose of search (Churchill, Saffidine, and Buro 2012).”
Algorithms for computing strategies in two-player simultaneous move games (2016, unknown): “Around the same time, a serialized (sequential) version of the alpha-beta algorithm was proposed for simultaneous move games and run on combat scenarios [71].”
Global State Evaluation in StarCraft (2014, methodology): “Evaluation can be done via simulation (Churchill, Saffidine, and Buro 2012) for combat, but for the full game different techniques will be needed.”
MazeBase: A Sandbox for Learning from Games (2015, background): “For example, we usually specify a uniform distribution over height and width (between 5 and 10 for the experiments reported here), and a percentage of wall blocks and water blocks (each range randomly from 0 to 20%).”
Heuristic Search Techniques for Real-Time Strategy Games (2016, methodology): “This was shown to give a substantial performance gain against scripted opponents in [26], and so we tested to see if it would have any effect against Portfolio Greedy Search, which searches over scripted moves.”
Game-Tree Search over High-Level Game States in RTS Games (2014, methodology): “…game state representation, SparCraft is a simplified branching factor of the low-level game state only considering combat units (as calculated by the combat simulator SparCraft1 (Churchill, Saffidine, and Buro 2012)), and High Level, which the branching factor using our high-level representation.”
Hierarchical Decision Making by Generating and Following Natural Language Instructions (2019, unknown): “, building orders [5], spatial placement of building [4], attack tactics between two groups of units [6], etc).”