Provided by: xlife_5.0-8_i386
lifesearch - search for oscillators and ancestors of life patterns
lifesearch -r rows -c columns -g generations [options...]
This program attempts to find life objects which are periodic, which
are spaceships, or which are parents of a given object.
You specify a region to search in, the number of generations of
interest, and some initial cells. The program then searches for all
objects which satisfy the conditions. The search applies transition
and implication rules which restrict the number of possible objects
considered to a small fraction of the total number. This makes it
practical to find these objects in a reasonable amount of time.
(Reasonable ranges from a few minutes to many days, depending on the
size of the search.)
The algorithm used here is based on the one described by Dean Hickerson
in a document included with the xlife distribution. Reading that
document will explain how the search in this program works, except for
The program usually looks for an object which is periodic in the number
of generations specified by the -g option. For example, use -g3 to
look for period 3 oscillators or spaceships. The program is pretty
fast for period 2, satisfactory for period 3, long for period 4, and
very long for period 5.
By default, the program only finds objects which have the full period
specified by the -g option. Objects having subperiods of the full
period are skipped. For example, when using -g4, all stable objects or
period 2 oscillators will not be found. The -a command line option
disables this skipping, thus finding all objects, even those with
subperiods. You probably want to use -a if you use any of the -tr,
-tc, or -p options.
The object is limited to the number of rows and columns specified by
the -r and -c options. Cells outside of this boundary are assumed OFF.
Thus if any generation of the object would expand out of the box, then
the object will not be found. The program finds things quicker for a
smaller number of rows and columns. Searching proceeds from left to
right column by column, and within a column from middle to edge. It is
quicker to search when there are less rows than columns.
The three command line options -r, -c, and -g are always required
(unless you are continuing a search using -l or -ln). If you do not
specify these options, or give them illegal arguments, a brief message
will be output and the program will exit. All other options are truly
If you want to find a symmetric object, then use the -sr or -sc
options. The -sr option enforces symmetry around the middle row if the
number of rows is odd, or the middle two rows if the number of rows is
even. The -sc option does the same thing for columns. You can specify
both options to look for fourfold symmetry. These options will speed
up the search since fewer cells need examining, but of course will miss
all unsymmetric objects.
Another way to speed up the search is to use the -m option to limit the
number of ON cells in generation 0. This will of course miss any
objects which have too many cells.
By default, the program looks for purely periodic objects. To find a
spaceship, you must use the -tr or -tc options to specify a
translation. This makes generation N-1 shift right or down by the
specified number of cells in order to become generation 0. Thus this
finds spaceships which move leftwards or upwards. Use -tc to translate
columns (thus making horizontal ships), and -tr to translate rows (thus
making vertical ships), or a combination (thus making diagonal
spaceships). The slowest ship for any period uses a translation of 1,
as for example -tc1. Remember that the fastest horizontal speed is C/2
and the fastest diagonal speed is C/4, so that for example, using -tc2
for a period 3 spaceship will find nothing.
By default, the program looks for objects such that generation N-1
implies generation 0, so that periodic objects can be found. The -p
command line option disables this circular dependency, so that
generation 0 has no past and generation N-1 has no future. This
enables you to search for the parents of any object you desire.
Commonly you specify -g2 with this option, to look only one generation
back. To look for parents of an object, you specify the cells of the
object in generation N-1, and leave the earlier generations unknown.
The ‘c’ command is useful with this option to completely specify the
last generation (see below).
The search program is always in one of two modes. It is either in
command mode, or in search mode. When first started, it is in command
mode. Command mode is indicated by the presence of a "> " prompt.
When in command mode, you can enter commands to the program, one per
line. To leave command mode and begin searching, you simply enter a
blank line. You can get back to command mode again by generating the
SIGINT signal. When this is done, the program will stop searching at a
convenient place, display the latest status of the search, and read
commands again. Do not forget to later type the blank line to continue
When first started, you may wish to specify the state of some cells to
guide the search. You can specify that any cell in any generation
should be either ON or OFF. Cells that you do not specify remain
unknown. As an example, if you were looking for a period 3 oscillator,
you might want to specify the middle cell as being ON in generation 0,
and OFF in generation 1. This would force period 3 behavior. Note
that when you specify cells, the state specified is permanent. The
program will not reverse your settings, and therefore can not find any
objects which do not match your settings. Also note that settings
unfortunately cannot be corrected, so if you set the wrong cell by
mistake, you must leave the program and start again.
To specify a cell, you use the ‘s’ command when in command mode. This
command takes 2 or 3 arguments. The first two arguments are the row
and column numbers of the cell to set. The third number is either 1
for setting the cell ON, or 0 for setting the cell OFF. If the third
number is omitted, then ON is assumed. The cell is always set in the
current generation, which is the one last displayed. If necessary, you
use the ’n’ or ’p’ commands to change the current generation to the
desired one before using the ’s’ command. For example, if the
currently displayed generation is generation 0, entering "s 5 6" would
set the cell at row 5 column 6 of generation 0 to ON, whereas "s 2 7 0"
would set the cell at row 2 column 7 to OFF. As a shortcut, you can
omit the ’s’ letter, so that the command "5 6" would set the cell at
row 5 column 6 ON. If you are using the -sr or -sc options for
symmetry, you don’t have to enter the symmetric cells since the program
does that for you.
You can use the -i or -ia options to input the initial settings for
either generation 0 or the last generation instead of typing in their
coordinates manually as above. The setting is normally for generation
0, but if the -p option was also used, then the setting is for the last
generation. The specified file contains a picture of the cells, with
’O’ or ’*’ indicating ON, ’.’ indicating OFF, and ’?’ indicating
unknown. If you use -i, then only the ON cells are set, making the OFF
cells stay unknown. If you use -ia, then both ON and OFF cells are
set. You can still specify additional cells after the ones in the file
have been read.
The ‘c’ command will set all the currently unknown cells in the current
generation to the OFF state. This is intended to be used when
searching for parents of an object that you have entered, and you know
exactly what the object in the last generation looks like. This
command requires confirmation before it is acted on.
Just before entering command mode, or occasionally if automatic viewing
is enabled, the program will display the current status of the search.
Cells marked as ’O’ are ON, cells marked as ’.’ are OFF, and cells
marked as ’?’ are currently unknown. The generation number and the
number of ON cells are also given, along with some of the command line
options that were used to start the program.
If you don’t like to keep hitting interrupt in order to see the
progress of a search, you can tell the program to automatically display
the object every so often. This is done either with the -v command
line option, or the ‘v’ command. The numeric argument is how many
thousand search iterations to perform between displays. As an example,
the command line option -v1 displays about every 5 seconds for a 20MH
Normally if the program finds something, it will display the object and
wait for commands. At this point you can write out the object if
desired. Typing ‘N’ will continue looking for further objects which
work. If you specified the -a command line option, then the ‘N’
command will be needed immediately after starting a search with no
initial settings, since the state of all OFF cells obviously satisfies
However, if you specify the -o option on the command line, the program
will NOT stop when it finds an object. Instead, it will append the
found object to the specified file name, and automatically keep looking
for further objects which work. The objects stored in the output file
are separated with blank lines. When no more objects have been found,
the program will print a final status message and exit.
The following is a summary of all the commands available. The ‘s’
command sets cells and has already been described above. The ‘n’
command displays the next generation of the current object, and will
wrap around from the last generation back to generation 0. The ‘p’
command displays the previous generation, also wrapping around. The
‘w’ command writes out a picture of the current generation out to the
specified file. The ‘d’ command dumps the state of the search out to
the specified file (see below). The ‘N’ command will continue
searching for the next object after an object has been found. The ‘v’
option specifies the frequency of automatic viewing. The ‘c’ command
turns all unknown cells in the current generation OFF. Finally, the
‘q’ command quits the program (confirmation is required).
Since it can take a very long time to find something (days or even
weeks!), the current state of a search can be dumped to a file and read
again later. You can explicitly dump the status to a file by using the
‘d’ command. After this has been done, you can use ‘q’ to quit the
program. Then later, you can use the -l command line option to
More useful and safer, however, is the autodump feature of the program.
Using the -d command line option causes a dump status file to be
automatically written after every so many search iterations. Thus
every so often the specified file will contain the latest status of the
search. Then if your machine crashes, you will not have lost days of
work. The -d option takes a numeric operand, which is how many
thousand searches to perform between dumps. The option also takes a
filename as an argument, and if it isn’t given, defaults to
"lifesrc.dmp". As an example, the option "-d100 foo" results in
automatically dumping status about every 10 minutes to the file "foo".
To load the dumped state that has been saved to a file, use the -l or
-ln command line options. Since the status file contains all
information about the search configuration, you do not need to specify
the number of rows, columns, generations, translations, symmetries, or
initial settings again. However, if you wish autodumps, an output
file, or automatic viewing, then you have to specify those options
After the state has been loaded, generation 0 is displayed and either
the program enters command mode if -l was used, or else the search
immediately continues where it left off if -ln was used. The -ln
option is provided so that continuing the search program within shell
scripts is easy.
There are two versions of the program, called lifesrc and lifesrcdumb.
They perform the same functions, but the user interfaces are slightly
different. Lifesrc uses the curses display routines to display the
objects prettily, whereas lifesrcdumb assumes nothing fancy and just
prints objects simply.
As you can see, finding something requires skill, luck, and patience.
Since you are limiting the search by specifying a rectangle, symmetry,
maximum cells, and initial cells, you probably have to keep varying
these parameters in order to come across something.
Example searches are the following:
lifesrc -r5 -c5 -g2 -a stable and period 2 oscillators
lifesrc -r10 -c10 -g3 -sr -sc -v1 period 3 oscillator
lifesrc -r4 -c4 -g4 -tr1 -tc1 glider
lifesrc -r5 -c7 -g4 -tc2 usual small spaceship
lifesrc -r5 -c16 -g3 -tr1 -v1 period 3 spaceship
lifesrc -r5 -c5 -g2 -p -a parents of glider (needs input)
David I. Bell. Based on an algorithm description by Dean Hickerson.