Evolutionary computation (EC) can be used to discover good game playing strategies with respect to a fixed group of existing opponents. Competitive coevolution (CC) is a generalization of EC in which the opponents also evolve, making it possible to find strategies for games in which no good players already exist. Since the performance criterion in CC changes over generations, a Coevolutionary Memory (CM) of good opponents is required to avoid regress. The layered Pareto Coevolution Archive (LAPCA) was recently proposed as an effective CM that guarantees monotonic progress under certain assumptions. The main limitation of LAPCA is that it requires numerous game evaluations because it has to determine Pareto-dominance relations between players. The Hall of Fame (HOF), consisting of previous generation champions, is an easier CM to implement and needs no extra evaluations besides those required by evolution. While the LAPCA has only been demonstrated in artificial numeric games, the HOF has been applied to real world problems such as the coevolution of neural networks.

This thesis makes three main contributions. First, a technique is developed that interfaces the LAPCA algorithm with NeuroEvolution of Augmenting Topologies (NEAT), which has been shown to be an efficient method of neuroevolution in game playing domains. The technique is shown to keep the total number of evaluations in the order of those required by NEAT, making it applicable to practical domains. Second, the behavior of LAPCA is analyzed for the first time in a complex game playing domain: evolving neural network players for the game of Pong. Third, although LAPCA and HOF perform equally well in this domain, LAPCA is shown to require significantly less space than the HOF. Therefore, combining NEAT and LAPCA is found to be an effective approach to coevolution; the main task for the future is to test it in domains that are more susceptible to forgetting than Pong, where it can potentially lead to improved performance as well.

PDF

Masters Thesis, Department of Computer Sciences, The University of Texas at Austin, Austin, TX, 2005.

@MastersThesis{monroy:ms05, title={Coevolution of Neural Networks Using a Layered Pareto Archive}, author={German A. Monroy}, school={Department of Computer Sciences, The University of Texas at Austin}, address={Austin, TX}, url="http://nn.cs.utexas.edu/?monroy:ms05", year={2005} }