Emergent processes in complex systems such as cellular automata can perform
computations of increasing complexity, and could possibly lead to artificial
evolution. Such a feat would require scaling up current simulation sizes to
allow for enough computational capacity. Understanding complex computations
happening in cellular automata and other systems capable of emergence poses
many challenges, especially in large-scale systems. We propose methods for
coarse-graining cellular automata based on frequency analysis of cell states,
clustering and autoencoders. These innovative techniques facilitate the
discovery of large scale structure formation and complexity analysis in those
systems. They emphasize interesting behaviors in elementary cellular automata
while filtering out background patterns. Moreover, our methods reduce large 2D
automata to smaller sizes and enable indentifying systems that behave
interestingly at multiple scales.
Presentation at ALife 2020
Animations from the paper
Figure 3: Side-to-side comparison
of a CA simulation and its coarse-grained version. The first simulation is 256 × 256 cells
and the second has been coarse-grained to 64 × 64. Notice the
interesting patterns on Figure 3a are hardly distinguishable.
They are highlighted by histogram-based coarse-graining in
Figure 3b.
Base grid.Coarse-grained.
Figure 9: Changing CA dynamics at multiple scales.9a is a single glider, oscillating
between 3 positions. They emerge spontaneously from a
random initialization of a small grid as shown in 9b. When scaling the
grid up, trails of gliders begin to appear, creating
moving straight and diagonal lines (9c). Going a
level higher, single gliders aren’t visible anymore (9d).
The grid had to be coarse-grained to 256×256. In an even
larger grid (9e), many more triangular-shaped
waves travel and collide into each other.
Single glider.Several gliders (128 × 128 cells).More gliders (512 × 512 cells).Higher-order structures emerge (2048 × 2048 cells).Wave-like triangular patterns (4096 × 4096 cells).Bursts of activity occasionally emerge
within the grid at an even larger scale (10240 × 10240 cells).For comparison, a non-coarsed-grained
example for a large grid. Structures are barely
visible (4096 × 4096 cells).
More examples
A few gliders (128 × 128 cells).More gliders (512 × 512 cells).Larger triangular structures begin to appear(2048 × 2048 cells).Glider guns form very large
structures spanning hundreds of thousands of cells.
These very large structures were not visible before (10240 × 10240 cells).
A few gliders (128 × 128 cells).More gliders (512 × 512 cells).Larger triangular structures begin to appear(2048 × 2048 cells).Glider guns form very large
structures spanning hundreds of thousands of cells.
These very large structures were not visible before (10240 × 10240 cells).
Acknowledgements
This work was partially supported the EU Structural and
Investment Funds, Operational Programe Research, Development
and Education under the project IMPACT (reg.\ no. CZ.02.1.01/0.0/0.0/15 003/0000468),
and the French government under management of Agence
Nationale de la Recherche as part of the "Investissements
d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA
Institute).
Copyright Notice
The documents contained in these directories are included by
the contributing authors as a means to ensure timely
dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein are
maintained by the authors or by other copyright holders,
notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by
each author's copyright.