[Zurück]

J. Inführ:
"Automatic generation of 2-antwars players with genetic programming";
Betreuer/in(nen): G. Raidl; Institut für Computergraphik und Algorithmen, 2010; Abschlussprüfung: 07/2010.

Im Rahmen dieser Arbeit wird die Möglichkeit der automatischen Generierung von
Spielern für das Spiel 2-AntWars untersucht. 2-AntWars ist eine Generalisierung von Ant-
Wars. AntWars wurde für einen Wettbewerb der Genetic and Evolutionary Computation
Converence 2007 erfunden. 2-AntWars ist ein Spiel für zwei Spieler, wobei jeder Spieler
die Kontrolle über zwei Ameisen auf einem Spielfeld hat. Auf diesem Spielfeld ist Futter
an zufälligen Orten platziert und die Aufgabe der Spieler ist es, mehr Futter zu finden als
der jeweilige Gegner.
Um das Problem zu lösen wird ein Modell für das Verhalten eines 2-AntWars Spielers
entwickelt und Genetic Programming, eine populationsbasierte evolutionäre Methode
zur Programminduktion, wird verwendet um Spieler basierend auf diesem Modell zu erstellen.
Die Machbarkeit dieses Ansatzes wird gezeigt, indem Spieler sowohl per Evolution
im Kampf gegen fixe Spielstrategien als auch per Koevolution im Kampf gegeneinander
entwickelt werden.
Ein weiterer Kernpunkt dieser Arbeit ist die Analyse der Dynamik die während der
Entwicklung der Spieler auftritt, sowohl von der evolutionären Perspektive als auch von
den zur Schau gestellten Verhaltensweisen der Spieler her. Das beinhaltet spezielle Eigenschaften
der Spieler (wie zum Beispiel welche Ameise wieviel Futter sammelt) aber auch
die Strategien der Spieler auf höherer Ebene und wie sie sich an ihre Gegner anpassen.
Die Ergebnisse zeigen, dass es in der Tat möglich ist erfolgreiche 2-AntWars Spieler
zu erzeugen die in der Lage sind, fixe Strategien ihrer Gegner zu schlagen. Das ist ein Resultat
das vor allem für Spieldesign-Probleme wichtig ist, da es für eine gute Spiel-Balance
unumgänglich ist, dass für jede Spielstrategie eine Gegenstrategie existiert. Mit Hilfe der
dargelegten Methode ist es möglich, solche Gegenstrategien automatisiert aufzufinden.
Der Versuch 2-AntWars Spieler von Grund auf durch Spiele gegeneinander zu entwickeln
war ebenfalls von Erfolg gekrönt. Das zeigt, dass es möglich ist, künstliche Intelligenz
für Spiele (und im Prinzip für alle Probleme die als Spiele formuliert werden können) zu
erzeugen, ohne Spielstrategien von Hand entwerfen zu müssen.
Die Verhaltensweisen die die entwickelten 2-AntWars Spieler an den Tag legten waren
überraschend vielfältig. Ameisen wurden als Köder verwendet, versteckt und wurden generell
verwendet um Schwächen im Spiel des Gegners schamlos auszunutzen. Das gewählte
Populationsmodell machte die simultane Entwicklung von Spielern mit verschiedenen
Spielstrategien in derselben Population möglich, ohne dies explizit zu fördern, beispielsweise
indem Spieler einer Strategie vor Spielern einer anderen Strategie geschützt werden.
Es zeigte sich, dass sowohl Mutations- als auch Crossover-Operationen für die Entwicklung
von leistungsfähigen 2-AntWars Spielern notwendig sind.

In the course of this thesis, the feasibility of automatically creating players for the game
2-AntWars is studied. 2-AntWars is a generalization of AntWars which was introduced as
part of a competition accompanying the Genetic and Evolutionary Computation Conference
2007. 2-AntWars is a two player game in which each player has control of two ants on a
playing field. Food is randomly placed on the playing field and the task of the players is to
collect more food than the opponent.
To solve this problem a model of the behaviour of a 2-AntWars player is developed
and players are built according to this model by means of genetic programming, which is a
population based evolutionary algorithm for program induction. To show the feasibility of
this approach, the players are evolved in an evolutionary setting against predefined strategies
and in a coevolutionary setting where both players of 2-AntWars evolve and try to beat each
other.
Another core part of this thesis is the analysis of the evolutionary and behavioural dynamic
emerging during the development of 2-AntWars players. This entails specific characteristics
of those players (e.g. which ant found how much food) and on a higher level their
behaviour during games and the adaption to the behaviour of the opponent.
The results showed that it is indeed possible to create successful 2-AntWars players that
are able to beat fixed playing strategies that oppose them. This is a solution to an important
problem of game designers as a well balanced game needs to have a feasible counter strategy
to every strategy and with the help of the proposed method such counter strategies can be
found automatically.
The attempt to create 2-AntWars players from scratch by letting the developed players
battle each other was also successful. This is a significant result as it shows how to automatically
create artificial intelligence for games (and in principle for any problems that can
be formulated as games) from scratch.
The developed solutions to the 2-AntWars problem were surprisingly diverse. Ants
were used as bait, were hidden or shamelessly exploited weaknesses of the opponent. The
population model that was chosen enabled the simultaneous development of players with
different playing strategies inside the same population without resorting to any special measures
normally associated with that like explicitly protecting a player using one strategy
from a player using another one. Both mutation and crossover operators were shown to be
essential for the creation of high performing 2-AntWars players.

http://publik.tuwien.ac.at/files/PubDat_188772.pdf