Methods for Competitive Co-Evolution: Finding Opponents Worth Beating

Abstract

Co-evolution refers to the simultaneous evolution of two or more genetically distinct populations with coupled fitness landscapes. In this paper we consider "competitive co-evolution," in which the fitness of an individual in a "host" population is based on direct competition with individual(s) from a "parasite" population. Competitive coevolution is applied to three game-learning problems: Tic-Tac-Toe (TTT), Nim and a small version of Go. Two new techniques in competitive co-evolution are explored. "Competitive fitness sharing" changes the way fitness is measured, and "shared sampling" alters the way parasites are chosen for testing hosts. Experiments using TTT and Nim show a substantial improvement in performance when these methods are used. Preliminary results using co-evolution for the discovery of cellular automata rules for playing Go are presented. 1 Introduction Co-evolution refers to the simultaneous evolution of two or more genetically distinct populations with coupled fit...