Programmable Cellular Automata
Ahmed Khalifa, Muhammad Umair Nasir, Matthew Siper, Steve James, Julian Togelius
cs.NE, cs.AI, cs.FL, cs.LG
2026-09-05
PCA evolves Python local, global, and decision functions with Claude 4.8 Opus. Zelda playability is 0% with no global function and 99% with one asynchronous global function.
Cellular automata grow complex structure from local rules. Games have used them for SimCity-style simulation and for cave maps. The rules are hard to write. Neural Cellular Automata replace the lookup table with a convolution, which is more expressive and much harder to read. Evolution can search for rules, but the result is often another pile of weights.
Researchers at the University of Malta, NYU, and the University of the Witwatersrand rewrite the automaton as programs. Each module is a Python function. Local functions see a 3×3 Moore neighborhood. Optional global functions see the whole grid. A decision function reads only those outputs, never the raw cell, and writes the next cell value. Local updates stay synchronous. Global functions run asynchronously so a count such as "one player already placed" reaches the next cell immediately. If that count were frozen at 0 for a whole sweep, the decision function would spawn a player in every empty cell.
A chromosome is l local functions, g global functions, and one decision function, all stored as Python strings. Code rather than kernels makes the rules readable and lets a code model act as the mutation operator. Uniform crossover copies whole functions from either parent. Mutation calls Claude 4.8 Opus with a 4096-token cap and feeds the rest of the chromosome plus the current fitness as context, so the new function has to fit the modules already present.
Fitness checks playability first, diversity second. Each generator runs on n=30 fixed random initial states for at most m=100 steps. Diversity distance enters the score only if every run is playable; otherwise that term is 0. The cascade stops unplayable but mutually different junk maps from ranking high.
The testbed is three games from the PCG Benchmark. Binary is a 14×14 maze that must be fully connected with a shortest path of at least 28 tiles. Zelda is an 11×7 dungeon with at least one player, one key, one door, and three enemies, and a key-then-door solution of at least 18 moves. Sokoban is 5×5 with one player, equal crates and targets, and an A solution of at least 10 moves. The sweep is l in {1,5,10,50} and g in {0,1,5}: 36 settings, 5 seeds each, 180 evolutionary runs. Population 40, 10% elitism, 50 generations, tournament size 7, 10% per-function mutation.
A global function is the on/off switch. The number of local functions barely is.
| Game | 0 global (l=1/5/10/50) | 1 global | 5 global |
| Binary | 100% / 100% / 97% / 99% | 98-100% | 98-100% |
| Zelda | 0% / 0% / 0% / 0% | 99% / 46% / 70% / 98% | 93% / 100% / 99% / 67% |
| Sokoban | 2% / 16% / 0% / 11% | 96% / 96% / 97% / 100% | 99% / 99% / 97% / 98% |
Zelda is 0% playable in every purely local setting and reaches 99%±1% once one global function is added. Sokoban peaks at 16%±32% with no global function and jumps above 96% with one. Binary is easy enough that purely local generators already sit near 100%. Fifty local functions are not a free lunch: Zelda with 5 global and 50 local functions falls to 67%±34%, while 5 local plus 5 global hits 100%.
Iteration count drops as well. Purely local Sokoban averages 90-100 steps, which is essentially the budget. With 1 global and 10 local functions it needs 6.863±4.806 steps. Zelda has no iteration number without a global function, because no playable room appears. Binary is fastest with 1 local and 0 global functions (6.903±0.934 steps). Extra modules sometimes slow the run down; evolution splits work across functions or keeps inefficient ones.
Diversity looks weak. The share of pairwise-distinct levels stays under 30% on the PCG Benchmark metric, and most Sokoban settings sit at 7-12%. Fitness can still reach about 1.7 because the diversity term uses distance, not a uniqueness rate. The strongest Zelda generator (50 local + 1 global) is worse by eye: it clears the map and randomly places the player, key, and door. The diversity metric scores shortest-path length, so shuffling those three items passes, and the rooms look dull.
Evolution rediscovers the same families of functions. On the global side, counters dominate (61%, 61%, and 43% of runs on Binary, Zelda, and Sokoban), followed by connected-component size. On the local side, neighborhood counts are the most common (100%, 85%, 66%), which turns the automaton into "count nearby tiles of this type, then decide." Those functions average about 5 lines.
For procedural level generation, the paper hardens an old observation. Global quantities such as counts and connectivity take on the order of the board width to propagate by local spreading. Hand the decision function an asynchronous counter and the problem gets easier. Because the rules are Python rather than kernels, people can read what evolution found. The same functions keep showing up across three games, which is a compact list of which constraints actually bind.
The paper does not claim to beat NCAs or hand-written automata. The comparison is with versus without global functions, and how many local functions to keep. On these small maps, if playability is the goal, one global function is often enough. Fifty local functions have no systematic payoff.
Each function is applied to one tile type at a time, so a BFS from player to key is inexpressible. The authors wanted simple functions. That choice also cuts the program space.
The diversity objective does not match visual variety. Zelda passes once path length is long enough, and the generator learns empty rooms plus shuffled items. The authors point to quality-diversity methods; this paper does not run them.
Global functions are no longer classical CA. Asynchronous updates make the count visible immediately, which is where the speed comes from and also a concession on purely local computation. Hidden-state channels, returning a Dijkstra map, and capping LLM output at 128 tokens appear only in the discussion. Mutation is locked to Claude 4.8 Opus. Whether another model rediscovers the same functions is unknown.