=Paper=
{{Paper
|id=Vol-2862/paper26
|storemode=property
|title=A Reasoning-Based Defogger for Opponent Army Composition Inference Under Partial Observability
|pdfUrl=https://ceur-ws.org/Vol-2862/paper26.pdf
|volume=Vol-2862
|authors=Hao Pan
|dblpUrl=https://dblp.org/rec/conf/aiide/Pan20
}}
==A Reasoning-Based Defogger for Opponent Army Composition Inference Under Partial Observability==
https://ceur-ws.org/Vol-2862/paper26.pdf
A Reasoning-based Defogger for Opponent Army Composition Inference under
Partial Observability
Hao Pan
QOMPLX, Inc.
1775 Tysons Blvd, Suite 800
Tysons, VA 22102
hao.pan@QOMPLX.com
Abstract one(s) to fight and where to do so. To deal with the strategy
selection problem under uncertainty, (Gehring et al. 2018)
We deal with the problem of inferring the opponent army utilized LSTM encoding and recorded game states based
size and composition in Real-Time Strategy (RTS) games
with partial observability. Using StarCraft R : Brood War R ,
on current observation every 5 seconds of game time. They
we propose a methodology to dynamically estimate the num- computed q-value to decide which of the 25 build orders
ber of production facilities the opponent has at any given time (BOs) to switch to. The build order is defined as the concur-
in a game, then in turn reason on how many army units the rent action sequences that, constrained by unit dependencies
opponent will produce in the near future and of which type. and resource availability, create a certain number of units
We conduct case studies to demonstrate the effectiveness of and structures in the shortest possible time span (Churchill
the proposed methodology and compare the results with those and Buro 2011). These 25 BOs are a drop in the ocean, since
from mainstream approaches. the game StarCraft offers a seemingly endless choice of BOs
which depend on factors such as the faction a player sides
Introduction with and which of the 45 unit types to train at a specific time.
(Fjell and Møllersen 2012) worked on extracting BOs from
The first known use of the exact phrase “Fog of War” in text replay files and employed Gaussian distribution to handle
dates to 1896, described as “the state of ignorance in which the uncertainty in the BOs caused by the FoW.
commanders frequently find themselves as regards the real
strength and position, not only of their foes, but also of their Defogging is equally as challenging as decision making
friends.”(Hale and Society 1896). In a nutshell, the Fog of under FoW. It should be noted that the defogger this paper
War (FoW) describes the uncertainty regarding one’s own concerns is about inferring the army size and the composi-
capability, the opponent’s capability and their intent during tion of the opponent (future state prediction) under partial
a military operation. In RTS games, FoW is often simulated. observability. This is quite different than the forward model-
In as early as 1989, (Setear 1989) identified the key element ing (Justesen and Risi 2017) used. In their paper, the authors
of simulating the Fog of War to be uncertainty. In this paper proposed a novel approach to counter an opponent’s BOs
we focus on the game StarCraft because it not only provides by incorporating a Genetic Algorithm into an online plan-
the environment with partial observability, but also has large ning algorithm so that the optimal BO can be found. A for-
state and action spaces, making the game itself challeng- ward model was constructed to predict the outcome of taking
ing for AI researchers to design algorithms to handle vari- some actions in a given game state. Such an outcome was
ous types of uncertainty and make appropriate decisions(On- not influenced by opponent information but only by one’s
tanón et al. 2013; Vinyals et al. 2017). own side such as the available mineral/gas amount, currently
There are attempts to tackle this challenge. (Hagelbäck completed number of certain units/buildings, etc. (Synnaeve
and Johansson 2009) attempted to address pathfinding under et al. 2018) employed convolutional LSTM encoder-decoder
Fog of War utilizing potential field. The authors argued that neural-network models to infer and predict an opponent’s
the bots equipped with Potential Fields can handle partial army composition under partial observability, and the Hu-
observatiblity caused by FoW well by gridifying the entire ber loss function to evaluate the accuracy of the prediction.
map and performing efficient exploration. In this way, a bot The results indicated that the win rates improved (by 5% in
can manage to navigate in a partially unknown environment some cases) with the proposed defogger. However, the au-
while at the same time search for enemies and choose which thors only compared the overall observed unit count as op-
posed to the count of each unit type.
Copyright c 2020, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved. In this paper, we propose a reasoning-based defogger to
Copyright c 2020 for this paper by its authors. Use permitted un- address the following challenges: 1) handling uncertainty
der Creative Commons License Attribution 4.0 International (CC under the fog of war; 2) inferring the opponent’s army com-
BY 4.0). position (unit types and corresponding quantities) accurately
and efficiently. In the sections to follow, we present the traverse from its birth place to our sight, and finally twait is
framework to reason about the opponent’s army composi- the time the unit is waiting. To ease the inference on tstart ,
tion with ECDFs to deal with the uncertainty, an entropy we assume that, when the opponent chooses to train a unit of
measure to intelligently choose the sampling rate of the in- a certain type, there are enough resources, and the opponent
formation, and a combat simulator to aid projection into the is not supply blocked. ttrain is a fixed value and measured by
future. We then demonstrate that the proposed approach per- logical steps2 . ttraverse is affected by the movement speed
forms better than a few mainstream approaches and is able of a unit and the map factors. While the movement speed is
to handle multiple unit types. fixed just as ttrain , there is much variation in the base-to-
base distances (which are a good indicator for determining
Methodology how far a unit needs to travel from its home to the enemy’s
The uncertainty brought about by the Fog of War makes de- base) on different maps. And finally, we assume twait is of-
fogging difficult. In the game StarCraft, if one were to pre- ten negligible.
dict how many of unit X there will be at a future time point, All of the things above are for a unit from a single pro-
there are several questions to consider: 1) how many pro- duction facility. In StarCraft, a player can have more than
duction facilities (ones responsible for training unit X) does one production facility. Inference on the number of the op-
the opponent have; 2) does the opponent have any produc- ponent’s production facilities can be tricky but can aid the
tion facility which is ready to train unit X; 3) whether the inference of the army composition. We do this by reasoning
opponent decides to train unit X (instead of training other on the arrival times of units. For example, with the current
types of units); 4) how reliable is the collected intelligence knowledge being the opponent having only 1 production fa-
of the opponent so far. And if we do believe that the op- cility, and if we observe the arrival of 2 new units after a
ponent is about to train unit X, what we are then mainly time period which is only enough to train 1 unit (for the
interested in is: a) when the previous unit X was trained, Terran and Protoss factions, only 1 unit can be trained at a
and b) how long does it take between the time the unit is production facility at a time), it is reasonable to infer that the
completed and the time we observe the newly-trained unit. opponent has at least 2 production facilities.
Aspect b) can be tricky to quantify. Sometimes an opponent Another important factor for inferring opponent army
would like to stage their units for defensive purposes before composition is the sampling rate. How often do we collect
they have a sizeable army, and sometimes such waiting time intelligence about the opponent? In StarCraft and with the
is negligible, especially when the opponent is doing a rush help of BWAPI, a bot can communicate with the game on
build, which means moving units and attacking the enemy as each frame which is roughly 42 ms long at the fastest speed
quickly as possible. We find the latter is often the case based setting. But is it necessary to do something on each frame?
on our observations of games happening on the StarCraft AI In StarCraft AI competitions, there are frame time limita-
ladder called BASIL1 . tions, which means one needs to care how much computa-
The first step in addressing these questions is to turn to tion to do per frame without slowing down the game. On the
the previous games vs the same opponent if such games are other hand, if we sample the information infrequently, some
available. For each of these games, we record the time his- valuable information may eventually slip away. How can one
tory of the count of each unit type that we observe in game decide the frequency to do so? Here we use the information
as well as the actual number obtained after the game was entropy, or more specifically, Rényi entropy, as it is the gen-
concluded. Then we form an empirical distribution function eralization of many other entropy measures such as Shan-
(ECDF) based on such time series data at each time point, so non entropy and Hartley entropy. Entropy is a way to mea-
that we can describe the distribution reasonably well regard- sure the information content of a system. Once we compute
less of the number of data points. If at the current time, the the entropy value, we then apply a change point detection
observation falls well within the distribution described by algorithm (Killick, Fearnhead, and Eckley 2012) to know
the ECDF, we will simply use the distribution at the next whether a drastic change in entropy value happens. A change
time step for prediction purposes, assuming continuity in point detection algorithm, in general, tries to segment the
time. Now doing so relies on several assumptions: 1) the data according to some statistical criteria such as penalised
opponent is following the same build order; 2) we also use likelihood and quasi-likelihood. When such a change point
the same BO; 3) map factors such as base-to-base distances is found, we’ll respond by increasing/decreasing the sam-
play an insignificant role. pling rate among the 4 levels: I) once per second, II) once
Regardless of the use of ECDF, the next step is the infer- per 2 seconds, III) once per 4 seconds, and IV) once per 8
ence of the time when we’ll see the arrival of the next unit. seconds.
The arrival time of any unit can be described as: Putting all things together, we arrive at our proposed ap-
proach for defogging: Algorithm 1 where T is the total du-
tarrival = tstart + ttrain + ttraverse + twait ration of a game (in seconds) and t is a specific time step. A
where tarrival means the time at which we observe the few things should be noted here. First, some production fa-
unit for the very first time, tstart means the time when the cilities are capable of producing multiple types of units, and
unit starts to get trained, ttrain is the time it takes to com- only one unit can be trained at a time. This affects both the
plete the training, ttraverse is how long it takes for the unit to inference about the number of production facilities as well as
1 2
BASIL ranking page: https://basil.bytekeeper.org/ranking.html Build times: https://liquipedia.net/starcraft/Game Speed
determining whether a certain unit type is going to be trained two things: 1) whether the standard deviation is at most half
next. For the sake of simplicity, we assume the worst case, the value of the mean; 2) whether the observed value falls
that the opponent is going to choose a unit type that would within one standard deviation from the mean. If both results
benefit their army value the most, provided their technology of these two tests are positive, we say the ECDF is valid and
level (which is based on our scouted information) supports will utilize the ECDF to predict the count of the associated
that. unit type. The amount of previous games used to form the
ECDF can be tricky. In a case study we will show that only
Algorithm 1 Our proposed approach for defogging a limited amount of such games are optimal for the purposes
for t in 1 : T do here.
* Infer how many production facilities the opponent has
considering all unit types the opponent has Case Study
* Update the number of production facilities using
For our first case study, the purpose is to demonstrate the
scouted information
inner working of our approach. For the sake of simplicity,
for unit type i in all unit types do
we pitch our own StarCraft AI bot called Halo4 against an
if there is any enemy unit of type i being newly ob-
opponent which only does a single build order, and we run
servered/destroyed currently at tcurrent then
10 games on a single map (Destination) to minimize the in-
* Increase/reduce the count of unit type i by the
fluence of map factors. The opponent name is WuliBot and
number of emerging/dying ones (check unit IDs
it is a competent bot which achieved the second place in the
to avoid double counting)
student division in the SSCAIT5 2016/17 tournament. Wuli-
end if
Bot does a zealot rush build exclusively so we only monitor
the count of the main unit of the build: Protoss Zealot.
if this is a time point to sample then
* Evaluate Rényi entropy
* Apply change point detection algorithm
* Determine sampling rate
* Compute next time to sample tnext
if ECDF is available and ECDF is applicable and
the current count falls within the distribution de-
scribed by the ECDF then
* Forecast the count by computing the mean
value of the distribution at tnext
else
if there is any newly-observed enemy unit of
unit type i and we believe the opponent will
train it next then Figure 1: Count of the Protoss Zealot unit from multiple
* Estimate the potential start time(s) of the games
next new unit(s): tcurrent − ttraverse − twait
* Forecast the completion time tcmpl by Figure 1 shows the count of Protoss Zealot from the 10
adding ttrain to the result above games we ran. The 10th game was used as the “current”
* Forecast the potential losses of unit type i one for forecasting purposes. Our observed and the actual
until tcmpl should a skirmish happen counts of Protoss Zealot in this game 10 are marked as
* Update the count of unit type i at tcmpl black and red circles on Figure 1, respectively. With the met-
end if rics deciding whether the ECDF is applicable, we were able
end if to ignore the ECDFs in the period between time points 50
end if and 65 where the variance is excessively large. On Figure
end for 1 we also show a few of the inferred and the actual tim-
end for ings of Protoss Gateway which is the production facility re-
sponsible for training Protoss Zealot. At time point 180 we
At each time step t, we also ask ourselves whether a skir- observed 3 Protoss Zealots, and after 40 seconds, we ob-
mish would take place and if so, how many of the units the served 2 more. It is impossible that there’s only one Pro-
opponent would lose. The simulation of such a hypotheti- toss Gateway as a Protoss Zealot takes 25 seconds to train
cal encounter wouldn’t be too hard as it would involve only and it would take more than 40 seconds for 2 new zealots
a few types of units and we know the timing of our army to appear. Therefore we arrived at the conclusion that the
pushing out. Here we used a combat simulator called FAP.3 opponent must have at least two Protoss Gateways at time
Another thing to note is that, for each unit type, we check 4
the validity of the associated ECDF carefully by looking at Halo’s liquipedia page: https://liquipedia.net/starcraft/Halo
5
SSCAIT stands for Student StarCraft AI Tournament and its
3
FAP’s github page: https://github.com/N00byEdge/FAP homepage: https://sscaitournament.com/
point 220. This was in fact confirmed by our scouted infor-
mation, as our scouting worker spotted 2 Protoss Gateways
at time point 180. We then update the inferred timings of the
two Protoss Gateways to time point 180. Efficient scouting
(the scouting worker covering as much enemy territory as
possible without dying) is vital to the inference here.
To examine the effect of the number of previous games
on defogging, we started by having no previous games, and
made one-step forward forecasts at each time step using the
observed values from game 10. Then we treated game 1,
games 1-2, and through to games 1-9 as the previous game(s)
to build the ECDFs, and used game 10 to perform the fore-
casting. We used Root Mean Squared Error (RMSE) to mea-
sure how good the forecast is.
Figure 3: Time history of Rényi entropy
and Moving Average (MA) terms, and the number of differ-
encing required to make the series stationary. For the neu-
ral network, we use a feed forward neural network called
multilayer perceptron (MLP) as it is fairly conventional. We
utilize an R package called “nnfor” which attempts to au-
tomatically specify autoregressive inputs and any necessary
pre-processing of the time series. With the pre-specified ar-
guments it trains multiple networks which are used to pro-
duce an ensemble forecast and a single hidden layer. For the
growth model we pick the exponential type. There are two
parameters to be estimated here: the initial state of the sys-
tem and the growth constant. We avoid the other type of the
growth model, the logistic type, since all the games run were
Figure 2: Evolution of RMSE as a function of the number of
nowhere close to either side hitting the supply max, which is
previous games
not an ideal scenario for this type of model.
Before we performed the comparison, we also set up both
Figure 2 shows the evolution history of RMSE values as a baseline model and a full-observability model in order to
the number of the available previous games increases. The better examine how much the partial observability impacts
RMSE values decreases because the ECDF describing the the forecasts. The baseline model is one obtained with zero
distribution of unit count gets better as the evidence from the observability. Effectively the baseline model is trying to an-
past accumulates. There is a slight upward trend in RMSE swer the question, “what army composition do we expect
as the number of past games approaches 9. This is largely from an average Protoss opponent given a time point in a
because the amount of noise/uncertainty is inevitably rising game?”. We address this by running games using our own
as the number of games increases. Taking advantage of a bot Halo with a fixed BO against all available Protoss op-
nice property of ECDF (that it works with low amounts of ponents on the BASIL ladder. The baseline model is then
data), we apply a moving window here to limit how many of constructed using the statistics from these games, mainly
the previous games we consider. the mean and the variance. We do this for the two Protoss
Figure 3 shows the time history of entropy values for units which are often a staple: 1) Protoss Zealot; 2) Pro-
game 10. As we can see, there’s a sudden increase around toss Dragoon.
time point 180, indicating that the sampling rate should be The full-observability model, on the other hand, was con-
raised. We were able to apply a change point detection algo- structed using information as if there was full observability.
rithm to identify this very time point. And this is consistent We run games pitching our bot Halo against a single oppo-
with Figure 1 as there’s also a sudden jump in Protoss Zealot nent named Locutus using sc-docker6 . After each game, sc-
count around that time point. It is the correct decision to in- docker produces a file named unit events.csv which con-
crease the sampling rate so that we have the count as accu- tains information such as location, unit type, and time as-
rate as possible. sociated with important events including unitCreate and
The second case study aims at comparing our proposed unitDestroy. One can then deduce the count of a unit at any
approach with a few mainstream methods to perform fore- given time from such information. Figures 4 and 5 demon-
casting for time series, namely, 1) ARIMA model; 2) neural
network; 3) growth model. For the ARIMA model, we au- 6
sc-docker’s github page: https://github.com/basil-ladder/sc-
tomatically choose the orders of the Auto Regressive (AR) docker. This is the version the BASIL ladder uses currently
strate both the baseline and the full-observability models for or those from the full-observability model. Table 1 shows
the two Protoss units. The curves denoted by games 1-3 rep- the summary of RMSE values from game 1 for the Pro-
resent the full-observability models for those games, respec- toss Dragoon unit only, as Locutus didn’t train any Pro-
tively. Both figures demonstrated that the baseline model toss Zealot at all. The results here suggest that our proposed
is working well. The upper bounds of the baseline model approach was able to produce the most accurate forecast as
successfully encompassed the counts of the two Protoss the RMSE values are the smallest. Discussion on the causes
units from the three full-observability models. In addition, of such results will follow next.
the baseline model has a wide coverage in time. Games 1-
3 ended much sooner compared to the average games de-
Table 1: RMSE using different approaches from game 1 for
picted by the baseline model, as Locutus is notorious for its
the Protoss Dragoon unit
early/mid game aggression.
Growth
ARIMA MLP Proposed Baseline
Model
One-step forecast
RMSE 3.5 1.8 1.9 1.7 4.7
Twelve-step forecast
RMSE 4.1 4.3 9.1 3.1 9.0
We discovered a few drawbacks associated with the alter-
native approaches. For the ARIMA model, forecasts are not
ideal, as evidenced by Figure 6. The twelve-step forecast is
indicated by the blue line, with a growing variance as time
goes by. The ARIMA (0, 2, 2) model fitted here is effec-
tively applying a linear exponential smoothing which uses
a moving average to create a forecast from a time series. In
the case here, this is problematic, as the count of a unit can
Figure 4: Baseline and full-observability models for the Pro- change drastically because it depends on so many factors
toss Zealot unit such as combat effectiveness, the number of production fa-
cilities, the amount of available resources, etc. The moving
average part simply cannot keep up. The one-step forecast is
even worse, as indicated by the red dots, especially towards
the end of the game. One large contributing factor to this is
the fact that the quantity of the Protoss Dragoon unit is zero
from the start for a very long time (up until 28 time units).
They “dragged down” the forecasts later on, because the
moving average term of the ARIMA model (0, 2, 2) is not
sensitive to new trends. While for our proposed approach,
such dependency exists, but the updated information from
either our scout or real-time observations prevents us from
being stranded by the past data.
Figure 5: Baseline and full-observability models for the Pro-
toss Dragoon unit
Unlike the previous study, we now choose an adaptive
opponent named Locutus which is performant and often
achieves the top place on the BASIL ladder. We ran and
chose a few games where Locutus executed a few of its main
build orders. The build orders used were: 14 nexus in game
1; proxy 2-gate zealot in game 2; 3-gate goon in game 3.
Next we apply the three mainstream methods and our pro-
posed approach to perform both one-step and twelve-step
forecasts, as we care about both the short-term and long-
term army compositions of the opponent. We then compared Figure 6: Forecasts from an ARIMA model
the forecasts produced from the four approaches, along-
side those from the baseline model, with the “true values”, For the neural network model, there’s a mandatory burn-
in period. In this case study, it required at least 10 data points
for the neural network model to produce meaningful fore-
casts. Also, there’s the issue of hyperparameter tuning where
one needs to decide the number of layers and the number
of nodes on each layer for a neural network model. How-
ever, the advantage of the neural network approach is that
it would work for any game, whereas the proposed method
might have to be redesigned for a different RTS game. For
example, some games might not even have the concept of
production facilities. Regardless of performing hyperparam-
eter tuning, the computational cost is the highest using neu-
ral network models compared to other methods. While for
our approach, it works right from the beginning without re-
quiring hyperparameter tuning. Then as time goes by, it up-
dates accordingly with minimal computational cost. Figure
7 shows the forecasts from the neural network model MLP. It Figure 8: Forecasts from an exponential growth model
is similar to the forecast from the ARIMA model earlier as it
also predicts an upward trend. The variance associated with
the forecast is much smaller, which is an improvement. The
upward trend is a bit conservative, which results in a growing
discrepancy between the forecast and the actual unit count.
Figure 9: Forecasts from our proposed approach
roughly matching the one from the curve representing the
true values. This is mainly because we correctly inferred the
Figure 7: Forecasts from an MLP model number of production facilities the opponent had, although
there’s a slight delay on the time the opponent started to train
For the growth model, we had to stick with the exponen- the unit. Also, we were successful in predicting the potential
tial type as the logistic type is quite sensitive to the zero casualties incurred upon the opponent unit.
values in the early times, resulting in unsuccessful fitting
of the model. While for our approach there is no need to
choose/fit a model, as it is relatively model-free. Figure 8 Table 2: RMSE using different approaches from game 2 for
shows the forecasts from the exponential growth model. The the Protoss Zealot unit
results are not meaningful, as the predicted values are un- Growth
ARIMA MLP Proposed Baseline
reasonably huge, well beyond the maximum number of Pro- Model
toss Dragoon a player can possibly have, not to mention that One-step forecast
the fitting of the model to the training data set is poor. The RMSE 2.1 0.8 0.9 1.0 2.9
model is overly simplistic and gives almost no consideration Twelve-step forecast
to limiting factors such as available supply and resources. RMSE 1.3 1.4 132.0 0.8 4.7
One may argue that the other main type of growth model
(the logistic type) may be applicable here despite its compu- Tables 2 and 3 show the RMSE values from games 2 and
tational difficulty. However, logistic models assume that the 3, respectively. In both of these games, Locutus went for a
growth rate decreases with population abundance, which is single type of unit exclusively for a really long time. The
not necessarily true in StarCraft. other type of unit was only added into the army mix in the
Figure 9 shows the result of our proposed approach. last minutes of those games. Nonetheless, the presence of
First we correctly captured the growth rate of the Pro- multiple unit types still poses a challenge to the defogging.
toss Dragoon unit, as the slope of our forecast curve is With different build orders used by the opponent and a more
Acknowledgements
Table 3: RMSE using different approaches from game 3 for
the Protoss Dragoon unit The authors would like to specifically thank Nathan Roth
(MSc) for his assisstance on the making of the authors’ Star-
Growth Craft bot Halo. The authors would also like to thank Dan
ARIMA MLP Proposed Baseline
Model
Gant for his review on this paper and advice. The authors
One-step forecast
are equally thankful to Dennis Waldherr and his BASIL lad-
RMSE 2.4 1.7 1.7 1.2 2.6
der, as it provided an invaluable testbed-like environment for
Twelve-step forecast
RMSE 4.5 5.8 28639.0 1.1 2.1 this research.
References
complex army composition, our proposed approach was still Churchill, D., and Buro, M. 2011. Build order optimiza-
able to produce a reasonable forecast with the minimum tion in StarCraft. The Seventh AAAI Conference on Artificial
RMSE compared to values from other approaches in most Intelligence and Interactive Digital Entertainment (AIIDE)
cases. We were successful in maintaining the accuracy of 14–19.
the forecast by taking into account multiple unit types at the Fjell, M. S., and Møllersen, S. V. 2012. Opponent model-
same time, thus preventing us from under-/over-predicting. ing and strategic reasoning in the Real-Time Strategy game
For production facilities the Protoss faction possesses, it is StarCraft. Master thesis, Norwegian University of Science
not possible to train more than one unit at a time. This fact and Technology.
aided our inference on the number of production facilities Gehring, J.; Ju, D.; Mella, V.; Gant, D.; Usunier, N.; and
the opponent had, and such an inference is an advantage Synnaeve, G. 2018. High-level strategy selection un-
other approaches do not have. Additionally in game 3, the der partial observability in StarCraft: Brood War. doi:
casualty count of Locutus’ Protoss Dragoon unit was ex- https://arxiv.org/abs/1811.08568.
ceedingly high. But thanks to our consideration of potential Hagelbäck, J., and Johansson, S. J. 2009. Dealing with Fog
combat outcomes, we were able to adjust our forecast ac- of War in a Real-Time Strategy game environment. 55 – 62.
cordingly. 2008 IEEE Symposium on Computational Intelligence and
Games (CIG08). doi: 10.1109/CIG.2008.5035621.
Conclusion Hale, L., and Society, A. M. 1896. The Fog of War, by
Colonel Lonsdale Hale ... Tuesday, 24th March, 1896. Ed-
In this paper we proposed a customized approach to handle ward Stanford, 26 and 27, Cockspur Street, Charing Cross,
the challenge of performing defogging under partial observ- S.W.
ability. We infer the counts of different types of units the op-
ponent has by reasoning on several things, such as the num- Justesen, N., and Risi, S. 2017. Continual Online Evo-
ber of production facilities, currently collected intelligence lutionary Planning for in-game build order adaptation in
about the opponent, the outcome of a future skirmish, etc. StarCraft. 187 – 194. GECCO ’17: Proceedings of the
We utilize ECDF to handle the uncertainty brought about Genetic and Evolutionary Computation Conference. doi:
by the Fog of War. We also employ information entropy to https://doi.org/10.1145/3071178.3071210.
adjust the sampling rate properly. In our case studies we Killick, R.; Fearnhead, P.; and Eckley, I. A. 2012.
demonstrated the effectiveness of our proposed approach Optimal detection of changepoints with a linear
and illustrated its supriority over a few mainstream ones computational cost. Journal of the American Sta-
such as ARIMA, MLP, and growth models. tistical Association 107’(500):1590–1598. doi:
There are a few things that we’d like to work on in the https://doi.org/10.1080/01621459.2012.737745.
future: 1) opponent build order classification/identification. Ontanón, S.; Synnaeve, G.; Uriarte, A.; Richoux, F.;
Proper opponent build order classification would allow us Churchill, D.; and Preuss, M. 2013. A survey of Real-
to select which of the previous games should be used based Time Strategy game AI research and competition in Star-
on the BO identified in the current game, thus facilitating Craft. IEEE Transactions on Computational Intelligence
the forecast process; 2) opponent intent inference. Currently and AI in games 5(4):293–311.
we assume that the opponent would choose the unit which Setear, J. K. 1989. Simulating the fog of war. Research
would counter our army the best. In reality, things are more report, RAND Corporation.
complex. For example, there can be multiple such units to Synnaeve, G.; Lin, Z.; Gehring, J.; Gant, D.; Mellla, V.;
choose from, or the opponent feints us by choosing to train Khalidov, V.; Carion, N.; and Usunier, N. 2018. Forward
sub-optimal units, so that we are led to situations that are modeling for partial observation strategy games - a StarCraft
hard to transition out of; 3) further reducing the delay in defogger. Advances in Neural Information Processing Sys-
the forecast. Although we were able to achieve good RMSE tems 31:10759 – 10770. doi: arXiv:1812.00054.
values, there’s still a gap in time between our forecast values
and the actual ones. On top of the factors that we are already Vinyals, O.; Ewalds, T.; Bartunov, S.; Georgiev, P.; Vezhn-
considering such as map terrain and unit speed, there are yet evets, A. S.; Yeo, M.; Makhzani, A.; Küttler, H.; Agapiou, J.;
potentially important ones, into which we can dive deeper, and Schrittwieser, J. 2017. StarCraft II: A new challenge for
such as unit waiting time. Reinforcement Learning. arXiv preprint, arXiv:1708.04782.