CS Paper Radar

Programmable Cellular Automata

Ahmed Khalifa, Muhammad Umair Nasir, Matthew Siper, Steve James, Julian Togelius

cs.NE cs.AIcs.FLcs.LG ·submitted 2026-09-05 13:54 UTC · v2
benchmark

Abstract

Cellular automata is a local computation paradigm where complex behavior can arise from local interactions between simple functions. This paradigm has been used to explain many systems such as biological processes, traffic simulation, computer networks, etc. In games, cellular automata have been used in games such as SimCity and for the generation of spatial content such as caves or dungeons. However, creating effective local rules is hard and unintuitive. Cellular automata can be effectively evolved, but may still be hard to interpret. In this work, we introduce the concept of programmable cellular automata, where we represent the system as Python code. We also modularize the cellular automata into local functions and a decision function. Local functions take a local neighborhood and return a value, while the decision function takes the output of the local functions and decides the value of the next state. Separating the cellular automata into modules written in Python helps with understanding how these systems are working. We also explore adding global functions where they take the whole state and compute a function from it. We tested generating levels for three different games from the PCG Benchmark. The results showed that global functions decrease the number of iterations that cellular automata need to solve a problem, and that we cannot find solutions for some problems with purely local functions. Looking into the generated functions, we can see common functions that have been used in different experiments, which not only helps us understand the generator but also helps us understand these games better and what is important for them.

Comment
Submitted to EXAG 2026, 15 pages, 6 figures, 5 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Reasoning with Neural Cellular Automata

cs.LG cs.AIcs.MAnlin.CG ·2026-09-28 ·Mayalen Etcheverry, Pietro Miotti, Aidan Sirbu, Konstantin Schürholt, Mariia Drozdova +5 more
similarity 0.56
Abstract

Modern AI architectures used to solve visual reasoning tasks typically rely heavily on global connectivity and synchronization. As biological systems demonstrate, though, sophisticated computation can be performed in a more decentralized fashion. In this work, we test the reasoning capabilities of Neural Cellular Automata (NCAs), networks of recurrent cells that use strictly local connectivity and asynchronous updates. NCAs have been extensively studied in artificial life experiments, but it is unclear whether they can perform complex multi-step reasoning. We show that NCAs produce spatio-temporal dynamics capable of solving challenging visual reasoning tasks, including large mazes, Sudoku, and ARC-AGI-1. Furthermore, we provide evidence that NCAs generalize out-of-distribution when running with larger grids, longer rollouts, or parallel trials; and that the latter can be made more efficient via pruning of redundant trajectories. We find that these generalization capabilities depend on training with sample replay and stochastic perturbations, and that stochasticity remains beneficial at test time. Finally, we show that NCAs are robust reasoners capable of dynamically modulating compute to recover efficiently from damage, and that they can scale to solve reasoning in raw pixel space.

0.43

Emergent Models: Intelligence from Tiny Substrates

cs.NE cs.LG ·2026-08-14 ·Giacomo Bocchese, Nicola Giacobbo, Etienne Guichard, James Wiles, Akshaj Devireddy
theory similarity 0.55
Abstract

Emergent Models (EMs) are a machine learning paradigm based on simple yet open-ended substrates, such as cellular automata, in which modeling is treated not as the learning of a closed-form input-output map but as the emergence, within simple dynamical systems, of computational behaviors that solve external tasks. Such substrates typically iterate a fixed local rule over a latent space for an adaptive number of steps, with an interface linking the latent state to external input/output signals. Training proceeds by evolutionary search. We hypothesize that some instances of this framework are biased toward global generalization: capturing the rule generating the data over its full domain, and therefore extrapolating beyond the training range. Theoretically, we prove that some EMs are latent-universal: with the update rule and interface held fixed, they can realize any partial computable function by varying only the initial condition of the latent state. Empirically, we study a zoo of minimal EM instantiations across discrete and continuous substrates, showing that local-recursive computation at a tiny scale (tens to hundreds of parameters) can extrapolate exactly on simple arithmetic functions, can support control behaviour and online adaptation, while still exposing several limitations. This work is foundational: it does not propose a competitive architecture, but a framework meant to widen the design space of machine learning beyond differentiable feed-forward maps.

0.04

ConwayNet: Interpretability, Activation Coherence, and Noise Resilience via a Game-of-Life-Inspired Lateral Inhibition in Artificial Neural Networks

cs.LG ·2026-11-07 ·Yair Cohen, Scott M. Gilmore
similarity 0.54
Abstract

Deep neural networks achieve universal function approximation by stacking interconnected nonlinearities, but as a consequence they are sensitive to noise and resist mechanistic interpretation. In contrast, the local update rules of cellular automata, such as Conway's Game of Life, give rise to not merely interpretable but programmable dynamics. We explore a bridge between these worlds: a lateral inhibition in neural networks based on continuous Game-of-Life rules that derives inhibitory and excitatory responses from the layer input and blends them into the activation map in a state-conditioned way. The mechanism is differentiable and architecture-agnostic, and its regulation is imposed rather than learned: the rule's parameters are fixed and are not optimised, while the rule's values and derivatives shape training throughout the network. Wired into fully connected, convolutional, wide-residual and graph convolutional networks, it gives rise to several properties. Activation maps become coherent across space, depth and seeds, with coarse structure persisting through depth while fine detail is renewed at every layer. The co-activation graph of the hidden units departs from an Erdős--Rényi random graph: it is laid out on the image and its giant component grows in steps, as in a spatial graph. Networks started from nearly identical initialisations, under label noise, disagree on thirty times fewer test images. Saliency maps rest on the object rather than the background, and resilience to pixel noise not seen in training is substantially improved.

0.21

Why Do Conventional World Models Fail to Learn Cellular Automata?

cs.AI ·2026-09-30 ·Shaoyang Guo, Ziming Liu
code/data similarity 0.54
Abstract · 35 pages, 18 figures. Code and reproduction materials: https://github.com/guoshaoyang-pku/momentum-induction

Although conventional world models - auto-regressive or diffusion models based on transformers or convolutional networks - may learn surface statistics of world dynamics, can they learn the exact world dynamics from its observed history? Leveraging cellular automata as a simple testbed, we find the answer to be no in many cases. Conventional architectures predict most pixels correctly yet rarely complete a rollout: a CNN predicts 96.3% of cells but completes 18.9% of rollouts; a joint diffusion model completes none. We trace the gap to three failure modes of these world models - namely, they fail to exactly capture spatial locality, temporal locality or temporal stability. Simple changes repair each: (1) for spatial locality, two-dimensional rotary positions lift a transformer from 39.1% to 100% on the Game of Life; (2) for temporal locality, handing each token its cell's previous-frame neighbourhood lifts the same transformer from 25.8% to 99.9% on unseen rules; (3) for temporal stability, causal freezing lifts the same diffusion weights from 42.2% to 99.9%. None of the three changes touches the architectural backbone; each only modifies the information flow within it. We also compare joint and ordered sampling on billiards and, in an exploratory study, on a simulated Burgers equation.

0.39

Proceedings Seventeenth International Symposium on Games, Automata, Logics, and Formal Verification

cs.LO cs.FL ·2026-10-06 ·Giorgio Bacci, Mickaël Randour
published similarity 0.53
Abstract

This volume contains the proceedings of GandALF 2026, the Seventeenth International Symposium on Games, Automata, Logics, and Formal Verification. The symposium was held in Aalborg, Denmark, on September 15-17, 2026. The aim of GandALF 2026 is to bring together researchers from academia and industry who are actively working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-fertilisation.

0.33

Synthesizing Reactive Character Behaviors for Continuous Games via Programmatic Policy Search

cs.AI ·2026-09-21 ·Maxim Gumin, Hsueh-Ti Derek Liu, Victor Zordan, Daniel Ritchie
top venuebenchmark similarity 0.53
Abstract · To be presented at SIGGRAPH Asia 2026

We present a method for synthesizing reactive character behaviors for continuous games as compact, human-readable programs. Game AI practice still relies heavily on manually authored behavior trees, state machines, and scripts, while academic reinforcement learning typically produces opaque neural controllers that are expensive to train and difficult to edit. Our approach bridges this gap by searching directly over a domain-specific language for continuous-space game policies. The language is designed around reactive geometric decisions and includes higher-order constructs such as direction maximization. These constructs help discretize a continuous behavior space into enumerable program structures. To make program search practical, we introduce a large set of synthesis antipatterns that remove redundant program forms while preserving behavioral coverage. We further combine bottom-up symbolic enumeration with top-down guidance from a coding agent. Our resulting method, agentic sketching, has the agent propose high-level policy structure and call an enumerator to complete local program slots. We evaluate the method on a benchmark of 14 continuous games, ranging from classic control tasks to multi-agent football. We find that pure enumeration is often more efficient than using a coding agent alone, while the combined method substantially outperforms both. Our results suggest that programmatic policy search can be a practical authoring tool for game AI: designers specify reward functions, and the system discovers editable behaviors that are effective, portable, and often surprising.

0.41

2D Spatial Reasoning with Adaptive Neural Cellular Automata

cs.CV ·2026-10-06 ·Martin Spitznagel, Janis Keuper
similarity 0.53
Abstract

Many modern learning approaches are still struggling with spatial reasoning tasks, i.e. they lack the ability to utilize geometric information of perceived entities and their spatial relation to each other to solve problems. We introduce a novel Adaptive Neural Cellular Automata (aNCA) architecture which uses deformable convolutions to dynamically adapt the perceptive field and iteratively reason over 2D spatial relations on grid-like data structures (e.g. images). Empirical results on public benchmarks show state of the art comprehensible results with high generalization abilities for solving image based puzzles like Sudoku or finding the shortest path in a maze.

0.22

Collision-based logic in Lenia and its composition boundary

cs.ET nlin.CGnlin.PS ·2026-09-01 ·Chakshu Gupta
code/dataunusual similarity 0.53
Abstract · 12 pages, 6 figures, 3 tables; code at github.com/ChakshuGupta13/lab

Continuous cellular automata such as Lenia spontaneously produce lifelike, self-propelling patterns, including the Orbium glider, which travels in a straight line while pulsing through a fixed breathing cycle. Collision-based logic, where moving patterns compute by colliding, is established in discrete cellular automata and continuous physical media. Within continuous cellular automata, computation has so far been trained into the rule rather than emerging from collisions, and whether a fixed-rule automaton like Lenia can support general collision-based computation remains open. This paper constructs an INHIBIT gate from collisions of the Orbium glider. Of the patterns searched across four continuous-CA rule types, the Orbium glider is the only one shown to survive a collision with both copies intact. A control glider deflects a signal glider off its output line, so the output carries a signal only when no control is present. The gate blocks across all twenty-four phases of the breathing cycle and nine integer offsets of the control. Two such gates in series, with one signal line and two controls, compose into an AND-NOT chain, correct on all eight input combinations. By contrast, routing a signal beyond that single chain is undemonstrated. A deflected signal is not restored to a fixed landing position, and no reusable absorber for the surviving gliders was found. The immediate open question for collision-based computation in Lenia therefore narrows from whether a gate exists to whether a deflected signal can be delivered to a downstream gate, the next requirement for composing the gate beyond a single straight chain.

0.44