Call For Papers
IEEE CIG 2005 Tutorials
All tutorials are included in the conference registration fee.
Practical Issues in Evolving Neural Network Controllers for Video Game Agents
Kenneth O. Stanley
Artificial Neural Networks (ANNs) are appealing controllers for video game
agents (i.e. non-player-characters; NPCs) because they can encode a variety of
realistic and intelligent behaviors with relatively simple representations and
low CPU burden. Unlike scripts that must be carefully hand-coded, ANNs can be
automatically evolved using genetic algorithms to fit the task. Evolving ANNs,
also called neuroevolution, has achieved increasing popularity among both video
game enthusiasts and Artificial Intelligence (AI) researchers in recent years.
For example, the NERO video game, in which ANN-controlled agents evolve in real
time while interacting with the player, has been downloaded over 65,000 times
since its 2005 release.
This tutorial will draw upon a significant accumulation of practical knowledge
that is rarely explained comprehensively in research
publications. The aim is to overcome practical challenges that arise when
evolving ANNs for video games, thereby lowering the barrier to entry.
Topics will include egocentric (i.e. deictic) perspective, heading, discrete
object sensing, contiguous object sensing, non-traditional sensors, sensor
resolution and cost, world symmetry, output configuration, multi-agent
processing, pre-game evolution, in-game real-time interactive evolution,
idiosyncratic behavior, and initialization from scripts. The tutorial will
conclude with a discussion session aimed at helping attendees start their own
Kenneth O. Stanley is an Assistant Professor in the School of
Computer Science at the University of Central Florida. His research focuses on
artificially evolving complex solutions to difficult real-world tasks. He
graduated magna cum laude with a B.S.E. in Computer Science Engineering and a
minor in Cognitive Science from the University of Pennsylvania in 1997. He
received an M.S. in Computer Science in 1999, and a Ph.D. in 2004 at the
University of Texas at Austin. He has won best paper awards for his work on NEAT
(at the 2002 Genetic and Evolutionary Computation Conference) and for his work
on NERO (at the IEEE 2005 Symposium on Computational
Intelligence and Games), and also won the Independent Games Festival Student
Showcase Award (at the 2006 Game Developers conference) for NERO. He has
published papers in JAIR, Evolutionary Computation, IEEE Transactions on
Evolutionary Computation, and Artificial Life journals.
This tutorial addresses the state-of-the-art of computer go in two parts:
old-fashioned computer go, and Monte-Carlo (MC) go.
In a first part, the tutorial shows the results achieved by "old-fashioned" go
programs on 19x19 boards since the beginning of computer go (i.e.medium on the
human scale). This average result is firstly caused by the game tree size that
forbids global tree search using classical techniques (alpha-beta and
Building accurate evaluation functions is a second difficulty addressed more or
less awkwardly by old-fashioned go programs. These go programs are
knowledge-based systems performing local and goal-directed searches with very
few global aspects. First, the impossibility to perform global tree search,
second, the hand-crafted-knowledge-based splitting of a global position into
sub-positions in order to perform local tree searches, and third, hand-crafted
evaluation functions lead to erratic behaviour of go programs in the curse of a
whole game played on 19x19 boards.
In a second part, the tutorial shows how the Monte-Carlo approach has enriched
the picture recently. To evaluate a non terminal position, the MC method in Go
consists in launching a lot of random games starting from this position, and
playing them out until terminal positions are reached (terminal position means a
position covered with stones and true eyes, and consequently easy to score).
Then, the MC evaluation of a position is the mean of the scores encountered. MC
evaluations cost a lot of time, but they are robust, and their precision
improves with the time available. To this extent, the previous second difficulty
of evaluating non terminal positions is thus smoothed. As proved by the results
obtained this year by UCT - Upper bound Confidence for Tree, a method inherited
Multi-Armed Bandit problem community - on 9x9 boards, the term Monte-Carlo Tree
Search (MCTS) is now meaningful, and MCTS is an adequate tool addressing global
tree search in go, the previous first difficulty. Since the random games are
played out until the
end, and because the terminal positions are scored globally, MC applied to Go is
really global: the previous third difficulty of splitting down a position into
sub-positions has merely vanished, at least on 9x9 boards on which the best MC
programs now clearly outperform old-fashioned programs.
Although MC programs already play on 19x19 boards, they are still weaker than
old-fashioned go programs on boards of such size. The tutorial concludes by
showing to what extent strong 19x19 MC go programs can be created in the near
future to reach and eventually surpass the level achieved by old-fashioned
Born in Paris (France), Bruno Bouzy is Assistant
Professor of Computer Science in the Department of Mathematics and Computer
Science at the René Descartes University since 1997. His academic degrees
include two engineering school diplomas (Ecole Polytechnique 1984, Ecole
Nationale Supérieure des Techniques Avancées, 1986), a Ph.D. in Computer Science
(1995) and an Habilitation for Research Supervising in Computer Science (2004).
Between 1986 and 1991, he held a consulting engineer position with GSI, a
leading software advisory company. Bruno Bouzy is the author of the Go playing
program Indigo which won three bronze medals at the computer olympiads: two on
19x19 board (2004, 2006), and one on 9x9 board (2005).
Ian C. Parmee
This largely speculative tutorial will explore the manner in
which computational intelligence currently supports decision-making within
various problem-solving domains seemingly not associated with Gaming.
Similarities and peculiarities will then be identified along with potential
areas where a crossover of technology may be beneficial to all sectors. An
example may be collaborative problem solving scenarios in design where both
qualitative and quantitative criteria must constantly be satisfied to the
satisfaction of all parties to allow the design process to continue.
Alternatively, it has been shown that by presenting complex multi-variate
problems in the form of games where the players have to find variable
combinations that provide best performance can support implicit learning of
relationships that would seem to be impossible to define. The common factor is
that these are inherently people-centred processes where human intuition,
experiential knowledge and interaction play a major role. Research in various
areas is attempting to develop user-centric intelligent systems that support and
enhance human capability in those situations where high dimension, poor
definition and uncertainty are inherent characteristics. Can the Gaming
technologies provide a platform for the further development of such technology
or itself benefit from the ideas, concepts and experimental systems that are
Sevan G. Ficici
With increasing frequency, computer agents are participating in
collaborative and competitive domains in which humans reason and make decisions.
Examples include auctions, games, and tactical military systems. The deployment
of computer agents in such domains requires that the agents understand something
about human behavior so that they can interact successfully with people. In this
tutorial, we will discuss the construction of computer agents that are sensitive
to human social utilities. Our discussion will begin with background on
classical game theory, bounded-rational agents, and behavioral economics. We
will then highlight new efforts at computational modeling of human behavior in
games and how these models can be used to build computer agents that interact
successfully in mixed groups of people and computers.
Sevan G. Ficici is currently a Post-Doctoral Fellow in computer
science at Harvard University. He received his Ph.D (2004) from
Brandeis University and has a Master's (1990) in music theory from the Eastman
School of Music. His research interests include
evolutionary dynamics, game theory, multiagent systems, machine learning,
robotics, and computer analysis of music.