Co-Evolvability of Games in Coevolutionary Genetic Algorithms
Date Issued
2009
Date
2009
Author(s)
Lin, Wei-Kai
Abstract
This thesis investigates the ability of coevolutionary genetic algorithms to evolve game-playing strategies. Specifically, it focuses on two-player, zero-sum and symmetric games with both pure and mixed strategies. Pure and mixed strategies are discussed separately. Co-evolving the mixed strategy Nash equilibrium is challenging since the Nash strategy does not yield a higher payoff than other strategies. This argument is verified on the game of rock-paper-scissor, where all mixed strategies yield the same expected payoff and fail to converge to the Nash quilibrium. On the other hand, pure strategies are more co-evolvable with some games especially when the diversity is maintained in the population. Empirically, adopting nichingechniques such as restricted tournament selection and deterministic crowding helps coevolution. Furthermore, this work empirically shows the trade-off between the population size and the optimal number of opponents used to evaluate an individual. Finally, this thesis demonstrates the existence of game strategies that require an exponentially large population with respect to the size of the game. In such games, exponentially many opponents need to be maintained to evolve an optimal strategy.
Subjects
genetic algorithm
coevolution
game theory
niching techniques
optimal sampling
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96921073-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):24ae185e1bbd6f57de7c10140903c209