SOMA Life: Stasis Detection in Cellular Automata

Hidden Computer Science Games Engineering Bachelor Master Project Thesis Games Research Lab

Introduction

Computational systems that exhibit complex, ongoing, and diverse behavior are among the most interesting subjects in computational science. Agent-based simulation is a versatile methodology to create such systems in a bottom-up fashion by defining rules of interaction between a simulated computational entities, so called agents.
Project SOMA is interested in identifying repeating patterns of interactions between agents in a simulation and subsequently exploiting them to reduce the number of computations necessary to advance the simulation. SOMA Life focuses on the first steps towards realizing this concept by focusing on Cellular Automata.

Background

Cellular Automata (CA) have fascinated researchers due their expressiveness and have been continuously researched since their first formulations in the 1950s. CA are composed of cells, each of which follow a set of rules that determines state changes from one time step to the next.

A highly valuable example is “Life” (or Game of Life, GoL), attributed to John Horton Conway. Here, a simple set of 3 rules governs the life of cells.

1. Any live cell with two or three neighbors stays alive for the next generation.
2. Any dead cell with exactly three neighbors gets born in the next generation.
3. All other live cells die in the next generation. All other dead cells stay dead.

Out of this simple rule set, infinitely changing constellations can arise - the CA became ‘alive’. From random initial configurations, clearly identifiable and self-replicating patterns can emerge. Try an interactive online version of Conways Game of Life.

Outline

SOMA Life will implement a basic 3-step process to investigate the Identify-Replace-Validate concept.

1. In a first step, local patterns will be identified. This should include unchanging constellations and periodically repeating patterns up to some reasonable number of steps. Such patterns might be identified on-the-fly or using a database.
2. In a second step, starting from these patterns, a boundary region will be identified. This boundary is defined as such an area where, unless an external change is occurring, the initially identified pattern remains unchanged.
3. In a third step, the identified pattern will be used to replace the computation of cells within the identified boundary, either by simply maintaining the state or by advancing in a recorded list of states. Simultaneously, a check for violations of the boundaries needs to be implemented. The handling of such violations can range from invalidation of the whole region to the use of hierarchies of boundary conditions that can be invalidated incrementally, reducing the size of the known static regions step-by-step.

Naturally, the amount of computations that have been avoided should be quantified, together with the overhead introduced by the boundary checks and abstraction mechanisms.

Contact Persons at the University Würzburg