Life Search Methodologies

Still-lifes | Oscillators | Other rules | Syntheses



Searching for Still-lifes

The Early Years

In Life's earliest days, lists of objects like still-lifes were compiled by hand. The lists of still-lifes up to 11 bits were compiled in this way. Unfortunately, such methods are slow and error-prone. While it is easy to automatically detect false positives by verifying that each object has the desired properties, it is easy to overlook unusual objects. Even today, new objects are occasionally discovered even in search spaces that have been thoroughly searched by hand previously. For example, H. Koenig discovered a three glider synthesis of the Pentadecathlon and in 2013, Josh Ball found a small c/7 spaceship, the Loafer.

In the late 1970s, Peter Raynham automated the process of searching for still-lifes by writing a computer program to systematically search for them. He used his program to verify the lists up to 11 bits, and newly compute the 12- and 13-bit lists. David Buckingham later used the same program to compute the 14-bit list.

Still Life Search Program

In the late 1980s, I decided to try to recreate a program like Raynham's, based on a general description of how it worked. My program grows still-lifes like crystals, starting with a seed bit at the top left corner (i.e. leftmost cell on topmost row), in such a way that only objects that are stable according to Life's rules are emitted. Of course, it is desirable to search as few non-viable objects as possible

The program treats an object as a two-dimensional array of cells. Each cell has one of three states: Living cells whose value has been fixed as alive, Dead cells whose value has been fixed as dead, and Uncommitted cells that are presumed to be dead, but that may later be either fixed as Dead, or changed to Alive. Each cell also has a counter of living neighbors, a counter of degrees of freedom (i.e. number of uncommitted neighbors), and a flag indicating the cell's stability.

The program iterates by picking an eligible uncommitted cell, then recursively searching two sub-branches, by fixing the cell as both dead one way, and alive the other way. (If any cell states have been previously mandated to be dead or alive, those cells are fixed to their mandated values without permitting the alternate value). Fixing a cell decreases the degrees of freedom of all its neighbors. Fixing a cell as alive also affects all its neighbors' neighbor counts, and possibly their stability and its own. Certain situations force pruning of the search tree:

Optimization

Many years ago, someone programmed a stand-alone word-processing machine at the office to search for viable tilings of pentominos. It inspired me to write a similar program on my computer. My program was able to find a solution within minutes, while the other program ran continually for over two months with no solutions, and was eventually lost during a power failure.

It was obvious, from watching the other program running, that its algorithm consisted of trying to place the first pentomino in every possible position, then the second, etc. This lead to many non-viable sub-trees being searched. In fact, for most of the program's two-month run, it was fruitlessly searching a space that had already been rendered non-viable because a few of the earlier pentominos had split the field into two disjoint areas whose sizes were not multiples of five. (In fact, it is possible for such an arrangement to occur by placing a single pentomino.)

The above example clearly illustrates the fact that, when performing searches, it is vitally important to perform them in the right order, so that non-viable branches can be discarded early all at once. The number of Life still-lifes seems asymptotic to around O(2.45n), or O(2.5n) when pseudo-still-lifes are included, and the number of living cells in those is around O(2.6n). The ideal search program would require commensurate computing resources. Raynham's program's execution time was around O(4n), and mine was similar to his.

In an attempt to improve the program's performance, I decided to try to optimize the search order. By sorting the cells available for fixing in order by degrees of freedom followed by stability, it makes the problem concentrate on those areas with few options (typically close to the center of the object). For example, if an object has an unstable core, the program will first try to stabilize the core, rather than wasting time on adding surface fluff to an object whose core can never be stabilized.

As a result, my program now uses time around O(2.6n). Since this is approximately the same order as that of the results, further improvements are unlikely.

I have used the program to verify Raynham's and Buckingham's results, and count all the still-lifes (and pseudo-still-lifes) up to 24 bits.

Deficiencies

In order to avoid finding up to 8 copies of every object, the program originally converted each object into a standard canonical representation, and discarded all instances except the canonical one.

In order to avoid wasting time creating large numbers of patterns that aren't even objects, the program avoids creating unnecessary disconnected islands of living cells, by only placing living cells adjacent to other living cells. It does, however, create necessary disconnected islands by also placing living cells next to unstable dead cells. Unfortunately, in situations where two islands, say A and B are related in such a way that A requires B but not vice versa (i.e. AB), this means that if the program starts with A, it will find AB, but if it starts with B, it will not find BA.

To alleviate this problem, the program was changed to emit all copies, and then remove duplicates in a separate post-processing pass, after the list of objects has been sorted. This means that objects of the form AB would be found, as long as at least one orientation begins with piece A. For this to fail, B would have to wrap around A on three sides in such a way that no part of A occurs on an exposed corner. The smallest such object has 23 bits (figure 1a). This also fails in objects of the form ABC where no part of B occurs at an exposed corner. The smallest such object has 20 bits (figure 1b).

The related problem occurs with objects of the form ABC, that could never be detected. The smallest such object has 16 bits (figure 1c).

One way to reduce this problem is to allow the program to create a domino island adjacent to a stable domino. This causes the program to find pseudo-objects as well as objects. Fortunately, the additional computation cost in adding them is virtually unchanged. The pseudo-objects can then be removed by a post-processing pass that runs in linear time. As a useful side-effect, this also allows the program to find pseudo-objects virtually free.

This solves most kinds of adjacent island problems except for one: a line of five bits vs. a single bit (e.g. a tub, or an eater tail). Problematic objects of the form ABC start to occur at 22 bits (figure 1d). There are 1 at 22 bits, 5 at 23 bits, and 26 at 24 bits. Problematic objects of the form ABC start to occur at 24 bits (figures 1e, 1f). The 4 different inductors can be combined in any way, and either up or down orientations, yielding 20 objects at 24 bits. While it was easy enough to add these specific missing objects manually, at 25 bits there would be hundreds of missing objects, and adding so many objects manually would be quite error prone.

One solution I tried was to allow the program to find "quasi-still-lifes", i.e. including those (like two adjacent tubs) that share adjacent dead cells. Unfortunately, the number of these seems to be around O(3.3n), making this impractical at large sizes, which is the only time when it is actually needed.

Another solution I recently tried was to have the program specifically check for single-bit near line-of-five. While this did find the missing objects, it inexplicably lost the ability to find one pseudo-still-life: four blocks on a pond (figure 1g). Since there is no algorithmic reason for this, I must conclude that this change introduced a subtle bug, and until I determine what the cause is, it would be inadvisable to attempt further larger searches (most specifically, for 25-bit still-lifes).

Figure 1.

searches

1a. 23-bit AB 1b. 20-bit ABC 1c. 16-bit ABC 1d. new 22-bit ABC 1e,1f. 24-bit ABC 1g. new missing 24-bit pseudo-object.


Searching for Oscillators

Oscillators may be viewed as still-lifes in a cylindrical three-dimensional cellular automata rule, with each plane corresponding to one Life time interval, where every cell's state is determined solely based on the conditions of its 9 neighbors on the previous plane. I modified the still-life search program to search for such three-dimensional "still-lifes".

A few additional considerations arose. For example, when searching for oscillators of a particular size, one needs to constrain the population of one generation, while other generations are allowed to have higher populations. As a result, the whole way of keeping track of populations needed to be done a different way. Also, all still-lifes are technically oscillators where all cells are stators and none are rotors, so these will be be found, and must later be discarded. (In fact, the vast majority of objects found would be of this form, so the program would spend most of its time finding and discarding still-lifes.)

I have used the program to count all the period 2 oscillators (and pseudo-oscillators) up to 21 bits. Since, with my computer equipment, searching for 22-bit ones would take around 15 days of uninterrupted dedicated computation, I am unlikely to attempt this any time soon.

Period 2 oscillators are a special case, in that each generation's parents are also that generation's children, so each generation is coupled to the other in two ways, and the two generations are symmetrical with each other. This is not true with higher periods. I have attempted to use the program to search for oscillators of higher periods. Unfortunately, in Life, the smallest such oscillators have 12 bits, and the program's computational requirements when finding oscillators increase so quickly that I was unable to even search for 12-bit objects in reasonable time. As a result, I leave searching for such oscillators to other people who have different search programs that use methodologies more suitable for finding higher-period oscillators.


Searching in Other Rules

The still-life search program can also find still-lifes and oscillators in other totalistic rules, provided that both birth and survival conditions occupy a single contiguous block, and birth-on-0 is not allowed.

I have used it to do several searches in 3/4-Life (B34/S34). One notable feature of this rule is that, with birth-on-4, there are no pseudo-objects.

A very unusual feature of B34/S34 is that, except for the 4-bit block, still-lifes are extremely rare. They must all resemble large fortresses, whose outer walls must have corners resembling Life's ships or long-ships, and connected by straight crenelations. While the interiors of such still-lifes are more flexible, the exterior must necessarily be constructed in this way. The smallest three still-lifes have 4, 36, and 44 bits respectively. I have been able to actually search for still-lifes up to 45 bits, because they are so unnatural, so the search tree has very few viable branches, so the computational requirements increase slowly.

Finally, since birth and survival conditions are identical, this rule has the peculiar property that a cell's subsequent state is totally independent of its current state. Thus, a cell cannot influence its own child, but it can indirectly influence its own grandchild. Essentially, activity in even and odd cells usually appear to alternate. Not surprisingly, most known oscillators are period 2, and a few have other even periods. The only exceptions are a few period 3 ones. Also, most known spaceships move at c/3 with a period of 3, that also correlates with this parity property.


Automated Syntheses

One thing that becomes quite apparent as one examines lists of larger objects, is that most such objects can be trivially derived from smaller, related objects. In fact, most object syntheses use this principle to synthesize larger objects from previously-synthesized smaller ones.

I also realized that I was wasting an extraordinary amount of time manually creating syntheses for hundreds (and, sometimes, thousands) of objects, most of which were largely a matter of cutting and pasting existing pieces together. It would be a much more effective use of time if one could identify which objects could be synthesized trivially, leaving short lists of difficult-to-synthesize objects that would require more sophisticated methods.

Around 2002, I wrote a search program that accepts a list of objects to synthesize and a set of synthesis recipes, and attempts to synthesize those objects. The output is the same list of objects, with an optional comment indicating a successful ancestor and synthesis recipe that can be used to convert that ancestor (always smaller and/or simpler) into the desired object. The object list is in the same format as output by the still-life search program. The recipes are normal Life files, with cells in 7 different states/colors:

Each recipe is a template for transforming an entire class of objects that share one particular bonding area into a similar class of objects with slightly different bonding areas.

The program is somewhat tolerant of human error. If any incorrect recipe is somehow included (for example, one that can never produce the specified outcome), the program will try to use it, but will merely never find any situation where the recipe is applicable, since it will always fail in any context where it is tried.

There are currently over 800 recipes available to the program. The following is a small sampling of some of the simpler recipes. The colors indicate cell types: black=tools, grey=permanently dead, teal=permanently alive, pink=birth, brown=death.

searches

Add block #3 [4] Add boat #2 [3] Boat to table #1 [2] Snake to carrier #1 [5]
Boat to shillelagh #3 [3] Snake to shillelagh #1 [4] Add beacon #1 [6]

Note that the recipes must be carefully chosen to avoid looping. This is done by assigning a total order to all objects. Recipes are free to convert smaller objects into larger ones (or objects of equal size, allowing only transformations from simpler to more complicated objects). For example, ship < snake < carrier < beacon. Mechanisms that violate this rule may be used in combinations, as long as the recipe itself does not do so. For example, a hypothetical recipe to grow a snake by 7 bits could consist of growing a snake by 8 and then shrinking it by 1.

This program has found syntheses for the following:

At present, the program is fairly rudimentary, and has several major design deficiencies:



See also: definitions, structure, search methodologies, other rules, news, credits, links, site map, search, expanded search, search help, downloads.

Home page | Life page

Copyright © 1997, 1998, 1999, 2013, 2014 by Mark. D. Niemiec. All rights reserved.
This page was last updated on 2015-02-19.