Enhancements to Constrained Novelty Search: Two-Population Novelty Search for Generating Game Content

Antonios Liapis, Georgios N. Yannakakis, Julian Togelius

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Novelty search is a recent algorithm geared to explore search spaces without regard to objectives; minimal criteria novelty search is a variant of this algorithm for constrained search spaces. For large search spaces with multiple constraints,
however, it is hard to find a set of feasible individuals that is both large and diverse. In this paper, we present two new methods of novelty search for constrained spaces, Feasible-Infeasible Novelty Search and Feasible-Infeasible Dual Novelty Search. Both algorithms keep separate populations of feasible and infeasible individuals, inspired by the FI-2pop genetic algorithm. These algorithms are applied to the problem of creating diverse and feasible game levels, representative of a large class of important problems in procedural
content generation for games. Results show that the new algorithms under certain conditions can produce larger and more diverse sets of feasible strategy game maps than existing algorithms. However, the best algorithm is contingent on
the particularities of the search space and the genetic operators used. It is also shown that the proposed enhancement of offspring boosting increases performance in all cases.
Original languageEnglish
Title of host publicationGECCO '13 Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference
Number of pages8
PublisherAssociation for Computing Machinery
Publication date2013
ISBN (Print)978-1-4503-1963-8
Publication statusPublished - 2013


  • Novelty search
  • Constraint satisfaction
  • Genetic algorithms
  • Procedural content generation
  • Game level design


Dive into the research topics of 'Enhancements to Constrained Novelty Search: Two-Population Novelty Search for Generating Game Content'. Together they form a unique fingerprint.

Cite this