ConwayLife.com

It's probably time to avoid hijacking Bob Shemyakin's 4-glider synthesis thread any longer. The question that came up there was the extent to which glider syntheses can be tested automatically, and also converted automatically from one form to another -- a continuous synthesis to an incremental synthesis, or vice versa.

A script written by chris_c is a really good start at solving the incremental-to-continuous conversion problem. The main improvement might be to make it fully automatic.

Currently it's necessary to carefully select the area to be analyzed, including some empty space to the left so that the divisions between stages end up in the right place. The pattern's construction stages all have to be separated by exactly the same distance in a single horizontal line, which is not true for most existing multi-stage synthesis patterns (Bob Shemyakin's and Mark Niemiec's especially). The distance is currently entered by the user, not auto-detected.

Continuing the discussion from here:

mniemiec wrote:

dvgrn wrote:In the case where side effects from one interaction remove debris from another, those gliders are really all part of one stage, and shouldn't be partitioned anyway. (?)

This is often true, but not always. For example, if the debris is a still-life, any additional delay of stage 2 usually works. Sometimes there is a trade-off between having a small number of gliders all arriving at once, and possibly cleaning up each other's debris, or having more gliders arriving in separate waves. The cheapness of the first may be outdone by the expense of getting that many closely-packed gliders into formation in the first place.

This seems like a part of the problem that I might not have thought about enough yet. If you have more examples besides the above, they might be very useful.

Considering just the partitioning algorithm for the continuous-to-incremental conversion, if gliders are arriving all at once and cleaning up each other's debris, they're going to get assigned to a single stage. Unpacking something like that into multiple stages seems more like a job for a human decision-maker, especially if extra gliders need to be added.

Closely-packed gliders are only a problem if some of them have to be dropped into place with a kickback or other reaction, to avoid a collision. If they're all coming from the same direction, it doesn't matter how closely packed they are (the gun-building problem has been solved elsewhere). Kickbacks often have a degree of freedom that this partitioning algorithm won't see -- but I think that's really more of a problem for the conversion in the other direction, anyway.

In general, any gliders involved in a kickback will have to end up as part of the same stage... and this might well increase the maximum epsilon by dozens more ticks, or even hundreds. A similar case is the sets of three or four gliders that sneak through gaps in adjacent salvos to build a spaceship.

mniemiec wrote:The simple method works in most cases, and for most steps in the difficult cases. Once a synthesis has been separated to small independent chunks, it should be much easier to use brute force binary searching to attempt to sub-divide those chunks. For example, even with a chunk containing 20 gliders, that's only half a million ways to partition them into to candidate stages.

Hmm. It looks to me as if combinations of spaceship-building gliders can't be found reliably by a brute-force search, because they'll be present in a stage of the partitioning process where there might still be many more than 20 gliders. They sometimes collide many dozens of ticks before the rest of the gliders in their stage. So it won't be hard to find that those gliders belong together, but it will be hard to associate them with whatever gliders the spaceship ends up doing the actual construction work with.

I think there's a way to solve this, by grouping gliders whose first interaction is on the same tick, but only when it turns out that their first interaction is with each other... then tracking the cells that result from each such colliding group, and adding to the same group any other gliders whose first collision is with one of those cells. None of that is too computationally intensive. Gliders will quickly aggregate into groups until there are no more unknown gliders left.

-- The above grouping method still has the problem that some cleanup gliders have to be synchronized, because junk has to be cleaned up quickly to get it out of the way, whereas some can be split off into a separate stage. But that can probably be checked in a separate step, after the first groupings are done.

Time to write a new Golly rule to help with the tracking process, I think.

dvgrn wrote:Considering just the partitioning algorithm for the continuous-to-incremental conversion, if gliders are arriving all at once and cleaning up each other's debris, they're going to get assigned to a single stage. Unpacking something like that into multiple stages seems more like a job for a human decision-maker, especially if extra gliders need to be added.

The practicality of this depends on whether you are looking for a 100% automatic solution, or if a 99% automatic solution is good enough. I found the 99% solution worked well for still-life syntheses, allowing for human resources to be prioritized on only the most difficult problems.

dvgrn wrote:Kickbacks often have a degree of freedom that this partitioning algorithm won't see -- but I think that's really more of a problem for the conversion in the other direction, anyway.
In general, any gliders involved in a kickback will have to end up as part of the same stage... and this might well increase the maximum epsilon by dozens more ticks, or even hundreds. A similar case is the sets of three or four gliders that sneak through gaps in adjacent salvos to build a spaceship.

Perhaps the conversion algorithm can be set up to recognize kickbacks, and allow trombone-lenghthening as appropriate. (Something similar happens when *WSS are synthesized on the fly, but that seems to happen much less frequently. I can only think of only one simple converter where that is essential, and it offers little to no freedom with regards to timing.)

dvgrn wrote:Hmm. It looks to me as if combinations of spaceship-building gliders can't be found reliably by a brute-force search, because they'll be present in a stage of the partitioning process where there might still be many more than 20 gliders. They sometimes collide many dozens of ticks before the rest of the gliders in their stage. So it won't be hard to find that those gliders belong together, but it will be hard to associate them with whatever gliders the spaceship ends up doing the actual construction work with.

This could be done algorithmically by backtracking the origin of the spaceship, but it would then tie in the spaceship creation to the gliders it later interacts with, despite the fact that some flexibility might be allowed (as with kickbacks, above).

A related problem is with objects that can be created more than one way (e.g. long boats), or from more than one direction (e.g. blocks, beehives, and ponds). Using a different synthesis or direction could improve speed and/or spacing (or possibly even cost), but such decisions are always done by hand, unless the disassembly algorithm is clever enough to make decisions like "these two gliders make a block. I know what a blocok is. What other ways do I know to make a block?"

dvgrn wrote:I think there's a way to solve this, by grouping gliders whose first interaction is on the same tick, but only when it turns out that their first interaction is with each other... then tracking the cells that result from each such colliding group, and adding to the same group any other gliders whose first collision is with one of those cells. None of that is too computationally intensive. Gliders will quickly aggregate into groups until there are no more unknown gliders left.

One possible way to improve this is to also consider gliders that interact with an object, and track the changes made to the object. For example, any living or dead cells in an object that are struck with green gliders (or anything resulting from a green glider) in a way that alters its normal state are colored green. Similar for red or other colors. If any living or dead cell in the object acquires more than one color, those two colors must be considered one group; otherwise, they can be safely separated. (This might not be true if the period or velocity of the object changes as a result, as in the final step of activating an oscillator or spaceship, but this is easy enough to check - before separating the two groups, see if the result remains the same if one group is applied first, and if not, try swapping them.)

mniemiec wrote:One possible way to improve this is to also consider gliders that interact with an object, and track the changes made to the object. For example, any living or dead cells in an object that are struck with green gliders (or anything resulting from a green glider) in a way that alters its normal state are colored green. Similar for red or other colors. If any living or dead cell in the object acquires more than one color, those two colors must be considered one group; otherwise, they can be safely separated.

I've done some experimental rule-building today along these general lines, and I think that that might be pretty close to the simplest algorithm that works reliably. I tried coloring two gliders at a time, to figure out whether they belonged in the same stage or not. Was hoping to get away without having to color the OFF cells different colors as well, but it was easy to find situations where my trial algorithm didn't work.

Your rule nicely handles the common case where two gliders hit each other before the resulting spark hits anything else. As soon as two gliders come into contact, either to cause a cell birth or to inductively suppress one, that cell would immediately be assigned two colors... and therefore those two gliders belong in the same stage and can be assigned one color.

Once all the directly interacting gliders are grouped together, though, I don't quite see how to resolve the next problem. If a target object gets incrementally adjusted several times (which happens a lot these days!) then a single cell might easily be changed twice or more, by two different stages of a long recipe -- turned ON in one stage, then OFF again in the next along with other changes. The two stages can be safely separated, but the algorithm as stated will recommend combining them into one stage.

It almost seems as if the colors should be allowed to fade over time. Maybe only a glider's new-birth cells and new induction cells should be colored, and only for one tick. Let's say anything that goes stable loses its color. If an ON or OFF cell has to acquire two different colors on the same tick, does that allow a more accurate partition?

In a quick-fade color system, I think a two-colored cell is a sufficient condition to prove that those two colors need to be merged, but it might not be a necessary condition -- and a more complicated rule might be needed to complete the partition.

Time to go hunt for some more good counterexamples...

mniemiec wrote:This might not be true if the period or velocity of the object changes as a result, as in the final step of activating an oscillator or spaceship, but this is easy enough to check - before separating the two groups, see if the result remains the same if one group is applied first, and if not, try swapping them.)

Ow, that's tricky. If an object is starting to move, then with my proposed quick-fade rule, the color is bound to spread through the object somehow: change in Cell 1 causes change in Cell 2 causes change in Cell 3, and so on. Eventually all cells in a moving object will be touched by one color, at least periodically, because otherwise the object isn't moving. Same with all cells of the rotor of an oscillator.

-- Drat. if the color never fades, then if an oscillator is constructed as an intermediate target, all the following stages will get combined into the oscillator-making stage.

Will have to short-circuit that somehow, maybe by checking if the intermediate target is stable mod 30, and killing the cycling colors if so. But it will be good to remember the period, because the algorithm is correctly indicating that the next stage (at least) has picked up a new mod-N dependency that wasn't there before.

I think that a two-color moving object will turn out to be impossible, if new suppressed-birth cells are colored as well as new birth cells. Not sure how easy it will be to prove that yet.

dvgrn wrote:Once all the directly interacting gliders are grouped together, though, I don't quite see how to resolve the next problem. If a target object gets incrementally adjusted several times (which happens a lot these days!) then a single cell might easily be changed twice or more, by two different stages of a long recipe -- turned ON in one stage, then OFF again in the next along with other changes. The two stages can be safely separated, but the algorithm as stated will recommend combining them into one stage.

That wasn't what I was talking about. I was assuming that the "simple algorithm" (i.e. attempting to separate stages that were obviously separate) was applied first, yielding only smaller chunks that were not obviously decomposable. In such cases, successive converters would already be separated (e.g. block to boat to long boat to pond). I was thinking more about multiple converters being applied simultaneously and independently to different parts of an object. Those could be separated this way.

dvgrn wrote:It almost seems as if the colors should be allowed to fade over time. Maybe only a glider's new-birth cells and new induction cells should be colored, and only for one tick. Let's say anything that goes stable loses its color. If an ON or OFF cell has to acquire two different colors on the same tick, does that allow a more accurate partition?

I was thinking more of considering a converter as an infection that alters anything it touches. If a cell has a different outcome when the converter is applied than when it isn't, it could potentially similarly affect/infect any other adjacent cells whose state it influences. (Setting up a Golly rule to do this is probably doable, but also probably fairly complicated).

For example, consider the following four states: alive white, dead white, alive green, and dead green (where white is part of the object, and green denotes something that is different from the default whenever green gliders are involved). Each generation, a cell's live/dead state is the same as according to normal Life rules, while its color is determined as follows: if the live/dead state would have been different if the green cells were inverted, it is green; otherwise, it is white.

This could be expanded to multiple non-white colors. If any cell would otherwise acquire more than one non-white color simultaneously, color it permanently black (i.e. this separation is not viable).

dvgrn wrote:In a quick-fade color system, I think a two-colored cell is a sufficient condition to prove that those two colors need to be merged, but it might not be a necessary condition -- and a more complicated rule might be needed to complete the partition.

The above method will implicitly implement quick-fade colors, as cells that eventually settle down to what they would have been without the conversion gliders will lose their color (e.g. shadows behind gliders).

mniemiec wrote:The above method will implicitly implement quick-fade colors, as cells that eventually settle down to what they would have been without the conversion gliders will lose their color (e.g. shadows behind gliders).

I guess that might work, as long as the previous rough partitioning step really does take care of all the obvious subdivisions. Otherwise pieces of the target object will get stuck at Stage N's color (because those cells have changed), and as soon as the first glider that's really part of Stage N+1 comes along, it will have to be classified as that same color.

I've made a few amusing rules in the last day or two, like one where the LifeHistory marked-ON state 3 moves instead of staying in place, and state 3 is the only state that leaves a state-2 trail; state-1 gliders just cross the trail like ghosts.

Below is the beginning of a Golly rule for doing a synchronization test, with two extra colors representing two stages that are supposed to be separate. If a yellow cell helps cause a birth or inducts a state-0 cell at the same time as a white cell, then a black hole is spawned that quickly eats up the whole pattern.

That means you can just run a test pattern 2^12 ticks or whatever, then check the state of the (0,0) cell. If it's not state 6, then yellow gliders are safely independent of white gliders -- theoretically. It's definitely not true yet in practice.

There's no proper implementation of the changed-state OFF cells yet, and even ON cells don't behave quite right (e.g., the white gliders in the attached sample should be turning on a cell in the target.) As it stands, a white glider could come in and knock out an obstruction, and a yellow glider could come by and interact with the far edge of the obstruction's dying spark, and this rule wouldn't flag the two properly as having to be in the same stage.

And then of course the yellow cells in the sample last longer than they should, then randomly get eliminated. It will probably turn out to be easier to implement this partitioning algorithm without bothering with a custom Golly rule. But it's an interesting problem to think about, anyway.