ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Enumerating Three-Glider Collisions

For scripts to aid with computation or simulation in cellular automata.

Enumerating Three-Glider Collisions

Postby dvgrn » April 23rd, 2017, 8:40 pm

From the "Implications of a Three-Glider Switch Engine" thread:
dvgrn wrote:Someone should start a new thread for best-practices methods of filtering as-near-as-possible all distinct 3-glider collisions that produce small constellations. I used chris_c's suggestions from gencols: techniques -- thanks, chris_c!

AbhpzTa's discovery of a three-glider SE recipe is something of a wake-up call here. That recipe could have been found any time in the last forty years by enumerating all possible collisions of a glider with a 2-glider [traffic light|block|nothing] recipe.

Given that surprising fact, how likely is it that this new switch-engine recipe is the last unknown three-glider constructible object? How do we know there isn't a clean three-glider recipe for a snake out there somewhere, for example? Or pick your favorite object that we think needs more than three gliders to construct.

Switch engines were a weird case
New super-cheap still life recipes are not terribly likely, of course. The search space has been combed over fairly thoroughly by now, by several people... it's just that no one doing three-glider searches was specifically looking for switch engines, so presumably they got thrown out with all the other big messy explosions.

-- Well, simsim314 found a three-glider collision that produces a switch engine, a few years back, but that search wouldn't have found AbhpzTa's recipe either because clean switch engines self-destruct before too many cycles.

Constellations
There's also the problem of generating arbitrary small constellations as cheaply as possible, with fair confidence that the cheapest recipe has been found. An incredible number of two- and three-object constellations can be constructed with just three gliders, it's a huge search space. But so far, unless someone has a pre-built gencols collisions file that they haven't mentioned, pretty much every such problem has been solved by a separate search.

An Exact Count
The problem of enumerating all distinct three-glider collisions seems just about within reach these days. One thing we might be able to come up with is a precise total number of distinct output patterns excluding gliders, produced by configurations of three gliders in which all three participate in a collision.

If we don't exclude gliders the number of distinct outputs is unlimited, thanks to useless kickbacks on the 2-glider mess, TL+glider, and the three B-heptomino recipes. For example, the following infinite series will have distinct hashes (until the hash-generating algorithm fails and there's a collision, but that's a mighty long way out...!)

x = 547, y = 120, rule = B3/S23
354bo$355b2o$177bo176b2o$178b2o$o176b2o$b2o$2o66$540bo2bo2bo36$129bo
176bo176bo$128bo176bo176bo$128b3o174b3o174b3o7$126bo176bo176bo$125b2o
175b2o175b2o$125bobo174bobo174bobo!

The hard part is that kickbacks do have to be allowed sometimes, when the kicked-back glider strikes an active or just-settled pattern. Once the kicked-back glider is striking the exact same settled pattern as another pattern's kicked-back glider, I think it shouldn't count as distinct. Seems like it will be pretty hard to get that count exactly right, but that's only a problem with five of the 71 collisions -- could leave those for last.

Thinking about moving the search tree up to four gliders, though, the problem is even worse. Kickback reactions that didn't count as distinct when the search stopped at three gliders, would suddenly count (by producing a different output pattern) when a fourth glider is added.

Collisions and Outputs
The full list of outputs, mostly copied from the 2-glider-collisions stamp collection, is

nothing, blinker, block, glider, boat, beehive, loaf, eater, pond, bi-block, loaf+blinker, loaf+blinker+tub+block (misc), half-blockade (misc), four skewed blocks (misc), traffic light, honeyfarm, B-heptomino, pi, lumps of muck, teardrop, interchange, traffic light+glider, octomino, 2-glider mess.

The great majority of the 71 collisions stabilize within a few dozen ticks. Only one of the "nothing" syntheses takes anywhere close to 100 ticks, for example. Even that is easily within reach of exhaustive enumeration of all possible third gliders.

Enumeration
I'd like to have an enumeration method with at least a little common sense built in -- something along the lines of gencols, tracking the 2-glider collision tick by tick and placing gliders in every possible position where they would interact with the collision for the first time at tick #T.

Really it might be simpler to use plain brute force -- place every glider in every orientation that could possibly touch the collision reaction. Run each one, and then throw away cases where the third glider is totally unaffected by the collision reaction (and vice versa).

Tangent on Heisenburps
If we're trying to get a count of all distinct 3-glider collisions, it's not sufficient to run the pattern and throw out cases where the added third glider is undamaged. There will be the occasional Heisenburp, like these four that showed up in 2003 from investigating just one orientation of B-heptomino:

x = 306, y = 46, rule = B3/S23
102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$
302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b
2o2bo!

-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?

Handling Different Kinds of Nothing
Along the same lines as those no-effect Heisenburps, it will be good to have a count not just of all the distinct patterns that can result from three-glider collisions, but also all the collisions themselves, even though many of them produce the same final results. A next step might be to use the resulting collision list to try out every possible edgy 3G spark pattern against various still lifes, and see how many new converters turn up.

If we're really trying to get a count of all the distinct three-glider collision reactions, as opposed to distinct outputs, a subtler problem would be Heisenburps that have only a temporary effect -- changing the shape of a dying spark that does something new but then dies out anyway. Theoretically this could matter if we extended the search tree and hit the changed spark with a fourth glider... but in practice, nobody's going to be trying to count four-glider collisions any time soon. And relatively few useful constructions would come out of reactions like this, because there's an extra output glider that has to be disposed of.

Lists of Hashes
It seems like a good place to start would be to make an official list of the 71 2-glider collisions, each at the position where the gliders will interact for the first time on the next tick. Maybe order them by time to stability. For each collision except for the glider-producing ones, it's not too hard for a search program to find all distinct locations/orientations of a third glider that will interact in some way with that collision. If the search is done with a couple of different independent methods and the count agrees, that will be a good sign.

Each initial pattern of three gliders can be assigned an (extended) apgcode, and a hash can be recorded of the initial canonical orientation and also of its eventual stabilized output pattern, minus any gliders. At least one infinite-growth pattern will show up, so I guess that and any other unknown ones can best be handled as special cases.

To determine a final count of three-glider collisions we'll just have to compare the 71 lists of initial hashes and remove any duplicates. The only potential duplicates will be between cases where the third glider interacts immediately, at the same tick as the first two.
dvgrn
Moderator
 
Posts: 3431
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Enumerating Three-Glider Collisions

Postby Extrementhusiast » April 23rd, 2017, 11:02 pm

dvgrn wrote:Really it might be simpler to use plain brute force -- place every glider in every orientation that could possibly touch the collision reaction. Run each one, and then throw away cases where the third glider is totally unaffected by the collision reaction (and vice versa).

I've already been doing this for a few of them as part of my work on syntheses, as it's useful for slightly modifying edgy subpatterns that appear within two-glider collisions.

dvgrn wrote:-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?

I've already done something similar: a rule that tracks if two differently-colored patterns interact:
@RULE objtracklife2

@TABLE

n_states:5
neighborhood:Moore
symmetries:permute

# all states
var Aa={0,1,2,3,4}
var Ab={Aa}
var Ac={Aa}
var Ad={Aa}
var Ae={Aa}
var Af={Aa}
var Ag={Aa}
var Ah={Aa}

# live states
var La={1,2,3}
var Lb={La}
var Lc={La}
var Ld={La}
var Le={La}
var Lf={La}
var Lg={La}
var Lh={La}

# dead states
var Da={0,4}
var Db={Da}
var Dc={Da}
var Dd={Da}
var De={Da}
var Df={Da}
var Dg={Da}
var Dh={Da}


# off in both universes
# on in both universes (pre-interaction)
# on in only current universe (pre-interaction)
# on in both universes (post-interaction)
# on in only current universe (post-interaction)
# on in only alternate universe
# history in current universe; off in alternate universe
# history in current universe; on in alternate universe


0,Da,Db,Dc,Dd,De,La,La,La,La
Da,Db,Dc,Dd,De,Df,La,Lb,Lc,3

La,Da,Db,Dc,Dd,De,Df,La,La,La
La,Da,Db,Dc,Dd,De,La,La,La,La
La,Da,Db,Dc,Dd,De,Aa,Lb,Lc,3
3,Aa,Ab,Ac,Ad,Ae,Af,Ag,Ah,4
La,Aa,Ab,Ac,Ad,Ae,Af,Ag,Ah,0

0,Aa,Ab,Ac,Ad,1,1,1,2,4
0,Aa,Ab,Ac,Ad,1,2,2,2,4

@COLORS

1 255   0   0
2   0 255   0
3 255 255 255
4 102 102 102

@ICONS

circles

One then just needs to check for cells of at least state 3, which is easily done with another rule: every generation, reduce all non-empty cellstates by one (a bit like //256 in reverse).

(However, I'm planning on making objtracklife3, featuring a three-layered simulation of A, B, and A+B, as soon as I can figure out the details within the damn transitions!)
I Like My Heisenburps! (and others)
User avatar
Extrementhusiast
 
Posts: 1611
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Enumerating Three-Glider Collisions

Postby Scorbie » April 23rd, 2017, 11:49 pm

Extrementhusiast wrote:
dvgrn wrote:-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?

I've already done something similar: a rule that tracks if two different patterns interact...
Why not just run the pattern until stabilization (or the until the generation of stabilization of the two-glider collision) And see if the end product is merely the sum of the two patterns, the two-glider collision stabilization and the third glider?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1296
Joined: December 7th, 2013, 1:05 am

Re: Enumerating Three-Glider Collisions

Postby dvgrn » April 24th, 2017, 8:15 am

Scorbie wrote:Why not just run the pattern until stabilization (or the until the generation of stabilization of the two-glider collision) And see if the end product is merely the sum of the two patterns, the two-glider collision stabilization and the third glider?

The possibility of zero-effect Heisenburps makes that not quite good enough. We could end up with a passing glider encouraging a huge and useful spark, for example. The spark might very well die out in the end, producing an identical output as if no Heisenburp had happened.

It looks like a regular no-interaction, and is in danger of getting discarded if we only use the run-to-stabilization test. But that case needs to be counted as a real three-glider collision, and it's not just a technicality -- the spark might turn out to be uniquely useful in some synthesis or other, for all we know.

In practice that's not going to happen much, since Heisenburps by definition always have an extra output glider that will probably need to be disposed of, so there's a built-in inefficiency. Really the main reason for noticing these is that if you don't, the statistics on the total number of 3-glider collisions will be wrong (horrors!)
dvgrn
Moderator
 
Posts: 3431
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Enumerating Three-Glider Collisions

Postby Scorbie » April 24th, 2017, 12:44 pm

dvgrn wrote:It looks like a regular no-interaction, and is in danger of getting discarded if we only use the run-to-stabilization test. But that case needs to be counted as a real three-glider collision, and it's not just a technicality -- the spark might turn out to be uniquely useful in some synthesis or other, for all we know.

In practice that's not going to happen much, since Heisenburps by definition always have an extra output glider that will probably need to be disposed of, so there's a built-in inefficiency. Really the main reason for noticing these is that if you don't, the statistics on the total number of 3-glider collisions will be wrong (horrors!)
Ah, I see, thanks :) Having a similar idea for ptbsearch, I decided (in my vaporware blueprint) to discard those cases...
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1296
Joined: December 7th, 2013, 1:05 am

Re: Enumerating Three-Glider Collisions

Postby dvgrn » April 24th, 2017, 1:58 pm

dvgrn wrote:It seems like a good place to start would be to make an official list of the 71 2-glider collisions, each at the position where the gliders will interact for the first time on the next tick.

On second thought, it seems like a better idea to start N ticks back from the first interaction. When we drop in glider #3, we have to have some way to verify that the new glider would not have interacted with either of the existing gliders before they collide with each other.

(If this happens, we'll get unnecessary duplication -- the collision usually becomes a different collision entirely, of a type that will be enumerated elsewhere.)

The only duplication that needs to be checked for will be in the fairly limited number of cases where the three gliders all start interacting on the same tick. If any two gliders A and B start interacting first, then that collision is the primary collision, and the 3-glider recipe can be enumerated unambiguously as "glider collision #{0..70} plus {NE|SE|SW|NW} glider on lane L, delay of T ticks".

It seems like an interesting subproblem to generate all of these simultaneous-collision cases, and remove the duplicates -- probably using a dictionary of apgcodes, to automatically choose a canonical orientation.

Once the duplicates are removed, a delayed glider can be added in every possible way to each of the 71 collisions. That will be 71 separate searches, with no possibility of duplication with any other search. Or am I missing something important here?

... It should be fairly easy to produce four graphs for each of the 71 collisions, showing the possible {NE|SE|SW|NW} lanes in one dimension, and the allowable values of T (delay times) on each lane that produce actual collisions -- instead of trivial flyby behavior, or duplication due to collision with an already-settled part of the pattern. Maybe separate colors for small constellations and for the occasional Heisenburp reactions.
dvgrn
Moderator
 
Posts: 3431
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Enumerating Three-Glider Collisions

Postby _zM » April 25th, 2017, 2:27 pm

dvgrn wrote:Tangent on Heisenburps
If we're trying to get a count of all distinct 3-glider collisions, it's not sufficient to run the pattern and throw out cases where the added third glider is undamaged. There will be the occasional Heisenburp, like these four that showed up in 2003 from investigating just one orientation of B-heptomino:

x = 306, y = 46, rule = B3/S23
102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$
302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b
2o2bo!

-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?



So I tried making that rule you mentioned, and it kind of works:
@RULE heisenbork

@TABLE
n_states:3
neighborhood:Moore
symmetries:rotate4reflect

var a = {0,1,2}
var b = a
var c = a
var d = a
var e = a
var f = a
var g = a
var h = a
var i = a

var j = {1,2}
var k = j
var l = j
var m = j

0,1,1,1,0,0,0,0,0,1 #B3a
0,0,1,1,1,0,0,0,0,1 #B3i
0,1,1,0,1,0,0,0,0,1 #B3n
0,1,0,1,1,0,0,0,0,1 #B3j

1,1,1,0,0,0,0,0,0,1 #S2a
1,1,0,1,0,0,0,0,0,1 #S2e
1,1,0,1,1,0,0,0,0,1 #S3j
1,1,1,0,1,0,0,0,0,1 #S3n
1,1,1,0,0,1,0,0,0,1 #S3r

j,k,l,0,0,0,0,0,0,2 #S2a
j,k,0,l,0,0,0,0,0,2 #S2e
j,k,0,0,l,0,0,0,0,2 #S2k
j,k,0,0,0,l,0,0,0,2 #S2i
j,0,k,0,0,0,l,0,0,2 #S2n
j,0,k,0,l,0,0,0,0,2 #S2c

a,j,0,k,l,0,0,0,0,2 #3j
a,j,k,0,l,0,0,0,0,2 #3n
a,j,k,0,0,l,0,0,0,2 #3r
a,0,j,0,k,0,l,0,0,2 #3c
a,j,0,k,0,l,0,0,0,2 #3e
a,j,0,k,0,0,l,0,0,2 #3k
a,j,k,l,0,0,0,0,0,2 #3a
a,0,j,k,l,0,0,0,0,2 #3i
a,0,j,k,0,0,l,0,0,2 #3q
a,j,0,0,k,0,l,0,0,2 #3y

a,b,c,d,e,f,g,h,i,0


Of the four heisenburps shown above, this rule detects two (by turning the glider from state 1 to state 2). I don't know if this is any useful, but...
wHO CARES.
User avatar
_zM
 
Posts: 120
Joined: June 26th, 2016, 3:07 pm

Re: Enumerating Three-Glider Collisions

Postby Rhombic » April 26th, 2017, 9:26 am

_zM wrote:
dvgrn wrote:Tangent on Heisenburps
If we're trying to get a count of all distinct 3-glider collisions, it's not sufficient to run the pattern and throw out cases where the added third glider is undamaged. There will be the occasional Heisenburp, like these four that showed up in 2003 from investigating just one orientation of B-heptomino:

x = 306, y = 46, rule = B3/S23
102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$
302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b
2o2bo!

-- It would slow things down quite a bit to have to track the third glider through every tick, to see if it ever has a temporary Heisenburp effect that isn't represented in a changed final pattern, I wonder if it would make sense to build a custom multistate Golly rule that changes a glider's color if it ever participates in a Heisenburp?



So I tried making that rule you mentioned, and it kind of works:
@RULE heisenbork

@TABLE
n_states:3
neighborhood:Moore
symmetries:rotate4reflect

var a = {0,1,2}
var b = a
var c = a
var d = a
var e = a
var f = a
var g = a
var h = a
var i = a

var j = {1,2}
var k = j
var l = j
var m = j

0,1,1,1,0,0,0,0,0,1 #B3a
0,0,1,1,1,0,0,0,0,1 #B3i
0,1,1,0,1,0,0,0,0,1 #B3n
0,1,0,1,1,0,0,0,0,1 #B3j

1,1,1,0,0,0,0,0,0,1 #S2a
1,1,0,1,0,0,0,0,0,1 #S2e
1,1,0,1,1,0,0,0,0,1 #S3j
1,1,1,0,1,0,0,0,0,1 #S3n
1,1,1,0,0,1,0,0,0,1 #S3r

j,k,l,0,0,0,0,0,0,2 #S2a
j,k,0,l,0,0,0,0,0,2 #S2e
j,k,0,0,l,0,0,0,0,2 #S2k
j,k,0,0,0,l,0,0,0,2 #S2i
j,0,k,0,0,0,l,0,0,2 #S2n
j,0,k,0,l,0,0,0,0,2 #S2c

a,j,0,k,l,0,0,0,0,2 #3j
a,j,k,0,l,0,0,0,0,2 #3n
a,j,k,0,0,l,0,0,0,2 #3r
a,0,j,0,k,0,l,0,0,2 #3c
a,j,0,k,0,l,0,0,0,2 #3e
a,j,0,k,0,0,l,0,0,2 #3k
a,j,k,l,0,0,0,0,0,2 #3a
a,0,j,k,l,0,0,0,0,2 #3i
a,0,j,k,0,0,l,0,0,2 #3q
a,j,0,0,k,0,l,0,0,2 #3y

a,b,c,d,e,f,g,h,i,0


Of the four heisenburps shown above, this rule detects two (by turning the glider from state 1 to state 2). I don't know if this is any useful, but...


It should make detection of Heisenburps trivial with a very simple script. The question is whether the Heisenburps themselves are useful and the answer should be "generally yes, especially for stable ash (i.e. stable glider detectors)". However, there's that - most Heisenburps will involve a Heisenburp chaotic explosion from a constellation or, in fact, mainly Heisenburps with non-stable patterns. The latter would need specific design to be incorporated into any kind of circuitry and, on top of that, synchronising a glider - if it is, say, p120 Herschel interactions, the gliders can only transmit information at a maximum of 120 ticks per bit. How useful is this? Just now, not that useful. But Boole never imagined his concepts ending up being so amazingly important either.

The main problem is, with the current state-of-art circuitry, at most there will be four or five Heisenburps that are actually worth discovering (without having to design massive circuits to use them in a totally different way). Even then, these will most certainly be edge-shooters and still, it is highly unlikely for there to be a useful Heisenburp associated.

But the script is trivial nonetheless (check that pattern evolution is different from the same without the glider, then check glider has changed colour to avoid trivial solutions and check that it is in the same position as an unhindered evolution).
there may be bugs in gfind
User avatar
Rhombic
 
Posts: 474
Joined: June 1st, 2013, 5:41 pm

Re: Enumerating Three-Glider Collisions

Postby dvgrn » May 27th, 2017, 3:31 pm

Extrementhusiast wrote:I've already done something similar: a rule that tracks if two differently-colored patterns interact:
@RULE objtracklife2...

That seems to work fine for any possible Heisenburp -- at least, it passes the test for all four samples that I posted:

x = 307, y = 166, rule = objtracklife2
102.B.B$103.2B$103.B$201.B.B$2.B199.2B$B.B199.B$.2B16$303.B$301.B.B$
302.2B19$3.A99.A99.A99.A$2.3A97.3A97.3A97.3A$.2A2.A95.2A2.A95.2A2.A
95.2A2.A75$103.A.A$104.2A$104.A$202.A.A$3.A199.2A$.A.A199.A$2.2A16$
304.A$302.A.A$303.2A19$4.B99.B99.B99.B$3.3B97.3B97.3B97.3B$2.2B2.B95.
2B2.B95.2B2.B95.2B2.B!

Extrementhusiast wrote:One then just needs to check for cells of at least state 3, which is easily done with another rule: every generation, reduce all non-empty cellstates by one (a bit like //256 in reverse).

Here's the cleanup rule boiled down to about as simple as I can make it. If the universe isn't empty after the combined state-1 and state-2 pattern runs for LONG_ENOUGH in objtrack2, and then one tick in objtrackcleanup, then the two subpatterns interacted:

@RULE objtrackcleanup

@TABLE
n_states:5
neighborhood:oneDimensional
symmetries:none

var a = {0,1,2,3,4}
var b = a
var c = {3,4}
var d = {1,2}
c,a,b,3
d,a,b,0

Extrementhusiast wrote:(However, I'm planning on making objtracklife3, featuring a three-layered simulation of A, B, and A+B, as soon as I can figure out the details within the damn transitions!)

Wasn't that already done a few years ago? ... ah, I guess that was just two superimposed layers, not three. For three layers I'd probably have to give up and write a script to generate the rule -- sorting out all the transitions by hand would be too much of a pain.
dvgrn
Moderator
 
Posts: 3431
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI


Return to Scripts

Who is online

Users browsing this forum: No registered users and 3 guests