16 in 16: Efficient 16-bit Synthesis Project

[Macbi]

Congrats!

Here's the current state of the art:

Code: Select all

Population  Max Cost
9            5
10           6
11           7
12           8
13           9
14           11
15           12
16           14
17           16
18           38
19           infinity

Every still life <9 cells can be done in 4 or less, which is known to be optimal since we've checked all the 3 glider collisions.

[Kazyan]

Congrats!

Here's the current state of the art:

Code: Select all

Population  Max Cost
9            5
10           6
11           7
12           8
13           9
14           11
15           12
16           14
17           16
18           38
19           infinity

Every still life <9 cells can be done in 4 or less, which is known to be optimal since we've checked all the 3 glider collisions.

All 14-bit still lifes can now be done in 10 gliders; this last one will show up during the next Catagolue update. As usual, Goldtiger helped a lot with reaching this benchmark.

Code: Select all

x = 42, y = 35, rule = B3/S23
9bobo$10b2o$10bo7$28bo$27bobo$28bobo$29bo2$35b2o$34bobo$36bo2b2o$39bob
o$30bo8bo$30b2o$29bobo2$39bo$38b2o$38bobo4$10b2o$9bobo$11bo2$bo$b2o$ob
o!

Furthermore, mostly due to A for Awesome's help and probably some transfer reductions, 18-bit still lifes now take at most 33 gliders. Aside from further work on reducing 18-bit still lifes, the only other reasonable target to go for right now is 19-in-anything. Or maybe an aggressive 5G search to find the three 10-bit still lifes that still require 6 gliders (very long hook with tail, tub with long long tail, and the remarkably long snake).

[Macbi]

Or maybe an aggressive 5G search to find the three 10-bit still lifes that still require 6 gliders (very long hook with tail, tub with long long tail, and the remarkably long snake).

Is there any hope for getting the two remaining 9-bitters in 4?

[Ian07]

Is there any hope for getting the two remaining 9-bitters in 4?

I don't see why not. Many of the objects that are about the same frequency class as long^3 snake have 4G syntheses, and if I understand correctly we've still only investigated a small fraction of the possible 4G collisions. It's just a matter of figuring out a way to efficiently do a mostly-comprehensive search (something like wildmyron's stdin_WM_4G census but on a larger scale)

[dvgrn]

Is there any hope for getting the two remaining 9-bitters in 4?

I don't see why not. Many of the objects that are about the same frequency class as long^3 snake have 4G syntheses, and if I understand correctly we've still only investigated a small fraction of the possible 4G collisions. It's just a matter of figuring out a way to efficiently do a mostly-comprehensive search (something like wildmyron's stdin_WM_4G census but on a larger scale)

What was the generator for that stdin_WM_4G census, exactly? Bob Shemyakin's suggestion a couple of years ago was

For 4G synthesis more effectively attack 2G set by two gliders from all possible directions. Because 2G set limited (71) and many of them short-lived, this should dramatically reduce the amount of computation (at least one of the gliders must reacts with 2G).

That was in response to simeks' random 4G collision search -- 10 CPU-days of picking random gliders. It does seem likely that a good number of additional 4G recipes are still out there waiting to be discovered, but it might be just the luck of the draw if the remaining 9-bitters are among them.

99 point some number of 9's percent of the 4G space can be characterized as a glider hitting an enormous mess far too late to clean anything up successfully, so any "mostly-comprehensive" search will have to make some reasonable assumptions about the value of "too late". It might be nice to clearly document the bounds of the search, so that future more ambitious searchers can extend the range over time.

[Jormungant]

I do not know if there is any interest in this, but it would be nice to also have glider synthesis for non-still-life with small populations. The obvious caveat is that many syntheses tend to have left over debris that takes a few more generation to clear, which makes defining the notion of "successful" synthesis of non-still lives a bit tricky, but I would say that having the expected downstream pattern sequence be unperturbed by such debris would be sufficient.
For instance, a 4-glider synthesis of a 8-bit pattern (the spark bit does not contribute the downstream sequence):

Code: Select all

x = 21, y = 19, rule = LifeHistory
A$.2A$2A16.A$18.A.A$18.2A3$14.A$14.A.A$14.2A4$4.D$3.D$4.D$5.D2.D3.2A$
5.3D3.2A$13.A!

Another task would be to list such pattern in a meaningful way, this 8-bit pattern give rise to 2 9-bit and 2 10-bit patterns later... The "meaningful" patterns would need to lead to distinct downstream pattern sequences. In order to for this to be tractable for <10 bits, one would need to make sure that the translation/rotation/symmetry of a sub-population the bits in a pattern does not cause the entirety to the downstream pattern sequence to match the original pattern with that same transformation applied on the offspring of that sub-population (basically, the idea as the distinction used for still life and Constellations)

That being said, maybe someone somewhere did make a repository for this already, but it's not a category on https://catagolue.appspot.com/home

[Kazyan]

I do not know if there is any interest in this, but it would be nice to also have glider synthesis for non-still-life with small populations. The obvious caveat is that many syntheses tend to have left over debris that takes a few more generation to clear, which makes defining the notion of "successful" synthesis of non-still lives a bit tricky, but I would say that having the expected downstream pattern sequence be unperturbed by such debris would be sufficient.
For instance, a 4-glider synthesis of a 8-bit pattern (the spark bit does not contribute the downstream sequence):

Code: Select all

x = 21, y = 19, rule = LifeHistory
A$.2A$2A16.A$18.A.A$18.2A3$14.A$14.A.A$14.2A4$4.D$3.D$4.D$5.D2.D3.2A$
5.3D3.2A$13.A!

Another task would be to list such pattern in a meaningful way, this 8-bit pattern give rise to 2 9-bit and 2 10-bit patterns later... The "meaningful" patterns would need to lead to distinct downstream pattern sequences. In order to for this to be tractable for <14 bits, one would need to make sure that the translation/rotation/symmetry of a sub-population the bits in a pattern does not cause the entirety to the downstream pattern sequence to match the original pattern with that same transformation applied on the offspring of that sub-population (basically, the idea as the distinction used for still life and Constellations)

That being said, maybe someone somewhere did make a repository for this already, but it's not a category on https://catagolue.appspot.com/home

There is no repository, but there are several utilities that have a similar functionality. Goldtiger's synthesize-patt checks a libary of 3-glider collisions for a small active object, though it checks this efficiently by relying on the object's population sequence, so it will miss any objects with dying sparks or random beehives in the corner. chris_c also wrote popseq, which does essentially the same thing, but with two-sided 4G collisions. There's also spark-search, which checks 3G collisions that can have the same functionality in a synthesis as an example active object.

[wildmyron]

Is there any hope for getting the two remaining 9-bitters in 4?

I don't see why not. Many of the objects that are about the same frequency class as long^3 snake have 4G syntheses, and if I understand correctly we've still only investigated a small fraction of the possible 4G collisions. It's just a matter of figuring out a way to efficiently do a mostly-comprehensive search (something like wildmyron's stdin_WM_4G census but on a larger scale)

What was the generator for that stdin_WM_4G census, exactly?

Details and code for part of the census are in the Hacking apgsearch thread. IIRC, the code I ran for the census actually generates a different (larger?) subset of one-sided collisions c.f. the original popseq.c. In addition to the one sided collisions I ran the same process with one glider coming from a third direction and also for all four gliders coming from different directions. If desired I can probably dig out the original code.

Alternatively, I set up a very similar generator for 4G collisions in an attempt to extend Goldtiger997's synthsise-constellation.py to 4G collisions. The code is available in LifAPI.h form and also ported to python-lifelib. These trials only covered subsets of one-sided and three-direction 4G collisions. The later also includes a version which converts the collisions to Shinjuku's gset/comp format. [ NOTE: I realise I haven't correctly acknowledged the original Shinjuku project and license. I will rectify this shortly. ]. The results of this brief survey and conversion to comp format are available here. There was some discussion about this project in the ConwayLife Discord server, and some further discussion privately with Goldtiger997. In short - I got stuck on coming up with a way to deal with the myriad of duplicate collisions that arise when a short lived 2G collision stabilises before interaction with the other two gliders at some later time. IOW, I needed to do something like Bob Shemyakin suggested below, but just didn't get my head around implementing the algorithm.

Bob Shemyakin's suggestion a couple of years ago was

For 4G synthesis more effectively attack 2G set by two gliders from all possible directions. Because 2G set limited (71) and many of them short-lived, this should dramatically reduce the amount of computation (at least one of the gliders must reacts with 2G).

That was in response to simeks' random 4G collision search -- 10 CPU-days of picking random gliders. It does seem likely that a good number of additional 4G recipes are still out there waiting to be discovered, but it might be just the luck of the draw if the remaining 9-bitters are among them.
<snip>

I am in total agreement with this last sentence. And just to show that a bit of luck is not outside the realm of possibility, the original stdin_WM_4G search turned up a new 4G synthesis for a 16-bit SL. (All the same, I'm not holding my breath!)