John Conway’s Game of Life has inspired enthusiasts, due to the emergence of behavior from a simple system. A phenomenon 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.» 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 gfind are the 'weekender' 2c/7
spaceship in Conway’s Life, the “dragon” c/6 Life spaceship found by Paul Tooke 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. 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. 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.


As well as providing a useful tool for discovering cellular automaton behavior,
our work may be of interest for its use of state space search techniques. Recently,
Buckingham and Callahan wrote «So far, computers have primarily been used to speed up the design process and fill gaps left by a manual search. Much potential remains for increasing the level of automation, suggesting that Life may merit more attention from the computer search community.»

Spaceship searching provides a search problem with characteristics intriguingly different
from standard test cases such as the 15-puzzle or computer chess, including a large state space that fluctuates in width instead of growing exponentially at each level, a tendency for many branches of the search to lead to dead ends, and the lack of any kind of admissable estimate for the distance to a goal state.

Therefore, the search community may benefit from more attention to Life. The software described here, a database of spaceships in Life-like automata, and several programs for related computations can be found online at http:// www.ics.uci.edu/̃eppstein/ca/.


The purpose here is to describe software that searches for spaceships in Conway’s
Game of Life and related two-dimensional cellular automata. The program
searches through a state space related to the de Bruijn graph of the automa-
ton, 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 2126 states.

sources: collidoscope.com, arxiv.org, ics.uci.edu