Evolving Complexity in Prediction Games

To study open-ended coevolution, we define a complexity metric over interacting finite state machines playing formal language prediction games, and study the dynamics of populations under competitive and cooperative interactions. In the past purely competitive and purely cooperative interactions have been studied extensively, but neither can successfully and continuously drive an arms race. We present quantitative results using this complexity metric and analyze the causes of varying rates of complexity growth across different types of interactions. We find that while both purely competitive and purely cooperative coevolution are able to drive complexity growth above the rate of genetic drift, mixed systems with both competitive and cooperative interactions achieve significantly higher evolved complexity.