Life Search Programs
It is possible to find small but interesting patterns
in Life just by trying random seed patterns, or by manually
setting up glider crashes, etc. But many lifenthusiasts have
written search programs to aid in finding larger patterns. It
may be more productive to write your own programs than to run
the ones listed here, since that way you're more likely to find
something nobody else could have found. But, sometimes there's
already an available tool for what you want, and anyway it's
hard to be original without knowing what's already been
done.
This page is intended as a catalog of these search
programs: who wrote them, how do they work, what can they find,
and how can one obtain them? I'm including even unobtainable
programs here, for historical purposes and since it may be
useful to have a description of their design
principles.
- Bays
- Author: Carter Bays
Requirements: Unknown
Availability: Unknown
Description: Forms seed patterns by setting cells on
or off randomly within a small rectangular block in a larger
field. If evolution of a seed reaches the field boundary, the
resulting pattern is recentered and evolved again. Patterns
that reach the boundary a second time are saved as possible
gliders. Used by Bays to find gliders in several
three-dimensional and triangular-lattice cellular
automata.
- catalyst
- Author: Gabriel
Nivasch
Requirements: Platform-independent C++
Availability: Freeware,
on web
Description: Places still-life catalysts to react
with a given pattern. The program uses an exhaustive
depth-first traversal of all possibilities. It only places a
catalyst at the moment that it will react with the pattern,
using a data structure to make sure that the placement will
not interfere with previous steps of the
reaction.
- dr
- Author: Dean
Hickerson
Requirements: Platform-independent C
Availability: Contact author
Description: Searches for patterns consisting of a
small perturbation "drifting" across a still-life background.
Takes as input the perturbation and part of the background.
Depth-first; simulates the evolution of the perturbation,
making a choice whenever it needs the value of an unknown
background cell, and backtracking whenever it finds an
inconsistency in the background or the perturbation grows too
large. Useful for finding high-period billiard-table
oscillators, circuitry consisting of signals moving through
static wires and components, and custom eaters.
- gencols
- Author: Paul Callahan
Requirements: Platform-independent C
Availability: Freeware,
on web
Description: Enumerates collisions between patterns
(e.g. gliders and still lifes). Includes output filters to
detect oscillators, spaceships, or successful eating of one
pattern by another. Life evolution rule is hardcoded as a
sequence of bit-parallel integer operations (so it's possible
to change but not easy).
- gfind
- Author: David
Eppstein
Requirements: Platform-independent C
Availability: Freeware, on
web
Description: Breadth first search for low-period
spaceships. Extends partial patterns a row at a time, keeping
track of rows in all phases of the pattern. Finds successor
rows using a bit-parallel graph path computation; hash table
eliminates redundant search branches; uses depth first
iterated deepening, garbage collection, and row width
reduction (triggered by excess depth in iterated deepening
stages) to limit the breadth first queue size. Includes modes
for finding symmetric patterns. For more details see my paper
"Searching for
Spaceships" .
- Glue
- Author: Paul Chapman
Requirements: MS-Windows
Availability: In development
Description: Searches for slow-salvo constructions in
Life (patterns that can be formed by starting from a blinker
or block and colliding a single glider at a time into a
previously constructed pattern, as described in Nicholas
Gotts' paper "Self-Organized Construction in Sparse Random
Arrays of Conway's Game of Life"). Takes a given starting
pattern and generates and catalogs every possible collision
between it and a glider.
- gsearch
- Author: David
Eppstein
Requirements: Platform-independent C. Memory
intensive
Availability: Freeware, on
web
Description: Performs a brute force search of all
patterns fitting within a small rectangle (4x7 taking a day
or two). Evolves each such pattern for a specified number of
generations or until it repeats, grows too large, or matches
a previously seen pattern. Recognizes spaceships,
oscillators, unstable oscillators (such as Life queen bee and
p90), replicators, and some puffers. Includes modes for
finding symmetric patterns.
- Hersrch
- Author: Karel Suhajda
Requirements: Windows
Availability: C++ source and executable
Description:
Searches for open or closed Herschel tracks in Conway's Game of Life,
using a database of known static and periodic track components.
Backtracking search, pruning the search tree when the pattern exceeds
given size bounds or when a self-overlapping sequence of
components is detected (using an Aho-Corasick string matching automaton
on a predefined list of impossible sequences).
- Holzwart
- Author: Hartmut Holzwart
Requirements: Unknown
Availability: Unknown
Description: Another search program similar to LS and
lifesrc. Limited by machine precision to patterns with width
at most 31. Used by Holzwart to find many variant c/2 and c/3
spaceships in Life, and related patterns including the
"spacefiller" in which four c/2 spaceships stretch the
corners of a growing diamond shaped still life.
- knight
- Author: Tim
Coe
Requirements: Platform-independent C. Memory
intensive
Availability: Contact author
Description: Breadth first search for low-period
spaceships. Extends partial patterns a row at a time in one
phase only; checks that evolving the pattern through a period
results in the same rows. Uses a fixed amount of depth-first
lookahead per node to limit the breadth first queue size.
Includes modes for finding symmetric patterns. Life evolution
rule is hardcoded as a sequence of bit-parallel integer
operations, multiple times throughout 25 pages of uncommented
C (so not really possible to change without rewriting the
whole program).
- LifeLab
- Author: Andrew
Trevorrow
Requirements: Macintosh
Availability: Shareware, on
web
Description: This is a general purpose CA
viewing/editing system, but it also includes a brute force
search of all patterns fitting within a small rectangle.
Evolves each such pattern for a specified number of
generations or until it repeats. Recognizes spaceships,
oscillators, still lifes, and methusalahs. Not very
fast.
- lifesrc
- Author: David
Bell
Requirements: Platform-independent C
Availability:
C source , Windows
executable
Description: Depth-first backtracking search for
low-period spaceships, oscillators, still lifes, puffers, or
predecessors of a given pattern. Maintains the state of each
phase of each cell in a specified region as unknown, live,
dead, or don't care; recursively tries setting each unknown
cell to live or dead and propagating the consequences to
neighboring cells in neighboring generations. Includes modes
for finding symmetric patterns.
- LS
- Author: Dean
Hickerson
Requirements: Apple IIe
Availability: Still exists on a 5 1/4" floppy
somewhere
Description: Depth-first backtracking search for
low-period oscillators, spaceships, and predecessors of a
given pattern, similar to lifesrc. The name is short for
"Life search". Written in 1989 using a combination of 6502
assembler and Basic; mentioned by Mark
Niemiec as the first program to search for oscillators.
Described in more detail in the file "ORIGIN" included in
some lifesrc distributions.
- new4
- Author: Keith Amling
Requirements: Windows-specific C++
Availability: Contact author
Description: Depth first search for low-period
spaceships. Extends partial patterns a column at a time,
keeping track of columns in a single phase of the pattern. At
each level of search, tries all possible choices for the next
column, and for each choice performs the evolution rule p
times on the last 2p+1 columns (where p is the desired
period). If the result of the evolution matches a shifted
copy of the original middle column, the search continues
recursively. Stops and outputs a successful spaceship when
the result of the evolution matches not just the middle
column but also all later columns. Life evolution rule is
hardcoded but only in a small number of easy to change
lines.
- Niemiec
- Author: Mark
Niemiec
Requirements: Unknown
Availability: Unknown
Description: This is described by Achim
Flammenkamp as an improved version of Raynham's still
life enumerator, written in 1989, capable of finding all
still lifes with up to 20 live bits. Design principles
unknown. Niemiec apparently also wrote a brute force search
program, which finds all oscillators or spaceships that fit
in a given area (5x5 taking a few days as of 1994) based on a
principle attributed by him to Raynham of simultaneously
running two copies, one twice as fast as the other, and
detecting when both reach the same state. (The same principle
has been discovered by many other workers in other areas e.g.
the Pollard rho factoring algorithm.).
- ofind
- Author: David
Eppstein
Requirements: Platform-independent C
Availability: Freeware, on
web
Description: Breadth first search for low-period
oscillators. Similar to gfind, but extends patterns in all
phases simultaneously rather than a single phase at a time,
and includes special handling of stator cells. User can
specify what spark the oscillator should produce, or how it
should interact with neighboring patterns of other
periods.
- polyomino
- Author: Paul Callahan
Requirements: Unknown
Availability: Contact author
Description: Enumerates all small polyominos
(presumably by a backtracking tree search that tries all ways
of adding a cell to each n-polyomino, in such a way that the
same (n+1)-polyomino couldn't have been formed in a
previously listed way). Simulates the evolution of each
polyomino, determining whether it generates a previously
known interesting pattern (such as a switch engine, Herschel,
or pi) by forming 32-bit words representing the recent
history of each cell and comparing against known signature
words. Useful for finding small infinite-growth
patterns.
- ptbsearch
- Author: Paul Callahan
Requirements: Platform-independent C
Availability: Freeware, on
web
Description: Attempts to perturb a starting reaction
by adding combinations of eaters or other still lifes, to
make a different reaction product without destroying the
added patterns. Life evolution rule is hardcoded in source
but easy to change. Useful for finding Herschel tracks and
glider guns.
- Random Agar
- Author: Gabriel
Nivasch
Requirements: Platform-independent C++
Availability: Freeware,
on web
Description: This program is intended to look for new
Life oscillators, wicks, and agars. It generates random
spatially periodic patterns, and runs them until they
oscillate. It includes complete support for all possible
symmetry types and clever oscillation detection
algorithms.
- Raynham
- Author: Peter Raynham
Requirements: Unknown
Availability: Unknown
Description: This is described by Mark
Niemiec and Achim
Flammenkamp as the first program to search for still
lifes, written in the mid-1970's. Design principles
unknown.
- sngdetect
- Author: Gabriel
Nivasch
Requirements: Platform-independent C++
Availability: Freeware,
on web
Description: Tests interactions of gliders with
patterns formed from common still lifes and oscillators. For
each interaction, test whether the same pattern reappears,
shifted some distance from its original position.
- stilledit
- Author: Paul Callahan
Requirements: Java-enabled web browser
Availability: Web
applet
Description: After the user edits a pattern, in which
some cells' states are marked as "fixed", this program
attempts to find a still life matching those requirements by
a hill-climbing approach, in which it toggles the state of
unfixed cells to minimize the number of violations of the CA
evolution rule, with some randomized variation to avoid
getting stuck in local minima. Only works for Life, not other
totalistic rules, but Java source code is
available.
- Still Lifes Auto
- Author: Gabriel
Nivasch
Requirements: Mac executable
Availability: Freeware,
on web
Description: Mac port of StillEdit with a few added
features.
- Tooke
- Author: Paul Tooke
Requirements: Unknown
Availability: Unknown
Description: Searches for puffers by truncating tails
of spaceships (generated by a modified version of gfind) and
testing what happens to the resulting patterns.
- torus
- Author: Jason Summers
Requirements: Platform-independent C
Availability: Freeware,
on web
Description: Searches for high-period oscillators by
testing the evolution of random periodic initial conditions.
No user interface; user must change parameters in the source
code.
- tweak
- Author: David
Bell
Requirements: Unknown
Availability: Unknown
Description: Modifies known puffers or wicktrailers
by changing cell values within a small rectangle using a
brute force enumeration. Filtering principles
unknown.
- Wechsler
- Author: Allan Wechsler
Requirements: Unknown
Availability: Unknown
Description: Developed in 1994, this program
attempted to use genetic programming to "breed" spaceships
and oscillators of a fixed period, using as a fitness
function the similarity between the original pattern and (a
shifted copy of) the pattern after evolving the given number
of iterations. However, this program was only capable of
finding small objects with small periods. Dave Greene tells
me he later ran a similar experiment with even less
success.