Special Tactics: a Bayesian Approach to Tactical Decision-making
Gabriel Synnaeve (gabriel.synnaeve@gmail.com) and Pierre Bessière (pierre.bessiere@imag.fr)
intention
partialinformation

Strategy (tech tree,
army composition)

3 min

Tactics (armypositions)

30 secMicro-management

1 sec

more
constraints
directknowledge

time to switch behaviors

Abstract—We describe a generative Bayesian model of tactical attacks in strategy games, which can be used both topredict attacks and to take tactical decisions. This model
is designed to easily integrate and merge information fromother (probabilistic) estimations and heuristics. In particular,
it handles uncertainty in enemy units’ positions as well as theirprobable tech tree. We claim that learning, being it supervisedor through reinforcement, adapts to skewed data sources. We
evaluated our approach on StarCraft1 : the parameters arelearned on a new (freely available) dataset of game states,
deterministically re-created from replays, and the whole model
is evaluated for prediction in realistic conditions. It is also
the tactical decision-making component of our StarCraft AI
competition bot.

Fig. 1. Gameplay levels of abstraction for RTS games, compared with
their level of direct (and complete) information and orders of magnitudesof time to chance their policies.

I. I NTRODUCTION
A. Game AI

1 StarCraft and its expansion StarCraft: Brood War are trademarks of
Blizzard EntertainmentTM

constraints
values, decisions
distributions

Incomplete Databuildings, technologies

units

Opponent Strategy

Opponent Tactics

opening, tech tree

attacks: where, how

Our Strategy

Our Tactics

wanted: units,buildings, tech units, tech order

Production plannerand managers

Opponent Positions

Goals

Real-time strategy (RTS) gameplay consist in producing
and managing group of units with attacks and movements
specificities in order to defeat an enemy. Most often, it isrequired to gather resources and build up an economic andmilitary power while expanding a technology tree. Parts ofthe map not in the sight range of the player’s units are under
fog of war, so the player only has partial information about
the enemy buildings and army. The way by which we expand
the tech tree, the specific units composing the army, and thegeneral stance (aggressive or defensive) form what we callstrategy. At the lower level, the actions performed by theplayer (human or not) to optimize the effectiveness of its
units is called micro-management. In between lies tactics:
where to attack, and how. A good human player takes muchdata in consideration when choosing: are there flaws in the
defense? Which spot is more worthy to attack? How much
am I vulnerable for attacking here? Is the terrain (height,
chokes) to my advantage? etc.
In this paper, we focus on tactics, in between strategy(high-level) and micro-management (lower-level), as seen

Opponent

B. RTS Gameplay

in Fig. 1. We propose a model which can either predict
enemy attacks or give us a distribution on where and how
to attack the opponent. Information from the higher-levelstrategy constrains what types of attacks are possible. As
shown in Fig. 1, information from units positions (or possibly
an enemy units particle filter as in [2]) constrains where
the armies can possibly be in the future. In the context of
our StarCraft bot, once we have a decision: we generatea goal (attack order) passed to units groups (see Fig.2). A
Bayesian model for micro-management [3], in which units
are attracted or repulsed by dynamic (goal, units, damages)
and static (terrain) influence maps, actually moves the units
in StarCraft. Other previous works on strategy prediction [4],[5] allows us to infer the enemy tech tree and strategies fromincomplete information (due to the fog of war).

Our AI

We believe video game AI is central to new, fun, replayable gameplays, being them multi-player or not. In theirstudy on human like characteristics in RTS games, Hagelbäck
and Johansson [1] found out that “tactics was one of themost successful indicators of whether the player was humanor not”. No current non-cheating AI consistently beats good
human players in RTS (aim cheating is harder to definefor FPS games), nor are fun to play many games against.
Finally, multi-player game AI research is in between realworld robotics (the world is simulated but not the players)
and more theoretical AI and can benefit both fields.

UnitGroups
UnitGroups
UnitGroupsobjectives, formations
how,
where

Priors (canevolve)BayesianUnit
BayesianUnit
BayesianUnit
BayesianUnit

BayesianUnit
BayesianUnit
BayesianUnit
BayesianUnit

Fig. 2.
Information centric view of the StarCraft bot player, the partpresented in this paper is inside dotted lines (tactics). Dotted arrows
represent constraints on what is possible, plain simple arrows represent
simple (real) values, either from data or decisions, and double arrows
represent probability distributions on possible values. The grayed surfaces
are the components actuators (passing orders to the game).

C. StarCraft Tactics
We worked on StarCraft: Brood War, which is a canonical RTS game. It had been around since 1998, sold 9.5
millions licenses and was played professionally for morethan a decade. StarCraft (like most RTS) has a mechanism,
replays, to record every player’s actions such that the stateof the game can be deterministically re-simulated. Numerous
international competitions and professional gaming (mainlyin South Korea) produced a massive amount of data ofhighly skilled human players, performing about 300 actions
per minute while following and adapting their strategies. In
StarCraft, there are two types of resources, often locatedclose together, minerals (at the base of everything) and gas(at the base of advanced units and technologies). There are
3 factions (Protoss, Terran and Zerg) which have workers togather resources, and all other characteristics are different:
from military units to “tech trees”, gameplay styles.
Units have different abilities, which leads to different
possible tactics. Each faction has invisible (temporarily or
permanently) units, flying transport units, flying attack units
and ground units. Some units can only attack ground or air
units, some others have splash damage attacks, immobilizing
or illusion abilities. Fast and mobile units are not costeffective in head-to-head fights against slower bulky units.
We used the gamers’ vocabulary to qualify different typesof tactics: ground attacks (raids or pushes) are the mostnormal kind of attacks, carried by basic units which cannot
fly. Then comes air attacks (air raids), which use flying units
mobility to quickly deal damage to undefended spots. Invisible attacks exploit the weaknesses (being them positionalor technological) in detectors of the enemy to deal damage
without retaliation. Finally, drops are attacks using groundunits transported by air, combining flying units mobility
with cost-effectiveness of ground units, at the expense ofvulnerability during transit.

confidence bounds on trees (UCT: a MCTS algorithm) totactical assault planning in Wargus.
In Starcraft, Weber et al. [14], [15] produced tactical goals
through reactive planning and goal-driven autonomy, finding
the more relevant goal(s) to follow in unforeseen situations.
Kabanza et al. [16] performs plan and intent recognition tofind tactical opportunities. On spatial and temporal reasoning,
Forbus et al. [17] presented a tactical qualitative descriptionof terrain for wargames through geometric and pathfinding
analysis. Perkins [18] automatically extracted choke points
and regions of StarCraft maps from a pruned Voronoi diagram. We used this technique to extract our regions representations. Wintermute et al. [19] used a cognitive approachmimicking human attention for tactics and units control.
Ponsen et al. [20] developed an evolutionary state-based
tactics generator for Wargus. Finally, Avery et al. [21] andSmith et al. [22] co-evolved influence map trees for spatial(tactical) reasoning in RTS games.
Our approach (and bot architecture, depicted in Fig. 2)
can be seen as goal-driven autonomy [14] dealing withmulti-level reasoning by passing distributions (without any
assumption about how they were obtained) on the module
input. Using distributions as messages between specialized
modules makes dealing with uncertainty first class, this way
a given model do not care if the uncertainty comes fromincompleteness in the data, a complex and biased heuristic,or another probabilistic model. We then take a decision by
sampling or taking the most probable value in the output
distribution. Another particularity of our model is that itallows for prediction of the enemy tactics using the samemodel with different inputs. Finally, our approach is not
exclusive to most of the techniques presented above, and it
could be interesting to combine it with UCT [13] and more
complex/precise tactics generated through planning.
B. Bayesian Programming

II. BACKGROUND
A. Related Works
Aha et al. [6] used case-based reasoning (CBR) to perform
dynamic tactical plan retrieval (matching) extracted fromdomain knowledge in Wargus. Ontañó et al. [7] based theirreal-time case-based planning (CBP) system on a plan dependency graph which is learned from human demonstrationin Wargus. A case based behavior generator spawn missing
goals which are missing from the current state and plan
according to the recognized state. In [8], [9], they used aknowledge-based approach to perform situation assessment
to use the right plan, performing runtime adaptation bymonitoring its performance. Sharma et al. [10] combined
CBR and reinforcement learning to enable reuse of tacticalplan components. Cadena and Garrido [11] used fuzzy CBR(fuzzy case matching) for strategic and tactical planning.
Chung et al. [12] adapted Monte-Carlo tree search (MCTS)
to planning in RTS games and applied it to a capture-theflag mod of Open RTS. Balla and Fern [13] applied upper

Probability is used as an alternative to classical logic
and we transform incompleteness (in the experiences, observations or the model) into uncertainty [23]. We introduce
Bayesian programs (BP), a formalism that can be used todescribe entirely any kind of Bayesian model, subsuming
Bayesian networks and Bayesian maps, equivalent to probabilistic factor graphs [24]. There are mainly two parts in a
BP, the description of how to compute the joint distribution,and the question(s) that it will be asked.
The description consists in explaining the relevant variables {X 1 , . . . , X n } and explain their dependencies bydecomposing the joint distribution P(X 1 . . . X n |δ, π) withexisting preliminary knowledge π and data δ. The formsof each term of the product specify how to compute theirdistributions: either parametric forms (laws or probability
tables, with free parameters that can be learned from dataδ) or recursive questions to other Bayesian programs.
Answering a question is computing the distribution
P(Searched|Known), with Searched and Known two

disjoint subsets of the variables. P(Searched|Known)P
P(Searched, F ree, Known)= F reeP(Known)X
1= ×
P(Searched, F ree, Known)
Z
F ree







V ariablesSpec.(π) DecompositionDesc.
F orms (P arametric or P rogram)

BP






Identif ication (based on δ)Question

Bayesian programming originated in robotics [25] andevolved to all sensory-motor systems [26]. For its use incognitive modeling, see [27] and for its first use in video
games (FPS, Unreal Tournament), see [28]; for Massively
Multi-Player Online Role-Playing Games, see [29].

The balanced score of units is just the sum on all unitsof each unit score (= minerals value + 43 gas value +50supply value). The heuristics we used in our benchmarks(which we could change) are:economical scored (r) = P
tactical scored (r) =X

We downloaded more than 8000 replays to keep 7649
uncorrupted, 1v1 replays of very high level StarCraft games(pro-gamers leagues and international tournaments) from
specialized websites234 , we then ran them using BWAPI5 anddumped units positions, pathfinding and regions, resources,
orders, vision events, for attacks (we trigger an attack tracking heuristic when one unit dies and there are at least two
military units around): types, positions, outcomes. Basically,
every BWAPI event was recorded, the dataset and its sourcecode are freely available6 .
We used two kinds of regions: BroodWar Terrain Analyser (BWTA) regions and choke-dependent (choke-centered)regions. BWTA regions are obtained from a pruned Voronoi
diagram on walkable terrain [18] and gives regions forwhich chokes are the boundaries. As battles often happensat chokes, choke-dependent regions are created by doing an
additional (distance limited) Voronoi tesselation spawned at
chokes, its regions set is (regions\chokes)∪chokes. Results
for choke-dependent regions are not fully detailed.
B. Tactical Model
The idea is to have (most probably biased) lower-level
heuristics from units observations which produce information
exploitable at the tactical level, and take some advantage ofstrategic inference too. The advantages are that 1) learning
will de-skew the model output from biased heuristic inputs2) the model is agnostic to where input variables’ values
come from 3) the updating process is the same for supervised
learning and for reinforcement learning.
or d
We note saunit
type (r) for the balanced score of units fromattacker or defender (a or b ) of a given type in region r.
2 http://www.teamliquid.net
3 http://www.gosugamers.net
4 http://www.iccup.com
5 http://code.google.com/p/bwapi/
6 http://snippyhollow.github.com/bwrepdump/

sdarmy (i) × dist(i, r)−1.5i∈regions

We used −1.5 such that the tactical value of a region in
between two halves of an army, each at distance 2, would
be higher than the tactical value of a region at distance 4 ofthe full (same) army. For flying units, dist is the Euclidean
distance, while for ground units it takes pathfinding into
account.
ground def ensed (r) =III. M ETHODOLOGY
A. Dataset

sdworkers (r)di∈regions sworkers (i)air def ensed (r) =sdcan attack ground (r)saground units (r)sdcan attack air (r)saair units (r)dinvis def ensed (r) = numberdetectors

We preferred to discretize continuous values to enable
quick complete computations. An other strategy would keep
more values and use Monte Carlo sampling for computation.
We think that discretization is not a concern because 1)
heuristics are simple and biased already 2) we often reason about imperfect information and this uncertainty tops
discretization fittings.
1) Variables: With n regions, we have:• A1:n ∈ {true, f alse}, Ai : attack in region i or not?
• E1:n ∈ {no, low, high}, Ei is the discretized economical value of the region i for the defender. We choose 3
values: no workers in the regions, low: a small amountof workers (less than half the total) and high: more thanhalf the total of workers in this region i.
• T1:n ∈ discrete levels, Ti is the tactical value of theregion i for the defender, see above for an explanation of
the heuristic. Basically, T is proportional to the proximity to the defender’s army. In benchmarks, discretization
steps are 0, 0.05, 0.1, 0.2, 0.4, 0.8 (log2 scale).
• T A1:n ∈ discrete levels, T Ai is the tactical value ofthe region i for the attacker (see above).
• B1:n ∈ {true, f alse}, Bi tells if the region belongs (ornot) to the defender. P(Bi = true) = 1 if the defender
has a base in region i and P(Bi = f alse) = 1 if theattacker has one. Influence zones of the defender canbe measured (with uncertainty) by P(Bi = true) ≥ 0.5
and vice versa.
• H1:n ∈ {ground, air, invisible, drop}, Hi : in predictive mode: how we will be attacked, in decision-making:how to attack, in region i.
• GD1:n ∈ {no, low, med, high}: ground defense (relative to the attacker power) in region i, result from aheuristic. no defense if the defender’s army is ≥ 1/10th

of the attacker’s, low defense above that and under half
the attacker’s army, medium defense above that andunder comparable sizes, high if the defender’s army isbigger than the attacker.
• AD1:n ∈ {no, low, med, high}: same for air defense.
• ID1:n ∈ {no detector, one detector, several}: invisible defense, equating to numbers of detectors.
• TT∈[∅, building1 , building2 , building1 ∧building2 , techtrees, . . . ]:allthepossibletechnological trees for the given race. For instance{pylon, gate} and {pylon, gate, core} are two different
T ech T rees.
• HP∈{ground, ground ∧ air, ground ∧invis, ground ∧ air ∧ invis, ground ∧ drop, ground ∧air ∧ drop, ground ∧ invis ∧ drop, ground ∧ air ∧invis ∧ drop}: how possible types of attacks, directly
mapped from T T information. In prediction, with thisvariable, we make use of what we can infer on the
opponent’s strategy [5], [4], in decision-making, weknow our own possibilities (we know our tech tree aswell as the units we own).
Finally, for some variables, we take uncertainty into accountwith “soft evidences”: for instance for a region in which
no player has a base, we have a soft evidence that it
belongs more probably to the player established closer. In
this case, for a given region, we introduce the soft evidence
variable(s) B 0 and the coherence variable λB and impose
P(λB = 1|B, B 0 ) = 1.0 if f B = B 0 , else P(λB =1|B, B 0 ) = 0.0; while P(λB |B, B 0 )P(B 0 ) is a new factor
in the joint distribution. This allows to sum over P(B 0 )distribution (soft evidence).
2) Decomposition: The joint distribution of our model
contains soft evidence variables for all input family variables(E, T, T A, B, GD, AD, ID, P ) to be as general as possible,
i.e. to be able to cope with all possible uncertainty (fromincomplete information) that may come up in a game. To
avoid being too verbose, we explain the decomposition
only with the soft evidence for the family of variables B,
the principle holds for all other soft evidences. For the nconsidered regions, we have:0P(A1:n , E1:n , T1:n , T A1:n , B1:n , B1:n, λB,1:n ,=H1:n , GD1:n , AD1:n , ID1:n , P, T T )nYP(Ai )P(Ei , Ti , T Ai , Bi |Ai )

(1)

i=1
0
0
P(λB,i |B1:n , B1:n)P(B1:n)P(ADi , GDi , IDi |Hi )P(Hi |HP ) P(HP |T T )P(T T )3) Forms and Learning: We will explain the forms for agiven/fixed i region number:•

P(A) is the prior on the fact that the player attacks in this region, in our evaluation we set it tonbattles /(nbattles + nnot battles ). In a given match it
should be initialized to uniform and progressively learn
the preferred attack regions of the opponent for pre-dictions, learn the regions in which our attacks fail orsucceed for decision-making.
• P(E, T, T A, B|A) is a covariance table of the economical, tactical (both for the defender and the attacker),
belonging scores where an attacks happen. We just use
Laplace succession law (“add one” smoothing) [23]and count the co-occurrences, thus almost performing
maximum likelihood learning of the table.
00• P(λB |B, B ) = 1.0 if f B = B is just a coherence
constraint.
• P(AD, GD, ID|H) is a covariance table of the air,ground, invisible defense values depending on how theattack happens. As for P(E, T, T A, B|A), we use a
Laplace’s law of succession to learn it.
• P(H|HP ) is the distribution on how the attack happens depending on what is possible. Trivially P(H =ground|HP = ground) = 1.0, for more complex
possibilities we have different maximum likelihood
multinomial distributions on H values depending on
HP .
• P(HP |T T ) is the direct mapping of what the tech tree
allows as possible attack types: P(HP = hp|T T ) = 1
is a function of T T (all P(HP 6= hp|T T ) = 0).
• P(T T ): if we are sure of the tech tree (prediction
without fog of war, or in decision-making mode),P(T T = k) = 1 and P(T T 6= k) = 0; otherwise, it
allows us to take uncertainty about the opponent’s techtree and balance P(HP |T T ). We obtain a distribution
on what is possible (P(HP )) for the opponent’s attack
types.
There are two approaches to fill up these probability tables,
either by observing games (supervised learning), as we did in
the evaluation section, or by acting (reinforcement learning).
In match situation against a given opponent, for inputs that
we can unequivocally attribute to their intention (style andgeneral strategy), we also refine these probability tables(with Laplace’s
Prule of succession). To keep things simple,
we just refine E,T,T A P(E, T, T A, B|A) corresponding totheir aggressiveness (aggro) or our successes and failures,and equivalently for P(H|HP ). Indeed, if we sum over E,
T and T A, we consider the inclination of our opponent toventure into enemy territory or the interest that we have to
do so by counting our successes with aggressive or defensive
parameters. In P(H|HP ), we are learning the opponent’s
inclination for particular types of tactics according to whatis available to their, or for us the effectiveness of our attack
types choices.
The model is highly modular, and some parts are more
important than others. We can separate three main parts:
P(E, T, T A, B|A), P(AD, GD, ID|H) and P(H|HP ). In
prediction, P(E, T, T A, B|A) uses the inferred (uncertain)
economic (E), tactical (T ) and belonging (B) scoresof the opponent while knowing our own tactical position fully (T A). In decision-making, we know E, T, B
(for us) and estimate T A. In our prediction benchmarks,P(AD, GD, ID|H) has the lesser impact on the results of

the three main parts, either because the uncertainty fromthe attacker on AD, GD, ID is too high or because ourheuristics are too simple, though it still contributes positively
to the score. In decision-making, it allows for reinforcement
learning to have pivoting tuple values for AD, GD, ID atwhich to switch attack types. In prediction, P(H|HP ) isused to take P(T T ) (coming from strategy prediction [4])into account and constraints H to what is possible. For theuse of P(H|HP )P(HP |T T )P(T T ) in decision-making, see
the Results sections.
4) Questions: For a given region i, we can ask theprobability to attack here,
P(Ai = ai |ei , ti , tai , λB,i = 1)00
Bi ,Bi0 P(ei , ti , tai , Bi |ai )P(ai )P(Bi ).P (λB,i |Bi , Bi )

P
= P

0
0
Ai ,Bi ,Bi0 P(ei , ti , tai , Bi |Ai )P(Ai )P(Bi )P(λB,i |Bi , Bi )∝X

P(ei , ti , tai , Bi |ai )P(ai )P(Bi0 )P(λB,i |Bi , Bi0 )Bi ,Bi0and the mean by which we should attack,P(Hi = hi |adi , gdi , idi )X ∝P(adi , gdi , idi |hi )P(hi |P )P(HP |T T )P(T T )T T,PFor clarity, we omitted some variables couples on which wehave to sum (to take uncertainty into account) as for B (andB 0 ) above. We always sum over estimated, inferred variables,
while we know the one we observe fully. In prediction mode,
we sum over T A, B, T T, P ; in decision-making, we sum
over E, T, B, AD, GD, ID. The complete question that we
ask our model is P(A, H|F ullyObserved). The maximumof P(A, H) may not be the same as the maximum of P(A) or
P(H), for instance think of a very important economic zonethat is very well defended, it may be the maximum of P(A),but not once we take P(H) into account. Inversely, someregions are not defended against anything at all but present
little or no interest. Our joint distribution (1) can be rewritten:
P(Searched, F ullyObserved, Estimated), so we ask:∝#regions − 1 observations for the i regions which were
not attacked: P(ei6=r , ti6=r , tai6=r , bi6=r |A = f alse). For eachbattle of type t we had one observation for P (ad, gd, id|H =t) and P (H = t|p). By learning with a Laplace’s law ofsuccession [23], we allow for unseen event to have a nonnull probability.
An exhaustive presentation of the learned tables is out of
the scope of this paper, but we displayed interesting cases
in which the learned probability tables meet concur withhuman expertise in Figures 3,4,5. In Fig. 3, we see that air
raids/attacks are quite risk averse and it is two times more
likely to attack a region with less than 1/10th of the flying
force in anti-aircraft warfare than to attack a region withup to one half of our force. We can also notice than drops
are to be preferred either when it is safe to land (no antiaircraft defense) or when there is a large defense (harassment
tactics). In Fig. 4 we can see that, in general, there are as
many ground attacks at the sum of other types. The two
top graphs show cases in which the tech of the attacker
was very specialized, and, in such cases, the specificity
seems to be used. In particular, the top right graphic may
be corresponding to a “fast Dark Templars rush”. Finally,
Fig. 5 shows the transition between two types of encounters:
tactics aimed at engaging the enemy army (a higher T value
entails a higher P(A)) and tactics aimed at damaging theenemy economy (at high E, we look for opportunities toattack with a small army where T is lower).

Fig. 3. P(H = air) and P(H = drop) for varying values of AD(summed on other variables), for Terran in TvP.

P(A1:n , H1:n |F ullyObserved)(2)
X
P(A1:n , H1:n , Estimated, F ullyObserved)
Estimated

IV. R ESULTS
A. Learning
To measure fairly the prediction performance of such amodel, we applied “leave-100-out” cross-validation from ourdataset: as we had many games (see Table. I), we set aside
100 games of each match-up for testing (with more than
1 battle per match: rather u 15 battles/match) and train ourmodel on the rest. We write match-ups XvY with X and Y thefirst letters of the factions involved (Protoss, Terran, Zerg).
Note that mirror match-ups (PvP, TvT, ZvZ) have less games
but twice as many attacks from a given faction. Learning
was performed as explained in III.B.3: for each battle in r
we had one observation for: P(er , tr , tar , br |A = true), andFig. 4. P(H|HP ) for varying values H and for different values of P
(derived from inferred T T ), for Protoss in PvT.

Fig. 5. P(A) for varying values of E and T , summed on the other variables,
for Terran in TvT.

B. Prediction Performance
We learned and tested one model for each race and eachmatch-up. As we want to predict where (P(A1:n )) and how(P(Hbattle )) the next attack will happen to us, we usedinferred enemy T T (to produce P ) and T A, our scores being
fully known: E, T , B, ID. We consider GD, AD to be
fully known even though they depend on the attacker force,
we should have some uncertainty on them, but we tested
that they accounted (being known instead of fully unknown)
for 1 to 2% of P(H) accuracy (in prediction) once P was
known. We should point that pro-gamers scout very well andso it allows for a highly accurate T T estimation with [4].
Training requires to recreate battle states (all units positions)and count parameters for 5,000 to 30,000 battles. Once thatis done, inference is very quick: a look-up in a probability
table for known values and #F look-ups for free variables
F on which we sum. We chose to try and predict the next
battle 30 seconds before it happens, 30 seconds being anapproximation of the time needed to go from the middle
of a map (where the entropy on “next battle position” ismaximum) to any region by ground, so that the prediction isuseful for the defender (they can position their army).
The model code7 (for learning and testing) as well as
the datasets (see above) are freely avaible. Raw results ofpredictions of positions and types of attacks 30 seconds
before they happen are presented in Table. I: for instancethe bold number (38.0) corresponds to the percentage ofgood positions (regions) predictions (30 sec before event)which were ranked 1st in the probabilities on A1:n forProtoss attacks against Terran (PvT). The measures on where
corresponds to the percentage of good prediction and themean probability for given ranks in P(A1:n ) (to give a senseof the shape of the distribution). As the most probable The
measures on how corresponds to the percentage of goodpredictions for the most probable P(Hbattle ) and the number
7 https://github.com/SnippyHolloW/AnalyzeBWDataof such battles seen in the test set for given attack types. We
particularly predict well ground attacks (trivial in the early
game, less in the end game) and, interestingly, Terran andZerg drop attacks. The where & how row corresponds to thepercentage of good predictions for the maximal probability inthe joint P(A1:n , H1:n ): considering only the most probableattack (more information is in the rest of the distribution, as
shown for where!) according to our model, we can predict
where and how an attack will occur in the next 30 seconds u
1/4th of the time. Finally, note that scores are not ridiculous
60 seconds before the attack neither (obviously, T T , andthus P , are not so different, nor are B and E): PvT where
top 4 ranks are 35.6, 8.5, 7.7, 7.0% good versus 38.0,
16.3, 8.9, 6.7% 30 seconds before; how total precision 60
seconds before is 70.0% vs. 72.4%, where & how maximum
probability precision is 19.9% vs. 23%.
When we are mistaken, the mean ground distance(pathfinding wise) of the most probable predicted region to
the good one (where the attack happens) is 1223 pixels (38build tiles, or 2 screens in StarCraft’s resolution), while themean max distance on the map is 5506 (172 build tiles).
Also, the mean number of regions by map is 19, so arandom where (attack destination) picking policy would havea correctness of 1/19 (5.23%). For choke-centered regions,the numbers of good where predictions are lower (between
24% and 32% correct for the most probable) but the mean
number of regions by map is 42. For where & how, a random
policy would have a precision of 1/(19*4), and even a random
policy taking the high frequency of ground attacks into
account would at most be u 1/(19*2) correct. For the location
only (where question), we also counted the mean number ofdifferent regions which were attacked in a given game, theratio over these means would give the best (consider onlyattacks that happened instead of threats) prediction rate we
could expect from a baseline heuristic based solely on thelocation data and would yield (depending on the match-up)
prediction rates between 20.5 and 25.2% for regions, versus
our 32.8 to 40.9%, and between 16.1% and 19.5% for chokedependent regions, versus our 24% to 32%.
Note that our current model consider a uniform prior on
regions (no bias towards past battlefields) and that we do notincorporate any derivative of the armies’ movements. Thereis no player modeling at all: learning and fitting the mean
player’s tactics is not optimal, so we should specialize theprobability tables for each player. Also, we use all types ofbattles in our training and testing. Short experiments showedthat if we used only attacks on bases, the probability of goodwhere predictions for the maximum of P(A1:n ) goes above
50% (which is not a surprise, there are far less bases thanregions in which attacks happen). To conclude on tactics
positions prediction: if we sum the 2 most probable regions
for the attack, we are right at least half the time; if we sum the
4 most probable (for our robotic player, it means it preparesagainst attacks in 4 regions as opposed to 19), we are rightu 70% of the time.
Mistakes on the type of the attack are high for invisi-

TABLE I
R ESULTS SUMMARY FOR MULTIPLE METRICS AT 30 SECONDS BEFORE ATTACK . T HE NUMBER IN BOLD (38.0) IS READ AS “38% OF THE TIME , THE
REGION i WITH PROBABILITY OF RANK 1 IN P(Ai ) IS THE ONE IN WHICH THE ATTACK HAPPENED 30 SECONDS LATER ”.

how

where

%: good predictions
Pr: mean probability
total # games
measure
rank
1
2
3
4
measure
type
G
A
I
D
total
where & how (%)

P
1336
%
Pr
40.9 .334
14.6 .157
7.8
.089
7.6
.062
%
N
97.5 1016
44.4
8122.7 225
55.9 340
76.3 1662
32.8

ProtossT
7225%
Pr
38.0 .329
16.3 .149
8.9
.085
6.7
.059
%
N
98.1 1458
34.5 415
49.6 337
42.2 464
72.4 2674
23

Z
6082

P
7225

%
Pr
34.5 .304
13.0 .152
6.9 .092
7.9 .064%
N
98.4 568
46.8 190
12.9 13245.2
9371.9 983
23.8%
Pr
35.3 .299
14.3 .148
9.8.09
8.6 .071%N
100 691405NANA93.5 10798.4 806
27.1

ble attacks: while these tactics can definitely win a game,the counter is strategic (it is to have detectors technology
deployed) more than positional. Also, if the maximum ofP(Hbattle ) is wrong, it doesn’t mean than P(Hbattle =good) = 0.0 at all! The result needing improvements themost is for air tactics, because countering them really ispositional, see our discussion in the conclusion.

TerranT
1384%
Pr
34.4 .295
14.7 .147
8.4
.087
6.9
.063
%
N
99.9 3218
13.3 444
NA
NA
86
1183
88.5 4850
23.6

Z
6322

P
6082

Zerg
T
6322

Z
598

%
Pr
39.0 0.358
17.8 .174
10.0 .096
7.0
.062
%
N
76.7
695
47.1
402
36.8
326
62.8
739
60.4 2162
30.2

%
Pr
32.8
.31
15.4 .166
11.3 .099
8.9
.07
%
N
86.6 612
14.2 155
32.6 227
67.7 535
64.6 1529
23.3

%
Pr
39.8 .331
16.6 .148
7.6 .084
7.7 .064%N
99.8 567
15.8
19
NA
NA
81.4
86
94.7 674
30.9%
Pr
37.2 .324
16.9 .157
10.7 .100
8.6
.07
%
N
67.2 607
74.2 586
NANA
63.6 588
67.6 1802
26.4

countering the attacks that we predict from the opponent.

C. In Game Decision-Making
In a StarCraft game, our bot has to make decisions about
where and how to attack or defend, it does so by reasoning
about opponent’s tactics, bases, its priors, and under strategic
constraints (Fig. 2). Once a decision is taken, the output of
the tactical model is an offensive or defensive goal. There aredifferent military goal types (base defense, ground attacks,
air attacks, drops...), and each type of goal has pre-requisites(for instance: a drop goal needs to have the control of adropship and military units to become active). The spawned
goal then autonomously sets objectives for Bayesian units[3], sometimes procedurally creating intermediate objectives
or canceling itself in the worst cases.
The destinations of goals are from P(A), while the typeof the goal comes from P(H). In input, we fully know
tactical scores of the regions according to our military units
placement T A (we are the attacker), what is possible for us
to do P (according to units available) and we estimate E, T ,B, ID, GD, AD from past (partial) observations. Estimating
T is the most tricky of all because it may be changing fast,
for that we use a units filter which just decays probability
mass of seen units. An improvement would be to use aparticle filter [2], with a learned motion model. From the joint(2) P(A1:n , H1:n |ta, p, tt) may arise a couple i, Hi moreprobable than the most probables P(Ai ) and P(Hj ) taken
separately (the case of an heavily defended main base and asmall unprotected expand for instance). Fig. 6 displays themean P(A, H) for Terran (in TvZ) attacks decision-making
for the most 32 probable type/region tactical couples. It is in
this kind of landscape (though more steep because Fig. 6 isa mean) that we sample (or pick the most probable couple)
to take a decision. Also, we may spawn defensive goals

Fig. 6. Mean P(A, H) for all H values and the top 8 P(Ai , Hi ) values,
for Terran in TvZ. The larger the white square area, the higher P(Ai , Hi ).

Finally, we can steer our technological growth towards
the opponent’s weaknesses. A question that we can ask ourmodel (at time t) is P(T T ), or, in two parts: we first findi, hi which maximize P(A, H) at time t + 1, and then ask amore directive:X
P(T T |hi ) ∝P(hi |HP )P(HP |T T )P(T T )P

so that it gives us a distribution on the tech trees (T T ) needed
to be able to perform the wanted attack type. To take adecision on our technology direction, we can consider the
distances between our current ttt and all the probable valuesof T T t+1 .
V. C ONCLUSIONS
A. Possible Improvements
There are three main research directions for possible
improvements: improving the underlying heuristics, improving the dynamic of the model and improving the model
itself. The heuristics presented here are quite simple but
they may be changed, and even removed or added, foranother RTS or FPS, or for more performance. In particular,
our “defense against invisible” heuristic could take detector
positioning/coverage into account. Our heuristic on tacticalvalues can also be reworked to take terrain tactical values
into account (chokes and elevation in StarCraft). For theestimated position of enemy units, we could use a particle

filter [2] with a motion model (at least one for ground units
and one for flying units). There is room to improve thedynamics of the model: considering the prior probabilities
to attack in regions given past attacks and/or considering
evolutions of the T ,T A,B,E values (derivatives) in time. The
discretizations that we used may show their limits, though
if we want to use continuous values, we need to setup amore complicated learning and inference process (MCMC
sampling). Finally, one of the strongest assumptions (which
is a drawback particularly for prediction) of our model isthat the attacking player is always considered to attack in thismost probable regions. While this would be true if the model
was complete (with finer army positions inputs and a modelof what the player thinks), we believe such an assumption ofcompleteness is far fetched. Instead we should express that
incompleteness in the model itself and have a “player decision” variable D ∼ M ultinomial(P(A1:n , H1:n ), player).
B. Final Words
We have presented a Bayesian tactical model for RTS
AI, which allows both for opposing tactics prediction andautonomous tactical decision-making. Being a probabilistic
model, it deals with uncertainty easily, and its design allows
easy integration into multi-granularity (multi-scale) AI systems as needed in RTS AI. Without any temporal dynamics,
its exact prediction rate of the joint position and tactical
type is in [23-32.8]% (depending on the match-up), andconsidering the 4 most probable regions it goes up to u
70%. More importantly, it allows for tactical decision-making
under (technological) constraints and (state) uncertainty. It
can be used in production thanks to its low CPU and memory
footprint. The dataset, its documentation8 , as well as ourmodel implementation9 (and other data-exploration tools) are
free software and can be found online. We plan to use thismodel in our StarCraft AI competition entry bot as it gives
our bot tactical autonomy and a way to adapt to our opponent.
R EFERENCES[1] J. Hagelbäck and S. J. Johansson, “A Study on Human like Characteristics in Real Time Strategy Games,” in CIG (IEEE), 2010.
[2] B. G. Weber, M. Mateas, and A. Jhala, “A Particle Model for State
Estimation in Real-Time Strategy Games,” in Proceedings of AIIDE,AAAI Press. Stanford, Palo Alto, California: AAAI Press, 2011, p.
103–108.
[3] G. Synnaeve and P. Bessière, “A Bayesian Model for RTS Units
Control applied to StarCraft,” in Proceedings of IEEE CIG 2011,
Seoul, South Korea, Sep. 2011.
[4] G. Synnaeve and P. Bessière, “A Bayesian Model for Plan Recognition
in RTS Games applied to StarCraft,” in Proceedings of the Seventh Artificial Intelligence and Interactive Digital Entertainment Conference(AIIDE 2011), ser. Proceedings of AIIDE, AAAI, Ed., Palo Alto, CA,
USA, Oct. 2011, pp. 79–84.
[5] G. Synnaeve and P. Bessière, “A Bayesian Model for Opening Prediction in RTS Games with Application to StarCraft,” in Proceedingsof 2011 IEEE CIG, Seoul, South Korea, Sep. 2011.
[6] D. W. Aha, M. Molineaux, and M. J. V. Ponsen, “Learning to Win:
Case-Based Plan Selection in a Real-Time Strategy Game,” in ICCBR,
2005, pp. 5–20.
8 http://snippyhollow.github.com/bwrepdump/
9 https://github.com/SnippyHolloW/AnalyzeBWData[7] S. Ontañón, K. Mishra, N. Sugandh, and A. Ram, “Case-basedplanning and execution for real-time strategy games,” in Proceedingsof the 7th international conference on Case-Based Reasoning: CaseBased Reasoning Research and Development, ser. International Joint
Conference on Neural Networks (ICCBR-07). Springer-Verlag, 2007,
pp. 164–178.
[8] K. Mishra, S. Ontañón, and A. Ram, “Situation Assessment for Plan
Retrieval in Real-Time Strategy Games,” in ECCBR, 2008, pp. 355–
369.
[9] M. Meta, S. Ontañón, and A. Ram, “Meta-Level Behavior Adaptation
in Real-Time Strategy Games,” in ICCBR-10 Workshop on Case-Based
Reasoning for Computer Games, Alessandria, Italy, 2010.
[10] M. Sharma, M. Holmes, , J. Santamaria, A. Irani, C. L. Isbell, and
A. Ram, “Transfer Learning in Real-Time Strategy Games Usinging
Hybrid CBR/RL,” in International Joint Conference of Artificial Intelligence, IJCAI, 2007.
[11] P. Cadena and L. Garrido, “Fuzzy Case-Based Reasoning for Managing Strategic and Tactical Reasoning in StarCraft,” in MICAI (1), ser.
Lecture Notes in Computer Science, I. Z. Batyrshin and G. Sidorov,Eds., vol. 7094. Springer, 2011, pp. 113–124.
[12] M. Chung, M. Buro, and J. Schaeffer, “Monte Carlo Planning in RTS
Games,” in CIG. IEEE, 2005.
[13] R. krishna Balla and A. Fern, “UCT for Tactical Assault Planning in
Real-Time Strategy Games,” in IJCAI, 2009.
[14] B. G. Weber, M. Mateas, and A. Jhala, “Applying Goal-Driven Autonomy to StarCraft,” in Artificial Intelligence and Interactive DigitalEntertainment (AIIDE), 2010.
[15] B. G. Weber, P. Mawhorter, M. Mateas, and A. Jhala, “Reactive
Planning Idioms for Multi-Scale Game AI,” in CIG (IEEE), 2010.
[16] F. Kabanza, P. Bellefeuille, F. Bisson, A. R. Benaskeur, and H. Irandoust, “Opponent Behaviour Recognition for Real-Time Strategy
Games,” in AAAI Workshops, 2010.
[17] K. D. Forbus, J. V. Mahoney, and K. Dill, “How qualitative
spatial reasoning can improve strategy game ais,” IEEE Intelligent
Systems, vol. 17, pp. 25–30, July 2002. [Online]. Available:
http://dx.doi.org/10.1109/MIS.2002.1024748[18] L. Perkins, “Terrain Analysis in Real-Time Strategy Games: An
Integrated Approach to Choke Point Detection and Region Decomposition,” in AIIDE, G. M. Youngblood and V. Bulitko, Eds. The
AAAI Press, 2010.
[19] S. Wintermute, J. Z. Joseph Xu, and J. E. Laird, “SORTS: A HumanLevel Approach to Real-Time Strategy AI,” in AIIDE, 2007, pp. 55–60.
[20] M. J. V. Ponsen, H. Muñoz-Avila, P. Spronck, and D. W. Aha, “Automatically Generating Game Tactics through Evolutionary Learning,”
AI Magazine, vol. 27, no. 3, pp. 75–84, 2006.
[21] P. Avery, S. Louis, and B. Avery, “Evolving CoordinatedSpatial Tactics for Autonomous Entities using Influence
Maps,” in Proceedings of the 5th international conference on
Computational Intelligence and Games, ser. CIG’09. Piscataway,
NJ, USA: IEEE Press, 2009, pp. 341–348. [Online]. Available:
http://dl.acm.org/citation.cfm?id=1719293.1719350[22] G. Smith, P. Avery, R. Houmanfar, and S. Louis, “Using Co-evolved
RTS Opponents to Teach Spatial Tactics,” in CIG (IEEE), 2010.
[23] E. T. Jaynes, Probability Theory: The Logic of Science. Cambridge
University Press, June 2003.
[24] J. Diard, P. Bessière, and E. Mazer, “A Survey of Probabilistic
Models Using the Bayesian Programming Methodology as a Unifying
Framework,” in Conference on Computational Intelligence, Robotics
and Autonomous Systems, CIRAS, 2003.
[25] O. Lebeltel, P. Bessière, J. Diard, and E. Mazer, “Bayesian Robot
Programming,” Autonomous Robots, vol. 16, no. 1, pp. 49–79, 2004.
[26] P. Bessière, C. Laugier, and R. Siegwart, Probabilistic Reasoning
and Decision Making in Sensory-Motor Systems, 1st ed. Springer
Publishing Company, Incorporated, 2008.
[27] F. Colas, J. Diard, and P. Bessière, “Common Bayesian Models for
Common Cognitive Issues,” Acta Biotheoretica, vol. 58, pp. 191–216,
2010.
[28] R. Le Hy, A. Arrigoni, P. Bessière, and O. Lebeltel, “Teaching
Bayesian behaviours to video game characters,” Robotics and Autonomous Systems, vol. 47, pp. 177–185, 2004.
[29] G. Synnaeve and P. Bessière, “Bayesian Modeling of a Human
MMORPG Player,” in 30th international workshop on Bayesian Inference and Maximum Entropy, Chamonix, France, Jul. 2010.