Gram-Elites: Fusing Probabilistic Style with Quality-Diversity Search

TL;DR

Gram-Elites is a significant evolution for Procedural Content Generation (PCG). By marrying N-gram models (capturing local style) with MAP-Elites (capturing global diversity), the authors created a system that generates game levels that "feel" like the original game while exploring a vast range of difficulty and layout possibilities. The secret sauce? Making the mutation and crossover operators "smart" so they only produce levels that actually make sense.

The Problem: The "Broken Level" Trap

In the world of PCGML (Procedural Content Generation via Machine Learning), we want two things:

1. Quality/Style: The level should look and feel like Mario or Kid Icarus.
2. Diversity: We want thousands of different levels—some hard, some easy, some flat, some vertical.

Standard Quality-Diversity algorithms like MAP-Elites are great at #2 but struggle with #1. They use "blind" genetic operators—essentially randomly swapping or flipping tiles. This often results in "Frankenstein" levels: a Mario level with a pipe floating in mid-air or a gap that is impossible to jump.

Prior works tried to fix this by using a fitness function to kill off "bad" levels. However, this is computationally expensive. It's like trying to write a Shakespearean play by randomly hitting keys on a typewriter and only checking if the result is English after the page is full.

Methodology: N-Gram Operators (The "How")

The core insight of Gram-Elites is to embed the rules of the game's style directly into the mutation and crossover steps.

1. The N-Gram Backbone

An N-gram model learns the probability of a "slice" (a column of tiles) appearing after a certain sequence of previous slices. It captures the local "grammar" of the game.

2. Intelligent Connection (The BFS Secret)

When Gram-Elites performs crossover (combining two level segments), it doesn't just stitch them together. It looks at the "end prior" of the first segment and the "start prior" of the second. It then uses a Breadth-First Search (BFS) through the N-gram's probability table to find a valid sequence of tiles that connects the two.

In the figure above, the "Cs" represent the generated connection slices that bridge two parents while maintaining stylistic validity.

Experiments: Testing across Genres

The authors tested Gram-Elites on three distinct games:

• Super Mario Bros. (Side-scroller)
• Kid Icarus (Vertical platformer)
• DungeonGrams (A custom roguelike with switches and spikes)

Results & SOTA Comparison

The results were clear: Gram-Elites (ME-NGO) filled more of the "behavioral grid" (the map of diverse level types) than standard operators (ME-SO).

The heatmaps show that Gram-Elites more consistently finds usable, completable levels (bins with higher percentages) compared to the baselines.

In Kid Icarus, the difference was particularly stark. Standard operators struggled to maintain the vertical structural requirements, whereas Gram-Elites successfully explored almost the entire behavioral space of density and leniency.

Deep Insights & Future Work

The brilliance of Gram-Elites lies in its Inductive Bias. By constraining the search space to only "generable" sequences, it avoids the vast "void" of invalid levels.

Limitations & Challenges:

• The "Strongly-Connected" Requirement: For the BFS connection to work, the N-gram must be able to get from any state to any other state. If the training data is too sparse, the operators might fail to find a bridge.
• Likelihood vs. Generability: Currently, the operators only care if a sequence can exist, not if it's likely. This can sometimes lead to "extreme" or weird-looking levels that are technically valid but statistically improbable.

Conclusion

Gram-Elites represents a shift in PCGML. Instead of letting an AI dream up anything and then correcting it, we are providing the AI with a "stylistic compass" (the N-gram) to guide its exploration. This ensures that the diversity we find is not just noise, but meaningful, playable variation.