Genetic evolution and co-evolution of game strategies

by

Koza, J., R.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: The International Conference on Game Theory and Its Applications, Stony Brook, New York. July 15, 1992 (Conference proceedings), 1992
Keywords:genetic algorithms, genetic programming
Abstract:
The problem of discovering a strategy for playing a game is an important problem in game theory. [GT] This problem can be viewed as requiring discovery of a computer program. The desired computer program takes either the entire history of past moves in the game or the current state of the game as its input and produces the next move as its output. This paper describes the recently developed genetic programming paradigm [GP] which genetically breeds populations of computer programs to solve problems. In genetic programming, [GP] the individuals in the population are independently acting hierarchical compositions of functions and arguments of various sizes and shapes. Each of these individual computer programs is evaluated for its fitness in playing the game. A simulated evolutionary process driven by this measure of fitness then uses the Darwinian principle of reproduction and survival of the fittest and the genetic operation [GO] of crossover (sexual recombination) to solve the problem. Genetic programming [GP] can also operate simultaneously on two (or more) populations of programs. In such "co-evolution," each population acts as the environment for the other population. In particular, each individual of the first population is evaluated for "relative fitness" by testing it against each individual in the second population, and, simultaneously, each individual in the second population is evaluated for "relative fitness" by testing it against each individual in the first population. In this paper, genetic programming [GP] is illustrated with three different problems. The first problem involves genetically breeding a population of computer programs to find an optimal strategy for a player of a discrete two-person 32-outcome game represented by a game tree in extensive form. In this problem, the entire history of past moves of both players is used as input to the computer program. The second problem involves genetically breeding a minimax control strategy in a differential game with an independently-acting pursuer and evader. In this problem, the state of the game is used as input to the computer program. The third problem illustrates the "co-evolution" and involves genetically breeding an optimal strategy for a player of a discrete two-person 32-outcome game represented by a game tree in extensive form.
Notes:
Paper presented at
Author(s) DL:Online papers for Koza, J., R.
Internet search:Search Google
Search Google Scholar
Search Citeseer using Google
Search Google for PDF
Search Google Scholar for PDF
Search Citeseer for PDF using Google

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{Koza:1992:GPgs,
  author =       "John R. Koza",
  title =        "Genetic evolution and co-evolution of game
                 strategies",
  booktitle =    "The International Conference on Game Theory and Its
                 Applications, Stony Brook, New York. July 15, 1992",
  year =         "1992",
  keywords =     "genetic algorithms, genetic programming",
  abstract =     "The problem of discovering a strategy for playing a
                 game is an important problem in game theory. This
                 problem can be viewed as requiring discovery of a
                 computer program. The desired computer program takes
                 either the entire history of past moves in the game or
                 the current state of the game as its input and produces
                 the next move as its output. This paper describes the
                 recently developed genetic programming paradigm which
                 genetically breeds populations of computer programs to
                 solve problems. In genetic programming, the individuals
                 in the population are independently acting hierarchical
                 compositions of functions and arguments of various
                 sizes and shapes. Each of these individual computer
                 programs is evaluated for its fitness in playing the
                 game. A simulated evolutionary process driven by this
                 measure of fitness then uses the Darwinian principle of
                 reproduction and survival of the fittest and the
                 genetic operation of crossover (sexual recombination)
                 to solve the problem. Genetic programming can also
                 operate simultaneously on two (or more) populations of
                 programs. In such {"}co-evolution,{"} each population
                 acts as the environment for the other population. In
                 particular, each individual of the first population is
                 evaluated for {"}relative fitness{"} by testing it
                 against each individual in the second population, and,
                 simultaneously, each individual in the second
                 population is evaluated for {"}relative fitness{"} by
                 testing it against each individual in the first
                 population. In this paper, genetic programming is
                 illustrated with three different problems. The first
                 problem involves genetically breeding a population of
                 computer programs to find an optimal strategy for a
                 player of a discrete two-person 32-outcome game
                 represented by a game tree in extensive form. In this
                 problem, the entire history of past moves of both
                 players is used as input to the computer program. The
                 second problem involves genetically breeding a minimax
                 control strategy in a differential game with an
                 independently-acting pursuer and evader. In this
                 problem, the state of the game is used as input to the
                 computer program. The third problem illustrates the
                 {"}co-evolution{"} and involves genetically breeding an
                 optimal strategy for a player of a discrete two-person
                 32-outcome game represented by a game tree in extensive
                 form.",
  notes =        "Paper presented at",
}