User:Goldenratio/draft
Planning to split the search program part of glider syntheses tutorial into a separate tutorial, as if we add any more programs it'll get too long. Goldenratio talk • contribs 16:45, 15 May 2021 (UTC)
3-glider collision database
For this part of the tutorial, you will need to use Python scripts with Golly.
synthesise-constellation.py
Below is a 25-glider synthesis of lightweight emulator:
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:
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:
Note: As of April 2020, a new version of this script is available which contains a subset of four-glider collisions in addition to the two- and three-glider collisions. 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.
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:
In generation 25, we can see the following unstable object, created from a blinker and two gliders, for 4 gliders total:
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:
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 I found that the third one from the left seemed promising:
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:
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:
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:
A four-glider solution can be found here.
find-octohash-Python3.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 12x12 constellation / glider interactions.
The current octohash database catalogues every generation of every possible collision between a single glider and all possible small constellations of common objects. Constellations may contain up to two well-separated objects -- no pseudo still lifes -- and must fit inside a 12x12 bounding box. The objects used in the enumeration were block, boat, beehive, tub, pond, ship, loaf, eater, long boat, and blinker.
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.
There turns out to be exactly one constellation of two common objects inside 12x12 that produces a clean pentadecathlon when hit by exactly the right glider:
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-octohash.Python3.py instead.
Unlike synthesise-patt.py vs. synthesise-constellation.py, the octohash search script works equally well for stabilized ash or for active patterns, because the database records a seven-byte hash value for every generation of every collision.
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:
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:
Run the script and — presto! It gives a solution:
Pasting it back, we find that it is compatible with the target still life. So the cleanup is done successfully:
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.
One-glider collision sript
Not written yet. The example non-cleaned up synthesis:
with the example clean up:
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:
- Copy the pattern to be cleaned to clipboard.
- 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.
- 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.
- 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.
- 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:
spark_search
Chris Cain's spark_search (thread) Golly script is a new way to search for replacement gliders to do the same job as hard-to-contruct cells.
Say we want to complete this converter, which transforms Achim's p4 into a "mutated" version:
However, if we run synth_patt on these white cells, we get no solution! But wait, we don't need those exact white cells to trigger this conversion: for example, this similar set works as well:
Enumerating all sets of cells which could trigger the conversion and running synth_patt on each one would be an absolute nightmare. This is where spark_search comes in. First, create a LifeHistory pattern which contains both the conversion pattern and the final result, with the cells that we want to be off in the final result in blue:
Now run the script, and it'll give a bunch of popup dialog boxes before it can run. Let's go through them:
- Direction: The direction in which the white cells go in to modify the green cells. The choices are only South (S) or Southeast (SE): if your two patterns are oriented in some other way you'll have to adjust them to point south or southeast. In this specific example, we choose South, as the green cells are directly south of the white cells. So, input S for this pattern.
- Delay: This is how many generations must pass before the pattern on the left becomes the one on the right (minus the blue cells). In this case, the delay is 10, so input 10 for this pattern.
- Cell increase at penultimate step: You usually won't have to change this, but essentially this parameter determines if the collision will have any clearance at all, and inputting a high number here (like more than 10) means that the solutions will usually not interact with the green cells until we want it to, which is what we want. However, choosing high numbers here could potentially cause the script to throw out perfectly valid collisions.
- Horizontal offset between before/after: How many cells the pattern on the left, after the amount of generations we put as the delay parameter, must be translated to equal the pattern on the right at the beginning. In this case, the horizontal offset is 18, so input 18.
- Final population: It is recommended to not change this unless you know that there will probably be a lot of solutions, in which case this parameter will help in finding solutions which leave no junk behind. In our example, it's not clear whether or not there will be any solutions at all, so we leave this unchanged.
- Gencols filename: The options here are 2g (two-glider two-sided collisions), 3g (three-glider two-sided collisions), s2g (two two-sided gliders plus one common stable object), and 3gb (three-glider three-sided collisions). In most cases, 3g (default) is the best option, unless you know there's going to be a lot of solutions (in which case 2g may be a better pick), or the direction is SE (in which case 3gb may provide some solutions in which 3g can't.) As we don't know whether or not there will be solutions, we pick 3g.
- symmetry: this can be d (default), x, or xd. In most cases you won't need to change this option here, but read the thread linked above to learn what each of these mean.
After inputting, if there is a warning box saying "example pattern is not a solution", then you probably made a mistake somewhere in the delay or horizontal offset inputs. In that case, stop the script and try to input the correct parameters.
conclusion coming soon.
(unrelated; to be put in the main syntheses tutorial):
How far should you stage syntheses?
There is dispute between glider synthesizers over how much exactly glider syntheses should be synthesized. However, the community consensus is that syntheses should be staged significantly, but not unnecessarily. RLE example and more explanation coming soon...