Searching for Spaceships

Abstract

We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.

17 pages, 13 figures. This revision adds Paul Tooke's new c/6 "dragon", and corrects one URL. For more information about the software and patterns described here, see http://www.ics.uci.edu/~eppstein/ca/

Cited by in corpus (9)

• A framework for the local information dynamics of distributed computation in complex systems
• Upper Bound on the Products of Particle Interactions in Cellular Automata
• Growth and Decay in Life-Like Cellular Automata
• Complex dynamics of elementary cellular automata emerging from chaotic rules
• Computation and Universality: Class IV versus Class III Cellular Automata
• Localization dynamics in a binary two-dimensional cellular automaton: the Diffusion Rule
• Complex dynamics emerging in Rule 30 with majority memory
• RealLife: the continuum limit of Larger Than Life cellular automata
• The B36/S125 "2x2" Life-Like Cellular Automaton