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.8051

@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