The core challenge facing search techniques when used to play Real-Time Strategy (RTS) games is the extensive combinatorial decision space. Several approaches were proposed to alleviate this dimensionality burden, using scripts or action probability distributions, based on expert knowledge. We propose to replace expert-authored scripts by a collection of smaller parametric scripts we call heuristics and use them to pre-select actions for Monte Carlo Tree Search (MCTS). The advantages of this proposal consist of granular control of the decision space and the ability to adapt the agent's strategy in-game, all by altering the heuristics and their parameters. Experimentation results in RTS using a proposed implementation have shown a signi cant performance gain over state-of-the-art agents.
Video games belonging to the Real-Time Strategy (RTS) sub-genre can be viewed as an evolution of classic board games. Games such as Chess, Checkers, and Go depict an abstract con ict situation between two parties. The capabilities of modern computing devices, usually paired with advanced game-engines, allow RTS games to portray concrete con ict situations, approximately simulating the dynamics of real-world military disputes. Players in an RTS game can simultaneously control multiple entities (units) in real-time, within a large, dynamic, and uncertain environment.
Designing a successful arti cial RTS player is a demanding task that requires
overcoming many challenges. In particular, the large combinatorial decision and
state spaces constitute a signi cant bottleneck for game-playing agents based on
search or machine learning. Task decomposition is a common solution to mitigate
the domain's complexities, usually by de ning multiple sub-tasks in each level
of abstraction. Decision making in an RTS game ows through three levels of
abstraction: strategic, tactical, and reactive-control [
Monte Carlo Tree Search (MCTS) is a sampling-based search approach with
a successful track record in many board games, especially those known for their
high branching factor such as Go. MCTS was also adapted for use as a holistic
agent in RTS games, but it still struggles to replicate the same degree of success
as in Go, due to the branching-factor bottleneck. The proposed improvements
usually fall in two main scopes: (1) The use of expert-knowledge to abstract the
decision space and lower the branching factor, and (2) the use of MCTS solely
as a component dedicated to smaller tactical and reactive situations, as part of
an agent. While there are e orts to combine both scopes [
In this paper, we propose an action pre-selection algorithm that relies on the building blocks of expert scripts rather than full scripts. Expert-authored scripts combine several smaller scripts, we call heuristics, to form a scripted agent. A heuristic represents an isolated task performed by a unit or a group of units, such as harvesting or attacking. Our algorithm depends on parametric heuristics to generate a wide variety of scripts that can be used to pre-select actions for prede ned groups of units, to feed into an MCTS agent. The heuristics' parameters can be modi ed in real-time to adjust both the decision granularity and the adopted strategy, which opens the perspectives for dynamic strategy adaptation through MCTS. Experimentation results in the RTS test-bed reveals a signi cant MCTS performance gain related to the reduced branching factor and the more focused decision space.
In the next section, we will review some preliminaries about RTS games and MCTS. In Section 3 we will explore some relevant works related to our proposal, and in Section 4 we will detail the theoretic and implementation aspects of our approach. Experimentation results will be presented and discussed in Section 5, followed by a conclusion in Section 6. 2 2.1
An RTS game is a zero-sum, multiplayer, non-deterministic, and imperfectinformation game, where players compete for resources to defeat an opposing side using military force. To win, the player is expected to devise and execute a strategy that can overcome his opponent and ultimately eliminate all his units. The player manages his units by issuing a unit-action to each, forming a playeraction in each decision. The game's environment usually consists of a large map with topographic features, covered by a fog-of-war layer that reduces visibility.
RTS games gained signi cant popularity on the PC platform thanks in part to their PC-friendly user interfaces and control schemes, reminiscent of a typical PC software. The most commercially successful RTS titles include StarCraft, Command & Conquer, and Age of Empires. Enabling AI research on commercial games started as an independent community e ort that resulted in several uno cial APIs, such as BWAPI and Wargus. Much later, Blizzard provided an o cial StarCraft II AI API and toolset in collaboration with DeepMind3. Independent RTS AI research platforms have also emerged, such as ORTS, RTS, ELF, and DeepRTS.
We used RTS [
Formally, an RTS game can be de ned as a tuple G = (S; A; P; ; L; W; sinit)
[
MCTS [
Upper Con dence Bounds for Trees (UCT) [
NaveMCTS [
lem. This change highlights the reward contribution of each component (unitaction) of a decision (player-action) and makes it possible to employ a nave sampling strategy. Nave sampling assumes that the reward estimates of unitactions can be summed to obtain the reward estimate of the player-action they form. The problem is thus subdivided into n local MABs (n: the number of units) and one global MAB. NaveMCTS does not need to explore all moves before exploitation since it relies on an -greedy strategy instead of UCB1. 3
Managing the complex decision-space of RTS games in the context of search is usually done by de ning a proxy layer that guides search towards high-value actions while ignoring the rest. This layer is de ned by expert knowledge and may take the form of expert-authored scripts, or action probability distributions learned from expert traces. State abstraction through unit clustering is also a way to further reduce the branching factor by considering clusters of units instead of individual units.
In RTS combat scenarios, Balla and Fern [
Notable non-MCTS abstraction-based search algorithms include Strati ed
Strategy Selection (SSS) [
Planning exclusively in a scripts-induced decision space can compromise
lowlevel tactical performance. For this reason, several works paired action
abstraction with low-level search. StrategyTactics [
We propose a parametric action pre-selection scheme that, in contrast with previous approaches, relies on heuristics instead of full scripts. Our approach works by altering the decision space for NaveMCTS, according to a set of provided parameters that govern the possible strategic and tactical decisions. Moreover, our approach supports assigning heuristics to individual units or groups of units. The advantage of this approach is its ability to implement a wide spectrum of strategies by adjusting the heuristics' parameters pre-game or in-game. 4
An expert-authored strategy or script in an RTS game can be broken down into a set of heuristics, each controlling a group of units. Changing or replacing one heuristic can a ect the goal and the performance of the strategy with varying degrees. If we assume that all the possible RTS heuristics are known, then it becomes possible to generate all RTS strategies by combining heuristics. An agent can adapt its strategy according to its opponent or environment by replacing problematic heuristics. To preserve tactical performance, a heuristic can delegate all tactical choices to a search approach.
We suggest that one way to capture a broad spectrum of all possible heuristics is by de ning parametric heuristics. Each parameter may govern an aspect of the heuristic, creating multiple possible heuristics with each di erent parameter value combination. Therefore, the combination of heuristics and their parameters de ne a strategy. A heuristic can be expert-authored or automatically learned.
Formally, we de ne a heuristic h 2 H, where H is the set of heuristics, as a function h : S U Al Rh ! Ak taking a game state s 2 S, a unit u 2 U , all legal unit-actions (a1; ; al) 2 Al possible for u in s, and a parameter vector p 2 Rh as input to produce a unit-action tuple = (a1; ; ak) 2 Ak where Ak Al and k l. The sets U , Rh and A represent the set of units, parameter vectors of heuristic h, and legal unit-actions, respectively.
In hard-coded scripts, parameter vectors are usually constant, but in our proposed approach, the parameter vector of a heuristic can be variable. A heuristic h is fully deterministic if k = 1 and no random aspect intervenes in its execution. In case k > 1, a search algorithm can select an optimal action from the heuristic's output, . A heuristic may employ any suitable algorithm, including path nding, to narrow down the number of actions in and reduce the overall branching factor.
For instance, a common heuristic in RTS games is the harvest heuristic which when applied to a Worker unit discards all unit-actions in favor of those that guide the Worker back and forth between a resource deposit (harvest) and a Base (return). harvest may expose parameters such as the maximum resources to harvest or the path nding algorithm to use.
A heuristic h can be associated with a group of units g 2 P(U ), in which case it will be applied to each unit in g under parameter vector p, and we denote it h[g; p]. We de ne D as the set of all possible unit partitionings, where a partitioning d 2 D can be de ned as d = fg1; ; gm j gi 2 P(U )g.
An action pre-selection process T (s; U ; A0; x1; ; xn) is an n-phase algorithm where each phase xi(Ai 1; di; Hi; i) consists of a unit partitioning scheme
A0 Game State s
Units U
T x1 di 2 D that generates a set of mi unit groups gj for which a heuristic hj [gj ; pj ] 2 Hi(Hi H) is applied 8j 2 1; ; mi, under the parameter vector pj 2 i. Each pre-selection phase operates on the unit-actions output of the previous phase, Ai 1, and the initial phase operates on A0, the set of all legal unit-actions of the units in U . The output of phase xi consists of the set of unit-actions Ai calculated by the heuristics of Hi for each unit in U . The nal output of T is the unit-action set An. Figure 1 illustrates the pre-selection process.
Intuitively, an action pre-selection process is a successive re nement strategy that works by manipulating the set of unit-actions possible for each unit in a game state according to a global strategy expressed by the set of heuristics, partitionings, and parameters de ned for each pre-selection phase. The resulting set of unit-actions represent a decision to execute, or the possible options admissible by the global strategy. In the latter case, a search algorithm such as MCTS can be employed to nd an optimal player-action in accordance with the global strategy, in a much smaller and focused decision space. A global strategy is represented by n = (d1; ; dn; H1; ; Hn; 1; ; n) in an action pre-selection process T .
As an example, it is possible to de ne a hierarchical 2-phase pre-selection process, where in the rst phase the units are split into two large groups d1 = fdefense; o enseg and are assigned to two heuristics H1 = fdefend ; attack g under parameters 1. In the second phase, the units could be split into more specialized groups such as: d2 = fbaseDef ; barracksDef ; o enseg. The rst phase assures a common behavior for defense units, and the second phase builds on that to create specialized defense units. We will describe an action pre-selection implementation proposition for RTS games next. We propose an action pre-selection implementation for RTS games that delegates tactical decision making to NaveMCTS and allows the expression of strategic decisions through parametric heuristics. Our implementation, ParaMCTS, relies on a 2-phase action pre-selection process that partitions units into four functional groups in the rst phase, and into two situational groups in the second phase. The intuition behind both group types comes from the way human RTS players attribute di erent functions to di erent unit groups while macro-managing, and how they switch to micro-management for units in con ict situations. We de ne d1 and d2, in the context of RTS, as such: d1: Functional groups { Harvesters: Worker units dedicated to gathering resources and building structures. { O ense: Mobile units with the purpose of assaulting opponent units. { Defense: Mobile units assigned to defend the Base's perimeter. { Structures: Barracks and Base. Responsible for producing mobile units. d2: Situational groups { Front-Line: Mobile units in close-contact with opponent units. { Back: All units not in the Front-Line group.
d1 assigns each unit to its relevant group based on a prede ned unit-composition that declares the maximum count of each unit-type to be found in each group. For instance, it is possible to specify the maximum number of Workers in the Harvesters, O ense or Defense group. As for d2, it populates the Front-Line group by selecting a number of units within the re-range of opponent units, or those targeting an opponent unit. The unit-composition and front-line selection method are both partitioning parameters to provide. The heuristics in H1 and H2 are rule-based and are described as follows: H1: { Harvest: Applies to the Harvesters group. Automates the resource harvesting process and provides Barracks building options whenever possible. Parameters include the building location selection mode (isolated, random, ..., etc.) and the number of build options. { Attack: Applies to the O ense group. Find and track opponent units for suppression. Parameters include the tracking mode (closest, minHP,...etc.), the maximum number of units to track, and the number of escape routes to consider in a close encounter. { Defend: Applies to the Defense group. Remain within a defense perimeter around the Base and attack incoming opponent units. Parameters include the geometry and size of the defense perimeter, the defense mode, and the maximum number of units to attack. { Train: Applies to the Structures group. Trains units following the unitcomposition provided to d1. Parameters include the unit-composition, the training mode (isolated side, random side, ..., etc), and the number of training options.
Note how in each heuristic a numeric parameter decides the number of options for certain actions (build, targets, ...). This type of parameter dictates how many choices (k) NaveMCTS can operate on for each unit of the same group, which directly impacts the branching factor. Harvest, Attack, and Defend use a path nding algorithm to direct units towards their goals.
H2: { Front-Line Tactics: Applies to the Front-Line group. Reduces the Wait unit-action duration to increase the units' reactivity while in combat. { Back Tactics: Applies to the Back group. Keeps the default Wait unitaction duration.
Note that Front-Line units do not depend on d1 partitioning, meaning that any unit in a d1 group can also be considered a Front-Line unit. In total 47 parameter was de ned for all heuristics and partitionings. The full parameters list can be consulted in this approach's source code repository 4.
Switching heuristics on the y is a way to adapt the agent's strategy according to changes in the overall situation. We propose to switch the heuristics of d1's Defense group from Defend to Attack according to a conditional trigger. The switch is triggered whenever the score of the army composition is greater than the opponent's by a prede ned margin we call the overpower factor. The score simply counts all mobile units and attributes greater weight to assault units.
Lastly, ParaMCTS uses a NaveMCTS enhancement, previously conceived
by the authors (to appear in [
Using ParaMCTS, we conducted a series of experiments to gauge the bene ts of action pre-selection on the performance of NaveMCTS. Since the main e ect of action pre-selection is a signi cantly reduced branching factor, we would like to test which MCTS parameter can exploit the downsized decision space to add the most value to performance. We focus on the two prominent search parameters, maximum depth, and playout duration. We experiment using the following sets of possible values for both parameters: depthV als = f10; 15; 20; 30; 50g and durationV als = f100; 150; 200; 300; 500g.
We de ne ParaMCTS (depth, duration) as the ParaMCTS variant using both depth and duration as the maximum search depth, and playout duration, respectively. All experiments were run on two PCs with relatively similar processors using the latest version of RTS as of 10 July 2020. Each agent was attributed a 100ms computation budget, similarly to the RTS competition setting, and each experiment was repeated on three maps representing increasingly larger
20 Maximum Depth 30 50 8x8 16x16 100 32x32 150
200 Playout Duration 300 500 branching factors, namely basesWorkers 8 8, 16 16, and 32 32. To guarantee a fair comparison, ParaMCTS was parameterized to adopt strategies similar to its opponents', even when there is a possibility for exploitation. In all experiments, we calculate the score of an agent likewise: score = wins + draws=2, and normalize it between 0 and 100. 5.1
To study the e ect of various search depths and playout durations on ParaMCTS we ran 120 iteration of a round-robin tournament between each ParaMCTS (10, duration) variant for each duration in durationV als, and another 120 roundrobin iteration between each ParaMCTS (depth, 100) variant for each depth in depthVals. Fixed values 10 and 100 for depth and duration, respectively, are the default NaveMCTS values. Results of this experiment are shown in Figure 2.
In the second experiment, we took all the possible depth and duration
combinations from depthV als durationV als and ran 100 matches (switching sides
after 50 matches) between each resulting ParaMCTS (depth, duration) and
MixedBot, a state-of-the-art agent combining various techniques [
From the results of both experiments, we can see how overall ParaMCTS performance seems to be particularly sensitive to the playout duration. In Fig100 90 80 70 reo 5600 cS 40 30 20 10 0 ure 2-(2) performance vary signi cantly between the playout durations. In the smallest maps, short playouts work best, but in larger maps, slightly longer playouts work well up to a certain threshold. As for search depth, it is clear that in the largest map a deeper search yields the most bene t, as seen in Figure 2-(1). As for the small and medium maps, deeper search holds fewer bene ts.
Against MixedBot (Table 1), the best results are obtained when the playout duration equals 100 cycles, in all three map sizes, even if 150 cycles seem promising for the 16 16 map. When looking at the search depth, going down 20 levels in the tree is the optimal depth for 8 8 and 16 16 maps. In the 32 32 map, searching as deep as 50 levels yield the best performance. Clearly, deeper search yields the most performance increase than longer playouts. We believe this is true because deeper search may be responsible for more accurate player-action reward estimates, due to the increased number of visited nodes, and playouts, towards the depth of the game tree. On the other hand, longer playouts yield a lower number of visited nodes, and playouts, which could negatively impact performance. Larger maps bene t the most from deeper search because the map's dimensions contribute to the sparsity of rewards, and a deeper search can reach rewarding states more frequently. 5.2
To compare the overall performance of ParaMCTS against the current best
performing agents, we took three top ranking agents from 2019's RTS
competition: MixedBot, Izanagi, [
In terms of overall performance, ParaMCTS outperformed all state-of-the-art agents by a comfortable margin. ParaMCTS was able to achieve an 11.9 points margin over the 2nd best agent, Izanagi, and 19.1 points margin over the 4th best, MixedBot. Both agents make use of a combination of advanced techniques. This result is direct evidence of the potency of our action pre-selection approach when coupled with NaveMCTS. In individual maps, ParaMCTS outperformed the other agents in 8 8 and 32 32 maps, but it was outdone in the 16 16 map by Droplet. This can be explained by the adoption of an opportunistic strategy by Droplet in the 16 16 map. Although ParaMCTS can be easily con gured to adopt such strategies, we chose not to do so to keep the comparison as fair as possible. NMCTS* did not o er any tangible performance gain over NaveMCTS, which indicates that increasing the search's depth will not yield any performance gain if not paired with a signi cant decision-space reduction. 6
We have presented an integrated action and state abstraction process that partitions units into multiple groups, and assigns heuristics to each group for the sake of obtaining a downsized set of pre-selected unit-actions. The proposed process receives a collection of parameters that de ne the partitioning and heuristics. It is possible to alter the heuristics parameters in-game to adapt the agent's strategy in a granular fashion. We have proposed a theoretical de nition and demonstrated how it can be implemented through a full RTS agent in RTS. Experimentation results show a signi cant improvement over state-of-the-art
RTS agents. ParaMCTS will take part in the 4th RTS competition (to be organized as part of IEEE CoG 2020), under the alias UMSBot.
The proposed action pre-selection implementation, ParaMCTS, is a single possibility among many. Using action pre-selection as a basis to develop more sophisticated agents is conceivable. Although proposed as an approach to lower the RTS decision space dimensionality, we believe this technique could be easily adapted to any multi-unit real-time game. Moreover, we believe that this technique can also provide di culty adjustment through parameter optimization.
As for future works, we are interested in auto-adapting the heuristics and their parameters on the y, using opponent modeling in di erent environments. We are also looking into applying evolutionary algorithms to evolve and nd optimal strategies. Automatically learning new heuristics and unit partitionings in the context of action pre-selection is also an interesting direction.