Tutorials/Glider syntheses

From LifeWiki
Jump to navigation Jump to search

Glider synthesis is the process of colliding gliders – the smallest spaceship in Conway's Game of Life – in a specific way to construct a specific object. It is one of the few areas in the Game of Life that many discoveries can still be made mostly manually.

This is an example of a glider synthesis:

x = 73, y = 28, rule = B3/S23 52bo$50bobo$51b2o4$51bobo$52b2o2bobo4bo$52bo3b2o5bobo$2bo54bo5b2o$ obo$b2o$49b2o$13bo35bo$3b2o6b2o37b3o12bo$4b2o6b2o38bo10b2o$3bo51b 2o7b2o$55b2o$8b2o$9b2o54b2o$8bo48b2o5b2o4b3o$58bo7bo3bo$12bo45bobo 10bo$12b2o45b2o$11bobo$16b3o$16bo$17bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

It is a 13-glider synthesis of Achim Flammenkamp's pseudo-barberpole, which, at the time of writing, is the cheapest synthesis known of that object. Note that this particular synthesis can be divided into two stages which can take place arbitrarily far apart; multi-stage synthesis are typically shown this way to make it easier to see what is happening in each step. The three still life syntheses are independent and could also be moved into separate stages, so this is really a four-stage synthesis. Simple well-separated still lifes tend to be trivial to construct, and often the order of construction doesn't matter, so several stages are sometimes left combined in cases like this.

Locating known glider syntheses

To locate a known glider synthesis, there are three main places you should look:

Also, there's a very important difference between the two databases. Shinjuku/Catagolue focuses on documenting the single synthesis of each object that takes the smallest number of gliders. By contrast, Niemiec's database collects many types of syntheses for a large number of objects, including more expensive ones. For example, there may be syntheses of two combined objects where each type of object is added to an already existing instance of the other type. Or there might be syntheses where all gliders come from one side of the object (useful in building the object near other existing objects), and so on.

Sometimes you will not find a synthesis for a particular object in any of these places. That could be because:

  • No syntheses are known because no-one has decided to synthesise that specific object before. These are usually pretty easy to make a synthesis for yourself.
  • No syntheses are known because the object is very difficult to synthesise. An example of this would be Sir Robin.
  • The object has been proven impossible to synthesise. Examples of this include all Gardens of Eden as well as solutions to the grandfather problem.

In the next section we will look at how to make your own syntheses.

Making your own glider syntheses

Using Catagolue to find glider syntheses

To find an existing glider synthesis of an object in Catagolue, start by selecting the object in Golly and copying its RLE to the clipboard. Then go to this Catagolue page, paste the RLE into the text box there, and click "Identify". You will be taken directly to the Catagolue page for that object. The bottom of that page will show a synthesis for the object if one is known.

Using Catagolue soups to find glider syntheses

NOTE: You might instead want to use synthtools.py in Shinjuku to do the following process more quickly. More details about this will be given in the section "Using search programs to assist in creating syntheses".

Let's say you want to find a synthesis for cis-block on candlefrobra, which, according to Mark Niemiec's website, takes 12 gliders:

x = 10, y = 5, rule = B3/S23 4bo$2obob2obo$2obo3bobo$3bo4bo$3b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Select the pattern in Golly and run the script mentioned above. It should bring you to this page on Catagolue. This page also contains a best-known synthesis with six gliders or less, but for the purposes of this tutorial, please ignore that!

Scroll down to the part of the page with lots of differently coloured dots. These are all sample soups for the object. The black ones are asymmetric soups, which are the easiest to make syntheses from. (However, it should not be forgotten that you can still get good syntheses from symmetric soups -- especially if the object has the same type of symmetry as the soup.)

So click on the first asymmetric soup (the first black dot), and copy the RLE it provides into Golly. You should get this:

x = 16, y = 16, rule = B3/S23 ob2o3bo2bo2bobo$ob5ob3o2bobo$obobo4b2obo2bo$3b2o5b3obo$2bobo8b3o$bo2bo 4b5obo$4b6obo2b2o$obo2b2o2b4o$o2bob4obo3b2o$5b3o2bo3bo$6bob2ob2o2bo$2b 2ob5obob2o$4o3b2obobo2bo$ob3ob2obo3b2o$3b3ob5o2b2o$bo3b2obob2obo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Now run the soup until the candlefrobra appears (this should happen at generation 919). Use the goto.py script (which comes with Golly) to go 20 generations back. Watch each generation up to the candlefrobra's formation step-by-step to see which objects react to make the candlefrobra. Next, go back 20 generations, select the objects that reacted to make a candlefrobra, and paste them into a new layer.

Test to see if that pasted pattern works. If it doesn't work, go back to the layer with the soup, and select and paste a larger area. Once you've deleted any objects that don't participate in the reaction, you should get something like this:

x = 11, y = 16, rule = B3/S23 9bo$8bobo$9b2o2$6bo$2o3bobo$2o2b2ob2o6$5bobo$4b3o$3b3o$3b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

The reaction is pi + block + boat + traffic lightcandlefrobra + some junk. We know how to make all those reactants with gliders, so we can now make a synthesis! In fact, all of the reactants can be made in two gliders (those collisions can be found in two-glider-collisions.rle in Golly's pattern collection).

However, before you start, you may notice that not all of the blinkers in the traffic light react before making the candlefrobra. So maybe we don't need all of the blinkers. In fact, the only blinker we need is the top one. Try deleting the rest of the blinkers just before the traffic light first reacts. This isn't necessary, but to help your understanding, I've replaced the traffic light predecessor with one that only makes a blinker to get this:

x = 11, y = 19, rule = B3/S23 9bo$8bobo$9b2o2$6bo$2o3bobo$2o2b2ob2o8$5b2o$2b3obo$2b2o$2b2obo$3bobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Now there is also no junk left over after the synthesis, only the candlefrobra.

Now you can start the synthesis. To do this, you should synthesise each of the reactants separately in such a way that they work when put together. You can find all the syntheses you need for this in two-glider-collisions.rle. Try to do this yourself. If you can't manage to make it work using only 2-glider collisions, look in Mark Niemiec's website to find more useful syntheses.

If you need a hint, these are the syntheses I would use (zoomed out in case you don't want the hint):

x = 35, y = 29, rule = B3/S23 bo26bo$2bo14bo11b2ob2o$3o13bobo9b2o2bobo$4bo12b2o13bo$3bo$3b3o8bo$8b2o 3bobo$8b2o2b2ob2o2$25b2o$24bobo$26bo2$27b2o$27bobo$13b2o12bo$10b3obo$ 10b2o$10b2obo$11bobo6$bobo$2b2o2b2o$2bo2b2o$7bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ ZOOM -16 THEME 6 ]]
(click above to open LifeViewer)

If you used the hint, note that you may need to rewind some of the syntheses to make it work.

How did you do? For reference, this is the synthesis I created which used 8 gliders:

x = 17, y = 21, rule = B3/S23 9bobo$bo8b2o$2bo7bo3b3o$3o11bo$4bo10bo$3bo$3b3o2$7b2o$6bobo$8bo$2bo$ob o6b2o$b2o6bobo$9bo4$10b3o$10bo$11bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

In this example with the block on trans-candlefrobra, we were lucky to get a good reaction from the very first soup. Sometimes you will have to look through 20 or more soups before finding a suitable reaction.

If you want more practice for creating synthesis from a reaction, here is the reaction the current record holding synthesis of why not (7 gliders) was made with:

x = 22, y = 14, rule = B3/S23 17bo$16b3o$15b2ob2o$19b2o$19b3o$19b2o$10b3o2b2ob2o$2o8bobo3b3o$b2o7b3o 4bo$o3$12b2o$12b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Good luck!

Using converters to make syntheses

Let’s say we want to make a synthesis for this 21-bit still-life:

x = 11, y = 9, rule = B3/S23 4b2o$4bo$b2obo$obobobo$2o3b2o$7b2o$7bobo$8bobo$9bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

We identify the object using Catagolue, and it brings us here. Why is there still a cheap synthesis of 12 gliders despite having no sample soups on Catagolue? It is time to be introduced to the world of converters…

A converter is a collision of gliders with a still-life/oscillator, which turns it into a new still-life/oscillator. Here is an example of a converter. It turns a hook into a barge:

x = 37, y = 11, rule = B3/S23 12bo$12bobo$5bo6b2o$3bobo$4b2o$bo26bo$b2o6b2o16bobo$obo7bo17bobo$9bo5b 2o12bo5b2o$10b3obobo13b3obobo$12b2o18b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Converters are very useful for creating syntheses that are too large and/or rare to turn up on Catagolue. For example, the duodecapole currently has no appearances on Catagolue, but we can still create a synthesis from a barberpole-lengthening converter and an already known synthesis for the decapole like this:

x = 113, y = 33, rule = B3/S23 26bo$27b2o15bo$26b2o16bobo$44b2o38bo$82bobo6bo$2bo80b2o4b2o5bo$obo83bo 3b2o2b2o$b2o83b2o7b2o$85bobo$26bobo$26b2o63b2o$27bo63bo$59bo32bobo$23b obo32bo$24b2o5bobo24b3o33bobo$24bo7b2o$32bo9bo53bobo$41b2o7bo$14b3o24b obo5b2o47bobo$16bo32bobo$15bo84bobo$47bo55bo$47b2o53b2o$46bobo$107bobo $72b2o24b2o7b2o$72bobo24b2o2b2o3bo$72bo25bo5b2o4b2o$103bo6bobo$29b2o 79bo$28bobo16b2o$30bo15b2o$48bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Here are three places you will find converters:

So with this new knowledge, we can get back to this 21-bit still life and see how the synthesis works.

Firstly, the 5-glider collision in the left of the synthesis creates a constellation of a long boat tie ship and a nearby boat. It may be initially thought that we must edgeshoot the boat after the long-boat-tie-ship is created, but we don’t need to do so. In the formation of this still life, it opens up an opportunity of a boat-bit reaction, where one glider collides with a pattern so that it is turned into a boat due to a snake catalysis.

Next, we see the first example of a converter. It converts a boat into a ship using three gliders. Since two of the cells of the boat are always turned on in its conversion to a ship, it is suitable in the edgiest of cases, like when the boat is stabilizing something unstable. This is a property of many other useful converters as well, whose purpose is to turn an object into another while still preserving the states of most of its cells.

x = 10, y = 12, rule = B3/S23 6bo$6bobo$2o4b2o$obo$bo2$7b3o$7bo$8bo$4b2o$3bobo$5bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

In the final step of the synthesis, we see another converter, this time a 4-glider one. It turns a ship into a long hook. Note that the ship does not get destroyed at all, as the long hook that is attached to it stays there. Here is the exact component standalone:

x = 15, y = 19, rule = B3/S23 3b2o3b2o$3bobobobo$4b2ob2o5$6bo$2o3b2o$b2o2bobo$o11b2o$12bobo$12bo4$7b 2o$6b2o$8bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

You can see that only one cell of the ship turns off during the conversion. Thus, it cannot interfere with the nearby ship or anything tied to it.

Keep in mind that there are many combinations of using converters to synthesize an object, so you should examine multiple options and estimate the cost of each one so that you can produce an optimal synthesis.

If you want more practice at using converters and Catagolue to find syntheses, try finding a synthesis for this still-life:

x = 9, y = 10, rule = B3/S23 2o$obo$3bo3bo$4bobobo$5b2obo$7bo$5b2o$5bo$6bo$5b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Converters are used in many others ways than just assisting soup search result-based syntheses. They are used a lot in the syntheses of difficult objects like unnatural billiard tables and spaceships. For example, this is the current best 29P3H1V0 synthesis as of June 2022 (35 gliders):

x = 372, y = 58, rule = B3/S23 350bo$340bo8bo$338b2o9b3o$339b2o5$371bo$369b2o$321bo48b2o$319bobo$ 320b2o$327bo7bobo$328bo6b2o$326b3o7bo7$66bo$66bobo$57bo8b2o205bo 82bobo$55bobo44bo168bobo3bobo49b2o25b2o$56b2o3bo38bobo169b2o3b2o 49bo2bo25bo$60bo40b2o175bo49bo2bo$60b3o42b2o222b2o23bo$104bo2bo 121bo123bo$105b2o121bo124b3o$138bobo87b3o$101b2o36b2o8b2o34b2o48b 2o46b2o50b2o$22bobo76bo37bo3bobo3bo35bo49bo40b2o5bo44b2o5bo16bo$ 22b2o79bo40b2o5bo35bo38b2o9bo37bo2bo6bo41bo2bo6bo13b2o$23bo78b2o 40bo5b2o34b2o37bobo8b2o37bobo6b2o41bobo6b2o13bobo$185bo41bo7bo40bo 6bo44bo6bo$61b2o36b2o46b2o36bo49bo47bo51bo$61bo2b2o33bo2b2o43bo2b 2o34b2o48b2o46b2o50b2o$62bobo2bo32bobo2bo42bobo2bo30bobo2bo44bobob o43bobobo47bobobo$14bo48bo2b2o33bo2b2o37b2o4bo2b2o30b2o2b2o44b2o3b o42b2o3bo46b2o3bo$obo11bobo127b2o46bobo45bo47bo51bo$b2o2bobo6b2o 127bo48b2o45b2o46b2o41b2o7b2o$bo3b2o140b2o44bo135b2o$6bo140bobo 181bo$141b3o3bo$143bo47b2o$142bo47b2o$192bo148b2o13b2o$340bobo12b 2o$323b2o17bo14bo$322bobo$324bo$349bo$329b2o17b2o$328bobo17bobo8bo $330bo27b2o$358bobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID WIDTH 1280 ]]
(click above to open LifeViewer)

Using search programs to assist in creating syntheses

3-glider collision database

For this part of the tutorial, you will need to use Python scripts with Golly.

find-preds.py

The find-preds.py script is useful for objects for which a large number of soups are listed in Catagolue. A script by this name used to be available as part of the Shinjuku repository, but the functionality is still available in the form of a "pred" function in the Shinjuku "synthtools" module. A findpreds.py script using this function can be found here.

To use it, clone the Shinjuku repo, then install lifelib using

pip install --upgrade python-lifelib

(see the Shinjuku readme-windows.md file for alternate installation options if you're on Windows, or readme.md for other OSes).

Then find the apgcode for the object you're interested in -- e.g., xs19_354ljgozw346 and pass that into the pred() function. Otherwise, run the findpreds.py script on the link above, and input the apgcode of the object and the symmetry you want to search once you run the script. The script has added two functionalities onto the standard pred() function, in which the list of soups is shuffled, and that you will not lose unsaved work even if you want to terminate your search early.

The function will work through all of the relevant soups of the desired symmetry, and for each one will find the minimum set of islands 50 ticks before the object appears, that still cooperate to produce the object -- removing any extraneous ash that doesn't participate in the creation of the object. It will create and output a stamp-collection RLE showing all of the resulting creation methods.

synthesise-constellation.py

Below is a 25-glider synthesis of lightweight emulator:

x = 163, y = 51, rule = B3/S23 71bo$47bobo19bobo$48b2o20b2o$48bo30bo$79bobo$79b2o18bo$99bobo$63bo6bo 28b2o$49bo12bo5b2o$50b2o10b3o4b2o$49b2o2$92bobo$92b2o$3bobo87bo$3b2o 146b2o2b2o2b2o$4bo70b2o74bo2b4o2bo$bo73b2o75b8o$b2o146b3o8b3o$obo146bo 2bo6bo2bo$150b2o8b2o$93b2o$93bobo$93bo10bo$103b2o$46bobo54bobo$47b2o$ 47bo10bo$56bobo$57b2o$150b2o8b2o$3bobo143bo2bo6bo2bo$3b2o144b3o8b3o$4b o70b2o75b8o$bo73b2o69b2o3bo2b4o2bo$b2o142bobo3b2o2b2o2b2o$obo55bo88bo$ 58b2o$57bobo2$101b2o$81b2o4b3o10b2o$82b2o5bo12bo$51b2o28bo6bo$50bobo$ 52bo18b2o$70bobo$72bo30bo$80b2o20b2o$80bobo19bobo$80bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Notice that in the first step, two blocks are created using a total of four gliders. This may be the most obvious way to synthesise them, but is it the cheapest?

This is where 2718281828's 3G collision database comes in. It contains ~460,000 different three-glider collisions and the objects/constellations they produce, and includes a Python script created by Goldtiger997 to search through the database. Download the three files and place them somewhere convenient, preferably your Scripts\Python folder. In Golly, paste the desired constellation into a new layer and run synthesise-constellation.py. If there are any collisions in the database that produce the same objects in the same positions relative to each other, they will all be displayed.

Let's try this with our two-block constellation. After running the script, we get this:

x = 268, y = 36, rule = B3/S23 2bo61bo35bo67bo44bo36bo$obo61bobo34b2o63b2o46b2o35b2o$b2o61b2o34b2o65b 2o44b2o35b2o2$218bo36bo$216b2o35b2o$217b2o35b2o17$111bo39bo$112bo39bo$ 13bo37bo58b3o37b3o$14bo37bo$12b3o35b3o62bo39bo$113b2o38b2o$114b2o38b2o $13b2o36b2o$13bobo35bobo$13bo37bo$201bo64bo$201b2o62b2o$200bobo62bobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

All six of these collisions work in essentially the same way, by colliding a glider with a pi-heptomino. Since the two blocks are the first step of our lightweight emulator synthesis, we don't have to worry about other nearby objects interfering, so any of these will be suitable. In other cases, you may have to try several of these collisions before finding one that works for the synthesis you're working on.

Now that we have a three-glider collision of the two blocks, our lightweight emulator synthesis has been reduced to 24 gliders, which is currently the cheapest known as of the time of writing:

x = 167, y = 47, rule = B3/S23 87bo$66bo21b2o$64bobo20b2o$65b2o26bo$91b2o$92b2o19bo$111b2o$82bo 29b2o$67bo7bobo3bo$68bo6b2o4b3o$66b3o7bo2$105bo58bo$105bobo43b2o2b 2o2b2o3bobo$90b2o13b2o44bo2b4o2bo3b2o$90b2o60b8o$149b3o8b3o$106b2o 41bo2bo6bo2bo$105b2o43b2o8b2o$107bo8b2o$116bobo$116bo$o$b2o3bo$2o 3b2o$5bobo57bo$63bobo$64b2o8bo$75b2o73b2o8b2o$74b2o73bo2bo6bo2bo$ 149b3o8b3o$90b2o60b8o$75b2o13b2o59bo2b4o2bo$74bobo74b2o2b2o2b2o$ 76bo$31b2o$30b2o73bo7b3o$32bo65b3o4b2o6bo$100bo3bobo7bo$68b2o29bo$ 69b2o$68bo19b2o$89b2o$88bo26b2o$93b2o20bobo$92b2o21bo$94bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Note: In April 2020, a version of this database was released which contains a subset of four-glider collisions in addition to the two- and three-glider collisions. In August 2022, a new version of the 4-glider database was also published, which is more than 10 times larger than the older one. The installation instructions are the same; just make sure to copy both the 3G and 4G files. If your three-glider search gives no results, try this search instead. The collisions are also laid out in a grid instead of a line in this version. The searches in both databases must be run separately because the synthesis data is stored slightly differently.

Note: As of February 2022, Golly 4.0 and above uses Python3, and the script mentioned above needs slight modifications. If you are unable to run it, replace all the xrange() functions in it with range() and you should be good to go.

synthesise-patt.py - synthesising active objects

synthesise-patt.py uses the same database as synthesise-constellation, but is instead used to synthesise unstable objects and is therefore more useful when multiple things are happening during a given synthesis step. It can be found here. Like before, place the three files in your Scripts\Python folder.

Let's start with a 7-glider bridge snake component, taken from Mark Niemiec's database:

x = 22, y = 22, rule = B3/S23 5bob2o$5b2obo2$10bo$10bo8bobo$10bo8b2o$20bo2$17b2o$16b2o$18bo5$3o16b2o $2bo16bobo$bo17bo2$3b3o$5bo$4bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

In generation 25, we can see the following unstable object, created from a blinker and two gliders, for 4 gliders total:

x = 6, y = 2, rule = B3/S23 3o$3b3o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Let's see if there's a way to make this object with only 3 gliders, and therefore the bridge snake component in 6 gliders. Place it into a new layer and run the script; if it's running correctly you should see something like "X collisions found, Y collisions tried" in the top left of Golly. After a few seconds, you should see a list of all syntheses whose population counts over time match that of the given object. For this object in particular, you should see these six syntheses:

x = 382, y = 14, rule = B3/S23 4bo70bo74bo81bo67bo77bo$5bo70b2o73b2o80bo67b2o73b2o$3b3o69b2o73b2o79b 3o66b2o75b2o$155bo$79bo75b2o147bobo74bo$2o77b2o73bobo76b3o68b2o73b2o$b 2o75bobo154bo69bo74b2o$o158b2o64bobo6bo74b2o65bo$158b2o66b2o80b2o67bo$ 160bo65bo83bo64b3o$7b2o$7bobo67b3o$7bo69bo$78bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Now comes the fun part: determining which, if any, of these is suitable for our bridge snake component. In most cases, collisions where gliders come from only two directions perpendicular to each other tend to be the most likely to work, but in this case third one from the left seemed promising:

x = 10, y = 11, rule = B3/S23 obo$b2o$bo2$4b2o$5b2o$4bo2$8bo$7b2o$7bobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Mirroring this horizontally, we can see that it seems to fit in well with the snake, as all three gliders come from the other three directions:

x = 15, y = 11, rule = B3/S23 12bobo$ob2o8b2o$2obo9bo2$9b2o$8b2o$10bo2$6bo$6b2o$5bobo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID STOP 13 ]]
(click above to open LifeViewer)

Now we can paste in the other three gliders, and rewind them a few generations so they show up at the correct time, and our 6G component is complete:

x = 17, y = 20, rule = B3/S23 14bobo$2bob2o8b2o$2b2obo9bo2$11b2o$10b2o$12bo2$8bo$8b2o$7bobo3$3o10b2o $2bo10bobo$bo11bo2$3b3o$5bo$4bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

When choosing a generation on which to run the script, it's often a good idea to pause just before the object begins to interact with other stuff, so you get as many potentially useful collisions as possible. However, if you run the script and it gives you several hundred collisions producing irrelevant objects, you may want to consider rewinding a few generations so that the script searches for a more specific population sequence and is therefore more likely to give the pattern you want.

As practice, try to complete this component:

x = 16, y = 14, rule = B3/S23 o$b2o$2o2$8bo$9b2o$8bobo$8bobo$9bo2$12b2o$12bo$13b3o$15bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

A four-glider solution can be found here.

find-by-octohash-Python3.py and find-by-octo3.py - finding active objects in 1G collisions

Another database that can be useful when a specific active reaction is needed is the octohash database. The name "octohash" denotes a hash function that returns the exact same hash value for any of the eight orientations of a pattern -- i.e., the octohash of any rotation or reflection of a pattern will always be the same as the octohash of the original pattern. lifelib has a similar function available called "octodigest", but the octohash database is designed to work with Golly and Python, without any dependency on lifelib.

The database is just a series of simple text files containing ten printable ASCII characters for each generation of each glider collision with each constellation. Python can search through these text files very quickly to find matching hashes. The hashing function first finds the canonical orientation of the current phase of the collision. Then it runs the RLE through a SHA1 hash function, throws away everything except the first seven bytes, and encodes the resulting integer in base 90 using the ASCII characters from 37 to 126 -- mostly. Backslashes, apostrophes, and commas are replaced with "!", "#", and "$" respectively, to make the text strings a little less likely to cause any escape-character or quote-character issues, in any programming language that may be used to work with these octohash strings.

This turns out to be a good enough hash function that no hash collisions showed up in the entire set of 12 × 12 constellation / glider interactions.

The current octohash databases catalogue every generation of every possible collision between a single glider and all possible small constellations of common objects:

To use the octohash database, clone the octohash Git repository, or try the "Download ZIP" option under the "Code" dropdown. In Golly, select the active pattern you want to create with a 1G collision. For example, if you want to create a pentadecathlon by hitting a seed constellation with a trigger glider, place any of the 15 phases of a pentadecathlon in the Golly universe, select it, and run find-octohash-Python3.py.

The octo3obj database can currently be downloaded from here, and the generating code including the find-by-octo3.py script can be found in the octo3obj repository.

There turns out to be exactly one constellation of two common objects inside a 12 × 12 bounding box (from the octohash database) that produces a clean pentadecathlon when hit by exactly the right glider:

x = 17, y = 8, rule = B3/S23 15bo$14bo$14b3o$2o$obo$2bo5bo$2b2o3bobo$7b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

There's also exactly one constellation of three common objects inside an 11 × 11 bounding box (from the octo3obj database) that is a clean pentadecathlon seed:

x = 10, y = 13, rule = B3/S23 5b2o$4bo2bo$5b2o$9bo$bo7bo$obo6bo$obo$bo3$6b3o$6bo$7bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

The original find-octohash.py works with Python 2.x and Golly 3.x. Presumably most users going forward will be using Golly 4.0 or above, so will need to run find-by-octohash-Python3.py instead. The octo3obj search script is Python3 only (and the name doesn't bother to mention that.)

Unlike synthesise-patt.py vs. synthesise-constellation.py, the octohash/octo3obj search scripts work equally well for stabilized ash or for active patterns, because the database records a seven-byte hash value for each individual generation of every collision.

collisrc.py

For this part of the tutorial, you will need to first install lifelib. If you already have apgsearch, you can use the filepath to your apgmera\lifelib folder to run this script.

praosylen's collisrc.py (short for "collision search") script randomly collides gliders with a given still life and records any interesting still lifes it finds, and is primarily designed to find new or reduced components. The latest version can be found here, and a list of search parameters can be found here. You can also try out Alex Greason's version of the script which relies on Shinjuku and runs on large numbers of still lifes, trying a set number of collisions for each one.

spark-search-Python3.py - finding cheaper substitutes for sparks

See Chris Cain's walkthrough at the beginning of the spark_search thread for details. A Python3-compatible version of the spark-search.py script has been edited in to the first post.

popseq.py and popseq.c - finding cheaper substitutes for sparks, continued

Another tool related to synthesise-patt.py and synthesise-constellation.py is Chris Cain's popseq, which comes in two versions: the original Python script and the much faster C version. Here again the idea is to look for active patterns by recognizing their distinct population sequences. In other words, population is used as a simple hash function to recognize the pattern. For active patterns that stabilize too quickly, popseq shares the same limitations as the 'synthesise' search tools: it can return an unmanageably large number of false positive matches.

popseq.c by default is set up to find active patterns in the search space of 4-glider collisions consisting of gliders coming from two perpendicular directions, the idea being that these collisions are most likely to produce useful results with good clearance. popseq.py was designed to operate on whatever set of gencols collision results you want it to search, so you might set up the script to use a database of 2-glider, 3-glider, or 4-glider collisions, or whatever custom collision set you might want to search. Setup details can be found in the above links.

Assisted cleanup

Sometimes the reaction involved in a synthesis produces not only the target product but also some leftovers. For instance, a 20-bit still life appears in the following reaction:

39bo$38bo$38b3o8$31b2o$30bo2bo45bo$22b2o7b2o46bo$21bo2bo54bo$22b2o10bo $33b2o39b2o$33bobo38b2o3$77b2o$76bo2bo$76bo2bo$17b2o47bo2bob2o4b2o$16b o2bo46b5obo$17b2o3b2o$21bo2bo43bob5o$22b2o38b2o4b2obo2bo$61bo2bo$61bo 2bo$62b2o3$5bobo57b2o$6b2o57b2o$6bo10b2o$16bo2bo41bo$8b2o7b2o42bo$7bo 2bo50bo$8b2o8$3o$2bo$bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

To make a synthesis from it, you need to get rid of the surrounding objects with extra gliders. But where should they go? Well, there are a couple of handy programs that can help you out.

glider-destruction.py

For this part of the tutorial, you will need to use Python scripts with Golly.

An easy way to locate the cleanup gliders is to apply gameoflifeboy's glider-destruction.py (see here). Given a pattern, the script attempts to find a clean 1-glider destruction for it; if there isn't one, it tells you the results with minimum bounding box and population. As usual, save the script in Scripts\Python folder.

Since the pattern is rotationally symmetric, considering one half is enough. Select the upper right constellation and copy it to a new pattern:

5bo$5bo$5bo2$2o$2o3$3b2o$2bo2bo$2bo2bo$3b2o! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Run the script and — presto! It gives a solution:

5bo$5bo$5bo2$2o$2o3$3b2o$2bo2bo$2bo2bo$3b2o$8b2o$8bobo$8bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Pasting it back, we find that it is compatible with the target still life. So the cleanup is done successfully:

23bo$23bo$23bo2$18b2o$18b2o3$21b2o$20bo2bo$20bo2bo$10bo2bob2o4b2o$2bo 7b5obo9b2o$obo23bobo$b2o9bob5o7bo$6b2o4b2obo2bo$5bo2bo$5bo2bo$6b2o3$9b 2o$9b2o2$5bo$5bo$5bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

However, it should be noted that we are lucky in this case. The results from the script is not guaranteed to be actually usable, as either the glider or the cleaning reaction may crash into the target. Besides, the suggested method is not always the most efficient if there isn't a clean 1-glider destruction.

Seeds of Destruction Game
Also see: Tutorials/Seeds of Destruction Game

For this part of the tutorial, you will need to install Java.

Seeds of Destruction Game is an interactive application that allows one to modify a pattern by hovering the mouse around and see the effects immediately. Basically the idea is simple — put a glider somewhere manually, observe and repeat — but what is italicized makes the trial-and-error process easier.

A brief summary of the procedure, for those who don't bother to read another tutorial:

  1. Copy the pattern to be cleaned to clipboard.
  2. In Seeds of Destruction Game, click the third button from below when its label reads "Puzzle". (If instead it reads "Seed", use mouse wheel to change.) This loads the pattern to the application and creates a new "Puzzle (something)" entry on the right.
  3. Ensure that the first button from above is labelled as "Glider" (if not, use mouse wheel again to change). Adjust the orientation and parity of the glider shown in the second button by rolling mouse wheel.
  4. Click somewhere to lay down the glider and observe how the pattern evolves by rolling mouse wheel on the "Start" and "Gens" buttons. If the result is not satisfying, click the "Puzzle (something)" entry on the right to reset and start a new attempt.
  5. Upon obtaining a good result, click the fifth button from above. This loads the current pattern to clipboard in LifeHistory RLE format (if the label shows "Golly") or in plain two-state RLE format ("Life").

With Seeds of Destruction Game, it is even possible to suppress debris by throwing a glider into the active soup. In the following synthesis for a variant of gray counter, the uppermost glider was found in this way, which tamed quite a lot of mess:

x = 114, y = 79, rule = B3/S23 60bobo$61b2o$61bo48$96bo$94bobo$95b2o$101bo$101bobo$101b2o$88bobo$89b 2o$89bo2$91bo$91bobo6bobo$91b2o7b2o$101bo5$27bobo$6bobo18b2o$6b2o20bo$ bo5bo81b2o$2bo86bobo$3o25b2o60b2o$27b2o82b3o$29bo56b2o$3b2o80bo2bo$3bo bo80bobo$3bo83bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] [[ THEME 6 GRID ]]
(click above to open LifeViewer)

Submitting syntheses to Catagolue

Once you've completed a new record-breaking synthesis for a still life, oscillator, or spaceship, you can add it to the object's Catagolue page by pasting the RLE into the submission box at the bottom of the "Syntheses" page. There are some important things to note about how to format the pattern in order for it to be interpreted correctly:

  • The rule must be either B3/S23 or LifeHistory (in the latter case only states 0 and 1 are allowed).
  • The pattern must not exceed a bounding box of 9999 × 9999, a population of 100,000, or a file size of 400 kilobytes.
    • Note that this restriction is in place to prevent the queue of user-submitted synthesis components from exceeding the object size limit of one megabyte. If you wish to submit more than about a megabyte of syntheses at a time, you're probably better off including your syntheses in Shinjuku format and submitting a merge request to Shinjuku.
  • xWSSes are allowed to substitute for gliders, and Shinjuku will automatically attempt to convert them into their respective three-glider collisions. However, because the conversions all happen at the same time, the resulting synthesis may not be valid due to gliders crossing paths, and the conversion might have to be done manually.[1]
  • Each individual step, including the gliders/xWSSes, must be separated by at least 20 empty rows/columns.
  • It is recommended that every glider/xWSS should begin interacting before generation 1000 if possible, and each step should overall stabilize by generation 4000. If Catagolue does not parse your synthesis properly, check the validity of your synthesis, or whether you omitted or added objects to the intended synthesis. If you still can't find the issue or if your synthesis is valid, there's unfortunately not much that can be done other than posting it somewhere else (the forums or Discord).
  • The initial pattern in each step must match the resulting pattern of the previous step (though rotations/reflections are allowed).
  • Although the synthesis RLEs on Mark Niemiec's website have the final object displayed next to the synthesis for each individual step, these are technically redundant and should be removed from the pattern when submitting to Catagolue.

When you submit, your RLE is added to a queue to be processed by the automatic update process, which runs every 8 hours. If you're not sure whether your synthesis is on Catagolue yet, you can check the "Jobs" page on the Catagolue repository, particularly the jobs named shinjuku, to see the console output for the update process. Dijkstra's algorithm is used to calculate the shortest path to the desired object using the known components, so you may find that earlier steps of your synthesis have been replaced by an already-known cheaper way of producing the same intermediate object.

Also, if you're submitting a new or newly-improved component to Catagolue, don't worry about manually applying it to every single possible object in the database, because Shinjuku's transfer.py does this automatically. The script has to be invoked manually, but as long as there's at least one synthesis featuring your component, the script will consider it when automatically creating new syntheses. Do note, however, that it will only attempt to synthesise objects that either already have a synthesis or are strict still lifes with 20 bits or less; in other cases you may want to consider submitting the synthesis yourself.[note 1]

Notes

  1. Other transfer.py runs have targeted objects constructible through intermediate components[2] and large objects which have appeared at least once in an apgsearch soup.[3]

References

  1. Ian07 (March 9, 2020). Re: Shinjuku: a database of glider syntheses (discussion thread) at the ConwayLife.com forums
  2. Adam P. Goucher (October 13, 2019). "level-2 and level-3 transfer searches". GitLab.
  3. Alex Greason (June 9, 2020). "Transfer run targeting all still lifes with at least one soup in an official symmetry but no synthesis". GitLab.

External links

Forum threads

Code repositories