LIFESRC 13 October 2001
This is version 3.8 of my lifesrc program. The program has been converted to be fully ANSI C compatible. The Makefile assumes gcc, and the program assumes the "ncurses" library instead of "curses". You may have to change these to get lifesrc to compile for you.
The following is a short explanation on how to run the Life search program.
This program attempts to find Life objects which are periodic, which are spaceships, or which are parents of an 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 his document that was included with the xlife program, and which is also included with this distribution. Reading that document will explain how the search in this program works, except for minor changes.
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 optional.
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. If you give a numeric argument to these options, then the symmetry will only apply from the specified row or column. For example, using -sr10 means force symmetry only from column 10 onwards.
Other forms of symmetry can be specified by -sp, -sf, or -sb. Using -sp forces symmetry around the central point of the search area. Using -sf forces symmetry around the forwards diagonal (/) of the search area. Using -sb forces symmetry arounds the backwards diagonal (\) of the search area. When using -sf or -sb, the number of rows and columns must be the same. These options don't accept any numeric argument.
Another way to speed up the search is to use the -mt option to limit the total number of ON cells in generation 0. This will of course miss any objects which have too many cells.
Another way to speed up the search is to use the -mc option to limit the number of ON cells in any column in generation 0. For example, using -mc5 means skip over all objects which have more than 5 cells in any column. Cells initially set before the search begins are not subject to this restriction.
Another way to speed up the search is to the use -wc option to limit the width of each column. The width of a column is the distance from the first ON cell in the column to the last ON cell in that column plus 1. For example, using -wc5 means that for each column, the topmost and the bottommost ON cell in each column must occupy the ends of 5 or less adjacent cells. The difference between this option and the -mc option is that using -mc restricts the number of cells in a column, but still allows them to appear anywhere within the column, whereas this option forces the cells to be near each other in the column. This option is therefore good for looking for objects which are thin, but which wander over many rows. If the -sr or -fr options are used, the meaning of -wc is modified for the affected columns so that the width limit is applied to the top and bottom halfs of the column independently. Therefore an object which splits into upper and lower halfs which are both thin can be searched for. Cells initially set before the search begins are not affected by the -wc restriction.
Another way to speed up the search is to use the -nc option to force cells to be near the cells in previous columns. This option takes the number of cells up, down, and leftwards from the current cell to check. Thus a cell can only be ON if there is another ON cell within the specified distance in a previous column. For example, using -nc1 forces cells to be connected to cells in the previous column, whereas -nc2 forces cells to be near enough to cells in the previous two columns to probably immediately affect each other. Cells in column 1 are not affected by this check, nor are cells initially set before the search begins.
Another way to speed up the search is to use the 'f' command to specify cells which are "frozen". Frozen cells can be either ON or OFF, but their value cannot change, so that the cell will have the same value in all generations. This is useful to look for "billiard table" areas surrounding volatile regions.
The final way to speed up the search is to use the -f option to change the order of setting ON cells in a column. Normally, cells are set from the middle row outwards. But when using this option, cells are set first from the row nearest the average position of the ON cells in the nearest previous column which has any ON cells. This option thus makes it easier to find wandering objects in a large area, without eliminating any possibilities. A failed search will be no faster using this option, but a successful search may be quicker.
By default, the program tries cells that are OFF first. The -fg option changes this so that a cell tries to be ON if the previous or next generation is ON, and to be OFF otherwise. This is useful when looking for mostly stable objects.
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. You can specify negative translations if convenient.
You can also change the mapping between generation N-1 and generation 0 by using the -fr, -fc, or -fq options. These flip the cells around the middle row, the middle column, or by a 90 degrees rotation around the center. By flipping rows or columns, you can search for objects which have actual periods of 2N instead of just N, and which flip over. By flipping quadrants, you can look for objects with actual periods of 4N instead of just N, and which rotate. The -fr and -tc options can be used together, and -fc and -tr can also be used together. This allows searching for spaceships with glide symmetry. For -fq, the number of rows and columns must be the same. Using -fr and -fc together provides flipping around the central point.
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).
By default, the program makes sure that every cell in the rectangular area is consistent. That is, all objects found are sure to correctly work in an infinite area according to the Life rules. But it is possible to remove this guarantee of consistency for a selected area of the search area. The reason this might be useful is that this allows searching for puffers. Puffers move like spaceships, but leave debris behind. Such objects cannot be found by default because the debris is not periodic, and thus the ship creating it will not be found. By allowing some cells at the back of an object to remain unchecked, then the search might find an object which is actually a puffer. There is no guarantee about this result, however, and commonly the unchecked area will destroy the ship completely. To maximize the chances of finding a puffer, you can set ON cells adjacent to the unchecked area to create something in that area, and otherwise surround the unchecked area with several layers of OFF cells to protect the rest of the ship from its influence. Finally, in a later generation, you can set the cells that were ON to be OFF, to guarantee that the object found will separate into two parts. You might also have to scatter some OFF cells on the edges of the the unchecked area to prevent long rows of ON cells there from affecting the search result.
Another use of unchecked cells is to enable searching from a fragment of an object. For example, when looking for a tagalong to a large ship, you don't have to have the complete ship involved in the search. Instead, you only initialize the search area with the small area where you want the tagalong to grow from. When doing this, make sure you specify enough cells of the ship to prevent wrong results. For example, with a period 3 ship it is probably a good idea to provide a 4 cell thick area of known cells around the location to attach the tagalong to.
Another use of unchecked cells occurs when an object splits into two pieces. You can temporarily ignore one half of the object by setting it to be unchecked, and concentrate the search on the other half, which can then be much more practical. Then after finding that half, you can go back and search for the first half. Once again, it is good to buffer the unknown area with layers of known ON or OFF cells to prevent unanticipated reactions between the areas.
Unchecked cells are not set on the command line, but are set either when reading in an initial object, or else manually.
By default the search program looks for objects using the standard Life rule of 3 live neighbors to be born, and 2 or 3 live neighbors to stay alive. You can change the Life rule to look for objects in other universes by using the -R command line option. It accepts two sets of digits separated by a slash or comma character. The first set of digits is the number of live neighbors for birth. The second set of digits is the number of live neighbors for staying alive. For example, -R3/23 specifies the default Life rule. You can also label these numbers using the 'B' and 'S' letters, as in -RB3/S23. An alternative method of specifying the rules is to use Wolfram format, which uses a hex number. In the number, every pair of bits from the rightmost bit specifies birth and life for a certain number of neighbors, with zero neighbors being the rightmost two bits. As an example, specifying -R8c8 is the same as specifying -R3/135.
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 lastest status of the search, and read commands again. Do not forget to later type the blank line to continue searching again!
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 any of the options for symmetry, you don't have to enter the symmetric cells since the program does that for you.
If you want to specify unchecked cells, then you can use the 'x' command. This command takes either one pair of numbers for a single cell, or else two pairs of numbers for selection the corners of a rectangular area to be unchecked. Setting cells as ON or OFF later will override this setting.
You can use the -i, -in, or -id 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, '?' indicating unknown, 'X' indicating unchecked, '+' indicating that the cell has the same state in all generations, and ':' indicating that the cell is OFF in all generations. If you use -i, then both ON and OFF cells are set, whereas using -in will only set the ON cells. If you use -id, then all OFF cells are set OFF in every generation. You can still specify additional cells after the ones in the file have been read.
The 'c' command is used to set all currently unknown cells in a rectangular area of the current generation to the OFF state. If no arguments are specified, then (after confirmation) all unknown cells are set to the OFF state. This is useful when searching for parents of an object that you have entered, and you know exactly what the object in the last generation looks like. Alternatively, the 'c' command can accept four numeric arguments, which are the beginning row and column numbers, and ending row and column numbers of a rectangular area to be cleared. All unknown cells in that specified area are set to the OFF state. No confirmation is required in this case.
The 'cg' command works just like the 'c' command, except that it clears the specified cells in all generations, not just the current generation.
The 'f' command is used for setting frozen cells. It accepts either one row and column number to set just one cell, or a pair of row and column numbers to set a rectangular region.
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. Cells where have been excluded from the search are marked as 'X', and cells which are frozen are marked as '+'. (Excluded or frozen cell are not shown if the cell is ON or OFF.) 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 the -o option is used to save results, then following the file name in the status line will optionally be a number in square brackets, as in "-o file ". If this appears, than this is the number of successful results which have been saved in the file. If this does not appear, then the search has not yet succeeded. This count does not include partial results saved in the file.
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 386. The verbosity is defaulted to -v10.
Normally if the prog 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 all conditions.
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.
You can also specify a numeric argument to the -o option, which also dumps partial results to the file. What this means is that every time the search successfully progresses to any multiple of the indicated number of columns, then the current object is written to the file. If the search then fails, and the number of successful columns falls again (very common), then when a new pattern is found which again becomes successful enough, then that pattern will then be saved too. Doing this records near misses during the search, which you can later examine and use as input for further searches with less constraints. As an example, using "-o8 file" saves partial results every 8 successful columns. When you examine the file, you can distinguish the successes from failures because the failures will have question marks in the object.
When stopped, the 'b' command can be used to back up the search. Backing up means that the most recent choice of a cell is reversed. Doing this will avoid searching through a whole set of possibilities (thus possibly missing something). Backing up is useful when you definitely want to skip searching on a path which you know is useless. The 'b' command takes an argument, which is the number of levels to be backed up. Because this command is irreversible, it always requires a numeric argument.
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 some unknown cells in the current generation OFF. The 'b' option backs up the search. The 'x' command sets cells as being unchecked. Finally, the 'q' command quits the program (confirmation is usually 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 continue searching.
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 again.
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)