PaperlayerView exact revision on arXiv

Source-linked AI summary

Programmable Cellular Automata

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

arXiv:2609.06102v2cs.NEcs.AIcs.FLcs.LG

TL;DR

Cellular automata are useful for generating content, but effective local rules can be hard to design and interpret. This paper represents cellular automata as modular programs with optional global functions, and reports that global functions help evolution solve benchmark problems more efficiently, while some problems resist purely local solutions.

  • Problem

    Effective cellular-automaton rules can be difficult to create and interpret, despite their use in content generation.

    Source: §1 · p. 2

  • Method

    The paper represents cellular automata as programs modularized into local functions and a decision function, with optional global functions.

    Source: §1 · p. 2

  • Results

    Across the three domains, at least one global function helped evolution find generators that solved problems efficiently, and some games reached playable fitness levels in reasonable time.

    Source: §6 · p. 7, §7 · p. 10

  • Takeaways & Limitations

    Generated functions reveal recurring patterns that can help explain both the generators and what matters in the games.

    Source: §7 · p. 10

    Functions operate on one tile type at a time, preventing cross-type distance calculations such as BFS between different tile types.

    Source: §7 · p. 12

Abstract

from arXiv · show

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.

1. Introduction

Cellular automata can produce complex behavior and support applications including game-level generation, but their rules can be difficult to design and interpret. The paper proposes representing and modularizing cellular automata as programs, with optional global functions.

1. Introduction

  • Cellular automata iteratively apply simple local rules that can yield complex behavior, and have been used to model biological and chemical growth, simulate traffic and networks, and generate game levels.Examples include SimCity and organic-looking cave systems.Source: §1 · pp. 1–2
  • Program code offers a representation intended to retain or increase neural cellular automata’s expressivity while making rules easier for people who can read the language to inspect and author.A local program takes the cells’ surroundings and returns the target cell’s next state.Source: §1 · p. 2
  • When a use case has an evaluation function, evolutionary search can construct cellular automata, and programmatic representations also permit code-writing LLMs to complement or replace mutation and recombination.The paper identifies rapid construction of a level generator for a new game as one motivation.Source: §1 · p. 2
  • Global functions and modularity target tasks that require counting, which is hard and inefficient to implement using only local computation.The functions can be understood, improved, and swapped separately.Source: §1 · p. 2
  • Programmable cellular automata represent local rules as programs and divide the system into local functions, optional global functions, and a decision function.The decision function uses the functions’ outputs to choose values for the next state.Source: §1 · p. 2

2. Related work

Related work spans cellular automata and procedural content generation, rule evolution, and LLM-generated code. The paper positions its approach among work that evolves generators and work that uses LLMs to produce code for problem-solving.

2. Related work

  • Prior PCG research applied cellular automata to varied game content, including buildings, dungeons, spatial layouts, terrain, and city layouts.Constructive generators are suited to online generation in games.Source: §2 · p. 2
  • Rule-evolution work combines constructive cellular automata with search, with some approaches evolving a single level indirectly and others evolving generator rules.Other work evolved neural cellular automata for game levels, game mechanics, or 3D voxel assets.Source: §2 · pp. 2–3
  • LLM-based PCG includes generating content and evolving code that solves problems, including scoring functions, robot designs, matrix multiplication, and reinforcement-learning reward functions.The surveyed work uses search or evolutionary methods alongside LLMs.Source: §2 · p. 3
  • The paper is inspired by work using LLMs and evolution to write constructive level generators, and treats cellular automata as modular code-producing components.Figure 1 depicts the PCA loop with local functions, optional global functions, and a decision function.Source: §2 · p. 3, Figure 1 · p. 3

3. Programmable Cellular Automata

Programmable cellular automata represent cellular-automaton functions as programs and combine local functions with a decision function, optionally adding global functions. The formulation retains iterative state updates while allowing global computations and asynchronous updates.

3. Programmable Cellular Automata

  • PCA represents local functions and the decision function as programs, generalizing cellular automata beyond transition tables and neural cellular automata’s kernels and fully connected layer.The programs may take forms such as program trees, Python code, or neural networks.Source: §3 · p. 4
  • At each iteration, local observations go to local functions, whose outputs feed the decision function to choose each cell’s next value; the completed next state then replaces the current state.The system processes all cells before starting the next iteration.Source: §3 · p. 4
  • Optional global functions use the whole state to compute values that the decision function can combine with local-function outputs.This extends computation beyond fully local updates and is intended to support more complex operations in fewer iterations.Source: §3 · p. 4
  • Local functions read a neighborhood and global functions read the current state, while the decision function uses their outputs rather than reading or changing the state directly.These constraints keep state changes within the decision function.Source: §3 · p. 4
  • The formulation retains synchronous updates, but global functions may benefit from asynchronous updates that incorporate a decision’s cell change into the next global computation.For example, an updated count can inform processing of the next location.Source: §3 · p. 4

4. Automated Discovery of Programmable Cellular Automata

The section describes an evolutionary workflow for discovering modular PCAs, with fitness combining output quality and diversity.

4. Automated Discovery of Programmable Cellular Automata

  • Genetic programming or evolutionary algorithms automate the process of writing programmable cellular automata.The section introduces the components needed for evolutionary algorithms to explore PCAs.Source: §4 · p. 4

4.1. Representation and Initialization

  • Each chromosome contains at least one local function, optional global functions, and a decision function, represented here as Python code.Python is chosen for readability and to let large language models provide stronger initial functions than random trees or neural networks.Source: §4.1 · pp. 4–5

4.2. Variational Operators

  • Uniform crossover swaps component programs between parents, while an LLM mutates functions through random or context-guided sampling.Context sampling also gives the LLM the other functions and their fitness score.Source: §4.2 · p. 5

4.3. Fitness

  • Fitness combines each run’s highest quality over its iterations with output diversity, which contributes only when all n runs are fully functional.If functionality is the priority, the diversity term can be removed.Source: §4.3 · p. 5

5. Experiments

The experiments evaluate PCA level generators on three PCG Benchmark games, varying local and global function counts across repeated evolutionary trials.

5. Experiments

  • The evaluation uses Binary, Zelda, and Sokoban level-generation tasks, with each task’s quality and distance metrics taken from the PCG Benchmark.The tasks impose game-specific level requirements, including maze connectivity, Zelda objectives, and Sokoban crate-target puzzles.Source: §5 · p. 6
  • Each PCA ran for up to 100 iterations on 30 fixed random starting inputs; evolution used a population of 40 for 50 generations and tournament selection of size 7.Uniform mutation replaced each function with a 10% chance, and crossover selected between parents with equal probability.Source: §5 · p. 6
  • The study tested 36 configurations of local-function counts {1, 5, 10, 50} and global-function counts {0, 1, 5}, with five runs each; Figure 3 plots fitness progression with 95% confidence intervals.This totals 180 runs across the three problems.Source: §5 · p. 6, Figure 3 · p. 7

6. Results

Global functions generally reduce the iterations needed to find playable levels, with Binary as an exception; analyses also expose diversity-metric limitations and recurring function patterns.

6. Results

  • Adding at least one global function helps evolution find playable generators efficiently and generally reduces iterations, except Binary's optimum uses one local function.The authors suggest that additional functions may split functionality or introduce inefficient functions.Source: §6 · pp. 7–8, Table 3 · p. 8
  • Global functions can avoid repeated board-wide propagation of information that local computation may need at least board-size iterations to communicate.For example, counting player tiles locally requires propagating their locations; global computation can reduce the iterations needed for such values.Source: §6 · pp. 8–9
  • Although diversity fitness can be high, fewer than 30% of generated levels are unique, which the authors link to using distance criteria rather than the percentage of different levels.Table 2 reports diversity percentages for the best generators over 100 sampled levels per experiment, with 95% confidence intervals.Source: Table 2 · p. 8, §6 · p. 9
  • Zelda outputs clear the layout and randomize player, key, and door positions; its diversity measure rewards shortest-path changes between those items.The authors attribute the limited visual diversity to the metric used for Zelda, rather than to the evolved automaton.Source: §6 · p. 9
  • Discovered global functions commonly count objects, check connectivity, or measure tile distribution; one count function suffices to solve the object-count issue across domains.The authors note that object-count constraints are hard to compute with local functions alone and that isolated areas can make a level unplayable.Source: §6 · pp. 9–10
  • Among local functions, count is most common, alongside pattern-based functions associated with connectivity and spreading objects across the map.The count function lets the decision function use the number of neighboring tiles; other functions can encode information for later decisions.Source: §6 · p. 10

7. Discussion & Conclusion

The authors report that adding at least one asynchronous global function decreases the iterations needed and, in some games, helps fitness reach playable levels in reasonable time. They also identify implementation limits and propose extensions involving state memory, function outputs, level diversity, and code-size constraints.

7. Discussion & Conclusion

  • At least one asynchronous global function decreases iterations, and in some games helps fitness reach playable levels in reasonable time.The paper says the advantages of adding even one asynchronous global function outweigh the disadvantages.Source: §7 · p. 10
  • Figure 6 shows 30 Sokoban levels from the highest-fitness generator, which uses 10 local and 5 global functions.The caption states the number of iterations per generation.Source: Figure 6 · p. 11
  • A visible and hidden state could let hidden state act as memory between steps, but this extension was not tested.The authors suggest it might help local functions by providing more channels to propagate information.Source: §7 · p. 11
  • Returning richer information from local or global functions could enable more complex functions, though global outputs could also simply provide final values for the decision function to copy.A Dijkstra map is given as an example of a possible global-function output.Source: §7 · p. 11
  • Visually similar levels motivate exploring quality-diversity methods rather than only changing the fitness function.The authors cite Zelda generators that pass quality criteria by producing empty levels and shuffling object positions.Source: §7 · pp. 11–12
  • Local and global functions are restricted to one tile type at a time, preventing cross-type distance measures such as BFS between different tile types.Same-type distance measures remain possible; the restriction was intended to keep functions simple but limits what they can produce.Source: §7 · p. 12
  • The study allowed code outputs up to 4096 tokens and proposes testing a 128-token limit to see whether evolution finds more efficient solutions.The authors report that generated functions were not large, while leaving the effect of an early size limit for future work.Source: §7 · p. 12

Declaration on Generative AI

The authors disclose using Grammarly for grammar and spelling checks. They also report using Claude Opus and Gemini for specific document-preparation tasks.

Declaration on Generative AI

Related papers

Loading 2609.06102v2…