Computational Intelligence - February 2017 - 46

sub-genres include arcade games, shooter games and platform games. In fact,
many of the video game genres can be
considered the extensions on or variations of action games.
Role-playing games (RPGs) are
another popular type of video game.
These games are generally characterized
by a strong storyline and a set of formal
game playing rules. One or more players
take on a role or a character in a given
story and perform actions that match the
story line. Conversely, the story might
unfold according to the players' actions.
Players are usually characterized by personality traits that define their capabilities
and action preferences. The massively
multi-player online role-playing games
(MMORPGs) are played among a large
number of players on social media or on
the internet. Non-player-characters
(NPCs) are introduced in these games to
make the finctional settings more realistic. The CI-based techniques, including
LCS, can be applied to model and control both the player and non-player characters in these games. Fallout [51], with its
different versions, is an example of a
famous RPG.
Real-time strategy (RTS) games are
also a popular class of video games. In
RTS games, players' actions are usually
related to resource planning in a continuously changing environment. In these
games, one or more players control a set
of semi-autonomous entities to perform
a real-time task, such as winning a military battle or a race. Star Craft, War Craft
and Supreme Commander are examples of
famous RTS games. The modeling of
artificial agents for playing RTS games is
quite challenging because of the diversity of multi-tasking that is inherent in
these games.
B. Combinatorial Games

Combinatorial games (aka board games)
usually involve two players who compete in sequential moves with perfect
information about each game state.
Chess and Go are famous examples of
such games, which have been the subject of rigorous research in AI for a long
time. AI approaches usually focus on
modeling agents or algorithms that can

compete with human experts in these
games. A brute-force strategy used is to
explore the space of all state-action possibilities and choose the best course of
action to achieve a goal, such as be the
first to complete a task. While for some
simpler games (e.g., Nim and Tic-tac-toe),
such a strategy works well, for more
complex games (e.g., Chess and Go) an
exhaustive search is impractical. Approximate techniques or other AI/CI techniques are commonly employed in these
situations to model intelligent agents
that could perform at the level of their
human competitors.
C. Simulation Games

Simulation games attempt to model
some aspects of real-world situations,
such as stock market trading or traffic
control. These games have numerous
uses in areas such as education, training,
policy, and system analysis and design.
While modeling and simulation is an
established field for dealing with issues
in these fields, games provide an engaging environment for the users to achieve
similar objectives. For example, simulation games are used to train surgeons for
complex surgeries [52]. Artificial agents
can play various roles in these games.
For instance, they may be used to colearn their strategies from the human
players [53] or to evolve challenging
scenarios for the trainees [54].
D. Game Theory

Game theory is a well-established mathematical approach to study the competition between rational decision-making
agents with wide-ranging applications in
economics and, political, biological and
computer sciences. CI-based approaches
extend the game-theoretic models in
simulated environments through developing agent models that aim to mimic
purely rational and human-like behaviors [55]. In a typical two-player game
(e.g., the Prisoner's Dilemma (PD)
game), two strategic players make discrete choices independently (e.g., cooperate or defect). These games can be
extended easily to become multi-player
or iterative games, in which players consider the outcomes of their previous

IEEE ComputatIonal IntEllIgEnCE magazInE | FEbruary 2017

moves in deciding their actions at each
iteration. Iterated Prisoner's Dilemma
(IPD) is a well-known example of this
type of game model.
Evolutionary game theory (EGT)
[56] is a more recent branch of game
theory that extends game-theoretic
models to study the population-based
evolutionary dynamics. The GA-based
approaches have been well studied in
EGT, as a result of Axelrod's seminal
work [57]. Standard GA-based agents
are conventionally used in the EGT
models to study the evolution of strategies under varying game conditions.
LCS-based strategic agents provide distinct advantages over traditional GAbased agent encoding, such as their
ability to generalize across the strategy
space and their ability to encode larger
memory sizes. It is rather surprising that,
despite this potential, only a handful of
researchers have explored the use of
LCS (reviewed in the next section) for
modeling the game-theoretic agents.
V. LCS in Games

This section presents a comprehensive
survey of LCS applications under the
four categories discussed in the previous section: video games, combinatorial
games, simulation games, and game
theory. The papers in each category
(and sub categories) are reviewed in a
chronological order. As discussed in a
later section, the first major piece of
work reported in the literature on the
explicit use of LCS for games was
Seredyski et al. [58]. Several game-like
environments, such as the infamous
"maze" or "woods" problems [23], were
introduced as evaluation benchmarks in
the early LCS research. Smith also tested his Pittsburgh-style LCS (LS-1) in a
poker-betting domain [59]. However,
this survey does not cover those studies,
which focused on testing LCS capabilities in typical multi-step RL tasks.
A. Video Games

A small number of researchers have
focused on modeling NPCs using LCS.
Robert et al. [60]-[62] introduced
MHiCS, a Modular and Hierarchical
Classifier System, for modeling NPCs in

Table of Contents for the Digital Edition of Computational Intelligence - February 2017