Fitness approximation for bot evolution in genetic programming: Lessons learned from the UT2004 TM computer game
Created by W.Langdon from
gp-bibliography.bib Revision:1.7954
- @Article{journals/soco/Esparcia-AlcazarM13,
-
author = "Anna I. Esparcia-Alcazar and Jaroslav Moravec",
-
title = "Fitness approximation for bot evolution in genetic
programming: Lessons learned from the UT2004 TM
computer game",
-
journal = "Soft Computing",
-
year = "2013",
-
volume = "17",
-
number = "8",
-
pages = "1479--1487",
-
month = aug,
-
keywords = "genetic algorithms, genetic programming, Game,
Computationally expensive fitness functions, SoftBot
evolution, Fitness approximation, Similarity
estimation, Unreal Tournament 2004, phenotypic
entropy",
-
ISSN = "1432-7643",
-
bibdate = "2013-07-11",
-
bibsource = "DBLP,
http://dblp.uni-trier.de/db/journals/soco/soco17.html#Esparcia-AlcazarM13",
-
DOI = "doi:10.1007/s00500-012-0965-7",
-
language = "English",
-
size = "9 pages",
-
abstract = "Estimating the fitness value of individuals in an
evolutionary algorithm in order to reduce the
computational expense of actually calculating the
fitness has been a classical pursuit of practitioners.
One area which could benefit from progress in this
endeavour is bot evolution, i.e. the evolution of
non-playing characters in computer games. Because
assigning a fitness value to a bot (or rather, the
decision tree that controls its behaviour) requires
playing the game, the process is very costly. In this
work, we introduce two major contributions to speed up
this process in the computer game Unreal Tournament
2004. Firstly, a method for fitness value approximation
in genetic programming which is based on the idea that
individuals that behave in a similar fashion will have
a similar fitness. Thus, similarity of individuals is
taken at the performance level, in contrast to commonly
employed approaches which are either based on
similarity of genotypes or, less frequently,
phenotypes. The approximation performs a weighted
average of the fitness values of a number of
individuals, attaching a confidence level which is
based on similarity estimation. The latter is the
second contribution of this work, namely a method for
estimating the similarity between individuals. This
involves carrying out a number of tests consisting of
playing a static version of the game (with fixed
inputs) with the individuals whose similarity is under
evaluation and comparing the results. Because the tests
involve a limited version of the game, the
computational expense of the similarity estimation plus
that of the fitness approximation is much lower than
that of directly calculating the fitness. The success
of the fitness approximation by similarity estimation
method for bot evolution in UT2K4 allows us to expect
similar results in environments that share the same
characteristics.",
- }
Genetic Programming entries for
Anna Esparcia-Alcazar
Jaroslav Moravec
Citations