AssemblyCA: A Benchmark of Open-Endedness for Discrete Cellular Automata

Introduction

Consider a set of agents able to modify CA initial conditions and execute them to find objects. These agents execute a CA and insert black, white, or higher-level cells on this CA, or modify already-found patterns to find new patterns in the output. The obtained objects by these agents are quantified by their assembly space and the number of copies found by each agent.


AssemblyCA Framework. Given a system where a set of agents can interact with a CA world and they have access to a limited amount of inputs, computation, and a library of discovered patterns. The agents will generate as a byproduct a series of objects, or CA patterns by modifying the CA initial conditions. By analyzing the output of objects of this system the amount of open-endedness of the system is quantified.

Assembly Theory

AT(assembly theory)quantifies the amount of selection needed to build complex objects abundantly. Given a pool of building blocks and lower complexity objects a system that explores the object-space with an undirected process is not selective, when this occurs complex objects are produced in low number. On the other hand, a directed process is one that utilizes already build objects to generate complex objects in high numbers.


Selection in Assembly Theory adapted from Sharma, et al 2023 . A) Representation of pathways to construct objects with undirected and directed processes (selected) leading to the low and high copy numbers of the observed object. B) Distributions of copy number vs assembly index(complexity) for processes that undergo selection or not.



The assembly theory quantities are defined and approximated in a CA.


Assembly Theory measures and approximations in CA. a) Given a set of starting building blocks a process that explores patterns, in this case in the Game of Life CA. b) An object that oscillates every two generations is found as a result of the exploration. c) Different agents have found the object and have added it to each library. d) The complexity of this object is calculated by finding the minimum way of building its two states together and calculating the properties of this space. e) Approximation algorithm for an arbitrary 2ⁿx2ⁿ block, by doing a quad-decomposition and joining the common elements one can find an assembly pathway. f) By joining the reconstructed pathways of all the states of the object one obtains an approximation of the assembly space.

Testing

Entropy Comparison

The time evolution of a one-dimensional CA is compared looking using the tools from information theory and assembly theory.

Simple Initial Condition

Comparison between entropy and assembly 1. Behaviour of a simple initial condition in the Rule 110 Cellular Automata. Comparison of the Assembly Index vs Entropy of the time evolution and the Mutual Information and the Assembly Distance between two arbitrary cells and subsequent cells.

Engineered Intial Condition

Comparison between entropy and assembly 2. Behaviour of an engineered initial condition in the Rule 110 Cellular Automata. Comparison of the Assembly Index vs Entropy of the time evolution and the Mutual Information and the Assembly Distance between two arbitrary cells and subsequent cells.

Random Initial Condition

Comparison between entropy and assembly 3. Behaviour of a random initial condition in the Rule 110 Cellular Automata. Comparison of the Assembly Index vs Entropy of the time evolution and the Mutual Information and the Assembly Distance between two arbitrary cells and subsequent cells.

Simple Initial Condition(Chaotic Automata)

Comparison between entropy and assembly 4. The behavior of the Rule 30 Cellular Automata. Comparison of the Assembly Index vs Entropy of the time evolution and the Mutual Information and the Assembly Distance between two arbitrary cells and subsequent cells.

Sample Patterns

Memory or complexity over time-step is computed for several patterns with different dynamical behaviors. We see that the complexity measure can characterize objects with vastly different stability timescales.

Still Life

Oscillator

Spaceships

Infinitely Growing Pattern

Experiments

We perform three experiments to showcase our benchmark:

• 1. Undirected process
• 2. Open-ended process that is undergoing selection
• 3. Algorithmic process with programmed agents

Undirected Process

Soup searches are a type of exploration where initial conditions are set at random and objects are found when the CA has reached stabilization.

Distribution of undirected process. An undirected process of searching GoL patterns generates a large number of unique low-memory objects and a handful of unique high-memory objects. The GoL soup search discovered objects of low-memory in very high copy whereas the high-memory objects are found in very low copy.

Open Ended Process

Objects found by the community of Game of Life CA practitioners in the 50-year collection of the LifeWiki database.

Distribution of directed process. Distribution of complexity and copy number of objects found by the GoL enthusiast community. We can see that the community has been systematically finding high-complexity objects in large quantities. This implies that the agent's search procedure is undergoing selection, therefore it is an open-ended process.

Algorithmic Agent

A group of agents search for novel patterns given a starting library. They select a random object, modify it and search for new patterns. If a new pattern is found it is added to the library.
Distributions of objects found by a group of agents. a) A group of agents searches for novel patterns given a starting library. They select a random object, modify it by means of growth, and search for new patterns from the resulting pattern. If a new pattern is found it is added to the library. b) The group of agents finds more unique objects at a given complexity than a completely undirected process, but they stagnate at a relatively low complexity. This implies that the agent's search procedure is not undergoing selection, therefore it is not an open-ended process.

Conclusion

In this work, a benchmark for open-endedness that analyses the products of a system consisting of agents, resources, and discrete cellular automata was introduced. The benchmark is capable of capturing the intuitive idea of unlimited complexity and novelty of an open-ended system. By analyzing the complexity and the copy number of a set of CA objects generated by our agents, we can characterize the amount of open-endedness of such a system. The benchmark is compared with other measures of open-endedness, its complexity measure is compared with entropy, and it's found that the AssemblyCA complexity or memory is able to properly characterize the phenomenon of historical contingency, key for generating complex objects. Finally, three experiments were performed with the aim of showing systems with different degrees of open-endedness. In the future, we intend to study in more detail some elements of the undirected-directed transition in the CA framework. These include the amount of selectivity in the agent's search, a robust definition of an object in CA, and the analysis of different CA rules and the transition between them. In addition, we plan a deeper study of the cultural behavior of the LifeWiki system. This is highly relevant for the understanding and quantification of open-endedness. Lastly, we plan to study more elaborate agents that can discover CA objects, such as LLM-based CA object explorers. This is highly relevant for a rigorous benchmark of the capabilities of different LLM-agents.