state instead of the current state in order to find
appropriate reactions to the opponent. Expectations
are also formed from the case library, using changes
in the opponent state to make predictions about
when new types of units will be produced. When an
expectation is not met (within a certain tolerance for
error), a discrepancy is created, triggering the system
to formulate a new goal. The resulting system
appeared to show better results in testing than the
previous ones, but further testing is needed to determine how effectively it adapts to unexpected situations (Weber, Mateas, and Jhala 2012).
Probabilistic plan recognition makes use of statistics
and expected probabilities to determine the most
likely future outcome of a given situation. Synnaeve
and Bessière (2011a), Dereszynski et al. (2011), and
Hostetler et al. (2012) carry out keyhole probabilistic
plan recognition in StarCraft by examining build
orders from professional replays, without any prior
knowledge of StarCraft build orders. This means they
should require minimal work to adapt to changes in
the game or to apply to a new situation, because they
can learn directly from replays without any human
input. The models learned can then be used to predict unobserved parts of the opponent’s current state,
or the future strategic direction of a player, given the
player’s current and past situations. Alternatively,
they can be used to recognize an unusual strategy
being used in a game. The two approaches differ in
the probabilistic techniques that are used, the scope
in which they are applied, and the resulting predictive capabilities of the systems.
Dereszynski et al. (2011) use hidden Markov models to model the player as progressing through a
series of states, each of which has probabilities for
producing each unit and building type, and probabilities for which state will be transitioned to next.
The model is applied to one of the sides in just one
of the six possible race matchups, and to only the
first seven minutes of game play, because strategies
are less dependent on the opponent at the start of
the game. State transitions happen every 30 seconds,
so the timing of predicted future events can be easily found, but it is too coarse to capture the more frequent events, such as building new worker units.
Without any prior information, it is able to learn a
state transition graph that closely resembles the
commonly used opening build orders (figure 12), but
a thorough analysis and evaluation of its predictive
power is not provided (Dereszynski et al. 2011).
Hostetler et al. (2012) extend previous work by
Dereszynski et al. (2011) using a dynamic Bayesian
network model for identifying strategies in StarCraft.
This model explicitly takes into account the reconnaissance effort made by the player — measured by
the proportion of the opponent’s main base that has
been seen — in order to determine whether a unit or
building was not seen because it was not present, or
because little effort was made to find it. This means
that failing to find a unit can actually be very informative, provided enough effort was made. The model is
also more precise than prior work, predicting exact
counts and production of each unit and building
type each 30-second time period, instead of just presence or absence. Production of units and buildings
each time period is dependent on the current state,
Figure 12. State Transition Graph.
As learned in Dereszynski et al. (2011), showing transitions with probability at least 0.25 as solid edges, and higher-probability transitions
with thicker edges. Dotted edges are low-probability transitions shown to make all nodes reachable. Labels in each state are likely units to
be produced, while labels outside states are a human analysis of the strategy exhibited. (Dereszynski et al. 2011).
Dragoon + Observer
Dragoon + Gateway
Arbiter tech Observatory
Support Bay /