Online imitation and adaptation in modern computer games [Elektronische Ressource] / Steffen Priesterjahn

University of Paderborn
Online Imitation and Adaptation
in Modern Computer Games
Steffen Priesterjahn
Dissertation
in Computer Science
submitted to the
Faculty of Electrical Engineering,
Computer Science and Mathematics
in partial fulfilment of the requirements for the degree of
doctor rerum naturalium
(Dr. rer. nat.)
Paderborn, December 2007II
Steffen Priesterjahn
Knowledge-Based Systems Research Group
Department of Computer Science
Faculty of Electrical Engineering, Computer Science and Mathematics
University of Paderborn
D-33095 Paderborn
Office: E4.153
E-Mail: spriesterjahn@uni-paderborn.de
Phone: ++49 (0)5251-60 3349
Fax: ++49 3338Abstract
Commercial computer games have significantly evolved in the recent decade. Current
games feature vast and highly detailed virtual environments with realistic physics,
complex and highly dynamic gameplay as well as complex multi-player game
modes. Therefore, the creation of sophisticated and intelligent game agents that
inhabit the game worlds and oppose or collaborate with the player has become a
considerable challenge in terms of competitive performance and fast adaptation, but
also concerning the believability and human-likeness of the shown behaviour.
This thesis gives a general introduction into the field of artificial intelligence in com-
puter games and proposes several approaches to create intelligent game characters for
a three-dimensional, action-oriented computer game. The focus of these approaches
is to create competitive and quickly adapting game agents that show sophisticated,
human-like behaviours. To achieve this, the proposed methods are based on the imita-
tion of other players and the usage of a population of several agents that collaborate to
accelerate the learning process. The foundation of the presented work lies in the util-
isation of powerful adaptation and learning techniques like evolutionary algorithms,
reinforcement learning and cultural learning.Inhaltsangabe
Computerspiele haben sich innerhalb des letzten Jahrzehnts signifikant weiter-
entwickelt. Aktuelle Spiele zeigen hochdetaillierte, virtuelle Umgebungen mit
realistischen Phyiskeffekten und verfugen¨ uber¨ vielfaltige¨ und hochdynamische
Spielmodi. Daruberhinaus¨ ermoglichen¨ viele Spiele die Teilnahme mehrerer Spieler.
¨ ¨ ¨Aus diesen Grunden ist die Erstellung von konkurrenzfahigen kunstlichen Spielern,
die in der Lage sind, sich in der Spielewelt autonom zu bewegen und sich schnell
an die menschlichen Spieler anzupassen, eine große Herausforderung. Insbesondere
muss dabei nicht nur auf die Performanz der Spieler, sondern auch auf ihre Glaubhaf-
tigkeit und menschenahnliche¨ Spielweise geachtet werden.
Diese Arbeit bietet eine allgemeine Einfuhrung¨ in das Thema der kunstlichen¨ Intelli-
genz fur¨ Computerspiele und stellt verschiedene Verfahren zur automatischen Erstel-
lung von intelligenten Spielecharakteren fur¨ ein dreidimensionales Actionspiel vor.
Das Hauptaugenmerk dieser Ansatze¨ liegt dabei darin, konkurrenzfahige¨ und schnell
lernende Agenten zu erstellen, die fortgeschrittene und menschliche Verhaltenswei-
sen zeigen. Um dies zu erreichen, basieren die vorgeschlagenen Methoden auf der
Imitation von anderen Spielern und der Ausnutzung einer Population von Agenten,
die gemeinsam lernt, um die Lerngeschwindigkeit zu steigern. Das Fundament bilden
dabei Adaptions- und Lerntechniken wie evolutionare¨ Algorithmen, Reinforcement
Learning und kulturelles Lernen.Acknowledgements
Several people have played an important role and have assisted in the creation of
this thesis. First and foremost I want to thank my wife Claudia and my son Tobias for
their strong support and for providing the distraction and family joy that I needed
after long working days. I also which to thank my family for providing me with the
support to start a scientific career.
In addition, I wish to thank my colleagues at the research group Knowledge-Based
Systems at the University of Paderborn. Especially I wish to thank Alexander Weimer,
Andreas Goebels and Oliver Kramer, for numerous fruitful discussions and for
sharing our visions, as well as my supervisor Prof. Kleine Buning¨ , for giving me a
research position and for believing into my topic. I also wish to thank the students
that have worked with me and have helped in the development of the used software
and the execution of various experiments - especially Matthias Keller as well as Felix
Schulte, Raphael Golombek, Christian Ikenmeyer, Markus Happe, Ulrich Scheller
and the members of the project group “Cooperative Intelligence”.
Steffen PriesterjahnContents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Part I Artificial Intelligence & Computer Games
2 An Introduction to Game AI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Basic Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 A Taxonomy of Computer Games. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Challenges in Game AI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1 Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Imitation & Memetics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Reinforcement Learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Swarm Intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1 Industry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Part II Working with QUAKE III & The CLIENTBOT INTERFACE
5 Working with QUAKE III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2 The Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.3 The “Complexity” of QUAKE III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4 The Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.5 Reengineering the QUAKE III Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101X Contents
6 The CLIENTBOT INTERFACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.1 The Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2 Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.3 The Subinterfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.4 The Shared Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Part III Imitation and Cooperation in QUAKE III
7 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8 Cooperative Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.2 The Danger Adaptive Waypoint System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9 Comba