The Co-Evolvability of Games in Coevolutionary Genetic Algorithms

This paper investigates the ability of coevolutionary genetic algorithm to solve games. Specifically, it focuses on two-player, zero-sum and symmetric games with both pure and mixed strategies. Games with mixed strategies are challenging for coevolution since the Nash strategy does not yield a higher payoff. On the other hand, games with pure strategies are more co-evolvable especially when the diversity is maintained in the population. Empirically, adopting niching techniques such as restricted tournament selection helps coevolution. Finally, this paper demonstrates the existence of games that require an exponential population size with respect to the size of the game. These issues are presented empirically using simpl