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

  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
  ISSN =         "1432-7643",
  bibdate =      "2013-07-11",
  bibsource =    "DBLP,
  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

Genetic Programming entries for Anna Esparcia-Alcazar Jaroslav Moravec