From the "Implications of a Three-Glider Switch Engine" thread:
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.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!
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.
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...!)
Code: Select all
x = 547, y = 120, rule = B3/S23 354bo$355b2o$177bo176b2o$178b2o$o176b2o$b2o$2o66$540bo2bo2bo36$129bo 176bo176bo$128bo176bo176bo$128b3o174b3o174b3o7$126bo176bo176bo$125b2o 175b2o175b2o$125bobo174bobo174bobo!
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.
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:
Code: Select all
x = 306, y = 46, rule = B3/S23 102bobo$103b2o$103bo$201bobo$2bo199b2o$obo199bo$b2o16$303bo$301bobo$ 302b2o19$3bo99bo99bo99bo$2b3o97b3o97b3o97b3o$b2o2bo95b2o2bo95b2o2bo95b 2o2bo!
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.