Jonathan C. Brant and Kenneth O. Stanley (2019)
Benchmarking Open-Endedness in Minimal Criterion Coevolution.
In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2019).  New York, NY: ACM (8 pages).


Minimal criterion coevolution (MCC) was recently introduced to show that a very simple criterion can lead to an open-ended expansion of two coevolving populations. Inspired by the simplicity of striving to survive and reproduce in nature, in MCC there are few of the usual mechanisms of quality diversity algorithms: no explicit novelty, no fitness function, and no local competition. While the idea that a simple minimal criterion could produce quality diversity on its own is provocative, its initial demonstration on mazes and maze solvers was limited because the size of the potential mazes was static, effectively capping the potential for complexity to increase. This paper overcomes this limitation to make two significant contributions to the field: (1) By introducing a completely novel maze encoding with higher quality mazes that allow indefinite expansion in size and complexity, it offers for the first time a viable, computationally cheap domain for benchmarking open-ended algorithms, and (2) it leverages this new domain to show for the first time a succession of mazes that increase in size indefinitely while solutions continue to appear. With this initial result, a baseline is now established that can help researchers to begin to mark progress in the field systematically.