amounts of each friendly and enemy unit type (for
example, none, few, many). After building the case
base from just one replay of a human playing against
the in-built AI, the system was able to win around 60
percent of games (and tie in about 15 percent) against
the AI on the same map. However, it is unclear how
well the system would fare at the task of playing
against different races (unique playable teams) and
strategies, or playing on different maps.
By breaking up a problem hierarchically, planning
systems are able to deal with parts of the situation
separately at different levels of abstraction, reducing
the complexity of the problem, but creating a potential new issue in coordination between the different
levels (Marthi et al. 2005; Weber et al. 2010). A hierarchical plan maps well to the hierarchy of goals and
subgoals typical in RTS games, from the highest-lev-el goals such as winning the game, to the lowest-lev-el goals, which map directly to in-game actions.
Some researchers formalize this hierarchy into the
well-defined structure of a hierarchical task network
(HTN), which contains tasks, their ordering, and
methods for achieving them. High-level, complex
tasks in an HTN may be decomposed into a sequence
of simpler tasks, which themselves can be decomposed until each task represents a concrete action
(Muñoz-Avila and Aha 2004).
HTNs have been used for strategic decision mak-
ing in RTS games, but not for StarCraft. Muñoz-Avi-
la and Aha (2004) focus on the explanations that an
HTN planner is able to provide to a human querying
its behavior, or the reasons underlying certain
events, in the context of an RTS game. Laagland
(2008) implements and tests an agent capable of
playing an open source RTS called Spring11 using a
hand-crafted HTN. The HTN allows the agent to
react dynamically to problems, such as rebuilding a
building that is lost or gathering additional
resources of a particular type when needed, unlike
the built-in scripted AI. Using a balanced strategy,
the HTN agent usually beats the built-in AI in
Spring, largely due to better resource management.
Efforts to learn HTNs, such as Nejati, Langley, and
Konik (2006), have been pursued in much simpler
domains, but never directly used in the field of RTS
AI. This area may hold promise in the future for
reducing the work required to build HTNs.
An alternative means of hierarchical planning was
used by Weber et al. (2010). They use an active
behavior tree in A Behavior Language, which has
parallel, sequential, and conditional behaviors and
goals in a tree structure (figure 6) very similar to a
behavior tree (discussed in the next subsection).
However, in this model, the tree is expanded during
execution by selecting behaviors (randomly, or based
on conditions or priority) to satisfy goals, and different behaviors can communicate indirectly by reading or writing information on a shared whiteboard.
Hierarchical planning is often combined as part of
other methods, such as how Ontañón et al. (2007)
use a hierarchical CBP system to reason about goals
and plans at different levels.
Behavior trees are hierarchies of decision and action
nodes that are commonly used by programmers and
designers in the game industry in order to define
behaviors (effectively a partial plan) for agents (Palma
et al. 2011). They have become popular because,
unlike scripts, they can be created and edited using
visual tools, making them much more accessible and
understandable to nonprogrammers (Palma et al.
and Execution Trace
Figure 5. A Case-Based Planning Approach.
The approach uses cases of actions extracted from annotated game logs to form plans that satisfy goals in Wargus. Adapted from Ontañón
et al. (2007).