ARTIKEL KOMPUTER :P

artikel komputer

Imitation-Based Evolution of Artificial Players
in Modern Computer Games
Steffen Priesterjahn
University of Paderborn
Department of Computer Science
33098 Paderborn, Germany
spriesterjahn@upb.de
ABSTRACT
Because of the rapid progress of commercial computer games in
recent years the development of artificial characters that inhabit the
presented game worlds has become a challenging task with very
specific requirements. A very important feature of artificial intelligence
for games is that, as the objective of computer games is
the entertainment of the player, the artificial game agents should
not only be competitive but also show intelligent and human-like
behaviours. Therefore, this paper proposes the usage of imitation
techniques to generate more human-like behaviours in an action
game, whereas the imitation is achieved by recording players and
by using these recordings as the basis of an evolutionary learning
approach.
Categories and subject descriptors:
I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence—
Intelligent agents, Multiagent systems; I.2.6 [Artificial Intelligence]
Learning—Knowledge Acquisition
General Terms: Algorithms
Keywords: Artificial Intelligence, Entertainment and Media,
Games, Heuristics, Machine Learning
1. INTRODUCTION
Many modern computer games feature very complex and highly
dynamic virtual worlds with realistic physics. However, the artificial
intelligence routines of the characters that inhabit these game
worlds - usually called game AI - is often static and relies on prewritten
scripts [1]. Scientific research in the area of game AI has
therefore concentrated on the deployment of learning methods to
create competitive agents - often with very high performing results
[2, 3].
However, creating game AI for a real game should also have
the goal to create more entertaining and believable game agents.
Therefore, gaming characters should not be as good as possible or
be almost invincible. They should show some sophisticated humanlike
behaviours. For example in an action game, the agents should
not just aggressively try to inflict as much damage as possible. It
is much more desirable that they try to use the map structure for
Copyright is held by the author/owner(s).
GECCO’08, July 12–16, 2008, Atlanta, Georgia, USA.
ACM 978-1-60558-131-6/08/07.
taking cover or try to trick their opponents.
The question is how such a behaviour can be achieved. In our
opinion, a pure learning approach based on the optimisation of behaviour
is inappropriate because it usually just optimises the raw
performance of the game agents. We argue that to behave humanlike,
an agent should base its behaviour on how human players play
the game and try to imitate them. This should especially be the case
in computer games in which human and artificial players meet at
the same level and where it is quite simple to record the behaviour
of a human player.
However, a raw imitation of other players is usually not able to
generate competitive performance. The reason for this lies in inherent
errors that are made in the imitation process - e.g. by assuming
a certain state and action model - that usually deteriorate the performance
of the imitator. Therefore, we propose to devise an optimisation
method on top of a representation that is based on recorded
player behaviour to obtain competitive and imitating agents.
This paper presents an imitation-based approach that uses an
evolutionary algorithm as the additional optimisation method, to
successfully train imitating agents for combat in QUAKE III
(c
1999, id software) - a popular three-dimensional action game.
It is based on an evolutionary learning approach that we have published
in 2006 [6]. However, in this case, the evolutionary process
is mainly not used to create new knowledge, but to select the right
combination of imitated behaviour pieces and to smooth the resulting
behaviour. Though we have already published the basic concept
of the presented imitation approach in 2005 [5], this paper presents
a more refined method and more results on its application.
2. IMITATION-BASED LEARNING
To achieve imitation, the approach uses the recording of some
player. This recording contains state to action matches, whereas
the states are encoded as a grid of quadratic regions that cover the
vicinity of the observed player and that are aligned relatively to the
view direction of the observed player (see figure 1). The actions
are just the movement commands - e.g. go forward, left and turn
by some degrees. These matches are recorded 10 times per second.
Figure 1: Grid Computation
The imitating agents also use the same state and action model for
the encoding of their behaviour. Each agent is controlled by a list of
rules which map states to fitting actions. These rules are initialised
with random state to action matches from a recording which is the
basis for the desired imitation.
The evolutionary algorithm that tries to optimise the rule lists basically
uses a population of game agents to breed well performing
ones. The performance and fitness of an agent is computed from
the damage the agent applied to its opponents minus the damage
that it received over a certain timespan. In our experiments we
evaluate each agent for one minute by playing against the built-in
QUAKE III agent because it presents a constant opponent that can
be used as a benchmark. In addition, the experiments also use the
QUAKE III agent as the imitation source because this makes it possible
to see, if the imitating agents can become competitive. In
addition, the QUAKE III agents show a very distinctive behaviour
that helps to judge the quality of the show imitation.
Concerning the evolutionary operators, recombination is
achieved by uniform crossover between two rule lists. Only mutation
can change the structure of the rules themselves by adding
small changes to the proposed movement commands. We assume,
that the recording already contains all important states and, therefore,
apply no mutation on the grids. Selection works according to
a (10+50) selection scheme. We keep the parents in the population
to better cope with the uncertain fitness function.
3. RESULTS
In the following we will shortly state the most important results
of the extensive experiments that we have conducted. For a detailled
analysis we refer to [4]. Figure 2 shows the mean and maximum
performance of each generation in the best parameter setup,
averaged over 20 runs. A performance of 0 means that the agent
has inflicted about the same damage as it has received. Therefore,
the agents in the population becomes in average as good as their opponents
and role models. The best individuals are able to reliably
defeat their opponent.
-1000
-500
0
500
1000
1500
0 10 20 30 40 50 60 70
performance
generation
mean performance maximum performance
Figure 2: Results of the best Setup
The striking result of the experiments is that the imitation-based
initialisation has a strong effect on the performance and the behaviour
of the evolved agents. The reached maximum performance
is considerably lower than the results of the pure evolution1 in [6].
Therefore, the evolution of competitive behaviour when starting
1The best agents reached a performance of above 2500
from an imitation rule base seems to be a harder problem. However,
it should be expected that the performance of an imitating
agent is closer to the level of its role model.
Concerning the gaming behaviour of the agents, the result is that
they very closely imitated the QUAKE III agents2 In the first generations
the right combination of rules had to be sorted out and
the agents behaved quite randomly. Though, they already showed
a much more valid gaming behaviour as a randomly initialised
agent. Then - beginning with approximately the fifth generation
- the agents started to closely mirror the QUAKE III agent in its
movements. Later, in the course of the evolution, the agents took
more and more freedom in their movements. For example, some
agents started to take cover behind a wall while their weapon
reloaded. This behaviour was not present in the rule base and represents
a level of sophistication in the learnt behaviour that was not
shown by our previous pure learning approach [6].
The presented system can be used to train certain aspects of the
behaviour of an artificial opponent based on the imitation of other
players. If an agent should show a certain behaviour, the usage of
imitation will allow it to just demonstrate the desired behaviour.
Our approach has also turned out to prevent disadvantageous behaviours,
because they impair the fitness of the agent. Such behaviours,
e.g. getting stuck in corners or standing still, have been
eliminated in all experiments after at most 20 to 30 generations.
The generated agents, though having a lower performance, showed
a much higher level of sophistication in their behaviour and appeared
much more human-like as the agents that were generated
by using plain evolution [6]. However, it should be noted that the
presented approach is only able to base its results on the imitation
of the respective role model but not to fully imitate it because of
the added rule optimisation. Therefore, the imitating agents will
always only imitate the behaviours that have proven to be useful.
In addition, the method can not be applied to an online scenario in
an ongoing game because it often generates defective agents which
compromises the gaming experience. To achieve this more cautious
variation operators would be needed.
4. REFERENCES
[1] M. Buckland. Programming Game AI by Example. Wordware
Publishing, 2005.
[2] S. M. Lucas and G. Kendall. Evolutionary Computation and
Games. IEEE Computational Intelligence Magazine, 1:10–18,
2006.
[3] R. Miikkulainen, B. D. Bryant, R. Cornelius, I. V. Karpov,
K. O. Stanley, and C. H. Yong. Computational Intelligence in
Games. Computational Intelligence: Principles and Practice,
pages 155–191, 2006.
[4] S. Priesterjahn. Online Adaptation and Imitation in Modern
Computer Games. PhD thesis, University of Paderborn, 2008.
[5] S. Priesterjahn, O. Kramer, A. Weimer, and A. Goebels.
Evolution of Reactive Rules in Multi-Player Computer Games
Based on Imitation. In Proceedings of the International
Conference on Natural Computation (ICNC’06), volume 2,
pages 744–755. Springer, 2005.
[6] S. Priesterjahn, O. Kramer, A. Weimer, and A. Goebels.
Evolution of Human-Competitive Agents in Modern
Computer Games. In Proceedings of the IEEE Congress on
Evolutionary Computation (CEC’06), pages 777–784. IEEE
Press, 2006.