In the Game of Life, which still lifes can be produced by crashing gliders together? We’ve known for a few years that the answer cannot be “all of them”, because in 2022 Ilkka Törmä and Ville Salo found a patch of still life that, if it exists in the universe, must have existed since the beginning of time. And so, there is no way we could have produced it out of empty space through glider collisions. Similar such patches have been found since, with the goal of optimising size or population, and at the time of writing the record holder is an unsynthesizable still life with population 154 produced by forum user “400spartans”.
Finding syntheses for small still lifes is easy, but at some unknown point below 154 it becomes impossible. Today, we completed our collaborative project to notch the lower bound up from 22 to 23, by giving explicit syntheses for all 1,646,147 (strict)A still life is strict when all its islands are necessary to maintain the stability of the pattern.
still lifes with population 23.
The final holdout shown below has systematic name xs23_g88m9icz1iu146, and was solved by vilc.
As you might imagine, this is not the first project of this kind; all still lifes with 18 bits were synthesised in October 2019, 19 bits in February 2020, 20 bits in March 2021, 21 bits in November 2022 and 22 bits in August 2024.
As the number of bits increases, the number of distinct still lifes explodes exponentially, so that the 23-bit project had about 2.4× as many still lifes to consider as the 22-bit project. The situation is actually worse than that: not only are there more problems to get through, but each additional bit reveals knotty new ways for a still life to fit together.
My contribution was the mass generation of synthesis recipes through computer searches. These disposed of roughly 99.97% of the targets, letting the people with actual synthesis talent focus on the ones where new ideas were needed. I’ll spend the rest of the post talking about the things I tried.
Here’s the solution for that final still life, split into steps:
Solutions like this are typical: there is a natural reaction that produces a large chunk of still life, and then many “synthesis components” massage that into the target.There is an unfortunate clash of terminology between this kind of “component” and a connected component of a pattern.
Many of these first steps are discovered via soup searches. Sometimes, a random soup will produce a still life of interest through the random collision of some simple reagents. If we are lucky, it is possible to reproduce the reaction by using gliders to re-create the same configuration of reagents. We can also find first steps by randomly colliding gliders directly; this was the topic of a previous post.
Most of the action happens after this first step, in finding sequences of components that massage a known still life into the target.
Transfer and Stomp
As you can see in the above example, most synthesis steps only touch a small part of the still life. And because pattern behaviour in the Game of Life is determined locally, the incoming gliders in a synthesis step don’t particularly care what the rest of a still life looks like, only that the part they interact with is correct.
For this reason, there is hope of “transferring” synthesis steps from
one still life to another. There is a transfer.py script in
Shinjuku that does exactly this: from each component, one can
extract a “component template” which only remembers the placements of
the gliders and the part of the still life which is affected. Then,
for each component template and each target, the script tests whether
the output of the template matches any location on the target, and for
anywhere that matches, whether the component actually effects that
change successfully. This script, together with some extensions by
Alex Greason, were important in all the synthesis projects up to the
current one.
Unfortunately, transfer.py is a little slow, and a little limited.
Independently, vilc and myself worked on some C++ replacements:
transfer.cpp and Stomp respectively.The transfer.py script
spends a lot of its time in the underlying C++ lifelib library, so
the change of language doesn’t have as much of an impact as you might
think.
Stomp is what I used to do the initial mass solving of the still lifes that only required one step to be transferred from a known component, as well as to find the long recipes that were necessary for some of the trickier still lifes.
Stomp does a few things that make it a lot faster; the first is that
it is multithreaded. This is easy enough: processing each target is an
embarrassingly parallel problem. Next, it uses a more refined notion
of “template” that also takes into account neighbourhood counts for
cells that don’t change. This cuts down on the number of false
positive matches a lot. The templates are also not simply applied one
at a time, instead, Stomp builds a tree of templates, where each node
branches on the state of an additional cell in the template (up to
some fairly shallow depth).This was apparently the intended strategy
to be used in the transfer.py script; one of the crucial functions
is called apply_tree but doesn’t actually use a tree.
This allows us to throw out a lot of the templates without checking individually whether they match, once we reach a branch in the tree that no longer matches any location in the target pattern.
On top of all the above, Stomp is quite discerning about which component templates it’s willing to consider. I tried a lot of heuristics while working on Stomp, and here are the ones I landed on by the end. We ignore components in any of the following situations:
- Pure cleanup steps, where the thing being deleted is unattached to
the remainder of the still life. Because we are doing a backwards
search for components that lead to a target, allowing cleanup steps
would lead to an explosion of precursors with, say, an extra block
in all possible positions. (
transfer.pydoes the same.) - All the input still lifes are small (<7 in population). These are likely first steps derived from soups as discussed above, and not generalisable.
- Less than 30% of the original still life survives unchanged; to avoid junk “components” that essentially blow up a still life and replace it with a new one.
- There are multiple disconnected changes to the still life. These often arise when performing symmetric changes to a symmetric base, and we may as well apply both steps separately.
- The component involves an unnecessary boat-bit reaction. There are a lot of these, and we may as well do that as a separate step.
With all the above, we still run into trouble with the search space exploding. The biggest problem is components that create a small still life, together with additional components that just shove it around pointlessly. For this reason, we further cut down on the new synthesis components we’re willing to consider while the search is running. We skip any new component where:
- The input or output is too sparse. For these purposes, “sparse” means that there is some connected component that is too far away from the largest component by population.
- The gliders interact with the largest connected component but not any smaller ones (if there are any).
This is all glued into a tree search, prioritising precursors with lowest population. At the end of this post, you can see a solution that required a very deep tree search to find, and which would certainly not have been possible without these improvements.
Using the existing components extracted from the Shinjuku database got us a lot of the way, with only around 2000 23-bit targets resisting solution at this point.
So, how do we find new components to feed into this machine?
Component Farming
The simplest strategy is to fire some gliders at an object and hope that it modifies it without destroying it. I did this using a modification of the GPU searcher from the previous post, to iterate through a list of objects and all possible 3-glider collisions that interact within a certain time range. If the still life is still mostly present but not exactly identical to the starting object, the configuration is logged. Sometimes some extra ash is left behind, so an additional script hunts for a minimal cleanup.
This kind of random searching surfaces components that couldn’t be found any other way, because they’re too weird and unexpected to have been dreamed up by a human. Here’s a few random examples, three of which have automatically-generated cleanup gliders:
With a little more work and a more restricted search area, going through 4-glider collisions is manageable, though I ended up getting fewer interesting results than the 3-glider set. One additional strategy was to place entire spark-producing configurations of gliders rather than individual gliders. For this, I stole a large set of such configurations from this forum thread. Again, this turned up some interesting results, but not as many as I had hoped.
Mr. Component
Kazyan had the following idea on Discord way back in 2021:
Take a look at the final step for
xs26_08o0u1eoz32q9871. It consists of two very distinct halves. Those two subcomponents, at the time, were known, but sincetransfer.pyhad never seen them be used together, it wouldn’t have known to use them if asked to take apart that xs26. This vaporware, which I’ve been thinking of as “Mr. Component”, would be supplied with a list of these halves, assemble as many complete pairings from that list as possible, and dump the resulting full components into shinjuku. Then,transfer.pywould do its thing.
For reference, here’s that last step that he’s referring to:
I’ve highlighted the crucial cell in red. This cell is never active, but is the single spot where the two halves of the component interact. In a single generation this cell goes from underpopulated to overpopulated, and to achieve this the two halves have to be correctly synchronised. Applying them to the starting still life in sequence would not work.
I wrote(For “wrote” read “vibecoded”, this worked disturbingly well.)
a small tool to realise Kazyan’s idea. This first goes through all known components and identifies the above situation; when there are two barely-interacting pieces that rely on each other to succeed. Each piece stores the “timing” it requires, that is, on which generation the above sort of neighbourhood change occurs.
Then, like Stomp above, we run through some list of targets and try to apply all of these discovered parts to it. Each pair of matching parts is tested to see whether they actually succeed simultaneously, once their timing is aligned.
Of course this is not fully general; in principle a component may have more than two pieces that require synchronisation at multiple generations. If you have any examples let me know! The two-part version of the tool worked well enough.
Overall Mr. Component worked well, and resulted in a bunch of automated solutions that I think would have had to be found by hand otherwise. Here’s a couple of example steps, with the crucial cells highlighted. Notice that the cell in the rightmost example actually goes from overpopulated to underpopulated, giving that tricky bridge motif in the middle.
The Trickiest Recipe
To conclude, here’s the 23-bit still life with the most complicated recipe at the time of writing: 47 steps and 178 gliders in total. This was found through a Stomp search with unlimited depth and maximum intermediate population of 32. If it works, it works!