Enumerating Three-Glider Collisions

[confocaloid]

[...] Once that's done, the only remaining data cleanup for three-glider collisions will be to figure out which 3G collisions are missing. [...]

Since there are infinitely many 3G collisions, it may be more sensible to provide an iterator over an infinite sequence. Desirable properties of the sequence would include lack of duplicates, and having the generated collisions roughly ordered by increasing size (in every metric that is considered useful) so that for every useful upper bound on the size of a 3G collision one can give an upper bound on the number of terms of the sequence before every "small enough" collision appears. Then it would be up to the application to decide how many terms of the sequence it needs and when to stop iterating.

[...] I'm currently running a rewritten script, which should perform additional checks, and output an exact copy of (one of duplicates of) the pattern taken from the input file. [...]

I did run the rewritten script (more details in the edited post), and got the count 453040 twice and the count 453038 once. As far as I can tell, the two missing results from the run over "3gdata.txt" must be due to the 23 patterns with touching gliders (shown in the same post).

[...]
The easiest way to immediately detect a hash collision is to run an additional quick test: whenever a match is found, the next hash recorded for the matching pattern should be the same as the hash of the search pattern evolved by one tick. The confidence level goes up way past the "not worth worrying about" point if there's a match on even one additional generation -- and that data will be readily available for all but the less-than-.1% of the hashes at the end of each recorded series.

Especially if the database is actually meant to be extensible in future with more kinds of enumerations of predecessors (other sets of stationary constellations, collisions involving other spaceships, etc.) having the additional checks against hash clashes in place will become necessary, so it would be helpful to design the system from the start so that the additional checks would be performed in a way that does not make things too slow/costly.

I would not be too surprised if simply merging the existing octo... databases with a single replacement 64-bit hash function happened to produce a hash clash. I would expect a clash once there are xWSSes with up to 1024 generations of each initial pattern.

[dvgrn]

Since there are infinitely many 3G collisions, it may be more sensible to provide an iterator over an infinite sequence. Desirable properties of the sequence would include lack of duplicates, and having the generated collisions roughly ordered by increasing size (in every metric that is considered useful) so that for every useful upper bound on the size of a 3G collision one can give an upper bound on the number of terms of the sequence before every "small enough" collision appears. Then it would be up to the application to decide how many terms of the sequence it needs and when to stop iterating.

Anyone is certainly welcome to design and implement something along those lines. Seems like it's definitely a good idea to do an enumeration like that, up to the 500,000th collision (or so), just to make sure that the 3G collision database is complete -- up to some specific value, for whatever metric is being used to limit the enumeration.

I'm not clear what "the application" would be, though. The point of the Online Octohash database is that a whole lot of "fingerprinting" hash calculations can be done in advance, and the results can be indexed such that matches can be returned near-instantly even for a much larger dataset than the current experimental octohash/octo3obj/octo3g ones.

That idea of large volumes of pre-calculated hashes doesn't mix well with an application that iterates through an unbounded set of 3G collisions.

Beyond the 500,000th collision (or so) we get really quickly diminishing returns on the effort of enumerating further collisions and hashing every generation. How often is someone really actually in practice going to want to be able to look up, say, the 999th generation of collisions like the one shown here?

So ... given limited resources and time, I'll be continuing to focus on a finite region of the search space -- the region where interesting and useful things are most likely to be found.

For 3G collisions, that region roughly matches the 453040 collisions in the current list. However, because we don't know exactly what parameters 2718281828 used to generate the original set of collisions, we don't really know how many "potentially useful" 3G collisions might be missing from the list. It just seems like there probably are some missing entries (as the above link mentions).

Especially if the database is actually meant to be extensible in future with more kinds of enumerations of predecessors (other sets of stationary constellations, collisions involving other spaceships, etc.) having the additional checks against hash clashes in place will become necessary, so it would be helpful to design the system from the start so that the additional checks would be performed in a way that does not make things too slow/costly.

Sure. I've already done that design work to my own satisfaction. What would you say is wrong with the design I've outlined?

I would not be too surprised if simply merging the existing octo... databases with a single replacement 64-bit hash function happened to produce a hash clash. I would expect a clash once there are xWSSes with up to 1024 generations of each initial pattern.

That seems about right.

On the other hand, a single hash clash, or even a few dozen of them, really doesn't do anything to damage the usefulness of the project. It just means that out of the billions of patterns represented by the hashes in the database, you'll get a few false positives along with your good results in just those few cases.

The valid results will still show up just fine, and the invalid results can be disqualified with a very simple test (e.g., evolving the search pattern by one tick, taking a second hash, and checking that it's the same as the hash of the successor of each matched pattern.)

[confocaloid]

[...] Once that's done, the only remaining data cleanup for three-glider collisions will be to figure out which 3G collisions are missing. [...]

Since there are infinitely many 3G collisions, it may be more sensible to provide an iterator over an infinite sequence. [...]
[...] it would be up to the application to decide how many terms of the sequence it needs and when to stop iterating.

Anyone is certainly welcome to design and implement something along those lines. [...]
I'm not clear what "the application" would be, though. [...]

Those are two different, overlapping problems, and neither of those problems would be fully covered by a solution to the other one.
Creating a database of "useful" collisions would not by itself solve classification of all three-glider collisions, and vice versa.

I think your earlier point about "the only remaining data cleanup for three-glider collisions..." belongs more to the problem of classification of all three-glider collisions, and less to the problem of designing and implementing a database of "useful" (for some definition of useful) collisions.

Assuming extensibility, at any point in future it should be possible to add any "new" "unexpectedly useful" collisions noted later, and the system should continue to work more or less as if those collisions were present in the database from the beginning. (Except probably for showing metadata about when such-and-such collision was added to the database, if discovery information/metadata is part of the project.)
That means that, if your goal is a database, then it is unnecessary to attempt to "figure out which three-glider collisions are missing" right now. The system should be designed to allow adding missing collisions later.

On the other hand, when the goal is classification, one would have to classify all three-glider collisions, regardless of their (perceived or actual) "usefulness", and there are infinitely many.

[...] I'm not clear what "the application" would be, though. [...]

"The application" is any application (e.g. a script) written by someone else, using the iterator as a library, and looking through three-glider collisions to solve some task which is not covered by any available database or software tool, and not predictable in advance. It is impossible to predict all kinds of things people will want to do with three-glider collisions.

[vilc]

I could not find a version of the latest database in sjk format, so I made one from dvgrn's "3G-collisions-tested-and-rewound-16-ticks.txt". There were no duplicates, and the resulting file is less than 10MB uncompressed.

[2718281828]

I tackled again the 3G enumeration, now I am confident that I tackled it well. The Question "How many 3G collisions do we have in Life?". As discussed years ago, it depends on the definition of "collision" and how you count. Furthermore, as there are a couple of 2G collisions which reveal escaping objects (Gs) there are infinitely many collisions, where the 3rd glider hits an escaping object (e.g. single G, or a flotilla of the 2 glider mess). However, we can parameterize them using integers - I prefer to define infinite family classes. Take this example:

From the representative member, we can deduce everything. In this example:

Code: Select all

x = 93, y = 68, rule = B3/S23
o29bo29bo$b2o28b2o28b2o$2o28b2o28b2o19$27bo31bo31bo$22bo2b2o27bo2b2o
27bo2b2o$23b2ob2o27b2ob2o27b2ob2o$22b2o30b2o30b2o20$obo25bobo28bobo$b
2o26b2o29b2o$bo27bo30bo18$27bo31bo32bo$22bo2b2o27bo2b2o28bo2b2o$23b2ob
2o27b2ob2o28b2ob2o$22b2o30b2o31b2o!

The first collision hits before the time to stability - thus it counts as unique collision. The middle pattern is the representative member of the infinite family, parametrized by an integer, say n. The representative pattern gives the final outcome at n=0. The next member for n=1 is here given at the right hand side. If stored correctly, we can compute all final outcomes knowing the representative member and n. This, particularly holds for the two (potential) ashes. The one from the original pattern, and the one from the infinite family. This also holds for potential kickbacks.
Note that it may also happen that an infinite class may be initialized (get a representative member) also after time to stability of the initial pattern. This is always the case if the collision of the 3rd G and the escaping object is reacting with the ash of the first pattern. A simple example is here:

Code: Select all

x = 138, y = 18, rule = B3/S23
obo102bobo$b2o103b2o$bo104bo12$30bo106bo$25bo2b2o102bo2b2o$26b2ob2o
102b2ob2o$25b2o105b2o!

The left pattern interacts so it is a unique representative. The right hand side pattern is not, so it is member of an infinite family (here in fact a representative member).

Without going to much into detail in the considered definition at the moment. Also the two 2G collisions that result a glider span infinite collision classes, whereas this is not the case if the 2G ash does not include an escaping object. Further, all collisions which appear till the time to stability are not a member of the infinite families.

I attached the results of my current script. All in all there are 563076 finite members in my new collision script. Further there are 3124 representative members of the infinite families.
So I would say we have 563076+3124=566200 3G collisions.

So far I did not spot any interesting new collision. (no new infinite growth, no new high-period oscillator, etc.)
However (I do not have my old script anymore - but if I remember the idea of the implementation correctly, it might be that it missed collisions like this one:

Code: Select all

x = 77, y = 7, rule = B3/S23
2bo5bobo31bobo23bo5bobo$obo5b2o32b2o22bobo5b2o$b2o6bo33bo23b2o6bo2$5bo
33bo$6bo33bo$4b3o31b3o!

where the basic 2G collision is catching up a front running glider.

Details follow in some time I am double checking the code before I want to publish it etc. However, the definition is suitable also for enumerating of the 4G's. Then the infinite family members can get up to two parameters. It can also works for the 3G infinite growth switch engine pattern. Still, this definition leads also to a lot of not interesting (almost redundant collisions) like those ones:

Code: Select all

x = 144, y = 50, rule = B3/S23
5$139bo$138bo$138b3o29$58bo$15bo41bo$14bo42b3o$14b3o3$70bobobo$3bo4bo
36bo4bo44bo4bo$4b2obo38b2obo46b2obo$3b2o2b3o35b2o2b3o43b2o2b3o!