Game of Life News: Records Archives

Records
Minimum-population sawtooth

David Bell has reduced the minimum repeating population of any known sawtooth from 262 to 260 cells. The sawtooth, similar to his 262-cell variant (from 2005), uses a 4-engine Cordership and stationary p256 gun. The space between the dynamic and static ends of the sawtooth is alternately filled with gliders and emptied.

David Bell's 260-cell sawtooth.

The population plot confirms the sawtooth behaviour of the pattern, showing that it is an exponential sawtooth. This is not the only possible envelope for a sawtooth, as Dean Hickerson built a parabolic sawtooth, so named because the convex hull of the population graph is a parabola.

David's sawtooth, despite having a very low population, still may not be optimal. There are two figure-8 oscillators between the p256 gun and four-engine Cordership, which could potentially be removed. Apparently, he searched for a sawtooth in which the interior of the gun performs this task, but to no avail.

We leave it as a challenge to the reader to create a sawtooth with a smaller minimum repeating population.

UPDATE: Thanks to Matthias Merzenich for noticing that I had confused David Bell and Paul Tooke; the article has now been amended.

Continue reading "Minimum-population sawtooth"

Posted by Adam P. Goucher at 03:58 | Permalink

Discovery
Progress of the Online Soup Search

Soup_search script screenshot for Golly 2.x

Over the last couple of months, Nathaniel Johnston's Online Soup Search for Conway's Life has been hunting for 20x20 random "methuselah" patterns, using a modest-sized distributed network -- a good fraction of the spare CPU cycles of perhaps a dozen computers. As of the end of August, the conwaylife.com server has tallied the final stabilizations of over 111 million random 20x20 Conway's Life "soups", totaling over three billion Life objects (still-life, oscillator, or spaceship). This is slowly approaching the scale of Achim Flammenkamp's earlier random-ash census project from a decade and a half ago -- which represented an impressive amount of dedicated CPU time for 1994.

Version 1.03 of the soup-search script is now available. It's a Python script that will run on the current version of Golly for Windows, Mac, or Linux. Version 1.03 displays much more detail about the progress of the current search.

Methuselah survival times appear to fit a simple inverse exponential sequence. Lifespans between 1000(N-1) and 1000N are about twice as frequent as lifespans between 1000N and 1000(N+1) -- for a wide range of N. Version 1.03 of the script continuously updates an on-screen table of these frequencies, starting at N=5. It is an open question how far this relationship continues, or whether a larger sample will yield a more precise approximation of the curve.

Continue reading "Progress of the Online Soup Search"

Posted by Dave Greene at 20:12 | Permalink

Records
New stable 180-degree glider reflector

A few months ago, Calcyman came up with a substantial improvement to stable-reflector technology, using some of Paul Callahan's search results from the 1990s.

Ultimate (so far...) stable 180 degree reflector, the 'rectifier'.
By Calcyman, 26th March 2009, 21:00 GMT

The previous smallest and fastest stable reflector, the "boojum reflector", produced an output glider 180 degrees from the input at a 9-cell offset. It contained nine still-life catalysts and took 202 ticks to recover. Calcyman's new discovery, the "rectifier", needs only five catalysts to produce the exact same reflected glider -- and it recovers in only 106 ticks.

This is an unusually short recovery time, to say the least -- because this is the first stable reflector that makes a perfect single-stage recovery.

All stable reflectors are triggered when an incoming glider strikes a "bait" still life and produces an active pattern. Until now, all known stable reflectors have fallen into one of two categories. In the first type, "destroy-then-rebuild", a glider colliding with one or more bait still lifes produces an output signal; the bait then has to be reconstructed as a separate step, by routing a branch of the output signal back to the key location.

In the second type, "rebuild-then-repair", catalysts successfully recreate the bait and an output signal from the original active pattern. But it's very difficult to find a set of catalysts that can recreate the bait in exactly the right place, allow a clean output signal to escape, _and_ suppress the remainder of the active pattern perfectly. So other unwanted still lifes generally appear along with the bait; the output signal then has to be routed around to clean up the extra junk (usually by annihilating it with a carefully-placed glider). Only then can the reflector safely accept another glider input.

The boojum reflector comes fairly close to a perfect single-stage recovery; a lucky cleanup glider is generated directly from the original active pattern, so no extra Herschel circuitry is needed. But Calcyman's new pattern is a significant step forward: it doesn't need any cleanup gliders at all!

Calcyman's article-length summary of the development of stable signal-processing technology includes examples of both "destroy-then-rebuild" and "rebuild-then-repair" reflector types. A more comprehensive collection of early stable-reflector constructions can be found in his reflector catalogue.

Continue reading "New stable 180-degree glider reflector"

Posted by Dave Greene at 10:32 | Permalink

Records
Stable Reflector with Record Recovery Time

Calcyman has designed a multi-stage stable glider reflector with a recovery time of 466 ticks -- an improvement over the long-standing record of 497 ticks, at the cost of a somewhat larger bounding box.

The reflector can be used as a glider-to-Herschel converter with the same recovery time, by replacing the final glider-producing conduit with a standard Fx176 component. This makes it possible to build glider-to-spaceship converters with 466-tick recovery times, also, by replacing the initial glider-to-Herschel stage in Stephen Silver's LWSS, MWSS, and HWSS converters.

Posted by Dave Greene at 23:16 | Permalink

Records
Update: smaller Garden of Eden previously known

Achim Flammenkamp's 12x11 Garden of Eden --
black cells ON, blue-gray cells must be OFF
Achim Flammenkamp, 23 June 2004

Paul Kwiatkowski has pointed out that Nicolay Beluchenko's 12x12 pattern, based on a 12x13 Garden of Eden pattern from June 14, 2004, is not the smallest known "orphan". Achim Flammenkamp discovered a 12x11 GoE a week later, on June 23, 2004:

It is still an open question whether 11x11 or smaller Garden of Eden patterns exist.

Posted by Dave Greene at 18:13 | Permalink

Records
Smaller Garden of Eden pattern

smaller (12x12) Garden of Eden pattern with 80 ON cells, based on
Achim Flammenkamp's 81-cell 13x12 orphan from 14 June 2004.
Single cell in rightmost column removed, and two other cells moved.
Nicolay Beluchenko, 11 February 2006

Nicolay Beluchenko has modified a previous 'orphan' (Game of Life pattern which has no possible predecessors, and thus can only appear at generation 0) to slightly reduce both the bounding box and the number of ON cells. Changed cells are shown at right: cells only in the original version are in blue, cells only in the new version are in red.

UPDATE: A week after producing the pattern on which Nicolay Beluchenko based his optimized version, Achim Flammenkamp built a smaller Garden of Eden pattern consisting of 72 ON cells inside a 12x11 bounding box. This 23 June 2004 discovery is the smallest Garden of Eden currently known.

Posted by Dave Greene at 20:34 | Permalink

Methuselahs
New Record Methuselah

Andrzej Okrasinski has found a new methuselah record holder, a 15 bit intial pattern with a final population of 1623 after 29053 generations. David Bell quickly found a 13 cell predecessor, bringing the record to 29055.

Some of the more unusual objects which make an appearance but which aren't in the final census include a Lightweight Spaceship [9P4H2V0.1], a Fishook Eater [7.3], a Long Barge [8.9], a Big S [14.492], a Bi-Pond [16.2630] and an unnamed 13 bit object [13.182].

Size	Discoverer	Gens	Final Pop.	Final Pattern, Census
13	[David Bell]	29055	1623	102(4.1), 2(4.2), 15(5.1), 6(6.2), 57(6.4), 1(7.2), 18(7.4), 5(8.7), 2(12.41), 135(3P2.1), 1(6P2.1), 1(6P2.2), 28(5P4H1V1.1)
15	[Andrzej Okrasinski]	29053

Note: Not all of the paths of escaped gliders are shown.

Posted by HKoenig at 22:54 | Permalink

Methuselahs
New Methuselah Records

Tomas Rokicki has announced some of the results of a survey for methuselahs. The table below shows the record holding patterns for given bit sizes. More information can be found at his webpage. Other information about methuselahs, can be found at Dean Hickerson's website. Andrzej Okrasinski also announced his finding of the current record holding pattern.

Size	Name	Gens	Final Pop.	Final Pattern, Census & Discoverer
	r Pentomino	1103	128	8(4.1), 1(5.1), 1(6.2), 4(6.4), 1(7.4), 4(3P2.1), 6(5P4H1V1.1)
5		1105
6		1108
7	Acorn [Charles Corderman]	5206	633	34(4.1), 8(5.1), 3(6.2), 30(6.4), 2(6.5), 5(7.4), 2(8.7), 1(8.8), 41(3P2.1), 13(5P4H1V1.1)
8	[Tomas Rokicki]	7467	952	51(4.1), 2(4.2), 11(5.1), 4(6.2), 35(6.4), 16(7.4), 2(8.7), 1(14.475), 61(3P2.1), 1(6P2.1), 24(5P4H1V1.1)
	Rabbits [Andrew Trevorrow]	17331	1749	109(4.1), 4(4.2), 18(5.1), 7(6.2), 65(6.4), 18(7.4), 3(8.7), 136(3P2.1), 2(6P2.1), 40(5P4H1V1.1)
9	[Paul Callahan]	17410
10	[Tomas Rokicki]	17423
11	[Tomas Rokicki]	17465
12-18	[Tomas Rokicki]	23334	2898	207(4.1), 7(4.2), 23(5.1), 12(6.2), 115(6.4), 2(7.2), 32(7.4), 4(8.7), 171(3P2.1), 1(6P2.1), 2(6P2.2), 70(5P4H1V1.1), 1(9P4H2V0.1)
19	[Andrzej Okrasinski]	28786	3091	196(4.1), 6(4.2), 31(5.1), 9(6.2), 143(6.4), 3(6.5), 34(7.4), 6(8.7), 2(12.41), 1(14.475), 213(3P2.1), 47(5P4H1V1.1)