Abstract
We consider the problem of tactical assault planning in real-time strategy games where a team of friendly agents must launch an assault on an enemy. This problem offers many challenges including a highly dynamic and uncertain environment, multiple agents, durative actions, numeric attributes, and different optimization objectives. While the dynamics of this problem are quite complex, it is often possible to provide or learn a coarse simulation-based model of a tactical domain, which makes Monte-Carlo planning an attractive approach. In this paper, we investigate the use of UCT, a recent Monte-Carlo planning algorithm for this problem. UCT has recently shown impressive successes in the area of games, particularly Go, but has not yet been considered in the context of multiagent tactical planning. We discuss the challenges of adapting UCT to our domain and an implementation which allows for the optimization of user specified objective functions. We present an evaluation of our approach on a range of tactical assault problems with different objectives in the RTS game Wargus. The results indicate that our planner is able to generate superior plans compared to several baselines and a human player.
Introduction
In Real-Time Strategy (RTS) games, the tactical assault phase—coordinating troops to attack enemy positions—is notoriously difficult for AI. It involves a highly dynamic environment, concurrent and durative actions (actions that take time to complete), and numeric attributes like health and spatial location. Historically, RTS game AI has relied on static, heavily scripted behaviors. While some recent Monte-Carlo planning approaches have shown promise, they typically require significant human-provided domain knowledge, such as predefined sets of strategies or complex, hand-crafted state evaluation functions.
This paper introduces a flexible, online planner that can dynamically orchestrate multi-agent assaults to optimize arbitrary, user-specified objectives (e.g., "win as fast as possible" or "win with minimal casualties") without needing a cheat sheet of pre-written strategies.
Methodology
The authors apply UCT (Upper Confidence bounds applied to Trees), a Monte-Carlo planning algorithm, to the RTS domain. Because tracking every individual unit is computationally intractable, they use several abstractions:
- Group-Level Abstraction: Instead of commanding individual units, the planner clusters units into proximity-based groups. The game engine's default AI handles the micro-management of individual units within those groups.
- Sequential Search for Concurrent Actions: Instead of creating a search tree where each branch is a massive "joint action" for all groups, the tree is structured so that each step assigns an action to just one idle group. This allows UCT to gather reliable statistics on "partial assignments," vastly improving search efficiency.
- Dynamic Exploration Constant: Standard UCT uses a constant $c$ to balance exploration and exploitation. Because RTS action values (like total hit points) have high variance, the authors dynamically set $c$ to equal the current action value estimate $Q(s,a)$.
- Fast-Forward Simulation: To run Monte-Carlo rollouts, the authors built a lightweight simulation model using numeric formulas to predict movement times and combat attrition rates.
Experimental Setup
The authors evaluated their approach using Wargus, an open-source clone of Warcraft II. They created 12 custom game scenarios varying the number of friendly and enemy units (10 to 20 per side) and their initial spatial groupings. To isolate tactical maneuvering, all scenarios were restricted to a single melee unit type (footmen). Two variants of the planner were tested: UCT(t) (minimize time to win) and UCT(hp) (maximize surviving hit points).
Key Results
UCT was the only automated planner capable of finding winning strategies across all 12 scenarios. The algorithm demonstrated remarkable flexibility; by simply changing the terminal reward function, the planner exhibited drastically different playstyles, such as rushing the enemy versus carefully massing troops.
As shown in the evaluation of the health-optimization objective, UCT(hp) consistently preserved the most friendly health, outperforming both scripted baselines and an experienced human player. Similarly, the UCT(t) variant achieved the fastest completion times. Performance scaled reliably with the number of rollouts, with 5,000 rollouts per decision epoch yielding significantly better results than 1,000, though improvements eventually plateaued.
Conclusion
By relying on Monte-Carlo rollouts to terminal game states, the UCT planner bypasses the need for complex, hand-crafted state evaluation functions. While the current prototype requires engineering optimization to reach true real-time execution speeds, it proves that UCT can effectively handle the complexities of multi-agent tactical planning in RTS environments. Future work will address mixed unit types and proactive adversaries.
Summary updated