Just started a new thread on enumerating three-glider collisions
, as a starting point for a (maybe somewhat) more exhaustive 5G search... or at least a better prebuilt database of small constellations.
I don't think I'll have time to work on any search code for the next few months at least -- too many other things on my To-Do list right now, and I'm trying not to have it be a LIFO stack...! But I do want to pick this topic up again eventually, if no one else gets to it first.
Maybe let's move any future progress on collision enumeration to that thread, to avoid polluting this thread any further...?
chris_c wrote:-Bonus points if the program is clever enough to realise that the active reaction has settled down to an oscillator or still life so that trying arbitrarily distant gliders is futile.
-Bonus points if the program is clever enough to recognise interesting objects that appear in the soup for a limited number of ticks before being destroyed.
The first item I think happens automatically if we keep a list of hashes of each "final initial" state of the 2G collision plus glider #3, at the last generation before they interact. Once we've backed off the T=0 position of glider #3 far enough that the new pre-collision picture is already in the hash table, we can stop investigating that glider lane and move to the next one.
... Unless there's some kind of spark that curls around behind the glider but dies before the glider reaches the stabilized constellation. Bother. To be safe, maybe we have to keep backing the glider off for some number of extra ticks proportional to the size of the 2G collision's total reaction envelope...? Or we could track cells lining the incoming glider's lane and move on to the next lane only if the hash value is in the table AND those lane cells are all undisturbed.
The interesting-objects-for-a-limited-time bonus points are going to be a lot harder to get, I think. For stabilized ash we have code lying around, like recognizer.py and the various apgsearches. It's going to slow things down a lot if we have to hunt through an active reaction every tick, or even every ten ticks or hundred ticks, looking for interesting still-life islands.
We'd also want to look for much more interesting things than still lifes -- things like a temporary loafer, which there really might be one of, out there somewhere unnoticed in an already-censused Catagolue soup. It's so much easier to run through a pattern and recognize-and-remove everything as we get to it, than to have to check every cell against a huge list of interesting stuff, and end up ignoring most cells because they're still active but not recognizable yet.
chris_c wrote:EDIT:Oh there's something I forgot that occurred to me recently. The above method only catches cases where every new glider added interacts with the main part of the pattern. It would not catch reactions like below where both gliders would miss the block on their own...
Good point. A clearer example for me would be something like this:
Code: Select all
x = 11, y = 41, rule = B3/S23
This constellation can't be found by adding a fourth glider to my proposed three-glider collision database, because none of the subsets of three out of the four gliders are valid three-glider collisions. So if we ever, Heaven forbid, get to the stage of trying to enumerate all four-glider collisions, we can start with the three-glider-database-plus-one-glider approach, but then as you say we'll have to add all two-glider-collision interactions with other-two-glider-collisions.
But for just three gliders I think this isn't a problem yet. There's no way to set up three gliders such that no two of them interact, but the combination of all three does interact. (Right?) So with a decent 3G database we could kinda sorta reach up to 6G before we start missing huge classes of reactions.
-- I'm sure people have thought of all these problems before, and maybe more, and that's why the collision census hasn't been done yet for more than two gliders. It still seems as if an exhaustive 3G search is a lot closer to being possible than 4G and above, though.