Looking for Complexity at Phase Boundaries in Continuous Cellular Automata

Vassilis Papadopoulos, Guilhem Doat, Arthur Renard, Clément Hongler

In the quest to create Artificial Life (Alife), researchers often find themselves lost in a desert of boring parameters. Most configurations of a complex system lead to either total stillness or chaotic noise. A new paper from researchers at EPFL proposes a clever shortcut: if you want to find the "interesting" stuff, look exactly where the system is about to break.

TL;DR

The researchers introduce the Phase Transition Finder (PTF), a lightweight algorithm that identifies parameters at the boundary between different system states (e.g., "dead" vs. "alive"). By targeting these phase transitions in the continuous cellular automata system Lenia, they more than doubled the frequency of discovering complex, life-like emergent behaviors compared to random sampling.

What Problem Does This Paper Address?

Designing systems that exhibit emergent, life-like behaviors—such as self-reproducing "creatures" or stable moving "gliders"—is a central challenge in Alife. Systems like Lenia (a continuous version of the Game of Life) have massive, high-dimensional parameter spaces. In the case of multi-channel Lenia, there are over 100 real-valued parameters to tune.

The "Goldilocks zone" where interesting dynamics happen is incredibly small. Most parameters result in a "dead" world (everything vanishes) or an "exploding" world (everything becomes noise). Traditional ways to find these zones, like genetic algorithms or gradient descent, are computationally expensive and often require a specific goal. The authors wanted a faster, more general way to "home in" on complexity without needing heavy machine learning machinery.

Methods

The authors propose the Phase Transition Finder (PTF) algorithm, which relies on a simple intuition from statistical physics: complexity often emerges at the "edge of chaos" or phase boundaries.

  1. Define Phases: They define two mutually exclusive phases. For Lenia, these are "dead" (average cell activation falls below a threshold) and "living" (everything else).
  2. Sample and Connect: They randomly sample parameters until they find two points that belong to different phases.
  3. Dichotomy (Binary Search): They draw a path between these two points in parameter space and use a binary search (dichotomy) to find the exact point where the system transitions from one phase to the other.
  4. Efficiency Hacks: To keep the search fast, they run the initial phase-checking simulations on a tiny 5x5 grid for a short duration before testing the resulting "transition parameters" on a larger toroidal world.

Datasets

The paper does not use external datasets. Instead, it uses the multi-channel Lenia framework as its experimental testbed. They evaluated their algorithm using two different "priors" (starting ranges for parameters):

  • Neutral Prior: Parameters generated uniformly across a broad range.
  • Smart Prior: A constrained range where the "ground state" is mathematically likely to be unstable, ensuring a better balance between dead and alive phases.

Key Insights and Ideas

  • Phase Transitions as a Proxy for Complexity: The most significant insight is that the boundary between "nothing happens" and "everything happens" is mathematically predisposed to scale invariance and non-trivial emergent structures.
  • Lightweight Search: Unlike Reinforcement Learning or Genetic Algorithms, PTF doesn't need a "fitness function" or a training phase. It just needs a binary definition of a phase.
  • Mitosis and Self-Reproduction: The authors observed that self-reproduction (solitons splitting into two) is a surprisingly common occurrence at these phase boundaries, suggesting that "mitosis" might be a fundamental feature of transition regions in Lenia.
  • The "Signal" Problem: The authors argue that the main barrier to using Deep Learning for Alife is the low "signal-to-noise" ratio of interesting behaviors in random data. PTF acts as a high-quality filter to create better datasets for future ML models.

Key Results

The researchers compared PTF against random sampling and found a significant "boost" in interestingness:

  • Yield Increase: Using a "smart" prior, random sampling yielded interesting dynamics 14.0% of the time. Applying PTF to that same prior jumped the success rate to 30.5%.
  • Efficiency: The algorithm is fast. It generated 100 phase transition points in roughly 4 minutes and 20 seconds on a single RTX 3080 GPU.
  • Qualitative Diversity: The method successfully discovered a wide variety of "creatures," including solitons, gliders, and complex multi-colored interacting structures that are rarely seen in random searches.

Limitations and Future Work

  • Prior Sensitivity: PTF still requires a human to define a "prior" region. If the prior doesn't contain a phase boundary, the algorithm can't find one.
  • "Soft" Transitions: Not all boundaries are sharp. Some lead to "critical slowing down," where the system takes a very long time to die but doesn't produce interesting structures. Currently, PTF cannot distinguish these from "sharp" transitions that produce gliders.
  • Human-in-the-loop: The evaluation of what is "interesting" still relies on visual inspection. The authors suggest that the next step is training a machine learning model on PTF-generated data to automate the "interestingness" detection.
  • Beyond Lenia: The authors are interested in applying this to other systems, like Flow-Lenia, where mass is conserved and the definition of "dead" must be reimagined.

Summary updated

Abstract

One key challenge in Artificial Life is designing systems that display an emergence of complex behaviors. Many such systems depend on a high-dimensional parameter space, only a small subset of which displays interesting dynamics. Focusing on the case of continuous systems, we introduce the 'Phase Transition Finder'(PTF) algorithm, which can be used to efficiently generate parameters lying at the border between two phases. We argue that such points are more likely to display complex behaviors, and confirm this by applying PTF to Lenia showing it can increase the frequency of interesting behaviors more than two-fold, while remaining efficient enough for large-scale searches.
BibTeX
@inproceedings{papadopoulos2024looking,
  author = {Vassilis Papadopoulos and Guilhem Doat and Arthur Renard and Clément Hongler},
  title = {{Looking for Complexity at Phase Boundaries in Continuous Cellular Automata}},
  booktitle = {GECCO Companion},
  year = {2024},
  doi = {10.1145/3638530.3654420},
}

Loading related content...

Figure