Searching for Spaceships
<|reference_start|>Searching for Spaceships: 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.<|reference_end|>
@article{eppstein2000searching,
    title={Searching for Spaceships},
    author={David Eppstein},
    journal={More Games of No Chance, MSRI Publications 42, 2002, pp. 433-453},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0004003},
    primaryClass={cs.AI nlin.CG}
}