A Bayesian Tactician
Gabriel Synnaeve (gabriel.synnaeve@gmail.com) and Pierre Bessière (pierre.bessiere@imag.fr)
Université de Grenoble (LIG), INRIA, CNRS, Collège de France (LPPA)

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

1

Introduction

1.1

Game AIWe believe video game AI is central to new, fun, re-playable gameplays, being them multi-player or not. Cooperative (player
versus AI) games are enjoying a new boom, recent RTS games delegate more micro-management to the AI as ever, and evermore realistic first-person shooters (FPS) immersion hardly cope with scripted (unsurprising) non-playing characters (NPC). In
their study 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 human or not”. No current non-cheating AI consistently beats good humanplayers in RTS (aim cheating is harder to define for FPS games), nor are fun to play many games against. Finally, as the world
is simulated but the players are not, multi-player game AI research is in between real-world robotics and more theoretical AI,
and so can benefit both fields.
1.2

RTS Gameplay

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 is required to gather resources and build up an economic and military power while
expanding a technology tree. Parts of the 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 the general stance (aggressive or defensive) form what we call strategy. At the lower level, the actions
performed by the player (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 much data 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 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-level strategy constrains what types of attacks are possible. As shown in Fig. 1, information fromunits’ 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 AI (“bot”), once we have a decision: we generate a goal (attack order) passed to units groups(see Fig.1). 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 from incomplete information (due to the fog of war).
1.3

StarCraft Tactics

We worked on StarCraft: Brood War, which is a canonical RTS game. It had been around since 1998, sold 9.5 million licenses
and reigned on competitive RTS for more than a decade. StarCraft (like most RTS) has a mechanism, replays, to record every
1

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

II

constraints
values, decisions
distributions

Incomplete Data

directknowledge

Micro-management

1 sec

Our AI

30 secunits

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

more
constraints

Tactics (armypositions)

3 mintime to switch behaviors

partialinformation

Strategy (tech tree,
army composition)

Opponent

buildings, technologies

intention

UnitGroups
UnitGroups
UnitGroupsobjectives, formations
how,
where

Priors (canevolve)BayesianUnit
BayesianUnit
BayesianUnit
BayesianUnit

BayesianUnit
BayesianUnit
BayesianUnit
BayesianUnit

Fig. 1. Left: Gameplay levels of abstraction for RTS games, compared with their level of direct (and complete) information and orders ofmagnitudes of time to change their policies. Right:Information centric view of the StarCraft bot player, the part presented in this paper isinside 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).

player’s actions such that the state of the game can be deterministically re-simulated. Numerous international competitions andprofessional gaming (mainly in South Korea) produced a massive amount of data of highly skilled human players, performing
about 300 actions per minute while following and adapting their strategies. In StarCraft, there are two types of resources, often
located close 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 to gather resources, and all other characteristics are different: frommilitary 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, someothers have splash damage attacks, immobilizing or illusion abilities. Fast and mobile units are not cost-effective in head-to-headfights against slower bulky units. We used the gamers’ vocabulary to qualify different types of tactics:– ground attacks (raids or pushes) are the most normal kind of attacks, carried by basic units which cannot fly,
– air attacks (air raids), which use flying units’ mobility to quickly deal damage to undefended spots.
– invisible attacks exploit the weaknesses (being them positional or technological) in detectors of the enemy to deal damage
without retaliation,– drops are attacks using ground units transported by air, combining flying units’ mobility with cost-effectiveness of groundunits, at the expense of vulnerability during transit.
This will be the only four types of tactics that we will use in this paper: how did the player attack or defend?
RTS games maps, StarCraft included, consist in a closed arena in which units can evolve. It is filled with terrain features likeuncrossable terrain for ground units (water, space), cliffs, ramps, walls. Particularly, each RTS game which allows production
also give some economical (gathering) mechanism and so there are some resources scattered on the map, where players needto go collect. It is way more efficient to build expansion (auxiliary bases) to collect resources directly on site. So when a player
decides to attack, she has to decide where to attack, and this decision takes into account how it can attack different places, due
to their geographical remoteness, topological access possibilities and defense strength. Choosing where to attack is a complex
decision to make: of course it is always wanted to attack poorly defended economic expansions of the opponent, but the player
has to consider if it places its own bases in jeopardy, or if it may trap her own army. With a perfect estimator of battles outcomes(which is a hard problem due to terrain, army composition combinatorics and units control complexity), and perfect information,
this would result in a game tree problem which could be solved my α − β. Unfortunately, StarCraft is a partial observation
game with complex terrain and fight mechanics.

2

Background

2.1

Related WorkAha et al. [6] used case-based reasoning (CBR) to perform dynamic tactical plan retrieval (matching) extracted from domain
knowledge in Wargus. Ontañó et al. [7] based their real-time case-based planning (CBP) system on a plan dependency graphIIIwhich is learned from human demonstration in 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 a knowledge-based approach to perform
situation assessment to use the right plan, performing runtime adaptation by monitoring its performance. Sharma et al. [10]used richly parametrized CBR for strategic and tactical AI in Spring (Total Annihilation open source clone). [11] combined
CBR and reinforcement learning to enable reuse of tactical plan components. Cadena and Garrido [12] used fuzzy CBR (fuzzycase matching) for strategic and tactical planning. Chung et al. [13] applied Monte-Carlo planning to a capture-the-flag modof Open RTS. Inspired by successes of MCTS with upper confidence bounds on trees (UCT) policies [14] on the game of Go,
Balla and Fern [15] applied UCT to tactical assault planning in Wargus.
In Starcraft, Weber et al. [16, 17] produced tactical goals through reactive planning and goal-driven autonomy, finding themore relevant goal(s) to follow in unforeseen situations. Kabanza et al. [18] performed plan and intent recognition to findtactical opportunities. On spatial and temporal reasoning, Forbus et al. [19] presented a tactical qualitative description of terrain
for wargames through geometric and pathfinding analysis. Perkins [20] automatically extracted choke points and regions of
StarCraft maps from a pruned Voronoi diagram, which we used for our regions representations. Wintermute et al. [21] used a
cognitive approach mimicking human attention for tactics and units control. Ponsen et al. [22] developed an evolutionary statebased tactics generator for Wargus. Finally, Avery et al. [23] and Smith et al. [24] co-evolved influence map trees for spatial(tactical) reasoning in RTS games.
Our approach (and bot architecture, depicted in Fig. 1) can be seen as goal-driven autonomy [16] dealing with multilevel 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 notcare if the uncertainty comes from incompleteness 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 ourmodel is that it allows for prediction of the enemy tactics using the same model with different inputs. Finally, our approachis not exclusive to most of the techniques presented above, and it could be interesting to combine it with UCT [15] and more
complex/precise tactics generated through planning.

2.2

Bayesian Programming

Probability is used as an alternative to classical logic and we transform incompleteness (in the experiences, observations or themodel) into uncertainty [25]. We introduce Bayesian programs (BP), a formalism that can be used to describe entirely any kindof Bayesian model, subsuming Bayesian networks and Bayesian maps, equivalent to probabilistic factor graphs [26]. There aremainly 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 by decomposing
the joint distribution P(X 1 . . . X n |δ, π) with existing preliminary knowledge π and data δ. The forms of each term of the productspecify how to compute their distributions: either parametric forms (laws or probability tables, with free parameters that can belearned 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
P(Searched, F ree, Known)
P(Searched|Known) = F ree
P(Known)=X
1
×
P(Searched, F ree, Known)
Z
F ree

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

Bayesian programming originated in robotics [27] and evolved to all sensory-motor systems [28]. For its use in cognitivemodeling, see [29] and for its first use in video games (FPS, Unreal Tournament), see [30]; for MMORPG, see [31].

IV

3Methodology

3.1

DatasetWe downloaded more than 8000 replays to keep 7649 uncorrupted, 1v1 replays of very high level StarCraft games (progamers leagues and international tournaments) from specialized websites234 , we then ran them using BWAPI5 and dumped
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 source code are freely available6 .
3.2

Spatial Reasoning

Fig. 2. A very simple map on the left, which is transformed into regions (between chokes in dotted red lines) by Voronoi tesselation andclustering. These plain regions (numbers in red) are then augmented with choke-dependent regions (letters in blue)

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 [20] and give regions for which chokes are theboundaries. As battles often happens at chokes, choke-dependent regions are created by doing an additional (distance limited)
Voronoi tesselation spawned at chokes, its regions set is (regions \ chokes) ∪ chokes. Figure 2 illustrate regions and chokedependent regions (CDR). Results for choke-dependent regions are not fully detailed.
3.3

Value Heuristics

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 of strategic inference too. The advantages are that 1) learning will de-skew themodel output from biased heuristic inputs 2) the model is agnostic to where input variables’ values come from 3) the updatingprocess is the same for supervised learning and for reinforcement learning.
a|d
We note sunit type (r) for the balanced score of units from attacker or defender (a|d ) of a given type in region r. The balanced
score of units is just the sum of units multiplied by each unit score (= minerals value + 43 gas value + 50supply value).
2

http://www.teamliquid.net
http://www.gosugamers.net
4
http://www.iccup.com
5
http://code.google.com/p/bwapi/
6
http://snippyhollow.github.com/bwrepdump/
3

VThe heuristics we used in our benchmarks (which we could change) are:sdworkers (r)di∈regions sworkers (i)economical scored (r) = P
tactical scored (r) =X

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 of the full (same) army. For flying units, dist is the Euclidean distance, while forground units it takes pathfinding into account.
ground def ensed (r) =air def ensed (r) =sdcan attack ground (r)saground units (r)sdcan attack air (r)saair units (r)dinvis def ensed (r) = numberdetectors

3.4

Tactical Model

We preferred to discretize continuous values to enable quick complete computations. Another 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.
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: noworkers in the regions, low: a small amount of workers (less than half the total) and high: more than half the total of workers
in this region i.
– T1:n ∈ discrete levels, Ti is the tactical value of the region i for the defender, see above for an explanation of theheuristic. Basically, T is proportional to the proximity to the defender’s army. In benchmarks, discretization steps are0, 0.05, 0.1, 0.2, 0.4, 0.8 (log2 scale).
– T A1:n ∈ discrete levels, T Ai is the tactical value of the region i for the attacker (see above).
– B1:n ∈ {true, f alse}, Bi tells if the region belongs (or not) to the defender. P(Bi = true) = 1 if the defender has abase in region i and P(Bi = f alse) = 1 if the attacker has one. Influence zones of the defender can be measured (withuncertainty) 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 a heuristic. 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 and under comparable sizes, high if the defender’s army is bigger 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.
– T T ∈ [∅, building1 , building2 , building1 ∧ building2 , techtrees, . . . ]: all the possible technological 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 this variable, 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 as well as the units we own).
Finally, for some variables, we take uncertainty into account with “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 ) if f B = B 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).

VI

Decomposition The joint distribution of our model contains soft evidence variables for all input family variables (E, T ,T A, B, GD, AD, ID, HP ) to be as general as possible, i.e. to be able to cope with all possible uncertainty (from incomplete
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 n considered 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 , HP, T T )nY=[P(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 )Forms and Learning We will explain the forms for a given/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 to nbattles /(nbattles +nnot battles ). In a given match it should be initialized to uniform and progressively learn the preferred attack regions of the
opponent for predictions, learn the regions in which our attacks fail or succeed 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) [25] and count the co-occurrences,thus almost performing maximum likelihood learning of the table.
– P(λB |B, B 0 ) = 1.0 if f B = B 0 is just a coherence constraint.
– P(AD, GD, ID|H) is a covariance table of the air, ground, invisible defense values depending on how the attack 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 functionof 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 andP(T T 6= k) = 0; otherwise, it allows us to take uncertainty about the opponent’s tech tree 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 theevaluation section, or by acting (reinforcement learning). In match situation against a given opponent, for inputs that we canunequivocally attribute to their intention (style and general
strategy), we also refine these probability tables (with Laplace’s rulePof succession). To keep things simple, we just refine E,T,T A P(E, T, T A, B|A) corresponding to their 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 inclinationof our opponent to venture 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 towhat is 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) scores of 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 from the attacker on AD, GD, ID is too high or
because our heuristics 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 at which 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 the use of
P(H|HP )P(HP |T T )P(T T ) in decision-making, see the Results sections.
Questions For a given region i, we can ask the probability to attack here,
P(Ai = ai |ei , ti , tai , λB,i = 1)

VII
P
= P

0
0
Bi ,Bi0 P(ei , ti , tai , Bi |ai )P(ai )P(Bi ).P (λB,i |Bi , Bi )0P(ei , ti , tai , Bi |Ai )P(Ai )P(Bi0 )P(λB,i |Bi , Bi0 )Ai ,Bi ,BiX
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 |HP )P(HP |T T )P(T T )]T T,PFor clarity, we omitted some variables couples on which we have to sum (to take uncertainty into account) as for B (and B 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 isP(A, H|F ullyObserved). The maximum of P(A, H) may not be the same as the maximum of P(A) or P(H), for instancethink of a very important economic zone that is very well defended, it may be the maximum of P(A), but not once we takeP(H) into account. Inversely, some regions 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:
P(A1:n , H1:n |F ullyObserved)(2)
X∝
P(A1:n , H1:n , Estimated, F ullyObserved)
Estimated

4

Results

4.1

Learning

To measure fairly the prediction performance of such a model, we applied “leave-100-out” cross-validation from our dataset:
as we had many games (see Table. 1), we set aside 100 games of each match-up for testing (with more than 1 battle permatch: rather ≈ J11 . . . 35K battles/match) and train our model on the rest. We write match-ups XvY with X and Y the first
letters of the factions involved (Protoss, Terran, Zerg). Note that mirror match-ups (PvP, TvT, ZvZ) have fewer 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), and #regions − 1 observations for the i regions which were not attacked:
P(ei6=r , ti6=r , tai6=r , bi6=r |A = f alse). For each battle 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 of succession [25], we allow for unseen event to have a non-zero probability.
An exhaustive presentation of the learned tables is out of the scope of this paper, but we displayed interesting cases in which
the posteriors of the learned model concur with human expertise in Figures 3 and 4. In Fig. 3, we see that air raids/attacks arequite 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 with up to one half of our force. We can also notice than drops are to be preferred either when it is safe toland (no anti-aircraft defense) or when there is a large defense (harassment tactics). In Fig. 3 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. 4 shows the transition between two types of encounters: tactics aimed at engaging theenemy army (a higher T value entails a higher P(A)) and tactics aimed at damaging the enemy economy (at high E, we lookfor opportunities to attack with a small army where T is lower).
4.2

Prediction Performance

We learned and tested one model for each race and each match-up. As we want to predict where (P(A1:n )) and how (P(Hbattle ))the next attack will happen to us, we used inferred 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 and so it allows for a highly accurate T T estimation with[4]. Training requires to recreate battle states (all units’ positions) and count parameters for 5000 to 30000 battles (dependingon the match-up). Once that is 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

VIII

Fig. 3. Left: (top) P(H = invis) and P(H = drop) for varying values of GD (summed on other variables); (bottom) P(H = air)and P(H = drop) for varying values of AD (summed on other variables), for Terran in TvP. We can see that it is far more likely thatinvisible (“sneaky”) attacks happen where there is low ground presence (top left plot). For drops, we understand that the high value forP(H = drop|GD = 1.0) is caused by the fact that drop armies are small and this value corresponds to drops which are being expectedby the defender. Drops at lower values of GD correspond to unexpected (surprise) drops. As ground units are more cost efficient than flying
units in a static battle, we see that both P(H = invis|AD = 0.0) and P(H = drop|AD = 0.0) are much more probable than situations
with air defenses. Right: P(H|HP ) for varying values of H and for different values of P (derived from inferred T T ), for Protoss in PvT.
Conditioning on what is possible given the tech tree gives a lot of information about what attack types are possible or not. More interestingly,
it clusters the game phases in different tech levels and allows for learning the relative distributions of attack types with regard to each phase.
For instance, the last (bottom right) plot shows the distribution on attack types at the end of a technologically complete game.

Fig. 4. P(A) for varying values of E and T , summed on the other variables, for Terran in TvT. Higher economical values is strongly correlatedwith surprise attacks with small tactical squads and no defenses, which almost never happens in open fields (“no eco”) as this would lead tovery unbalanced battles (in terms of army sizes): it would not benefit the smaller party, which can flee and avoid confrontation, as opposed towhen defending their base.

IX

being an approximation 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 is useful for the defender (they can position their army).
The model code7 (for learning and testing) as well as the datasets (see above) are freely available. Raw results of predictionsof positions and types of attacks 30 seconds before they happen are presented in Table. 1: for instance the bold number (38.0)
corresponds to the percentage of good positions (regions) predictions (30 sec before event) which were ranked 1st in theprobabilities on A1:n for Protoss attacks against Terran (PvT). The measures on where corresponds to the percentage of goodprediction and the mean probability for given ranks in P(A1:n ) (to give a sense of the shape of the distribution). As the mostprobable The measures on how corresponds to the percentage of good predictions for the most probable P(Hbattle ) and thenumber of such battles seen in the test set for given attack types. We particularly predict well ground attacks (trivial in theearly game, less in the end game) and, interestingly, Terran and Zerg drop attacks. The where & how row corresponds to thepercentage of good predictions for the maximal probability in the 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 ≈ 1/4th of the time. Finally, note that scores are also useful 60 seconds
before the attack (obviously, T T , and thus 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%. This gives even more time for the player to adapt their tactics.
Table 1. Results summary for multiple metrics at 30 seconds before attack. The 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
445
%
Pr
40.9 .334
14.6 .157
7.8
.089
7.6
.062
%
N
97.5 1016
44.4
81
22.7
225
55.9
340
76.3 1662
32.8

ProtossT
2408%
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
2027

P
2408

%
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
691
40
5
NA
NA
93.5 10798.4 806
27.1

TerranT
461%
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
2107
%
39.0
17.8
10.0
7.0
%
76.7
47.1
36.8
62.8
60.4

Pr
0.358
.174
.096
.062
N
695
402
326
739
2162
30.2

P
2027

Zerg
T
2107

Z
199

%
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
NA
NA
63.6
588
67.6 1802
26.4

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 (38 build tiles, or 2 screens in StarCraft’s resolution), while the mean max distanceon the map is 5506 (172 build tiles). Also, the mean number of regions by map is 19, so a random where (attack destination)
picking policy would have a 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 ≈ 1/(19*2) correct.
For the location only (where question), we also counted the mean number of different regions which were attacked in agiven game (between 3.97 and 4.86 for regions, depending on the match-up, and between 5.13 and 6.23 for choke-dependent
regions). The ratio over these means would give the best prediction rate we could expect from a baseline heuristic based solely
on the location data. These are attacks that actually happened, so the number of regions a player have to be worried about is atleast this one (or more, for regions which were not attacked during a game but were potential targets). This baseline heuristic
would yield (depending on the match-up) prediction rates between 20.5 and 25.2% for regions, versus our 32.8 to 40.9%, andbetween 16.1% and 19.5% for choke-dependent regions, versus our 24% to 32%.
Note that our current model considers a uniform prior on regions (no bias towards past battlefields) and that we do notincorporate any derivative of the armies’ movements. There is no player modeling at all: learning and fitting the mean player’s
tactics is not optimal, so we should specialize the probability tables for each player. Also, we use all types of battles in our
training and testing. Short experiments showed that if we used only attacks on bases, the probability of good where predictions
for the maximum of P(A1:n ) goes above 50% (which is not a surprise, there are far less bases than regions 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 prepares against attacks in 4 regions as opposed
to 19), we are right ≈ 70% of the time.
7

https://github.com/SnippyHolloW/AnalyzeBWDataX

Mistakes on the type of the attack are high for invisible attacks: while these tactics can definitely win a game, the counteris strategic (it is to have detectors technology deployed) more than positional. Also, if the maximum of P(Hbattle ) is wrong,
it doesn’t mean than P(Hbattle = good) = 0.0 at all! The result needing improvements the most is for air tactics, because
countering them really is positional, see our discussion in the conclusion.
4.3

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. 1). Once a decision is taken, the output of the tacticalmodel is an offensive or defensive goal. There are different 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 a dropship 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 type of the goal comes from P(H). In input, we fully know tactical scoresof the regions according to our military units placement T A (we are the attacker), what is possible for us to do P (according tounits 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 a particle 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 more probable than the most probables P(Ai ) and P(Hj ) taken separately (the case of an heavily defended main base anda small unprotected expand for instance). Fig. 5 displays the mean P(A, H) for Terran (in TvZ) attacks decision-making for themost 32 probable type/region tactical couples. It is in this kind of landscape (though more steep because Fig. 5 is a mean) that
we sample (or pick the most probable couple) to take a decision. Also, we may spawn defensive goals countering the attacks
that we predict from the opponent.

Fig. 5. 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 ). A simple way of taking a tactical decision according to this model, and the learned parameters, is by sampling in this distribution.

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

P(hi |HP )P(P |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 a decisionon our technology direction, we can consider the distances between our current ttt and all the probable values of T T t+1 .

5Conclusions

5.1

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, andeven removed or added, for another RTS or FPS, or for more performance. In particular, our “defense against invisible” heuristic

XI

could take detector positioning/coverage into account. Our heuristic on tactical values can also be reworked to take terrain tactical values into account (chokes and elevation in StarCraft). For the estimated 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 the dynamics 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 a more complicated learning and inference process (MCMC sampling). Finally, one of the strongest
assumptions (which is a drawback particularly for prediction) of our model is that the attacking player is always considered toattack in this most probable regions. While this would be true if the model was complete (with finer army positions inputs anda model of what the player thinks), we believe such an assumption of completeness 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).
5.2

Final Words

We have presented a Bayesian tactical model for RTS AI, which allows both for opposing tactics prediction and autonomous
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), and considering the 4 most probable regions
it goes up to ≈ 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 wellas our model 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.

References
1. Hagelbäck, J., Johansson, S.J.: A Study on Human like Characteristics in Real Time Strategy Games. In: Proceedings of CIG, IEEE
(2010)
2. Weber, B.G., Mateas, M., Jhala, A.: A Particle Model for State Estimation in Real-Time Strategy Games. In: Proceedings of AIIDE,
Stanford, Palo Alto, California, AAAI Press (2011) 103–108
3. Synnaeve, G., Bessière, P.: A Bayesian Model for RTS Units Control applied to StarCraft. In: Proceedings of CIG, Seoul, South Korea,
IEEE (September 2011)
4. Synnaeve, G., Bessière, P.: A Bayesian Model for Plan Recognition in RTS Games applied to StarCraft. In: Proceedings of AIIDE, Palo
Alto, CA, USA, AAAI Press (October 2011) 79–84
5. Synnaeve, G., Bessière, P.: A Bayesian Model for Opening Prediction in RTS Games with Application to StarCraft. In: Proceedings of
CIG, Seoul, South Korea, IEEE (September 2011)
6. Aha, D.W., Molineaux, M., Ponsen, M.J.V.: Learning to Win: Case-Based Plan Selection in a Real-Time Strategy Game. In: ICCBR.
(2005) 5–20
7. Ontañón, S., Mishra, K., Sugandh, N., Ram, A.: Case-based planning and execution for real-time strategy games. In: Proceedingsof the 7th international conference on Case-Based Reasoning: Case-Based Reasoning Research and Development. International Joint
Conference on Neural Networks (ICCBR-07), Springer-Verlag (2007) 164–178
8. Mishra, K., Ontañón, S., Ram, A.: Situation Assessment for Plan Retrieval in Real-Time Strategy Games. In: ECCBR. (2008) 355–369
9. Meta, M., Ontañón, S., Ram, A.: Meta-Level Behavior Adaptation in Real-Time Strategy Games. In: ICCBR-10 Workshop on CaseBased Reasoning for Computer Games, Alessandria, Italy. (2010)
10. Bakkes, S.C.J., Spronck, P.H.M., Jaap van den Herik, H.: Opponent modelling for case-based adaptive game AI. Entertainment Computing 1(1) (January 2009) 27–37
11. Sharma, M., Holmes, M., , Santamaria, J., Irani, A., Isbell, C.L., Ram, A.: Transfer Learning in Real-Time Strategy Games Usinging
Hybrid CBR/RL. In: International Joint Conference of Artificial Intelligence, IJCAI. (2007)
12. Cadena, P., Garrido, L.: Fuzzy Case-Based Reasoning for Managing Strategic and Tactical Reasoning in StarCraft. In: Proceedings of
MICAI (1), Springer (2011) 113–124
13. Chung, M., Buro, M., Schaeffer, J.: Monte Carlo Planning in RTS Games. In: Proceedings of CIG, IEEE (2005)
14. Gelly, S., Wang, Y.: Exploration exploitation in Go: UCT for Monte-Carlo Go. In: NIPS: Neural Information Processing Systems
Conference On-line trading of Exploration and Exploitation Workshop, Canada (December 2006)
15. Balla, R.K., Fern, A.: UCT for Tactical Assault Planning in Real-Time Strategy Games. In: IJCAI. (2009)
16. Weber, B.G., Mateas, M., Jhala, A.: Applying Goal-Driven Autonomy to StarCraft. In: Artificial Intelligence and Interactive DigitalEntertainment (AIIDE). (2010)
17. Weber, B.G., Mawhorter, P., Mateas, M., Jhala, A.: Reactive Planning Idioms for Multi-Scale Game AI. In: Proceedings of CIG, IEEE
(2010)
89

http://snippyhollow.github.com/bwrepdump/
https://github.com/SnippyHolloW/AnalyzeBWDataXII
18. Kabanza, F., Bellefeuille, P., Bisson, F., Benaskeur, A.R., Irandoust, H.: Opponent Behaviour Recognition for Real-Time Strategy Games.
In: AAAI Workshops. (2010)
19. Forbus, K.D., Mahoney, J.V., Dill, K.: How qualitative spatial reasoning can improve strategy game ais. IEEE Intelligent Systems 17(July 2002) 25–30
20. Perkins, L.: Terrain Analysis in Real-Time Strategy Games: An Integrated Approach to Choke Point Detection and Region Decomposition. In: Proceedings of AIIDE, AAAI Press (2010)
21. Wintermute, S., Joseph Xu, J.Z., Laird, J.E.: SORTS: A Human-Level Approach to Real-Time Strategy AI. In: Proceedings of AIIDE,AAAI Press (2007) 55–60
22. Ponsen, M.J.V., Muñoz-Avila, H., Spronck, P., Aha, D.W.: Automatically Generating Game Tactics through Evolutionary Learning. AI
Magazine 27(3) (2006) 75–84
23. Avery, P., Louis, S., Avery, B.: Evolving Coordinated Spatial Tactics for Autonomous Entities using Influence Maps. In: Proceedingsof the 5th international conference on Computational Intelligence and Games. Proceedings of CIG, Piscataway, NJ, USA, IEEE (2009)341–348
24. Smith, G., Avery, P., Houmanfar, R., Louis, S.: Using Co-evolved RTS Opponents to Teach Spatial Tactics. In: Proceedings of CIG,
IEEE (2010)
25. Jaynes, E.T.: Probability Theory: The Logic of Science. Cambridge University Press (June 2003)
26. Diard, J., Bessière, P., Mazer, E.: 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)
27. Lebeltel, O., Bessière, P., Diard, J., Mazer, E.: Bayesian Robot Programming. Autonomous Robots 16(1) (2004) 49–79
28. Bessière, P., Laugier, C., Siegwart, R.: Probabilistic Reasoning and Decision Making in Sensory-Motor Systems. 1st edn. Springer
Publishing Company, Incorporated (2008)
29. Colas, F., Diard, J., Bessière, P.: Common Bayesian Models for Common Cognitive Issues. Acta Biotheoretica 58 (2010) 191–216
30. Le Hy, R., Arrigoni, A., Bessière, P., Lebeltel, O.: Teaching Bayesian behaviours to video game characters. Robotics and Autonomous
Systems 47 (2004) 177–185
31. Synnaeve, G., Bessière, P.: Bayesian Modeling of a Human MMORPG Player. In: 30th international workshop on Bayesian Inference
and Maximum Entropy, Chamonix, France (July 2010)