Qitian Liao

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2021-150

May 21, 2021

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-150.pdf

A cellular automaton consists of a grid of cells, and the grid can be in any finite number of dimensions. Each cell is in one of a finite number of states, and evolves with respect to time steps according to a set of evolution rules based on the previous states of its neighbors and itself. The evolution rules are applied iteratively for as many steps as desired to produce new generations. There are many possible configurations; this report specifically explores two-dimensional outer totalistic cellular automata using the Moore neighborhood with decay, meaning that sick cells are not able to recover and have to move one step closer to death at each generation.

The challenge when searching for interesting patterns in two-dimensional cellular automata is a huge parameter search space. The number of possible combinations of rule parameters can easily exceed 2^18. Our research focused on adjusting the rules to find new, interesting spaceships (oscillating translators that move across the grid). Existing research has not discovered a clear pattern among rules that generate spaceships.

Manually searching for the interesting rules would be unrealistic, but fortunately, the introduction of neural networks has revolutionized a variety of tedious classification tasks. This report explores the use of neural networks to detect interesting cellular automata rules, specifically Recurrent Neural Networks (RNN), Convolutional Neural Networks (CNN), feature extraction, entropy analysis, and other techniques. We then put the trained machine learners into practice and detected several new rules with only three states. We discovered an entire family of spaceships of different periods, as well as many other interesting results.

Advisors: Dan Garcia

---

BibTeX citation:

@mastersthesis{Liao:EECS-2021-150,
    Author= {Liao, Qitian},
    Title= {Automatic Detection of Interesting Cellular Automata},
    School= {EECS Department, University of California, Berkeley},
    Year= {2021},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-150.html},
    Number= {UCB/EECS-2021-150},
    Abstract= {A cellular automaton consists of a grid of cells, and the grid can be in any finite number of dimensions. Each cell is in one of a finite number of states, and evolves with respect to time steps according to a set of evolution rules based on the previous states of its neighbors and itself. The evolution rules are applied iteratively for as many steps as desired to produce new generations. There are many possible configurations; this report specifically explores two-dimensional outer totalistic cellular automata using the Moore neighborhood with decay, meaning that sick cells are not able to recover and have to move one step closer to death at each generation.

The challenge when searching for interesting patterns in two-dimensional cellular automata is a huge parameter search space. The number of possible combinations of rule parameters can easily exceed 2^18. Our research focused on adjusting the rules to find new, interesting spaceships (oscillating translators that move across the grid). Existing research has not discovered a clear pattern among rules that generate spaceships.

Manually searching for the interesting rules would be unrealistic, but fortunately, the introduction of neural networks has revolutionized a variety of tedious classification tasks. This report explores the use of neural networks to detect interesting cellular automata rules, specifically Recurrent Neural Networks (RNN), Convolutional Neural Networks (CNN), feature extraction, entropy analysis, and other techniques. We then put the trained machine learners into practice and detected several new rules with only three states. We discovered an entire family of spaceships of different periods, as well as many other interesting results.},
}

EndNote citation:

%0 Thesis
%A Liao, Qitian 
%T Automatic Detection of Interesting Cellular Automata
%I EECS Department, University of California, Berkeley
%D 2021
%8 May 21
%@ UCB/EECS-2021-150
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-150.html
%F Liao:EECS-2021-150