Evolving Many Worlds: Towards Open-Ended Discovery in Petri Dish NCA via Population-Based Training

This paper introduces PBT-NCA, a population-based training algorithm that evolves Petri Dish Neural Cellular Automata to sustain open-ended complexity and diverse emergent lifelike phenomena by rewarding behavioral novelty and visual diversity while penalizing static or random states.

The Gist

Imagine you have a giant, digital petri dish. Inside this dish, you drop in a few tiny, invisible "creatures" made of code. These creatures are like microscopic robots that can only see the cells immediately next to them. They have one goal: to survive and take up as much space as possible.

In most computer experiments, these digital creatures quickly get bored. They either freeze into a static, boring pattern (like a frozen pond), turn into chaotic static noise (like a broken TV screen), or one single type of creature eats everyone else until the dish is empty. This is called "collapse."

The Big Idea: The "Evolutionary Zoo"
The authors of this paper wanted to stop this collapse and create a world that never stops evolving. They created a system called PBT-NCA.

Think of PBT-NCA not as a single experiment, but as a massive, automated zoo with 30 different "worlds" running at the same time.

1. The Contest: In every world, the digital creatures fight for territory.
2. The Judges: Instead of judging them on who wins the most land, the judges (the computer algorithm) look for novelty and diversity.
   • Novelty: "Have we seen this behavior before?" If a creature does something weird and new, it gets points.
   • Diversity: "Does this world look different from the other 29 worlds right now?" If it looks unique, it gets points.
3. The Survival of the Fittest (and Funniest): Every few rounds, the computer checks the scores. The worlds that are boring or have collapsed are thrown out. They are replaced by "children" of the most interesting worlds.
4. The Twist: These children aren't perfect copies. They get a little "mutation." Maybe their learning speed changes, or their internal code gets a tiny glitch. This is like evolution in nature: you keep the good traits but mix in random changes to see if something even cooler pops up.

What Happened? (The Magic Show)
Because the system was constantly pressured to be "new" and "different," it didn't just find one solution. It discovered a whole library of lifelike behaviors that the researchers didn't program it to do. It's like telling a group of artists, "Don't paint what you've seen before; paint something totally new," and watching them invent entirely new art styles.

Here are some of the amazing things the digital creatures learned to do on their own:

• The "Spore" Strategy: Some groups of creatures learned to shoot out little clusters of themselves, like dandelion seeds, to colonize distant parts of the dish.
• The "Glider" and "Spaceship": Just like in the classic game Conway's Game of Life, they created shapes that could move across the screen, carrying information with them.
• The "Amoeba": They formed giant, fluid blobs that could change shape, move around, and even split apart to reproduce.
• The "Archipelago": They built stable islands of territory that looked like a chain of islands, with creatures living in harmony inside them.

The "Edge of Chaos"
The paper mentions a concept called the "Edge of Chaos." Imagine a tightrope walker.

• On one side is Order: Everything is rigid, frozen, and predictable (like a crystal).
• On the other side is Chaos: Everything is random, noisy, and meaningless (like static).
• The Edge: The sweet spot right in the middle. Here, things are structured enough to have a shape, but flexible enough to change and move.

The PBT-NCA system kept its digital creatures walking this tightrope. They never froze, and they never turned into noise. They stayed in that magical middle ground where complex life happens.

Why Does This Matter?
This isn't just about making cool animations. It's a step toward Artificial Superintelligence.
To build a truly smart AI, we can't just program it to solve one math problem. We need to create systems that can keep learning, adapting, and inventing new things forever—just like nature did for billions of years.

This paper shows that if you set up the right "rules of the game" (rewarding novelty and diversity), simple digital cells can spontaneously evolve into complex, lifelike societies without a human telling them how to do it. It's like giving a digital ecosystem a nudge and watching it discover its own version of biology.

Technical Summary

1. Problem Statement

The generation of sustained, open-ended complexity from local interactions is a fundamental challenge in artificial life. While differentiable multi-agent systems like Petri Dish Neural Cellular Automata (PD-NCA) can exhibit rich self-organization through spatial competition, they suffer from significant instability:

• Hyperparameter Sensitivity: They are highly sensitive to hyperparameters.
• Collapse Modes: Without careful tuning, they frequently collapse into uninteresting dynamics, such as:
  • Frozen equilibria: Static, non-moving patterns.
  • Structureless noise: High-entropy, random fluctuations.
  • Monocultures: A single agent dominating the entire substrate, eliminating diversity.
• Lack of Open-Endedness: Traditional training aims for a fixed target, leading to convergence rather than perpetual innovation. The goal is to operate at the "edge of chaos"—a phase transition between order and randomness where complex, adaptive dynamics emerge.

2. Methodology: PBT-NCA

The authors introduce PBT-NCA (Population-Based Training of Petri Dish Neural Cellular Automata), a meta-evolutionary algorithm designed to evolve a population of PD-NCA worlds under continuous novelty-driven pressure.

A. The Substrate (PD-NCA)

• Multi-Agent Competition: A shared 2D grid where $N$ neural network agents (species) compete for territory.
• State Representation: Each cell contains attack channels, defense channels, and a hidden state.
• Competition Mechanism: Agents propose updates based on local Moore neighborhoods. A "winner-takes-most" mechanism (soft-maxed cosine similarity between attack/defense vectors) determines the cell's new state.
• Survival Pressure: A background "environment" agent constantly applies random noise, forcing active agents to maintain defenses to survive, preventing evolutionary stagnation.
• Learning: Agents optimize their internal weights via gradient descent to maximize their "log-aliveness" (territorial expansion) over a rollout horizon.

B. Population-Based Training (PBT) Loop

Instead of training a single world, PBT-NCA maintains a population of $P$ worlds. The process follows an Exploit-Explore cycle (inspired by Jaderberg et al., 2017):

1. Rollout & Scoring: All worlds are rolled out for a fixed horizon.
2. Composite Scoring: Each world is scored based on a composite function $F = N + D$:
   • $N$ (Archive Novelty): Measures behavioral novelty against a history of past behaviors. It uses handcrafted ecological descriptors (mean occupancy, temporal variance, turnover, entropy) and calculates the Euclidean distance to the $k$-nearest neighbors in a FIFO archive.
   • $D$ (Visual Diversity): Measures visual distinctiveness against the current population. It uses a frozen DINOv2 encoder to embed frames and computes the median cosine distance between a world's frames and all other worlds' frames at the same timestep.
3. Selection & Replacement:
   • The top-$m$ worlds (by score) are added to the archive.
   • The bottom $\rho$ fraction of low-scoring worlds are discarded.
   • Lamarckian Inheritance: Discarded worlds are replaced by mutated copies of elite parents. This includes:
     • Copy: Inheriting weights, optimizer states, and world state.
     • Crossover: Swapping hyperparameters between parent and child.
     • Mutation: Perturbing hyperparameters (e.g., learning rate) and adding Gaussian noise to weights.

3. Key Contributions

• Novelty-Driven Meta-Evolution: Unlike previous methods that search over frozen configurations, PBT-NCA applies selection pressure to a population where agents adapt their local rules while interacting.
• Dual-Objective Scoring: The combination of handcrafted ecological descriptors (for behavioral novelty) and foundation model embeddings (DINOv2) (for visual/morphological diversity) prevents the system from collapsing into trivial solutions.
• Autonomous Discovery of Strategies: The system spontaneously discovers complex survival strategies without explicit objectives for cooperation or specific morphologies.
• Edge-of-Chaos Stabilization: The method successfully maintains the system in the "edge of chaos" regime, balancing order and randomness to sustain complex dynamics.

4. Results

Experiments were conducted with populations of 30 worlds, varying the number of agents (3, 5, 7) and meta-iterations (up to 500).

Emergent Phenomena

PBT-NCA generated a plethora of lifelike, emergent behaviors, including:

• Coordinated Waves: Highly regular, periodic waves.
• Spore-like Scattering: Homogeneous groups ejecting cell clusters to colonize distant territories (self-replication).
• Fluid Macro-Structures: Shape-shifting entities that migrate across the substrate while maintaining stable boundaries.
• Decentralized Locomotion: Trail-like movement patterns arising purely from local interactions (e.g., "gliders," "shooters," "pirate worlds").
• Geometric Patterns: In extended search spaces, the system discovered rigid, circuit-like patterns and information propagation.

Quantitative Performance

• Composite Score: The mean composite score steadily increased over meta-iterations, indicating the continuous generation of novel dynamics.
• Scalability: Systems with more agents (7 NCAs) retained higher levels of novelty in later training stages compared to smaller populations.
• Hyperparameter Adaptation: The system naturally selected for higher learning rates and smaller batch sizes, which injected necessary gradient noise to prevent stagnation.
• Edge-of-Chaos Metrics:
  • Ecological Persistence (EP): Remained near 1.0, indicating sustained multi-agent coexistence (no monocultures or extinction).
  • Effective Complexity ($C_{eff}$): Averaged ~0.21, significantly above the zero baselines of pure order or pure noise, confirming the system operates at the edge of chaos.

Baseline Comparisons

• Fixed Hyperparameters: Collapsed into high-entropy noise.
• Random Search: Found some cyclic dynamics but failed to sustain open-ended complexity or diversity over long horizons.

5. Significance

• Open-Ended Artificial Life: PBT-NCA demonstrates a viable path toward artificial systems that do not converge to a single solution but instead perpetually accumulate behavioral and structural diversity.
• Biological Realism: The emergent behaviors (migration, self-replication, phase separation, territorial competition) closely mirror biological phenomena observed in nature, suggesting the system captures fundamental principles of evolution.
• Computational Primitives: The emergence of stable "regular domains" and moving structures (gliders) hints at the potential for the substrate to perform emergent computation.
• Red Queen Dynamics: The system effectively implements a "Red Queen" hypothesis, where agents must constantly evolve just to survive against an ever-changing competitive landscape, driving perpetual innovation.

In conclusion, PBT-NCA transforms the training of Neural Cellular Automata from a static optimization problem into a dynamic, open-ended evolutionary process, successfully sustaining complex, lifelike dynamics at the edge of chaos.