Miscellaneous topics in Conway's Game of Life -- unfinished projects of all kinds and conditions

02 November 2006

Xlife #I format for Golly? Sort of...

I've added a couple of Python scripts, breeder.py and breeder-display.py, to a subsidiary folder in the Golly CVS system. These are by way of being translations of the original Xlife breeder.life -- one is short and fast, and the other is a slower on-screen walkthrough showing the breeder being incrementally constructed from smaller pieces.

I was hoping to be able to use breeder.life as a test case for code that would take *.life as input and produce one of these two types of .py script as output... but it's only _almost_ that simple.

The breeder.py script is a direct translation -- the numbers after each #I line show up pretty much unchanged in the Python script, and there's an easy glife conversion for the rotation and reflection specs:

0, 1 -> identity
1, 1 -> rcw
2, 1 -> flip
3, 1 -> rccw
0,-1 -> flip_y
1,-1 -> swap_xy
2,-1 -> flip_x
3,-1 -> swap_xy_flip

The only problem is that four subpatterns in breeder.life are defined with an 18-step time offset, like this:

#B ./breederrake.11
#I :breederpuffer 71 37 0 1 0
#I :ss.s 75 14 0 1 18
#I :ss.m 60 6 0 1 18
#I :ss.m 60 -8 0 -1 18
#E

Translated into English: "To make a breederrake11, put a breederpuffer at (71,37), run it for 18 generations, and then drop an LWSS at (75,14), an MWSS at (60,6), and a reflected MWSS at (60,-8)" [where breederpuffer, LWSS (ss.s), and MWSS (ss.m) are defined later in the file.]

This would all be very well and good, but here's the rub: the resulting breederrake11 subpattern is _not_ the 'flat' pattern resulting from running breederpuffer for 18 generations and adding the *WSSs. It's a true recursive definition -- which means that to get the right results in the final pattern, you have to rebuild each and every instance of breederrake11 by dropping a breederpuffer at the right relative location, waiting 18 ticks, and then adding the spaceships!

The glife system, on the other hand, generally deals with 'flat' subpatterns: if you give the above recipe for a breederrake11 and drop a copy of it into the Golly universe, what you'll see at t=0 in your final pattern is *generation 18* of breederpuffer!

The only safe way around this appears to be to "unpack" every definition that has a nonzero time value -- flatten out the nested definitions... and end up with a significantly longer recipe.

So in the end I cheated. In this specific case, it was easy enough to move the spaceships forward 9 cells to produce an equivalent breederrake11 that was all defined at t=0 -- no 18-tick time offset. The revised subpatterns were safe to use for the next level of definitions (this is not necessarily true, but it happened to be true in this case.)

The only remaining ugliness was the way that Xlife drops subpatterns into the universe, then runs the universe until it's time to drop in the next pattern -- instead of running each subpattern in isolation, then dropping it in when it has reached the right phase. Doing this in Python and storing the subpatterns in variables can require a lot of nested parentheses [or a long series of assignments to intermediate variables]:

flotilla = (((((((breederrake11(314,242)[4]
+ breederrake11(312,201,flip_y))[101]
+ breederrake00(368,286))[33]
+ breederrake10(359,158,flip_y))[306]
+ breederrake10(406,137,flip_y))[129]
+ breederrake01(349,273))[141]
+ breederrake10(428,336) + breederrake10(426,107,flip_y))[223]
+ breederrake00(473,371))[1]
+ breederrake00(472,71,flip_y)

The final result is a Python variable containing a complete breeder pattern.

--------------------------------------

The other way to build a breeder using the Xlife recipe is to use Golly's visible universe -- actually drop subpatterns in and run them. The second Python script, breeder-display.py, does this, in a way that lets you see the breeder pattern coming together:

breederrake11.put(314,242)
run(4)
breederrake11.put(312,201,flip_y)
run(101)
breederrake00.put(368,286)
run(33)
breederrake10.put(359,158,flip_y)
run(306)
breederrake10.put(406,137,flip_y)
run(129)
breederrake01.put(349,273)
run(141)
breederrake10.put(428,336)
breederrake10.put(426,107,flip_y)
run(223)
breederrake00.put(473,371)
run(1)
breederrake00.put(472,71,flip_y)

[if you look at what the script is actually doing, it's actually a bit more complicated than that, because it highlights the location of the next paste operation ahead of time -- but the above is the basic idea.]

--------------------------------------

In either case, the Xlife model doesn't seem to be the most efficient way of describing patterns compactly _or_ building them quickly -- my final target here is still a structured-format Caterpillar. The Xlife system essentially requires rebuilding every single copy of every single component pattern! It's possible to take shortcuts some of the time, but they're dangerous -- a pattern that Xlife can successfully load may blow up catastrophically if shortcuts are used.

Golly's normal method of defining new patterns in terms of transformed and rephased subpatterns, and then re-using the 'flat' results, seems to be more generally useful for recursive pattern definitions.

09 September 2006

Brice Due's Game-of-Life Metapixel -- Sample Patterns

Here are a few sample screenshots showing "metapatterns" created using Brice Due's new Conway's Life metacell and displayed with Golly 1.0. Click on the images to see them at full size:
Download this file


Download this file



A metacell is a large pattern that "simulates" a single cell in Conway's Game of Life or another similar CA rule; that is, when a grid of metacells is run for the right number of ticks -- one "metatick", so to speak -- a metacell will turn ON or OFF according to the rules it's programmed to follow, just as a single cell does.

David Bell's original unitcell was the first example of a metacell, followed by Jared Prince's modification which allowed multiple independent cell states in a single "Deep Cell". Both of these unitcells were hard-coded to simulate only the Conway's Life rule (which is also the only rule that allows the patterns to function.)

One of these days, Brice Due will probably get around to finishing the work of documenting his recent OTCAMP [Outer Totalistic Cellular Automaton Meta-Pixel] construction, which showed up as a star feature of the Golly 1.0 pattern collection. This new 2048-cell-square pattern is capable of acting like a single CA cell following any "outer totalistic" rule -- i.e., birth and survival can be programmed to depend on any combination of number of ON neighbors, from zero to eight, in the metacell's immediate neighborhood. The official OTCAMP weblog describes the new signal-processing technology (mostly period 46) included in the construction.

But the most impressive feature is the "metapixel" behavior: where Bell's and Prince's designs relied on a single glider in a particular spacetime location to signal an ON or OFF state for the metacell, Brice's metapixel quickly switches rows and columns of LWSSs on and off across a large area -- so the state of a metacell can be seen even when a viewer is zoomed out so far that it's impossible to distinguish individual circuit elements, let alone single cells.

The effect is that Golly can run a large metapixel pattern at surprisingly high speeds (after some initial warmup time to build up the hash table) -- and if the zoom level is high enough to show the whole metapattern, the effect is fairly similar to watching a regular pattern in a conventional Life player. When I started zooming in for the first time, the effect was thoroughly jaw-dropping -- it takes several successive magnifications before the individual components become visible.

The OTCAMP weblog is currently [as of 2/5/2007] a work in progress, and since Brice is also working on another very interesting Game-of-Life project (reworking Paul Callahan's 'ptbsearch' signal-conduit search program) I don't want to distract him... so I figured I'd make the ON and OFF metapixel patterns available here, along with a few pictures and sample metapatterns -- just in case anyone wanted to look at some of the metapatterns that didn't make it into the Golly "top-100" collection.

A full archive of the metapatterns Brice sent me, plus one or two that I generated myself with a Golly Python script (metafier.py, now included in the Golly 1.1 Scripts folder), can be downloaded from http://cranemtn.com/life/weblog/metablog.tar.gz. And here are the base patterns from which any metapattern in any outer totalistic rule can be composed -- a single OFF cell and a single ON cell. Notes on programming these metacells to simulate any rule of the form B??/S?? [each cell's birth and survival depending on the number of ON cells in its eight-cell neighborhood] can be found in the comments of the OFF and ON cells; I've also reproduced the header at the bottom of this posting.

Here's a detail from a metapattern made out of copies of Jason Summers' p156 gun:
B3/S23 p156 sigma-guns metapattern detail
Download this file or click on it to see a full-sized image.

Here's a detail of one particularly interesting phase of the p156 tiling:
detail of p156 geometric design



Here's a sample metapattern showing what happens when the tiles are programmed to run the B1/S1234568 rule instead of B3/S23:B1-S1234568 tree metapattern
Download this file to open it in Golly, or click on the image to see a full-sized screenshot. Detail after the pattern runs several metacycles:
B1-S1234568 tree metapattern detail



Here are a couple of simple B3/S23 patterns, generated with the Golly 'metafier' script (left) and Brice's original Perl script (right), showing what metapixels look like at various scales. The Perl script works on HistoricalLife three-state rule patterns from MCell 4.20, so the presence or absence of a metapixel cell can be used to denote the third state -- a "history" state that is used for cells that are currently OFF but have been ON in the past:





Here's an MWSS -- a middle-weight spaceship from Conway's Life, B3/S23 -- made out of metapixel tiles. However, the tiles are programmed to simulate a completely different rule, B3-S12345, which uses the MWSS as a seed for an expanding maze pattern: MWSS maze metapattern starting detail
Download this file

Here's the same pattern after it has run for a few hundred meta-generations:


Header (slightly modified) for metapixel ON and OFF base tiles:



------------------------------------------------------------------
OTCAmetapixel unit cell by Brice Due (fall 2005 - spring 2006). For info, base patterns, and a perl script to automate tilings, see b3s23life.blogspot.com/2006/09/brice-dues-game-of-life-metapixel.html

Both ON and OFF tiles must be programmed identically before tiling a model pattern. See below for programming instructions.
------------------------------------------------------------------
OTCAmetapixel tilings require Golly hashlife to run. Get Golly at http://golly.sourceforge.net

USAGE: Speed steps 8^3 - 8^6 are good. Be patient after changing the speed step; the hashlife cache needs time to warm up. Try increasing the maximum hash memory setting if the meta-pattern continues to run haltingly.
------------------------------------------------------------------
OTCAmetapixel = Outer Totalistic Cellular Automata Meta Pixel = OTCAMP

Period: p35328 = 2^9 * 3 * 23
Dimensions: 2048x2048 but physically 2058x2058 (see TILING below)
Pixel Area: 1720x1720 = 70% of the tile area
Duty Cycle: 90% (1720 / lwss c/2 = 3440 gens to transition pixel display)

TILING: To tile by hand, place tiles so that the cornermost blocks overlap. The tiles will physically overlap by 5 cells in every direction. The overlap will place tubs inside cross-corner neighbors. When tiling by script the tiles can be trimmed to 2048x2048 and the corner blocks and tubs removed. But the script MUST place the tubs inside cross-corner neighbor tiles.

PROGRAMMING: There are three different programmings. Two must be done explicitly by the user while the third is done implicitly during tiling.

B/S RULE: Any outer totalistic rule can be programmed. The lookup tables in the SW corner of the tile are in the familiar B/S format. The presence of an eater denotes membership of {B,S}n within the active rule set. To aid programming by hand, defective eaters have been placed at all 18 positions. These defective eaters burn cleanly. Thus, programming a rule is as simple as completing the eaters at the desired positions within the lookup tables. The lookup tables have been graphically annotated to make things clear. (Note: to study a single tile, program the rule B0/S = B0/Snone.)

CONNECTIVITY: There are eight glider output channels {NW, N, NE, E, SE, S, SW, W}. These channels are initially closed by eaters. The physical presence of a neighbor tile will trigger the appropriate proximity fuses and open the necessary glider channels. This programming is done automatically when tiles are placed.

NEIGHBORHOOD: Any subset of a Moore neighbrhood can be programmed. Initially there are 8 active proximity fuses {NW, N, NE, E, SE, S, SW, W}. Disabling a fuse results in that glider *output* channel remaining permanently closed. To disable the corner fuses, remove the lwss for that corner. To disable edge fuses, remove the block in the middle of that edge. Do not remove the eater near the block. For example, a von Neumann neighborhood is programmed by disabling the four corner fuses, leaving the four edge fuses active.

06 June 2006

The Last Few Years of Life News

For the past few years, Heinrich Koenig has been making available an ongoing catalog of new Game of Life results and current open problems. [I've been helping out some, but it's his server, so he ends up doing most of the work...]

Some randomly selected highlights:

Based on a recent 41-cell construction by Bill Gosper that exhibits O(t ln t) growth, Nick Gotts produced a pattern with only 26 ON cells with O(t^2) growth. [Update based on Nick Gotts' comment: Gosper's 41-cell construction remains the smallest pattern with a growth rate that is not an integral power of t.]

Hartmut Holzwart spent a little time recently constructing strange some patterns that look like inside-out spaceships. They're actually signals that travel through a half-ON, half-OFF striped agar -- the pattern that serves as the center of most of Holzwart's recent extensible "greyship" spaceships. The new signals move at 2c/3, two thirds of the "speed of light", and at right angles to previously-known lightspeed signals in the same medium.

Speaking of 2c/3, a while back Noam Elkies and I put together a 2c/3 diagonal signal transceiver based on a "wire" designed by Dean Hickerson. A transceiver is a device capable of transmitting information along a variable-length "wire"; in this case, the signal travels diagonally at two thirds of the speed of light, faster than any possible spaceship-based signal.

For diagonal signalling, this can even beat Jason Summers' telegraph from February 2003, which can communicate along an orthogonal "wire" at the speed of light (see Gabriel Nivasch's discussion of lightspeed signals -- a pair of telegraphs at right angles can only manage c/2 diagonally.)

Nicolay Beluchenko, in addition to producing several incredible collections of new Game-of-Life spaceships with a variety of new shapes and speeds -- and has also modified a known 'Garden of Eden', or 'orphan' pattern to fit it into a 12x12 bounding box. [Update: Achim Flammenkamp had previously discovered a 12x11 Garden of Eden with only 72 ON cells.]

Along with his extended explorations of c/12 Cordership technology, David Bell created a series of new sawtooth patterns. Definition of 'sawtooth' from Stephen Silver's Life Lexicon: "Any finite pattern whose population grows without bound but does not tend to infinity. (In other words, the population reaches new heights infinitely often, but also infinitely often returns to some fixed value.)".

Dean Hickerson invented some new "transcendental patterns" consisting of puffers and guns, which grow in what appear to be unpredictable ways.

A little farther back (December of 2004) Gabriel Nivasch, in an incredible feat of Life engineering, put the finishing touches on a Caterpillar -- a spaceship that travels at the previously unknown speed of 17c/45.

Many of the above patterns are much easier to study now that Andrew Trevorrow and Tomas Rokicki have made available their new cross-platform Life simulator, "Golly". It works on Macintosh, Windows, and Linux boxes, and makes clever use of hash tables to display the evolution of patterns with interesting large-scale behavior to a previously unheard-of number of generations.

Before the Caterpillar appeared on the scene, Karel Suhajda, Scot Ellison, David Eppstein, Paul Chapman, and others collaborated on the project of completing Jason Summers' sub-1000 gun collection [download link] -- an impressive conglomeration of the smallest known patterns that produce one output glider every p generations, for each period p=14 to 999.

This "gun collection" showcases a surprising variety of Life patterns, since as a general rule most new primes or prime factors require different mechanisms! (Some patterns have adjustable periods, but adjusting them tends to increase their size... and quite soon a custom-designed alternative with a smaller bounding box can generally edge them out of the running.)

Most of the higher-period guns were produced with Karel Suhajda's search program 'Hersrch' [download link], which given a target period can automatically generate a minimal Herschel loop (standard period-independent signal-guiding Life technology, originated by David Buckingham and extended by Paul Callahan). But the gun collection is an apparently inexhaustible source of optimization problems: as new Life technology is discovered, it can be incorporated into new guns with smaller bounding boxes, as in the case of this new piece of Herschel technology.

Back in 2004, Paul Tooke discovered an amazing new Cordership with only three engines, much easier to construct with gliders than any of its predecessors -- see '/jslife/guns/gun-corder-p690.lif' in Jason Summers' patttern collection.

Mark Niemiec's incredible collection of glider constructions is always worth mentioning. He's been steadily adding to the collection with syntheses of new discoveries.

Also in 2004, Jared Prince made an ingenious modification to David Bell's old Unit Life Cell. His new "Deep Cell" can process two independent states in parallel, opening up the possibility of running an infinite number of infinite Life configurations simultaneously in a single infinite universe (it's just that most of the configurations are simulated very, very, very slowly...) But of course for this kind of proof-by-example, execution speed isn't really the point: the pudding is in the proof, not in the practical details -- or however one should phrase that.

---------------------------------------------

Number-theory curiosities of various kinds have been showing up in of Game of Life patterns for a long time, of course. Many Game of Life engineering efforts involve infinitely-expanding patterns -- ranging from mathematically simple ones like Hartmut Holzwart's MAX pattern, which expands at the maximum sustainable speed in all directions, to much more complex engineering efforts like Dean Hickerson's prime-number generator -- or Jason Summers' modification of Hickerson's pattern, which expands forever unless it discovers a new Fermat prime (!). In August 2003 Jason Summers constructed a pattern that expands at O(log n) -- and logic circuitry that can store and manipulate integer values in O(log n) space is also within reach now.

24 February 2006

New results from Glue 2

Paul Chapman's Glue project is producing some interesting results these days. Glue (or rather Glue 2) is a search program that finds "natural" constructions of singlets (indivisible p1 and p2 patterns) by starting with a target object -- usually a block -- and bombarding it with a p2 slow salvo of gliders.


'salvo' means that all the gliders come from the same direction; 'slow' means that glider #n+1 must not arrive until the reaction from glider #n's collision has settled down into stability or a p2 oscillation, and 'p2' means that the only timing constraint on the gliders is that an even or odd phase may be specified. (Many intermediate collision results contain blinkers, beacons, toads, or other p2 patterns, and a glider on a given input lane can interact with a p2 target in two possible ways.)



eater recipes with MCell outlines of construction envelopes

You can also download the RLE, or have a look at a larger image. Here are the actual recipes in text format, and the MCell file used to create the above picture.


This is an example of a clever new MCell rule by Brice Due -- it shows not only the Smear but also the starting locations of the gliders and block, without changing anything about how Life actually evolves. Potentially a fairly useful trick for displaying this stuff. His notes also taught me a new way to do cell-state substitutions, with an MCell command I hadn't noticed (or at least realized the potential of). I had been doing the same task much more painfully by setting up whole new rules to do state conversions.


After the pattern is run, the full cell history is visible, just as in MCell's 'HistoricalLife' rule: all cells that were ON at any point during the reaction are blue instead of black --



Here's another take on the same display problem: Koenig's annotation format allows for multiple layers in different colors, in a format that's backwards compatible with standard RLE (at least for most Life editors.) Click on the image to see the RLE:


Finally, here's a screenshot of the current version of the Glue 2 search program used to generate these recipes: