quality-diversity-search technique sourced
Quality-diversity search (MAP-Elites) for content and balance
Evolutionary search that keeps the best solution found in each cell of a grid of designer-chosen behavior descriptors, returning an archive of diverse high-quality levels, decks, or strategies instead of one optimum.
mechanism
The designer picks k behavior descriptors (for a level: enemy count and number of jumps; for a deck: mean mana cost and minion count) and discretizes them into a grid. Each cell stores the highest-fitness solution seen with those descriptor values. Each iteration selects elites from the archive, mutates or recombines them, evaluates the child's fitness and descriptors (usually by simulation or an agent playthrough), and inserts it if its cell is empty or it beats the incumbent. The archive shows which trait combinations can be good and how good. Variants slide cell boundaries to follow where solutions cluster (MESB), search a generative model's latent space with CMA-ES emitters (CMA-ME on a Mario GAN), use a learned surrogate to predict agent behavior and skip simulations (DSAGE), or use language models both to propose variations and to judge quality and diversity (QDAIF). GAVEL applies MAP-Elites to game rule sets.
limitations
- Every candidate needs a fitness and descriptor evaluation, usually a simulated playthrough, so large archives cost many simulations; surrogate methods such as DSAGE exist to cut that cost.
- Results depend on the chosen descriptors: poor choices give diversity along axes players do not perceive, and the grid grows exponentially with the number of descriptors.
- Fitness measured with AI agents reflects agent skill, not human experience, so cells marked playable or balanced may not match player perception.
- Game applications in the cited work are research prototypes on small games (Mario levels, Hearthstone decks); no documented shipped use in a simulation game was found in this run.
relations
6 stored edgesDesign performance rating
Searching for the top-scoring design in every descriptor cell stress-tests the rating formula and surfaces degenerate designs that score well, such as rides or bridges that game the metric.
Machine boosting
Searches over module and beacon layouts expose dominant boosting configurations that collapse design choice.
Modular assembly
Mapping the build space by behavior descriptors, as was done for Hearthstone decks, shows the best design in each style niche, exposing dominant part combinations and empty niches before players find them.
Procedural terrain
Instead of one seed-to-map generator, a game can ship an archive of maps spanning designer axes, such as resource density by chokepoint count, each verified by simulation and served to players by trait.
Rival firms
An archive of competitor strategies, each the strongest found for its niche (aggressive expander, low-price discounter), gives AI rivals distinct styles without hand-tuning each persona.
Scenario objectives
Scenario maps and starting conditions can be generated across a difficulty-by-style grid and filtered by agent playthroughs, replacing hand-built scenario sets with a curated archive.
backlinks
computed from other recordsclaims
6 with sourcesMAP-Elites (2015) returns a map of high-performing solutions across user-chosen dimensions of variation, revealing trade-offs and often finding a better best solution than standard search.
Gravina et al. (IEEE CoG 2019) framed procedural content generation as a quality-diversity problem and reviewed early applications to content generation and game playing.
MAP-Elites with sliding boundaries mapped Hearthstone deck spaces along play-style dimensions, found diverse strong decks, and was proposed as an aid to rebalancing.
CMA-ME searching a GAN's latent space produced playable Super Mario Bros levels spanning designer-chosen measures such as enemy and obstacle counts, and a user study found those measures changed perceived difficulty.
DSAGE (2022) used a deep surrogate to predict agent behavior in generated environments and beat earlier QD environment-generation methods at finding environments that elicit diverse agent behaviors.
QDAIF (2023) used language models to generate variations and to judge quality and diversity of creative text, covering more of the target space than non-QD baselines with reasonable agreement with human raters.