Searching for Spaceships
David Eppstein · 2002
. 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 2 c /7 spaceship in Life, found by searching a space with 2 states. 1. Introduction John Conway's Game of Life has fascinated and inspired many enthusiasts, due to the emergence of complex behavior from a very simple system. One of the many interesting phenomena in Life is the existence of gliders and spaceships: small patterns that move across space. When describing gliders, spaceships, and other early discoveries in Life, Martin Gardner wrote (in 1970) that spaceships “are extremely hard to find” [10]. Very small spaceships can be found by human experimentation, but finding larger ones requires more sophisticated methods. Can computer software aid in this search? The answer is yes - we describe here a program, gfind, that can quickly find large low-period spaceships in Life and many related cellular automata. Among the interesting new patterns found by gf ind are the “weekender” 2 c /7 spaceship in Conway's Life (Figure 1, right), the “dragon” c /6 Life spaceship found by Paul Tooke (Figure 1, left), and a c /7 spaceship in the Diamoeba rule (Figure 2, top). The middle section of the Diamoeba spaceship simulates a simple one-dimensional parity automaton and can be extended to arbitrary lengths. David Bell discovered that two back-to-back copies of these spaceships form a pattern that fills space with live cells (Figure 2, bottom). The existence of infinite-growth patterns in Diamoeba had previously been posed as an open problem (with a $50 bounty) by Dean Hickerson in August 1993, and was later included in a list of related open problems by Gravner and Griffeath [11]. Our program has also found new spaceships in well known rules such as HighLife and Day&Night as well as in thousands of unnamed rules.