RTS AI Problems and Techniques

Download as pdf or txt
Download as pdf or txt
You are on page 1of 12

R

RTS AI Problems and Techniques deal with the behavior of an artificial player. This
consists among others to learn how to play, to
Santiago Ontañón1, Gabriel Synnaeve2, Alberto have an understanding about the game and its
Uriarte1, Florian Richoux3, David Churchill4 and environment, and to predict and infer game situ-
Mike Preuss5 ations from a context and sparse information.
1
Computer Science Department, Drexel
University, Philadelphia, PA, USA
2
Cognitive Science and Psycholinguistics Introduction
(LSCP) of ENS Ulm, Paris, France
3
Nantes Atlantic Computer Science Laboratory The field of real-time strategy (RTS) game artifi-
(LINA), University of Nantes, Nantes, France cial intelligence (AI) has advanced significantly
4
Computing Science Department, University of in the past few years, partially thanks to compe-
Alberta, Edmonton, AB, Canada titions such as the “ORTS RTS Game AI Com-
5
Information Systems and Statistics, petition” (held from 2006 to 2009), the “AIIDE
Westfälische Wilhelms-Universität Munster, StarCraft AI Competition” (held since 2010), and
M€unster, Germany the “CIG StarCraft RTS AI Competition” (held
since 2011). Based on the work presented in
Othman et al. (2012), here we first define RTS
Synonyms games, then list the open problems in creating AI
for RTS games, and finally point to the
AI; Artificial intelligence; Game AI; Real-time approaches that have been proposed to address
strategy games; RTS games these problems.

Definition Real-Time Strategy Games

Real-time strategy (RTS) games is a subgenre of From a theoretical point of view, the main differ-
strategy games where players need to build an ences between RTS games and traditional board
economy (gathering resources and building a games such as Chess are:
base) and military power (training units and
researching technologies) in order to defeat their – RTS games are simultaneous move games,
opponents (destroying their army and base). Arti- where more than one player can issue actions
ficial intelligence problems related to RTS games at the same time.
# Springer International Publishing Switzerland 2015
N. Lee (ed.), Encyclopedia of Computer Graphics and Games,
DOI 10.1007/978-3-319-08234-9_17-1
2 RTS AI Problems and Techniques

– Actions in RTS games are durative, i.e., In the past few years, StarCraft: Brood War
actions are not instantaneous, but take some (an immensely popular RTS game released in
amount of time to complete. 1998 by Blizzard Entertainment) has become
– RTS games are “real time,” which actually the standard testbed for evaluating AI techniques
means that each player has a very small amount in RTS games. StarCraft is set in a science-
of time to decide the next move and that, in fiction-based universe where the player must
contrast to turn-based games, the game keeps choose one of the three races: Terran, Protoss,
advancing even if a player does not execute or Zerg. In order to win a StarCraft game, players
any actions. Compared to Chess, where players must first gather resources (minerals and Vespene
may have several minutes to decide the next gas). As resources become available, players
action, in StarCraft, a popular RTS game, the need to allocate them for creating more buildings
game executes at 24 frames per second, which (which reinforce the economy and allow players
means that players can act as fast as every to create units or unlock stronger units), research
42 ms, before the game state changes. new technologies (in order to use new unit abili-
– Most RTS games are partially observable: ties or improve the units), and train attack units.
players can only see the part of the map that Units must be distributed to accomplish different
has been explored. This is referred to as the fog tasks such as reconnaissance, defense, and attack.
of war. While performing all of those tasks, players also
– Most RTS games are nondeterministic: some need to strategically understand the geometry of
actions have a chance of success, and the the map at hand, in order to decide where to place
amount of damage dealt by different units is new buildings (concentrate in a single area or
sometimes stochastic. expand to different areas) or where to set defen-
– And, finally, the complexity of these games, sive outposts. Finally, when offensive units of
both in terms of state space size and in terms of two players meet, each player must quickly
number of actions available at each decision maneuver each of the units in order to fight a
cycle, is very large. For example, the state battle, which requires quick and reactive control
space of Chess is typically estimated to be of each of the units.
around 1050, heads up no-limit Texas holdem From a theoretical point of view, the state
poker around 1080, and Go around 10170. In space of a StarCraft game for a given map is
comparison, the state space of StarCraft in a enormous. For example, consider a typical
typical map is estimated to be many orders of 128  128 map. At any given moment, there
magnitude larger than any of those, as might be between 50 and 400 units in the map,
discussed in the next section. each of which might have a complex internal
state (remaining energy and hit points, action
For those reasons, standard techniques used being executed, etc.). This quickly leads to an
for playing classic board games, such as game immense number of possible states (way beyond
tree search, cannot be directly applied to solve the size of smaller games, such as Chess or Go).
RTS games without the definition of some level For example, just considering the location of each
of abstraction or some other simplification. Inter- unit (with 128  128 possible positions per unit),
estingly enough, humans seem to be able to deal and 400 units, gives us an initial number of
with the complexity of RTS games and are still 16384400  101685. If we add the other factors
vastly superior to computers in these types of playing a role in the game, such as resources, hit
games (Buro and Churchill 2012). For those rea- points, energy, research status, cool-down timers,
sons, a large spectrum of techniques have been etc., we obtain even larger numbers (see Othman
attempted to deal with this domain, as we will et al. (2012) for a more in-depth description of the
describe below. complexity of StarCraft).
RTS AI Problems and Techniques 3

Challenges in RTS Game AI – In-game learning: How can bots deploy online
learning techniques that allow them to
Early research in AI for RTS games (Buro 2003) improve their game play while playing a
identified the following six challenges: resource game? These techniques might include rein-
management, decision making under uncertainty, forcement learning techniques, but also oppo-
spatial and temporal reasoning, collaboration nent modeling. The main problem again is the
(between multiple AIs), opponent modeling and fact that the state space is too large and the fact
learning, and adversarial real-time planning. that RTS games are partially observable.
While there has been a significant work in many, – Inter-game learning: What can be learned
others have been untouched (e.g., collaboration). from one game that can be used to increase
Moreover, recent research in this area has identi- the chances of victory in the next game? Some
fied several additional research challenges, such work has used simple game-theoretical solu-
as how to exploit the massive amounts of existing tions to select among a pool of predefined
domain knowledge (strategies, build orders, strategies, but the general problem remains
replays, and so on). Thus, the challenges in RTS unsolved.
game AI can be grouped in six main different
areas, described below. Uncertainty Adversarial planning under
Planning As mentioned above, the size of the uncertainty in domains of the size of RTS
state space in RTS games is much larger than that games is still an unsolved challenge. In RTS
of traditional board games such as Chess or games, there are two main kinds of uncertainty.
Go. Additionally, the number of actions that can First, the game is partially observable, and
be executed at a given instant of time is also much players cannot observe the whole game map
larger. Thus, standard adversarial planning (like in Chess) but need to scout in order to see
approaches, such as game tree search, are not what the opponent is doing. This type of uncer-
directly applicable. As we elaborate later, plan- tainty can be lowered by good scouting and
ning in RTS games can be seen as having multi- knowledge representation (to infer what is possi-
ple levels of abstraction: at a higher level, players ble given what has been seen). However, scouting
need long-term planning capabilities, in order to also means deliberately reducing economic pro-
develop a strong economy in the game; at a low gress in order to obtain information. Second,
level, individual units need to be moved in coor- there is also uncertainty arising from the fact
dination to fight battles taking into account the that the games are adversarial, and a player can-
terrain and the opponent. Techniques that can not predict the actions that the opponent(s) will
address these large planning problems by either execute. For this type of uncertainty, the AI, as
sampling or hierarchical decomposition do not the human player, can only build a sensible model
yet exist. of what the opponent is likely to do.
Learning Given the difficulties in playing by Spatial and Temporal Reasoning Spatial
directly using adversarial planning techniques, reasoning is related to each aspect of terrain
many research groups have turned attention to exploitation. It is involved in tasks such as build-
learning techniques. We can distinguish three ing placement or base expansion. In the former,
types of learning problems in RTS games: the player needs to carefully consider building
positioning into its own bases to both protect
– Prior learning: How can we exploit available them by creating defenses or walls against inva-
data, such as existing replays, or information sions and to avoid bad configurations where large
about specific maps for learning appropriate units could be stuck. In base expansion, the player
strategies before hand? A significant amount has to choose good available locations to build a
of work has gone in this direction. new base, regarding its own position and
4 RTS AI Problems and Techniques

opponent’s bases. Finally, spatial reasoning is – Reactive control: is the implementation of tac-
key to tactical reasoning: players need to decide tics. This consists in moving, targeting, firing,
where to place units for battle, favoring, for fleeing, and hit-and-run techniques (also
instance, engagements when the opponent’s known as “kiting”) during battle. Reactive
units are lead into a bottleneck. control focuses on a specific unit.
Analogously, temporal reasoning is key in – Terrain analysis: consists in the analysis of
tactical or strategic reasoning. For example, regions composing the map: choke points,
timing attacks and retreats to gain an advantage. minerals and gas emplacements, low and
At a higher strategic level, players need to reason high walkable grounds, islands, etc.
about when to perform long-term impact eco- – Intelligence gathering: corresponds to infor-
nomic actions such as upgrades, building con- mation collected about the opponent. Because
struction, strategy switching, etc. all taking into of the fog of war, players must regularly send
account that the effects of these actions are not scouts to localize and spy enemy bases.
immediate but longer term.
Domain Knowledge Exploitation In tradi- In comparison, when humans play StarCraft,
tional board games such as Chess, researchers they typically divide their decision making in a
have exploited the large amounts of existing very different way. The StarCraft community
domain knowledge to create good evaluation func- typically talks about two tasks:
tions to be used by alpha-beta search algorithms,
extensive opening books, or end-game tables. In – Micro: is the ability to control units individu-
the case of RTS games, it is still unclear how the ally (roughly corresponding to reactive con-
significantly large amount of domain knowledge trol above and part of tactics). A good micro
(in the forms or strategy guides, replays, etc.) can player usually keeps their units alive over a
be exploited. Most work in this area has focused on longer period of time.
two main directions: (1) hard-coding existing – Macro: is the ability to produce units and to
strategies into bots (so that bots only need to expand at the appropriate times to keep your
decide which strategies to deploy, instead of hav- production of units flowing (roughly
ing to solve the complete planning problem) and corresponding to everything but reactive con-
(2) mining large datasets of replays (Synnaeve trol and part of tactics above). A good macro
et al. 2012a; Weber and Mateas 2009) to automat- player usually has the larger army.
ically extract strategies, trends, or plans.
Task Decomposition Most existing The reader can find a good presentation of task
approaches to play RTS games work by decomposition RTS game AI in Weber
decomposing the problem into a collection of et al. (2011a). Although the previous task decom-
smaller problems to be solved independently. position is common, other task decompositions
Specifically, a common subdivision is: have been explored (see Othman et al. (2012) for
an overview of the task decomposition used by
– Strategy: corresponds to the high-level several StarCraft bots).
decision-making process. This is the highest
level of abstraction for the game comprehen-
sion. Finding an efficient strategy or
counterstrategy against a given opponent is Existing Work on RTS Game AI
key in RTS games and concerns the whole
set of units a player owns. Systems that play RTS games need to address
– Tactics: are the implementation of the current most, if not all, the aforementioned problems
strategy. It implies army and building posi- together. Therefore, it is hard to classify existing
tioning, movements, timing, and so work on RTS AI as addressing the different prob-
on. Tactics concerns a group of units. lems above. For that reason, we will divide it
RTS AI Problems and Techniques 5

RTS AI Problems
and Techniques, Strategic Tactical Reactive Control
Fig. 1 RTS AI levels of High Level, Abstract Mid-Level Low-Level, Concrete
abstraction and typical 3 mins + 3 sec - 1 min ∼ 1 sec
subproblems associated
with them: Timings Knowledge
Scouting
correspond to an estimate & Learning
of the duration of a
Opponent
behavior switch in
Modeling
StarCraft
Strategic
stance

Army Combat Timing Unit


Composition & Position Micro

Bulid-Order Unit & Building Multi-Agent


Planning Placement Pathfinding

according to three levels of abstraction: strategy techniques, like hard-coded approaches, plan-
(which loosely corresponds to “macro”), tactics, ning, or machine learning. We cover each of
and reactive control (which loosely corresponds these approaches in turn.
to “micro”). Hard-Coded Approaches They have been
Figure 1 illustrates how strategy, tactics, and extensively used in commercial RTS games.
reactive control are three points in a continuum The most common ones use finite state machines
scale where strategy corresponds to decision- (FSM) (Houlette and Fu 2003) in order to let the
making processes that affect long spans of time AI author hard-code the strategy that the AI will
(several minutes in the case of StarCraft), reactive employ. The idea behind FSMs is to decompose
control corresponds to low-level second-by-second the AI behavior into easily manageable states,
decisions, and tactics sit in the middle. Also, stra- such as “attacking,” “gathering resources,” or
tegic decisions reason about the whole game at “repairing,” and establish the conditions that trig-
once, whereas tactical or reactive control decisions ger transitions between them. Commercial
are localized and affect only specific groups of approaches also include hierarchical FSMs, in
units. Typically, strategic decisions constrain which FSMs are composed hierarchically. These
future tactical decisions, which in turn condition hard-coded approaches have achieved a signifi-
reactive control. Moreover, information gathered cant amount of success and have also been used
while performing reactive control can cause recon- in many academic RTS AI research systems.
sideration of the tactics being employed, which However, these hard-coded approaches struggle
could trigger further strategic reasoning. to encode dynamic, adaptive behaviors and are
The remainder of this section presents work easily exploitable by adaptive opponents.
toward addressing the previous six open RTS Planning Approaches using planning tech-
game AI problems, grouped as work focused niques have also been explored in the literature.
toward strategy, tactics, or reactive control, as well For example, Ontañón et al. (2008) explored the
as a final section dedicated to holistic approaches use of real-time case-based planning (CBP) in the
that attempt to deal with all three levels at once. domain of Wargus (a Warcraft II clone). In their
work, they used human demonstration to learn
plans, which are then composed at run-time in
Strategy order to form full-fledged strategies to play the
game. In Mishra et al. (2008), they improve over
In the context of RTS games, high-level strategic their previous CBP approach by using situation
reasoning has been addressed using many AI assessment for improving the quality and speed
6 RTS AI Problems and Techniques

of plan retrieval. Hierarchical task network (2008) based their work on Aha et al.’s CBR
(HTN) planning has also been explored with model (Aha et al. 2005) and used StarCraft
some success in the context of simpler first- replays to construct states and building sequences
person shooter games (Hoang et al. 2005). Plan- (“build orders”). Schadd et al. (2007) applied a
ning approaches offer more adaptivity of the AI CBR approach to opponent modeling through
strategy compared to hard-coded approaches. hierarchically structured models of the opponent
However, the real-time constraints of RTS behavior, and they applied their work to the
games limit the planning approaches that can be Spring RTS game (a “Total Annihilation”
applied, HTN and case-based planning being the clone). Jaidee et al. (2011) study the use of CBR
only ones explored so far. Moreover, none of for automatic goal selection while playing an
these approaches address any timing or schedul- RTS game. These goals will then determine
ing issues, which are key in RTS games. One which Q-tables to be used in a reinforcement
notable exception is the work of Churchill and learning framework. Finally, Čertický
Buro (2011), who used planning in order to con- et al. (2013) used CBR to build their army,
struct its economic build orders, taking into based on the opponent’s army composition, and
account timing constraints of the different they pointed out on the importance of proper
actions. scouting for better results.
Machine Learning Concerning machine Scouting One final consideration concerning
learning-based approaches, Weber and Mateas strategy is that RTS games are typically partially
(2009) proposed a data mining approach to strat- observable. Games like StarCraft implement the
egy prediction and performed supervised learning “fog of war” idea, which basically means that a
on labeled StarCraft replays. Dereszynski player can only see the areas of the map close to
et al. (2011) used hidden Markov models her own units. Areas of the map away from the
(HMM) to learn the transition probabilities of field of view of individual units are not observ-
sequences of building construction orders and able. Players need to scout in order to obtain
kept the most probable ones to produce probabi- information about the opponent’s strategy. The
listic behavior models (in StarCraft). Synnaeve size of the state space in StarCraft prevents solu-
and Bessiére (2011a) used the dataset of Weber tions based on POMDPs from being directly
and Mateas (2009) and presented a Bayesian semi- applicable, and very few of the previous
supervised model to learn from replays and predict approaches deal with this problem. Much work
openings (early game strategies) from StarCraft in RTS game AI assumes perfect information all
replays. The openings are labeled by EM cluster- the time. For example, in the case of commercial
ing considering appropriate features. Then, in games, most AI implementations cheat, since the
Synnaeve and Bessiére (2011b), they presented AI can see the complete game map at all times,
an unsupervised learning Bayesian model for while the human player does not. In order to make
tech-tree prediction, still using replays. Finally, the human player believe the AI of these games
evolutionary approaches to determine priorities does not cheat, sometimes they simulate some
of high-level tasks were explored by Young and scouting tasks as Bob Fitch described in his
Hawes in their QUORUM system (Young and AIIDE 2011 keynote for the WarCraft and
Hawes 2012), showing improvement over static StarCraft game series. Even if the StarCraft AI
priorities. competition enforces fog of war, which means
Case-Based Reasoning Also falling into the that bots are forced to work under partial infor-
machine learning category, a significant group of mation, little published research exists on this
researchers has explored case-based reasoning topic. A notable exception is the work of Weber
(CBR) (Aamodt and Plaza 1994) approaches for et al. (2011b), who used a particle model with a
strategic decision making. For example, Aha linear trajectory update to track opponent units
et al. (2005) used CBR to perform dynamic plan under fog of war in StarCraft. They also produced
retrieval in the Wargus domain. Hsieh and Sun tactical goals through reactive planning and goal-
RTS AI Problems and Techniques 7

driven autonomy (Weber et al. 2010a, b), finding Machine Learning Concerning tactical deci-
the more relevant goal(s) to spawn in unforeseen sion making, many different approaches have been
situations. explored such as machine learning or game tree
search. Hladky and Bulitko (2008) benchmarked
hidden semi-Markov models (HSMM) and parti-
Tactics cle filters for unit tracking. Although they used
first-person shooter (FPS) games for their experi-
We will divide the work on midrange tactical mentation, the results apply to RTS games as well.
reasoning in RTS games in two large groups: They showed that the accuracy of occupancy maps
spatial reasoning and decision making (that has was improved using movement models (learned
been addressed both using machine learning and from the player behavior) in HSMM. Kabanza
game tree search). et al. (2010) improve the probabilistic hostile
Spatial Reasoning The most common form of agent task tracker (PHATT (Geib and Goldman
spatial reasoning in the literature of RTS games is 2009), a simulated HMM for plan recognition) by
terrain analysis. Terrain analysis supplies the AI encoding strategies as HTN, used for plan and
with structured information about the map. This intent recognition to find tactical opportunities.
analysis is usually performed off-line, in order to Sharma et al. (2007) combined CBR and rein-
save CPU time during the game. For example, forcement learning to enable reuse of tactical
Pottinger (2000) described the BANG engine plan components. Cadena and Garrido (2011)
implemented by Ensemble Studios for the game used fuzzy CBR (fuzzy case matching) for strate-
Age of Empires II. This engine provides terrain gic and tactical planning. Synnaeve and Bessièere
analysis functionalities to the game using influ- (2012b) combined space abstraction into regions
ence maps and areas with connectivity informa- from Perkins (2010) and tactical decision making
tion. Forbus et al. (2002) showed the importance by assigning scores (economical, defenses, etc.) to
to have qualitative spatial information for war regions and looking for their correspondences to
games, for which they used geometric and path- tactical moves (attacks) in pro-gamer replays.
finding analysis. Hale et al. (2008) presented a 2D Finally, Miles and Louis (2006) created the idea
geometric navigation mesh generation method of IMTrees, a tree where each leaf node is an
from expanding convex regions from seeds. influence map, and each intermediate node is a
Finally, Perkins (2010) applied Voronoi decom- combination operation (sum, multiplication);
position (then pruning) to detect regions and rel- Miles used evolutionary algorithms to learn
evant choke points in RTS maps. This approach is IMTrees for each strategic decision in the game
implemented for StarCraft in the BWTA (http:// involving spatial reasoning by combining a set of
eode.google.eom/p/bwta/) library, used by most basic influence maps.
state of the art StarCraft bots. Game Tree Search These techniques have
Another form of spatial reasoning that has also been explored for tactical decision making.
been studied in RTS games is walling. Walling Churchill et al. (2012a) presented the ABCD
is the act of intentionally placing buildings at the algorithm (Alpha-Beta Considering Durations),
entrance of your base to block the path and to a game tree search algorithm for tactical battles
prevent the opponent’s units from getting inside. in RTS games. Chung et al. (2005) applied Monte
This technique is used by human StarCraft Carlo planning to a capture-the-flag version of
players to survive early aggression and earn Open RTS. Balla and Fern (2009) applied the
time to train more units. Čertický addressed this UCT algorithm (a Monte Carlo Tree Search algo-
constraint satisfaction problem using answer set rithm) to tactical assault planning in Wargus. To
programming (ASP) (Čertický 2013). Richoux make game tree search applicable at this level,
et al. (2014) presented an alternative approach abstract game state representations are used in
based on constraint programming and local order to reduce the complexity. Uriarte and
search, designed to be run-time. Ontañón (2014) explored different game state
8 RTS AI Problems and Techniques

abstractions in the context of Monte Carlo Tree Machine Learning There has been a signifi-
Search for high-level tactical reasoning in cant amount of work on using machine learning
StarCraft. Other algorithms, such as Greedy Port- techniques for the problem of reactive control.
folio Search (Churchill et al. 2012a), perform Bayesian modeling has been applied to inverse
abstraction at the level of actions, by employing fusion of the sensory inputs of the units
a collection of predefined “scripts” and using (Synnaeve and Bessiere 2011c), which subsumes
these scripts as the possible actions that the potential fields, allowing for integration of tacti-
players can execute in the context of game tree cal goals directly in micromanagement.
search. Additionally, there have been some interesting
uses of reinforcement learning (RL) (Sutton and
Barto 1998): Wender and Watson (2012) evalu-
Reactive Control ated the different major RL algorithms for
(decentralized) micromanagement, which perform
Reactive control has been addressed mainly via all equally. Marthi et al. (2005) employ concurrent
the application of potential fields or by using hierarchical Q-learning (units’ Q-functions are
machine learning to learn good control policies. combined at the group level) RL to efficiently
We also include work on pathfinding as part of control units in a “one robot with multiple effec-
reactive control. tors” fashion. Madeira et al. (2006) advocate the
Potential Fields Potential fields and influence use of prior domain knowledge to allow faster RL
maps have been found to be useful techniques for learning and applied their work on a turn-based
reactive decision making. Some uses of potential strategy game. This is because the action space to
fields in RTS games are avoiding obstacles explore is gigantic for real game setups. It requires
(navigation), avoiding opponent fire (Uriarte exploiting the existing structure of the game in a
and Ontañón 2012), or staying at maximum partial program (or a partial Markov decision pro-
shooting distance (Hagelbäck and Johansson cess) and a shape function (or a heuristic) (Marthi
2009). Potential fields have also been combined et al. 2005). Another approach has been proposed
with A* pathfinding to avoid local traps by Jaide and Muñoz-Avila (2012) through learn-
(Hagelbäck 2012). Hagelbäck and Johansson ing just one Q-function for each unit type, in order
(2008) presented a multi-agent potential field- to cut down the search space. Other approaches
based bot able to deal with fog of war in the that aim at learning the parameters of an underly-
Tankbattle game. Avery et al. (2009) and Smith ing model have also been explored. For example,
et al. (2010) coevolved influence map trees for Ponsen and Spronck (2004) used evolutionary
spatial reasoning in RTS games. Danielsiek learning techniques, but face the same problem
et al. (2008) used influence maps to achieve intel- of dimensionality. For example, evolutionary opti-
ligent squad movement to flank the opponent in mization by simulating fights can easily be
an RTS game. Despite their success, a drawback adapted to any parameter-dependent microman-
for potential field-based techniques is the large agement control model, as shown by Othman
number of parameters that has to be tuned in et al. (2012) which optimizes an AIIDE 2010
order to achieve the desired behavior. micromanagement competition bot.
Approaches for automatically learning such Finally, approaches based on game tree search
parameters have been explored, for example, are recently being explored for micromanage-
using reinforcement learning (Liu and Li 2008) ment. Churchill et al. (2012b) presented a variant
or self-organizing maps (SOM) (Preuss of alpha-beta search capable of dealing with
et al. 2010). We would like to note that potential simultaneous moves and durative actions, which
fields are a reactive control technique, and, as could handle reactive control for situations with
such, they do not perform any form of lookahead. up to eight versus eight units.
As a consequence, these techniques are prone to Other research falling into reactive control has
make units stuck in local optima. been performed in the field of cognitive science,
RTS AI Problems and Techniques 9

where Wintermute et al. (2007) have explored smaller, separate problems achieve better results in
humanlike attention models (with units grouping practice. However, holistic approaches, based, for
and vision of a unique screen location) for reac- example, on Monte Carlo Tree Search, have only
tive control. been explored in the context of smaller-scale RTS
Pathfinding Finally, although pathfinding games (Ontañón 2013). Techniques that scale up to
does not fall under our previous definition of reac- large RTS games as StarCraft are still not available.
tive control, we include it in this section, since it is A related problem is that of integrating rea-
typically performed as a low-level service, not soning at multiple levels of abstraction.
part of either tactical or strategical reasoning Molineaux et al. (2008) showed that the difficulty
(although there are some exceptions, like the tac- of working with multi-scale goals and plans can
tical pathfinding of Danielsiek et al. (2008)). The be handled directly by case-based reasoning
most common pathfinding algorithm is A*, but its (CBR), via an integrated RL/CBR algorithm
big problem is CPU time and memory consump- using continuous models. Reactive planning
tion, hard to satisfy in a complex, dynamic, real- (Weber et al. 2010b), a decompositional planning
time environment with large numbers of units. similar to hierarchical task networks (Hoang
Even if specialized algorithms, such as D*-Lite et al. 2005), allows for plans to be changed at
(Koenig and Likhachev 2002) exist, it is most different granularity levels and so for multi-scale
common to use A* combined with a map simpli- (hierarchical) goal integration of low-level con-
fication technique that generates a simpler navi- trol. Synnaeve and Bessière (2011c) achieve hier-
gation graph to be used for pathfinding. An archical goal (coming from tactical decisions)
example of such technique is Triangulation integration through the addition of another sen-
Reduction A* that computes polygonal triangula- sory input corresponding to the goal’s objective.
tions on a grid-based map (Demyen and Buro
et al. 2006). Considering movement for groups
of units, rather than individual units, techniques
Conclusions
such as steering of flocking behaviors (Reynolds
1999) can be used on top of a pathfinding algo-
This entry has defined real-time strategy (RTS)
rithm in order to make whole groups of units
games from an AI point of view and summarized
follow a given path. In recent commercial RTS
the set of open problems in RTS game AI. After
games like StarCraft 2 or Supreme Commander
that, we have summarized existing work toward
2, flocking-like behaviors are inspired of contin-
addressing those problems.
uum crowds (“flow field”) (Treuille et al. 2006).
RTS games can be seen as a simulation of real
A comprehensive review about (grid-based) path-
complex dynamic environments, in a finite and
finding was recently done by Sturtevant (2012).
smaller world, but still complex enough to study a
series of key interesting problems. Finding effi-
cient techniques for tackling these problems on
Holistic Approaches
RTS games can thus benefit other AI disciplines
and application domains and also have concrete
Finally, holistic approaches to address RTS AI
and direct applications in the ever-growing indus-
attempt to address the whole problem using a single
try of video games.
unified method. To the best of our knowledge, with
a few exceptions, such as the Darmok system
(Ontañón et al. 2010) (which uses a combination
of case-based reasoning and learning from demon- Cross-References
stration) or ALisp (Marthi et al. 2005), there has not
been much work in this direction. The main reason ▶ Computer Go
is that the complexity of RTS games is too large, ▶ Monte Carlo Tree Search
and approaches that decompose the problem into ▶ StarCraft Bots and Competitions
10 RTS AI Problems and Techniques

References and Further Reading Dereszynski, E., Hostetler, J., Fern, A., Hoang, T.D.T.T.,
Udarbe, M.: Learning probabilistic behavior models in
Aamodt, A., Plaza, E.: Case-based reasoning: founda- real-time strategy games. In: AAAI (ed.) Artificial
tional issues, methodological variations, and system Intelligence and Interactive Digital Entertainment
approaches. Artif. Intell. Commun. 7(1), 39–59 (1994) (AIIDE), Palo Alto, USA (2011)
Aha, D.W., Molineaux, M., Ponsen, M.J.V.: Learning to Forbus, K.D., Mahoney, J.V., Dill, K.: How qualitative
win: case-based plan selection in a real-time strategy spatial reasoning can improve strategy game AIs.
game. In: ICCBR, pp. 5–20. Chicago, USA (2005) IEEE Intell. Syst. 17, 25–30 (2002). doi:10.1109/
Avery, P., Louis, S., Avery, B.: Evolving coordinated MIS.2002.1024748
spatial tactics for autonomous entities using influence Geib, C.W., Goldman, R.P.: A probabilistic plan recogni-
maps. In: Proceedings of the 5th International Confer- tion algorithm based on plan tree grammars. Artif.
ence on Computational Intelligence and Games, Intell. 173, 1101–1132 (2009)
pp. 341–348. CIG ’09. IEEE Press, Piscataway. http:// Hagelbäck, J.: Potential-field based navigation in starcraft.
dl.acm.org/citation.cfm?id=1719293.1719350 (2009) In: CIG (IEEE), Granada, Spain (2012)
Balla, R.K., Fern, A.: Uct for tactical assault planning in Hagelbäck, J., Johansson, S.J.: Dealing with fog of war in
real-time strategy games. In: International Joint Con- a real time strategy game environment. In: CIG
ference of Artificial Intelligence, IJCAI, pp. 40–45. (IEEE), pp. 55–62. Perth, Australia (2008)
Morgan Kaufmann Publishers, San Francisco (2009) Hagelbäck, J., Johansson, S.J.: A multiagent potential
Buro, M.: Real-time strategy games: a new AI research field-based bot for real-time strategy games. Int.
challenge. In: IJCAI 2003, International Joint Confer- J. Comput. Games Technol. 2009, 4:1–4:10 (2009)
ences on Artificial Intelligence, pp. 1534–1535. Aca- Hale, D.H., Youngblood, G.M., Dixit, P.N.:
pulco, Mexico (2003) Automatically-generated convex region decomposi-
Buro, M., Churchill, D.: Real-time strategy game compe- tion for real-time spatial agent navigation in virtual
titions. AI Mag. 33(3), 106–108 (2012) worlds. Artificial Intelligence and Interactive Digital
Cadena, P., Garrido, L.: Fuzzy case-based reasoning for Entertainment AIIDE, pp. 173–178. http://www.aaai.
managing strategic and tactical reasoning in StarCraft. org/Papers/AIIDE/2008/AIIDE08-029.pdf (2008)
In: Batyrshin, I.Z., Sidorov, G. (eds.) MICAI (1). Lec- Hladky, S., Bulitko, V.: An evaluation of models for
ture Notes in Computer Science, vol. 7094, predicting opponent positions in first-person shooter
pp. 113–124. Springer, Puebla (2011) video games. In: CIG (IEEE), Perth, Australia (2008)
Čertický, M.: Implementing a wall-in building placement Hoang, H., Lee-Urban, S., Muñoz-Avila, H.: Hierarchical
in starcraft with declarative programming CoRR abs/ plan representations for encoding strategic game ai. In:
1306.4460 (2013). http://arxiv.org/abs/1306.4460 AIIDE, pp. 63–68. Marina del Rey, USA (2005)
Čertický, M., Čertický, M.: Case-based reasoning for Houlette, R., Fu, D.: The ultimate guide to FSMs in games.
army compositions in real-time strategy games. In: In: AI Game Programming Wisdom 2, Charles River
Proceedings of Scientific Conference of Young Media, Hingham, MA, USA (2003)
Researchers, pp. 70–73. Baku, Azerbaijan (2013) Hsieh, J.L., Sun, C.T.: Building a player strategy model by
Chung, M., Buro, M., Schaeffer, J.: Monte Carlo planning analyzing replays of real-time strategy games. In:
in RTS games. In: IEEE Symposium on Computa- IJCNN, pp. 3106–3111. Hong Kong (2008)
tional Intelligence and Games (CIG), Colchester, UK Jaidee, U., Muñoz-Avila, H., Aha, D.W.: Case-based
(2005). learning in goal-driven autonomy agents for real-time
Churchill, D., Buro, M.: Build order optimization in strategy combat tasks. In: Proceedings of the ICCBR
starcraft. In: Proceedings of AIIDE, pp. 14–19. Palo Workshop on Computer Games, pp. 43–52. Green-
Alto, USA (2011) wich, UK (2011)
Churchill, D., Saffidine, A., Buro, M.: Fast heuristic Jaidee, U., Muñoz-Avila, H.: Classq-l: A q-learning algo-
search for RTS game combat scenarios. In: AIIDE, rithm for adversarial real-time strategy games. In:
Palo Alto, USA (2012a) Eighth Artificial Intelligence and Interactive Digital
Churchill, D., Saffidine, A., Buro, M.: Fast heuristic Entertainment Conference, Palo Alto, USA (2012)
search for RTS game combat scenarios. In: Artificial Kabanza, F., Bellefeuille, P., Bisson, F., Benaskeur, A.R.,
Intelligence and Interactive Digital Entertainment Irandoust, H.: Opponent behaviour recognition for
Conference (AIIDE 2012) (2012b) real-time strategy games. In: AAAI Workshops,
Danielsiek, H., Stuer, R., Thom, A., Beume, N., Naujoks, Atlanta, USA (2010)
B., Preuss, M.: Intelligent moving of groups in real- Koenig, S., Likhachev, M.: D*lite. In: AAAI/IAAI,
time strategy games. In: 2008 I.E. Symposium on pp. 476–483. Edmonton, Canada (2002)
Computational Intelligence and Games, pp. 71–78. Liu, L., Li, L.: Regional cooperative multi-agent
Perth, Australia (2008) q-learning based on potential field. In: Natural Com-
Demyen, D., Buro, M.: Efficient triangulation-based path- putation, 2008. ICNC’08. Fourth International Confer-
finding. In: Proceedings of the 21st National Confer- ence on, vol. 6, pp. 535–539. IEEE (2008)
ence on Artificial intelligence, vol. 1, pp. 942–947. Madeira, C., Corruble, V., Ramalho, G.: Designing a
Boston, USA (2006) reinforcement learning-based adaptive AI for large-
RTS AI Problems and Techniques 11

scale strategy games. In: AI and Interactive Digital Schadd, F., Bakkes, S., Spronck, P.: Opponent modeling
Entertainment Conference, AIIDE (AAAI), Marina in real-time strategy games. In: GAMEON, pp. 61–70.
del Rey, USA (2006) Bologna, Italy (2007)
Marthi, B., Russell, S., Latham, D., Guestrin, C.: Concur- Sharma, M., Holmes, M., Santamaria, J., Irani, A., Isbell,
rent hierarchical reinforcement learning. In: Interna- C.L., Ram, A.: Transfer learning in real-time strategy
tional Joint Conference of Artificial Intelligence, games using hybrid CBR/RL. In: International Joint
IJCAI, pp. 779–785. Edinburgh, UK (2005) Conference of Artificial Intelligence, IJCAI, Hydera-
Miles, C.E.: Co-evolving real-time strategy game players. bad, India (2007)
ProQuest (2007) Smith, G., Avery, P., Houmanfar, R., Louis, S.: Using
Miles, C., Louis, S.J.: Co-evolving real-time strategy co-evolved RTS opponents to teach spatial tactics.
game playing influence map trees with genetic algo- In: CIG (IEEE), Copenhagen, Denmark (2010)
rithms. In: Proceedings of the International Congress Sturtevant, N.: Benchmarks for grid-based pathfinding.
on Evolutionary Computation, Portland (2006) Transactions on Computational Intelligence and AI
Mishra, K., Ontañón, S., Ram, A.: Situation assessment in Games. http://web.cs.du.edu/sturtevant/papers/
for plan retrieval in real-time strategy games. In: benchmarks.pdf (2012)
ECCBR, pp. 355–369. Trier, Germany (2008) Sutton, R.S., Barto, A.G.: Reinforcement Learning: An
Molineaux, M., Aha, D.W., Moore, P.: Learning continu- Introduction (Adaptive Computation and Machine
ous action models in a real-time strategy strategy envi- Learning). The MIT Press, Cambridge, MA (1998)
ronment. In: FLAIRS Conference, pp. 257–262. Synnaeve, G., Bessiere, P.: A Bayesian model for opening
Coconut Grove, USA (2008) prediction in RTS games with application to StarCraft.
Ontañón, S.: The combinatorial multi-armed bandit prob- In: Proceedings of 2011 I.E. CIG, p. 000. Seoul, Corée,
lem and its application to real-time strategy games. In: République De, Seoul, South Korea (2011a)
AIIDE, Boston, USA (2013) Synnaeve, G., Bessière, P.: A Bayesian model for plan
Ontañón, S., Mishra, K., Sugandh, N., Ram, A.: Learning recognition in RTS games applied to StarCraft. In:
from demonstration and case-based planning for real- AAAI (ed.) Proceedings of the Seventh Artificial Intel-
time strategy games. In: Prasad, B. (ed.) Soft Comput- ligence and Interactive Digital Entertainment Confer-
ing Applications in Industry, Studies in Fuzziness and ence (AIIDE 2011), pp. 79–84. Proceedings of AIIDE,
Soft Computing, vol. 226, pp. 293–310. Springer, Palo Alto, États-Unis, Granada, Spain (2011b)
Berlin (2008) Synnaeve, G., Bessiere, P.: A Bayesian model for RTS
Ontañón, S., Mishra, K., Sugandh, N., Ram, A.: On-line units control applied to StarCraft. In: Proceedings of
case-based planning. Comput. Intell. 26(1), 84–119 IEEE CIG 2011, p. 000. Seoul, Corée, République De
(2010) (2011c)
Othman, N., Decraene, J., Cai, W., Hu, N., Gouaillard, A.: Synnaeve, G., Bessiere, P.: A dataset for StarCraft AI & an
Simulation-based optimization of starcraft tactical AI example of armies clustering. In: AIIDE Workshop on
through evolutionary computation. In: CIG (IEEE), AI in Adversarial Real-time games 2012, Seoul, South
Granada, Spain (2012) Korea (2012a)
Perkins, L.: Terrain analysis in real-time strategy games: Synnaeve, G., Bessièere, P.: Special tactics: a Bayesian
an integrated approach to choke point detection and approach to tactical decision-making. In: CIG (IEEE),
region decomposition. In: Artificial Intelligence and Granada, Spain (2012b)
Interactive Digital Entertainment Conference (AIIDE Treuille, A., Cooper, S., Popović, Z.: Continuum crowds.
2010), vol. 10, pp. 1687–173 (2010) ACM Trans. Graph. 25(3), 1160–1168 (2006)
Ponsen, M., Spronck, I.P.H.M.: Improving adaptive game Uriarte, A., Ontañón, S.: Kiting in RTS games using
AI with evolutionary learning. In: University of influence maps. In: Eighth Artificial Intelligence and
Wolverhampton, pp. 389–396 (2004) Interactive Digital Entertainment Conference, Palo
Pottinger, D.C.: Terrain analysis for real-time strategy Alto, USA (2012)
games. In: Proceedings of Game Developers Confer- Uriarte, A., Ontañón, S.: Game-tree search over high-level
ence 2000, San Francisco, USA (2000) game states in RTS games. In: Artificial Intelligence
Preuss, M., Beume, N., Danielsiek, H., Hein, T., Naujoks, and Interactive Digital Entertainment Conference
B., Piatkowski, N., Ster, R., Thom, A., Wessing, S.: (AIIDE 2014). AAAI Press (2014)
Towards intelligent team composition and maneuver- Weber, B.G., Mateas, M.: A data mining approach to strat-
ing in real-time strategy games. Trans. Comput. Intell. egy prediction. In: IEEE Symposium on Computational
AI. Game (TCIAIG) 2(2), 82–98 (2010) Intelligence and Games (CIG), Milan, Italy (2009)
Reynolds, C.W.: Steering behaviors for autonomous Weber, B.G., Mateas, M., Jhala, A.: Applying goal-driven
characters. Proc. Game Dev. Conf. 1999, 763–782 autonomy to starcraft. In: Artificial Intelligence and
(1999) Interactive Digital Entertainment (AIIDE), Palo Alto,
Richoux, F., Uriarte, A., Ontañón, S.: Walling in strategy USA (2010a)
games via constraint optimization. In: Artificial Intel- Weber, B.G., Mawhorter, P., Mateas, M., Jhala, A.: Reac-
ligence and Interactive Digital Entertainment Confer- tive planning idioms for multi-scale game AI. In: IEEE
ence (AIIDE 2014) (2014)
12 RTS AI Problems and Techniques

Symposium on Computational Intelligence and Games starcraft: Broodwar. In: CIG (IEEE), Granada, Spain
(CIG), Copenhagen, Denmark (2010b) (2012)
Weber, B.G., Mateas, M., Jhala, A.: Building human-level Wintermute, S., Joseph Xu, J.Z., Laird, J.E.: Sorts:
AI for real-time strategy games. In: Proceedings of A human-level approach to real-time strategy AI. In:
AIIDE Fall Symposium on Advances in Cognitive AI and Interactive Digital Entertainment Conference,
Systems. AAAI Press, AAAI Press, Stanford (2011a) AIIDE (AAAI), pp. 55–60. Palo Alto, USA (2007)
Weber, B.G., Mateas, M., Jhala, A.: A particle model for Young, J., Hawes, N.: Evolutionary learning of goal pri-
state estimation in real-time strategy games. In: Pro- orities in a real-time strategy game. In: Artificial Intel-
ceedings of AIIDE, pp. 103–108. AAAI Press, AAAI ligence and Interactive Digital Entertainment
Press, Stanford (2011b) Conference (AIIDE 2012) (2012)
Wender, S., Watson, I.: Applying reinforcement learning
to small scale combat in the real-time strategy game

You might also like