Stratified Strategy Selection for Unit Control in Real-Time Strategy Games

1 Introduction

Real-time strategy (RTS) games represent a major challenge to Artificial Intelligence (AI). In contrast with traditional games such as Chess and Go, players act simultaneously, actions are durative, and the branching factor can be very large-for some RTS games it can be as large as 1050 [Onta˜n´on et al., 2013]. Although some RTS games are partially observable and non-deterministic, we assume deterministic and perfect information RTS games in this paper.

In an RTS game, the player controls a set of units to gather the resources needed to train and evolve an army. Eventually, the player's army is used to battle the opponent's. One of the challenges playing agents face in an RTS match is the control of dozens of combat units during battles. Due to the real-time constraints, agents have little time to plan before acting-planning time is on the order of milliseconds.

Churchill and Buro [2013] launched a line of research for dealing with large-scale RTS combat scenarios. Namely, they assume the existence of a pool of scripts Σ. A script ¯σ is a function mapping a game state s and a unit u to a legal action m for u at s. In every game state s in which a unit u is ready to perform an action, a search algorithm selects a script ¯σ from Σ for u. We call strategy selection algorithms the methods that search for a script assignment to every unit a player controls. Since a script maps a unit to an action, by assigning a script to a unit, strategy selection algorithms effectively decide which action each unit will perform. Churchill and Buro's strategy selection algorithm, Portfolio Greedy Search

(PGS), substantially outperforms search algorithms such as Alpha-Beta [Knuth and Moore, 1975] and UCT [Kocsis and Szepesv´ari, 2006] in combat scenarios with dozens of units.

The strategy selection scheme allows search algorithms to concentrate their efforts in parts of the game tree that are deemed as promising by the scripts. That is, instead of considering all legal actions for unit u at game state s, a search algorithm considers only the actions returned by scripts in Σ. However, even then, depending on the number of units and scripts considered, search algorithms often evaluate only a small fraction of all possible actions within the time limit.

The main contribution of this paper is a search algorithm that uses a partition of the player's units, which we call a type system, to further reduce the number of possible unitaction assignments considered during search. This reduction is achieved by assigning the same script to units of the same type. For example, all wounded units (type) must move away from the battle (strategy encoded in a script). We call our algorithm Stratified Strategy Selection (SSS).

Another contribution of this paper is a meta-reasoning approach to automatically choose SSS's type system. Our approach chooses, from a pool of options, the type system to be used based on an estimate of SSS's running time. We call SSS+ this meta-reasoning-based variant of SSS.

Finally, with SSS and SSS+, we test the hypothesis that one is able to find strong strategies by searching the space of script assignments in which all units of the same type must be assigned the same script. Our experiments are run in SparCraft, a simplified combat simulation environment of Blizzard's StarCraft [Churchill and Buro, 2013]. Our results show that SSS and SSS+ are able to substantially outperform stateof-the-art approaches in combats with up to 100 units. We also show empirically SSS+'s advantage over SSS.

As the first of their kind, SSS and SSS+ represent new research directions, which include the development of novel type systems and algorithms for searching in type-induced state spaces for controlling units in RTS combats.

2 RelatedWork

Wang et al. [2016] also presents a strategy selection algorithm to control RTS combat units. However, instead of performing a hill-climbing search as is done by PGS, Wang et al. use a genetic algorithm for searching in the space of script assignments. Wang et al. showed that their genetic algorithm, Portfolio Online Evolution (POE), outperforms PGS.

The work of Justesen et al. [2014] also deals with the script assignment problem. Their algorithm is similar to ours because it also uses a partition of the units to guide its search. However, their method differs from ours in fundamental ways. SSS's partitions are defined by a type system, while Justesen et al. use a clustering algorithm to define their partitions. Our type systems use a diverse set of gamestate features, while Justesen et al. use only position-based features. Also, one of our methods uses a meta-reasoning approach for selecting the type system from a pool of options. These differences result in a major performance improvement. Wang et al. [2016] showed that Justesen et al.'s approach is only competitive with PGS and is substantially outperformed by POE. We show in this paper that our stratified approaches substantially outperform both PGS and POE.

Before the invention of strategy selection approaches, state-of-the-art search-based algorithms included MonteCarlo methods [Chung et al., 2005; Balla and Fern, 2009; Onta˜n´on, 2013] and Alpha-Beta variants [Churchill et al., 2012]. Note that some of these methods are more general than strategy selection approaches (e.g., [Onta˜n´on and Buro, 2015]) in the sense that they can be used to control a playing agent throughout a complete RTS game. By contrast, the algorithms we consider in this paper are specialized for combat scenarios. Sailer et al. [2007], Preuss et al. [2013], and Tavares et al. [2016] present methods for selecting strategies for players in RTS games. By contrast, our strategy selection approaches assign strategies to units through scripts.

Another line of research uses learning to derive combat strategies. Search algorithms require an efficient forward model of the game to plan before acting. By contrast, learning approaches do not necessarily require an efficient forward model of the game as they learn from past experiences. Notable examples of this line include the work by Usunier et al. [2016] and Liu et al. [2016]. Likely due to the use of an efficient forward model, strategy selection algorithms tend to scale more easily to large combat scenarios than learningbased methods-while the former can effectively handle battles with more than 100 units, the latter are usually tested on battles with around 50 units.

Others have used type systems as part of algorithms for estimating the running time of search methods [Chen, 1992; Korf et al., 2001; Zahavi et al., 2010; Lelis et al., 2013b; 2013a]. Type systems have also been used to enhance singleagent search algorithms [Lelis et al., 2013c; Xie et al., 2014; Betzalel et al., 2015] and as part of algorithms for predicting the optimal cost of search problems [Lelis et al., 2016]. By contrast, we use type systems as a means of enhancing search algorithms for RTS combat scenarios.

3 RTS Combat Scenarios

Combat scenarios that arise in RTS games, which we also call matches, can be described as finite zero-sum two-player games with simultaneous and durative moves. These matches can be defined by a tuple (N , S, sinit, A, R, T ), where,

• N = {i,-i} is the set of players (we assume to be

controlling i and -i to be our opponent);

• S = D ∪ F is the set of states, where D denotes the set of non-terminal states and F the set of terminal states. Every state s ∈ S includes the joint set of units U = Ui ∪ U-i, for players i and -i, respectively;
• sinit ∈ D is the start state of the match;
• A = Ai ×A-i is the set of joint player actions. Each player action a is denoted by a tuple of n unit actions (m1, · · · ,mn), where mk ∈ a is the action of the k-th ready unit of player i. A unit u is not ready at a given state s if u is currently performing an action. Whenever clear from the context, we will write action instead of player action and unit action;
• R : F × N → R is a utility function with R(s, i) = -R(s, -i), for any s ∈ F;
• The transition function T : S ×Ai ×A-i → S determines the sucessor state given a state s and the set of joint player actions taken at s.

We denote the set of unit actions as M, which includes actions for moving up, left, right and down, waiting, and attacking an enemy unit. Also, every unit u ∈ U has x and y coordinates, given by x(u) and y(u), attack range r(u), attack damage d(u), unit action duration, which depends on the unit and action being performed, current hit points hp(u), maximum hit points hpm(u), and weapon cool-down time (i.e., the time the unit has to wait before repeating an attack action). We assume Euclidean distance whenever referring to the distance between units.

A decision point of player i is a state s in which i has ready units and i has to decide on which action to take. A strategy σi : S → Ai for player i maps a state s to a player action a. One way of deriving good strategies for RTS games is by simplifying the problem's state space through the script assignment scheme introduced by Churchill and Buro [2013].

4 Scripts

A script ¯σ : S×U → M is a function mapping a state s and a unit u in s to an action m for u. A script ¯σ allows one to define a strategy σ by applying ¯σ to every ready unit in the state. We write ¯σ instead of ¯σ(s, u) whenever s and u are clear from the context. At every decision point s, strategy selection algorithms assign a script ¯σ from Σ to every ready unit u in s. Unit u then performs the action returned by ¯σ(s, u).

The success of strategy selection algorithms depends on the quality of the set of scripts Σ available. We use two scripts introduced by Churchill and Buro [2013] which they named No-Overkill-Attack-Value (NOKAV) and Kiter. NOKAV assigns actions to units so that the units do not cause more damage than the required to reduce an enemy's unit hp to zero. Kiter allows a unit to attack and then move away from the target; see Churchill and Buro [2013] for details.

In addition to NOKAV and Kiter, we use a third script called Cluster. 1 Cluster computes the average x and y coordinates, denoted (¯x, ¯ y), of all ally units Ui. Then, it assigns

1 The Cluster script was invented by David Churchill and is available in the SparCraft codebase [Churchill and Buro, 2013].

Algorithm 1 Stratified Strategy Selection

Require: scripts Σ, default script ¯σd, time limit e, evaluation

function Ψ, type system T for the set of units Ui. Ensure: action a for player i, boolean c indicating if the algorithm finished a complete iteration over all types in T 1: bi ← {¯σd, · · · , ¯σd} // vector with |Ui| elements 2: b-i ← {¯σd, · · · , ¯σd} // vector with |U-i| elements 3: c ← false 4: while time elapsed is not larger than e do 5: for each t ∈ T do 6: for each ¯σ ∈ Σ do 7: b′i ← bi with the script of all units of type t replaced by ¯σ 8: if Ψ(b′i , b-i) > Ψ(bi, b-i) then 9: bi ← b′i 10: if time elapsed is larger than e then 11: return action computed from bi and boolean c 12: c ← true // iterated over all types 13: return action computed from bi and boolean c

to unit u an action that will take it closer to (¯x, ¯ y); Cluster assigns the wait move if the unit is already at (¯x, ¯ y).

The Cluster script allows us to expose a weakness in PGS's evaluation function while dealing with non-offensive scripts. In contrast with NOKAV and Kiter, which include attack actions in their rules, Cluster never assigns an attack action to a unit. We explain why PGS's evaluation function is unable to properly evaluate non-offensive strategies in Section 5.2. Also, we show empirically that the effective use of the Cluster script altogether with NOKAV and Kiter can result in strong gameplay strategies.

5 Stratified Strategy Selection (SSS)

SSS uses a partition of units, which we call a type system, and assigns the same script to units of the same type. For example, all units with low hp-value (type) move away from the battle so that they can survive longer (strategy encoded in a script). A type system is defined as follows.

Definition 1 (Type System) Let Ui be the set of player i's units. T = {t1, . . . , tk} is a type system for Ui if it is a partitioning of Ui. If u ∈ Ui and t ∈ T with u ∈ t, we write T (u) = t.

We describe our type systems in Section 5.1.

Algorithm 1 shows the pseudocode of SSS, which is invoked for deciding player i's action in their decision points throughout the game. SSS performs a hill-climbing search similar to PGS's search (see Churchill and Buro [2013] for details). However, in contrast with PGS, SSS searches in the space of script assignments induced by a type system.

SSS receives as input a set of scripts Σ, a default script ¯σd ∈ Σ, a time limit e, an evaluation function Ψ, and a type system for the units Ui at state s. SSS returns a player action for i (i.e., a vector containing one unit action for each ready unit in s) and a boolean value c indicating whether SSS was able to complete one iteration over the set of types in T. The boolean value c is used by SSS+, as explained in Section 5.3.

SSS starts by initializing vectors bi and b-i with the default script ¯σd; bi and b-i store one script for each ready unit controlled by players i and -i, respectively (in the pseudocode we assume all units in Ui and U-i to be ready). We also assume an arbitrary ordering of the units in Ui and U-i so that the script stored in the first position of bi (resp. b-i), denoted bi[0] (resp. b-i[0]), corresponds to the script of Ui's (resp. U-i) first unit. Vector bi unambiguously define a player action for i. The player action is computed from bi by using bi[0] to compute the unit action of the first unit in Ui, bi[1] to compute the unit action of the second unit and so on.

SSS performs a greedy search to iteratively improve the script assignment of bi (lines 4-9). Namely, SSS evaluates all possible assignments of scripts from Σ to units of a given type t while the script of units with types other than t are fixed. SSS keeps in bi the assignment with largest Ψ-value encountered during search (lines 8 and 9).

The evaluation function Ψ receives bi and b-i as input and estimates the end-game utility assuming player i has taken the action computed from bi and player -i the action computed from b-i. We discuss different evaluation functions in Section 5.2. SSS returns the player action computed from bi once it reaches the time limit e (lines 11 and 13).

Note that vector b-i does not change during search and SSS is effectively searching for a best response to b-i. In theory, players following strategies derived by SSS can be exploited as -i might be able to anticipate that i is computing a best response to b-i and thus compute a best response to i's action. However, due to the problem's size and real-time constraints, it is currently impractical to guess a player's strategy and compute a best response to it. Also, in theory, even if SSS had unlimited time to compute a strategy, an opponent that considers all legal actions during search might be able to exploit player i, as SSS is constrained to the unit actions returned by the scripts. In practice, however, as Churchill and Buro [2013] have shown, one is only able to derive good strategies while accounting for all legal actions in scenarios with very few combat units.

5.1 Type Systems

Since SSS assigns the same script to all units of a given type, it is important that the type system captures important strategic information regarding the game state at hand.

Intuitively, the units' attack range (r), damage (d), and hit points (hp) encode important strategic information. For example, the Kiter script tends to be more effective if employed by units with a large attack range, as it allows the unit to attack and retreat without being hit by the enemy. Similarly, by assigning a less offensive script to units with lower hp-values one might be able to preserve the units longer in the match. We define the canonical type system Tc as follows.

where l is an integer used for mapping u's hp-value into "levels",

We do not use similar mappings for r and d because they are fixed (and thus less diverse) throughout the match.

Example 1 Let u1, u2, and u3 be three units with r = 20, d = 5, hpm = 60, and with hp-values of 10, 15, and 30, respectively. For l = 3, Tc,3(u1) = Tc,3(u2) = (20, 5, 0), but u3 has a different type as Tc,3(u3) = (20, 5, 1).

The parameter l of Tc allows one to create type systems with different granularities. By increasing the value of l one creates larger type systems, thus allowing SSS to find "finer strategies" at the cost of increasing the running time for completing one iteration of SSS's while loop (see Algorithm 1). The granularity of type systems is defined as follows.

Definition 2 (Type Systems Granularity) Let T1, T2 be type systems for Ui. Also, let |T1| and |T2| be the maximum number of types T1 and T2 might have during a match. T1 is finer than T2, denoted T1 ⪯ T2, if |T1| ≥ |T2|.

For example, since the maximum number of different types Tc,3 might have is larger than the maximum number of different types Tc,2 might have in a given match, we say that Tc,3 is finer than Tc,2, or Tc,3 ⪯ Tc,2.

5.2 Evaluation Functions

In this section we discuss different evaluation functions Ψ. The first evaluation we discuss is LTD2, a function introduced by Kovarsky and Buro [2005] that accounts for the unit's hp and how much damage each unit can cause per frame of the game (dpf). The LTD2 of a state s with units U = Ui ∪ U-i is written as follows,

Churchill et al. [2012] introduced a playout-based evaluation that outperforms LTD2. Instead of evaluating the state s directly, their scheme simulates the game from s to a terminal state sf while following a fixed set of scripts for player i, bi, and for player -i, b-i (all player actions in the simulation are computed according to bi and b-i); the LTD2-value of sf is computed and returned as an estimated end-game value of s. PGS uses Churchill et al.'s evaluation function. The drawback of this evaluation scheme is that it incorrectly evaluates actions computed from vectors bi containing non-offensive scripts such as Cluster. This is because the evaluation function assumes that the units will follow the scripts defined in bi in every decision point to the end of the match. This means that one assumes that units following the Cluster script will not attack for the rest of the match, which is unreasonable.

A secondary contribution of this paper is the use of a different evaluation function with PGS. Namely, we use a playoutbased evaluation in which the first joint player action in the simulation is computed from bi and b-i and all the others, to the end of the simulation, are computed according to the NOKAV script. We call PGS with this evaluation function PGS+. SSS and SSS+ also use PGS+'s evaluation scheme. We note that POE's evaluation function is similar to PGS+'s; see Wang et al. [2016] for details.

5.3 SSS with Adaptive Type Systems (SSS+)

Depending on the number and on the diversity of units (e.g., units with different attack ranges) present in the match, SSS might be unable to iterate through all types in T before reaching time limit e. This is because a large diversity of units result in more types being considered during search. Also, the running time of Ψ tends to increase as one increases the number of units in the match as the simulation takes longer.

If SSS is unable to iterate through all types, then it returns moves computed from the default script ¯σd for units u whose type T(u) was not accounted for during search. The assignment of ¯σd might lead to a poor overall strategy as there could be better scripts that were not verified by the algorithm due to the lack of time. Aiming at preventing SSS from not iterating at least once over all types, we developed a meta-reasoning system to adjust the granularity of the type system used. This adjustment occurs in between searches and is based on the estimated running time of a SSS iteration. We call the resulting algorithm SSS+.

Instead of receiving one type system T, SSS+ receives a set of type systems Y = {T1, T2, · · · , TN} with T1 ⪯ T2 ⪯ · · · ⪯ TN. SSS+ starts with T1, the finest type system in Y. If the search returns false while using T1 (see variable c in Algorithm 1), SSS+ replaces T1 by T2 for its next search. If the search returns true while using T2 and the meta-reasoning system estimates that SSS+ will be able to complete an iteration of the algorithm with T1, then it replaces T2 by T1.

In general, let Tj be the type system in Y used in SSS+'s last search. SSS+'s meta-reasoning defines the type system T to be used in its next search as follows.

Here, conditions C1 and C2 are defined as,

Here, ˜ t is an estimate of Ψ's running time and˜ |Tj-1| is an estimate of the number of types in Tj-1. As mentioned before, Ψ's running time varies during the match as the number of units in the game state changes. Thus, ˜ t is estimated as the average running time of the multiple Ψ runs performed in SSS+'s last search. Whenever the meta-reasoning approach changes the type system employed from Tj-1 to a coarser type system Tj we store in memory the number of types of Tj-1 encountered during search, which we use as˜ |Tj-1|.

Condition C1 is satisfied when SSS+ is unable to iterate through all types (¬c) and the current type system being employed is not the coarsest in Y (j < N). Condition C2 is satisfied when SSS+ is able to iterate through all types (c), the current type system being employed is not the finest in Y (j > 1), and the meta-reasoning approach estimates that SSS+ will be able to iterate through all types if using a type system that is finer than the last used (˜ t ט |Tj-1| × |Σ| ≤ e).

6 Empirical Results

We use as our testbed a simulation environment of Blizzard's StarCraft called SparCraft. 2 The unit properties such as hit points, cool-down time, and damage are exactly the same as the original game. However, SparCraft does not implement fog of war, collisions, and unit acceleration (all units move at constant speed) [Churchill and Buro, 2013]. We use SparCraft because, in contrast with the original game, it offers an efficient forward model of the game. All experiments are run on 2.66 GHz machines.

6.1 Combat Scenarios

We experiment with units with different hp, d, and r-values. We use ↑ to denote large and ↓ to denote small hp and dvalues. Also, we call u a melee unit if u's attack range equals zero (r = 0), and we call u a ranged unit if u is able to attack from far (r > 0). Namely, we use the following unit kinds: Zealots (Zea, ↑hp, ↑d, melee), Dragoons (Dra, ↑hp, ↑d, ranged), Zerglings (Ling, ↓hp, ↓d, melee), Marines (Mar, ↓hp, ↓d, ranged). We consider the combat scenarios where each player controls units of the following kinds: (i) Zea; (ii) Zea and Dra; (iii) Zea, Dra, and Ling; and (iv) Zea, Dra, Ling, and Mar. We experiment with matches with as few as 4 units and as many as 56 units on each side. The largest number of units controlled by a player in a typical StarCraft combat is around 50 [Churchill and Buro, 2013].

The units are placed in a walled arena with no obstacles of size 1280 × 780 pixels; the largest unit is approximately 40 × 50 pixels large. The walls ensure finite matches by preventing units from indefinitely moving away from enemies. For each combat scenario we generate 1,000 start states as explained by Churchill and Buro [2013]. Namely, player i's units are placed at a random coordinate to the right of the center of the arena, which we define to be the coordinate (0, 0). Player -i's units are placed at a symmetric position to the left of (0, 0). The coordinates are chosen so that the units are at a distance in between 0 and 128 pixels from (0, 0). Then, to ensure that no unit starts within the attack range of an enemy unit, we add 220 pixels to the x-coordinate of player i's units, and subtract 220 pixels from the x-coordinate of player

2 github.com/davechurchill/ualbertabot/tree/master/SparCraft

-i's units, thus increasing the distance between enemy units by 440 pixels. We present the winning rate over the 1,000 matches for each combat scenario and algorithm tested.

6.2 Configurations of Algorithms Tested

We test PGS [Churchill and Buro, 2013], PGS+ (PGS with our Ψ), POE [Wang et al., 2016], and SSS and SSS+. We also experimented with ABCD [Churchill et al., 2012] and UCTCD [Churchill and Buro, 2013], but both algorithms performed much worse than the others and we omit their results for clarity. All algorithms use the same set Σ = {NOKAV, Kiter, Cluster} of scripts, and have a time limit of 40 milliseconds for each decision point.

PGS and PGS+: Instead of limiting PGS and PGS+ to a fixed number of iterations (the number of times they try to improve their script assignments), as Churchill and Buro [2013] did, we let PGS and PGS+ improve the assignments while there is time available. Also, as suggested by Churchill and Buro, we set PGS's and PGS+'s improvement response parameter to 0; see Churchill and Buro [2013] for details.

POE: We have implemented POE in SparCraft's codebase and tested several configurations of its parameters, including the values suggested by Wang et al. [2016]. The best configuration we found is the following: population size of 36, with the 6 fittest individuals being selected for generating 5 offsprings each. Also, POE uses a playout-based evaluation function that is limited to 25 decision points; see Wang et al. [2016] for details.

SSS and SSS+: For SSSwe use Tc,3 and for SSS+we use Y = {Tc,3, Tc,2, Tc,1, Tc,0, TRGD}, where TRGD is a type system that assigns the same type to two units if they are either both melee or both ranged. Clearly, Tc,3 ⪯ Tc,2 ⪯ Tc,1 ⪯ Tc,0 ⪯ TRGD. We also tested SSS with Tc,2, Tc,1, Tc,0, and TRGD (results are omitted for lack of space); the best overall results for SSS were obtained with Tc,3.

6.3 Discussion

Table 1 shows the winning rate of the row player against the column player for various combat scenarios. For example, for the combat scenario in which each player controls 8 Zealots and 8 Dragoons (Zea 8, Dra 8) SSS wins 92% of the matches against POE. The orange-colored cells in Table 1 show scenarios in which the row player won more than 50% of the 1,000 matches tested; black-colored cells show the results in which SSS and SSS+ differ the most.

POE substantially outperforms PGS in all scenarios tested. Note, however, that PGS+ outperforms both PGS and POE. This is because the evaluation function used with PGS assumes that the script chosen at a given decision point will be used throughout the match. As a result, PGS does not select the non-offensive Cluster script. By contrast, our results suggest that PGS+ is able to effectively select non-offensive strategies and gain strategic advantage over its opponents.

SSS and SSS+'s winning rates are smaller for scenarios with fewer units, e.g., (Zea 4), (Zea 2, Dra 2), (Zea 2, Dra 2, Ling 2), and (Zea 2, Dra 2, Ling 2, Mar 2), but almost always above 50%, with the exception of (Zea 2, Dra 2, Ling 2, Mar 2), where PGS+ won 57% of the matches against both SSS and SSS+. PGS+ is able to outperform SSS and SSS+ because it might be able to evaluate all possible script assignments in scenarios with fewer units, while SSS and SSS+ consider only a subset of the assignments considered by PGS+. Nevertheless, SSS and SSS+ have winning rates usually above 80% in scenarios with more units. Our results show that one is able to find stronger strategies than competing schemes by searching in the space induced by a type system. This suggests that the type system effectively prunes a potentially large and unpromising portion of the game tree by reducing the number of script assignments considered.

SSS and SSS+ present similar results for matches with one, two, and three kinds of units. However, major differences are observed between the two algorithms in scenarios with four kinds of units; these differences are highlighted by the dark cells in Table 1. In such scenarios, due to the large number of types and units, SSS might be unable to iterate through all types within the time limit. As a result, most units follow the default NOKAV script. As the match progresses and units are removed from the game state, the running time of Ψ reduces, which allows SSS to iterate through all types within the time limit. However, by then, the enemy has likely gained an irreversible strategic advantage over SSS.

Figure 1 shows the running time of Ψ throughout the first 150 decision points of player i in a representative (Zea 14, Dra 14, Ling 14, Mar 14) match. The background color shows the type system being used at a given decision point. Here, the darkest color indicates the use of the coarsest TRGD type system, while the lightest color indicates the use of the finest Tc,3. SSS+ quickly switches to the coarsest TRGD type system (depicted by the dark region on the left-hand side of the figure). As the match progresses and the running time of Ψ decreases, the coarsest type system is replaced by finer ones, allowing SSS+ to search in a richer space of possibilities, until it eventually converges to the Tc,3 type system.

SSS+'s automatic type system selection results in major improvements in the (Zea 14, Dra 14, Ling 14, Mar 14) configuration: SSS+ wins 96% and 95% of its matches against POE and PGS+, respectively, while SSS wins only 46% and 16% of the matches against the same opponents. Moreover, in this scenario, SSS+ wins 93% of the matches against SSS.

7 Conclusions and FutureWorks

In this paper we introduced SSS, a search algorithm for RTS combat scenarios that is guided by a type system. We also introduced SSS+, a SSS variant that uses a meta-reasoning approach to automatically choose its type system. Experiments on SparCraft showed that both SSS and SSS+ are able to substantially outperform state-of-the-art algorithms. Also, our results showed that in combat scenarios with a large and diversified number of units SSS+ can outperform SSS.

As future research, we intend to test SSS and SSS+ in games with unit acceleration and collision. Also, Churchill and Buro [2015] showed that a variant of PGS is used in a comercial card game. SSS could also be used to enhance the game's AI so that it might challenge the more skilled players.

Acknowledgements

The author gratefully thank Rubens de O. Moraes Filho, Rob Holte, Anderson Tavares and the anonymous referees of this paper for great suggestions, and David Churchill, Chen Wang and Julian Togelius for kindly answering questions about SparCraft, PGS, and POE. Financial support for this research was provided by Brazil's CAPES CsF, FAPEMIG, and CNPq.