🚀 Discover this trending post from Hacker News 📖
📂 **Category**:
✅ **What You’ll Learn**:
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!
💬 **What’s your take?**
Share your thoughts in the comments below!
#️⃣ **#23Bit #Lifes #Glider #Constructible**
🕒 **Posted on**: 1768566127
🌟 **Want more?** Click here for more info! 🌟
