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

Caterpillar's little brother research

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Re: Caterpillar's little brother research

Postby HartmutHolzwart » February 19th, 2016, 8:46 am

Additionally to the helix, you also need quite a sophisticated mechanism to multiply the one gilder transported by the helix into the 24 gliders needed to build the two rows of six blinkers needed to support the caterpillars front end.

Also for every *WSS to be build, much more than the minimum four gliders for one sided construction, due to the heavy use of kickback reactions. So overall it comes out to about 80 *WSS and 600 to 800 gliders produced and consumed per cycle.

In the thread, various options are discussed how to get a smaller caterpillar by reducing these numbers, but so far none of these was really implemented.

All in all, the existing caterpillar already is highly optimized and in my view best possible given the design.
HartmutHolzwart
 
Posts: 398
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Caterpillar's little brother research

Postby dvgrn » February 24th, 2016, 2:08 pm

HartmutHolzwart wrote:In the thread, various options are discussed how to get a smaller caterpillar by reducing these numbers, but so far none of these was really implemented.

I'm still fairly optimistic about one of the options, based on experience with 31c/240 self-supporting spaceships. It seems quite likely that slow-salvo recipes can be designed, that build the standard 6x Caterpillar helix, and that can be regenerated by structures traveling on some number of blinker trails (no idea how many yet).

Even though it will take a lot more gliders to produce each *WSS, the resulting caterpillar will probably be shorter. Parallel streams of gliders can be packed together much more tightly than the huge triangle structures in the current Caterpillar.

Also, slow salvos can construct a helix closer to the blinker trails, because it won't be necessary to leave space for long chains of rephasers between the NE and SE edges of the triangles. And slow-salvo construction is convenient because there's no need for the precise timing needed to get kickbacks to work.

There's still the rephasing problem associated with generating gliders on demand for the slow salvos, on 102 different lanes -- relative to the blinkers in the blinker trails, or rather, relative to the output gliders from the 6x period-multiplier mechanism.

I guess it remains to be seen whether the lane rephasing problem can be solved with just a few pi climbers plus throw-and-catch trickery making a variety of rake types, similar to the collection of rakes used in the Centipede.
User avatar
dvgrn
Moderator
 
Posts: 4980
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Caterpillar's little brother research

Postby muzik » June 28th, 2016, 7:55 am

This is kind of unrelated, but how did the program that assembled the original caterpillar work; did it simply piece together some existing parts, or did it actually generate the caterpillar somehow?

If the latter is true, couldn't you just run it again and hope for a caterpillar with 100 or so less cells than the existing one?

It would be a *really* trivial improvement, but it's definitely an improvement, especially seeing that Daniel apparently got a smaller than 232815-cell caterloopillar from running the caterloopillar-generating script (I am yet to test that assertion).


Although I heard that getting the thing that made the caterpillar up and running wasn't exactly the most pleasant thing ever.
waiting for apgsearch to support one-dimensional rules
muzik
 
Posts: 2855
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Caterpillar's little brother research

Postby dvgrn » June 28th, 2016, 9:59 am

muzik wrote:This is kind of unrelated, but how did the program that assembled the original caterpillar work; did it simply piece together some existing parts, or did it actually generate the caterpillar somehow?

If the latter is true, couldn't you just run it again and hope for a caterpillar with 100 or so less cells than the existing one?

If you run robocat again, not surprisingly, you'll get exactly the same Caterpillar. You'd have to reprogram it to put the pieces together differently, to have any hope of an improvement.

However, it's easy enough to optimize the Caterpillar by hand and end up with a smaller population and/or bounding box. The robocat program often just put together pieces without optimizing the phasing, because it would have taken forever to run (and write) the robocat code, if every possible rephasing optimization had to be tested.

As an experiment, I just made a smaller Caterpillar by moving the bottom 575 cells of the last four blinker trails up by 34 cells, along with the rephaser column just above it (third blinker trail from the left). That makes a Caterpillar that fits inside a 4195x330683 bounding box, with a population that's smaller by 24 cells.

Then that whole cleanup mechanism could be rephased one tick at a time, to bring it even closer to the last p45 glider rake above it. One of those phases will turn out to give the whole Caterpillar the lowest population (at one of its 270 possible phases). That may or may not be the same phase that allows for the smallest possible bounding box, so you have to decide what you want to optimize.

And then you could repeat that micro-optimization in probably several hundred places along the length of the Caterpillar, and you'll have... well, still not a very interesting amount of improvement, percentage-wise, compared to a thorough Little-Brother rebuild.

We should probably run competitions to find shorter *WSS-building components, for starters -- the two-part HWSS synthesis is especially worth improving. Anything that can be constructed incrementally with backward slow salvos, should be, because you can pack slow-salvo components much closer together... no long empty stretches of blinker trails needed any more, to give enough space between backward rakes and their matching forward rakes.

Another tangential idea: it's probably possible to build a Caterpillar with a significantly smaller population, just by rephasing the pi heptominoes wherever possible so that a large fraction of them are in their lowest-population phase simultaneously. It's not possible to get them all synchronized that way, or even nearly, but paying attention to that detail during a rebuild could still make a sizable difference.
User avatar
dvgrn
Moderator
 
Posts: 4980
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Caterpillar's little brother research

Postby muzik » June 28th, 2016, 10:57 am

Since I'm far (like, pretty damn far) from being engineered-spaceship savvy, I probably won't be of much help for the new ship's construction.

One thing that kind of strikes me is that the structure of the main body of the caterpillar looks pretty repetitive (emphasis here on "looks"), with a lot of triangles in it. Although these probably aren't exact clones of each other except in different generations, so that doesn't look to be a good enough method of compression.


Say, in the nearish future, we do find the smaller 17c/45. What would it look like? I'd assume just like the caterpillar (using the same main reaction), but not quite as tall. More importantly, how many cells would it have? Would we be able to knock it down into the hundreds of thousands range, maybe even smaller than the centipede? Or would it still be a multi-million cell beast?
waiting for apgsearch to support one-dimensional rules
muzik
 
Posts: 2855
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Caterpillar's little brother research

Postby gmc_nxtman » June 28th, 2016, 11:18 am

To my understanding, the reason that the caterpillar "looks" repetitive is that each segment that looks almost the same as the last one is used to build a part of the helix, which then lays down the tracks, which then build the helix, etc. So it's a self-sustaining loop. In order to compress the repetitive parts, one would have to use a smaller helix (which, luckily, already exists). But it's not a trivial process to reassemble the caterpillar with a smaller helix.
User avatar
gmc_nxtman
 
Posts: 1130
Joined: May 26th, 2015, 7:20 pm

Re: Caterpillar's little brother research

Postby Kazyan » June 28th, 2016, 3:52 pm

The Little Brother would probably not have triangles--there's been talk of using slow-salvos to build the helix, which can pack more tightly. So you'd have a string of closely-spaced "rakes" with the glider streams all pointing in the same direction towards the helix, instead of several triangles (composed of two different rakes pointing in different directions) trying to build the helix with synchronized shots.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 770
Joined: February 6th, 2014, 11:02 pm

Re: Caterpillar's little brother research

Postby muzik » June 28th, 2016, 4:03 pm

I'm assuming this version is focused more on the bounding box than the population?
waiting for apgsearch to support one-dimensional rules
muzik
 
Posts: 2855
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Caterpillar's little brother research

Postby dvgrn » June 28th, 2016, 5:25 pm

muzik wrote:I'm assuming this version is focused more on the bounding box than the population?

Not sure you can really assume anything at this point, since nobody has quite picked up all the pieces and started the re-assembly. Larger size means longer strings of gliders and *WSSes and blinkers, so population and bounding box will both definitely be reduced. As I mentioned, just paying a lot of attention to pi-heptomino phasing could cut down the population by a very large amount -- it's mostly just a matter of whether the rebuilder cares enough about minimizing the population to do the extra work.

The switch to slow-salvo construction could allow the Little Brother to be much narrower. I believe the current width is dicated by the necessity of rephasing the blinker trails between each backward rake and its paired forward rake. Depending on what rephasing is needed, it can take ridiculously tall columns of pi climbers to get the spacing and timing just right, and in the original design those have to fit in the vertical edge of each of those large triangles.

-- More or less, anyway. I bet that's an oversimplification. I definitely haven't memorized what each of those 25-tracks and 32-tracks is actually used for... The main point is that if we're not using any forward rakes, or not very many, then we can construct the upward *WSS streams very close to the blinker trails on both sides. Slow salvos don't care how far they travel before they do their work.

And we might not really need as many blinker trails as the original Caterpillar has. For making slow salvos, we could get away with just two blinker trails, except that we still need the downward MWSS filter streams, or some equivalent mechanism, to cut the pi-climber rakes' output down from period 45 to period 270. So we have to have enough blinker trails to conveniently build those downward MWSSes.

-- I suppose it might turn out that those MWSSes could be built with "not-so-slow" salvos using p45 backrakes lined up on just the right lanes. In that case, the minimum might be back down to two blinker trails again -- or maybe six trails, if we need catch-and-throw 25-tracks on either side, to get the construction timing right.

[Oddly enough, for most slow-salvo gliders, we won't need the catch-and-throw trick -- the timing of the middle gliders in a slow-salvo recipe don't matter. But we'll still need very precise timing to produce the glider that triggers each *WSS seed to build the upward streams in the helix.]

Or maybe eight trails will be better, so we can run leftward and rightward backrakes on separate trails up the middle, without the rakes having to wait for each other to get out of the way. Or more, for further increases in efficiency... and pretty soon we'll be right back up to the Caterpillar's trail count.

-----------------------------------------------

The simplest rebuild would involve copying the top 17,000 rows of the Caterpillar exactly -- that's a lot of very hard design work that it would be convenient not to have to re-do! Or maybe just move the left and right sides in by 1000 cells or so, since that's mostly just a copy-and-paste adjustment. Then attach rakes to those existing blinker trails to make slow salvos that build all those upward *WSS streams, using slow salvos or other new tricks.

I suspect that just with this kind of minimal rebuild, the Little Brother could end up at half the original Caterpillar's population and length (and bounding box), maybe somewhat less. But I have no hard evidence to back up this crackpot theory. Can't really measure Little Brother until somebody actually finishes building it; there are too many unsolved problems and unknown unknowns. It might not end up being any smaller at all...!
User avatar
dvgrn
Moderator
 
Posts: 4980
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Caterpillar's little brother research

Postby biggiemac » June 28th, 2016, 5:31 pm

The bounding box is generally a more useful metric for optimization, because as dvgrn said above, just changing the phase of pis so that they all reach a low population in sync could drastically reduce the minimum population.

I feel like the caterpillar is an order of magnitude more complicated than the Waterbear, just looking at Gabriel's page about it. I presume filters and catch/throw retiming are still going to be necessary in the slow salvo version as well?

Also, I was not under the impression that slow salvos could get more helix spaceships built per unit height - so to optimize bounding box they should only being used when the helix ship couldn't be put into place by a standard synthesis; am I wrong? I guess I might be out of date on the contents of this thread.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 503
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: Caterpillar's little brother research

Postby dvgrn » June 28th, 2016, 7:17 pm

biggiemac wrote:I feel like the caterpillar is an order of magnitude more complicated than the Waterbear, just looking at Gabriel's page about it.

I dunno. I don't know a whole lot of the details about either one, but at this point I think I'd personally get fewer and smaller headaches building Little Brother, than trying to rebuild the waterbear. Maybe I kinda sorta think I understand what's going on in the Caterpillar because of experience with 31c/240. Orthogonal designs seem a lot easier to break down into independent pieces, whereas some of the waterbear's mechanisms just seem like black magic.

biggiemac wrote:I presume filters and catch/throw retiming are still going to be necessary in the slow salvo version as well?

Filters, yes, because pi climbers inevitably throw out p45 glider streams, and nobody has come up with anything near a p45-repeatable helix reaction.

Catch/throw, probably, or at least maybe -- but just for the trigger glider in each slow-salvo recipe. The other gliders in a slow salvo don't need timing adjustments, but the last glider's timing will determine how the newly constructed *WSS lines up with the rest of the helix.

... Right now it seems to me that it might be possible to substitute a spatial offset for a temporal one. That is, if you wait long enough before sending the trigger glider stream, it will turn out that the *WSS stream lines up correctly with the helix. But too much of that kind of waiting around and you end up with an oversized bounding box again.

biggiemac wrote:Also, I was not under the impression that slow salvos could get more helix spaceships built per unit height - so to optimize bounding box they should only being used when the helix ship couldn't be put into place by a standard synthesis; am I wrong? I guess I might be out of date on the contents of this thread.

I might be out of date also.

My recollection is that it was very hard to find a reasonable slow-salvo recipe that could build some of the closely spaced *WSSes in codeholic's 5x helix (at the top of this thread). The original 6x helix didn't seem to be as much of a problem.

Now, the current rakes for building helix LWSS and MWSS streams seem to be roughly 5000 cells high, and HWSS streams need 9000+ cells and a double rake (two triangles).

There seems to be no trouble packing backrakes about 200 cells apart on average in the existing Caterpillar, with gliders in exactly the right spacetime locations for the current multi-kickback synchronized constructions. That might mean that a LWSS or MWSS-creating slow salvo should have no more than 25 or 30 gliders, and a HWSS-creating salvo would stop being competitive at around 50 gliders. Very roughly.

I'm hoping that at least the HWSS double-rake construction can be replaced cost-effectively by slow salvos. Ideally I guess we'd run a new search that checks slow salvo recipes in order of cost, measured in pi climbers.
User avatar
dvgrn
Moderator
 
Posts: 4980
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Caterpillar's little brother research

Postby simsim314 » June 29th, 2016, 4:04 am

How about using the universal helix? I think it somewhat simpler, but the period is higher...

An example:

x = 118, y = 390, rule = B3/S23
9$29b2o$28bo2bo$28bobo$29bo6$54bo4b3o$53b3o3bo2bo$46b3o3b2obo3bo$46bo
2bo2b3o4bo3bo$46bo5b3o4bo$46bo3bob3o5bobo$46bo3bob2o$46bo6b2o$47bobo8b
3o$58bo2bo$53bo4bo$53bo4bo3bo$53bo4bo3bo$58bo$53bo5bobo$53bo$53bo2$53b
o$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo
$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo
2$53bo$53bo$53bo8b3o$62bo2bo$53bo8bo$53bo8bo3bo$53bo8bo3bo$62bo$53bo9b
obo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$
53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo18b3o$53bo18bo2bo$
72bo$53bo18bo$53bo19bobo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$
53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo$40b3o$40bo2b
o9bo$40bo12bo$40bo12bo$41bobo$20bo32bo$19b3o31bo$19bob2o30bo$20b3o$20b
3o30bo$20b2o31bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo
2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo
$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$
53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$
53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$
53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$
53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$27bo25bo$26b3o24bo$25b2obo24bo$
25b3o$26b2o25bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$
53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$
53bo$53bo$53bo2$36b3o14bo$36bo2bo13bo$36bo16bo$36bo3bo$36bo16bo$37bobo
13bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$53bo$53bo$53bo2$47bo5bo$46b
3o4bo$46bob2o3bo$47b3o$47b3o3bo$47b3o3bo$47b2o40$64b3o$63bo2bo$66bo$
62bo3bo$66bo$63bobo!
User avatar
simsim314
 
Posts: 1539
Joined: February 10th, 2014, 1:27 pm

Re: Caterpillar's little brother research

Postby dvgrn » June 29th, 2016, 10:36 am

simsim314 wrote:How about using the universal helix? I think it somewhat simpler, but the period is higher...

Looks simpler enough to me that it might be worth switching over to it, if it weren't for the higher-period issue. I'd love to see one of these in action, but I'm not sure that it would make very good support for a standard 17c/45 Caterpillar.

The sample you posted seems like it could be cut down to a period of about 1700, roughly. Filter streams could turn p45 rakes into p1710 rakes with no problem -- but that would be 38x instead of the current 6x. That means a factor of six increase in the number of fanout devices. Those are the secondary streams of more widely spaced LWSS and MWSS streams, separate from the actual helix at the far right. Their job is to build the initial 32-track -- two blinker trails -- for the first pi climbers to run on.

The original Caterpillar has a 6x helix, so that means building twelve blinkers for each p270 period of the spaceship. A 38x helix would mean building 76 blinkers in each p1710 cycle, assuming that the universal helix can really be cut down that to that low a period -- I'm not sure how quickly those blinker puffers can really be constructed with one-sided recipes, for example.

EDIT: I'm a little nervous about the idea of constructing any other c/2 objects as part of a helix, besides the standard *WSSes. HWSSes, at least close to anything else, have turned out to be plenty hard enough to handle.

-- It's quite possible I'm missing something, though. Is there a different approach that might work better for supporting a Caterpillar front end?
User avatar
dvgrn
Moderator
 
Posts: 4980
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Caterpillar's little brother research

Postby Sphenocorona » June 29th, 2016, 6:29 pm

Well, this is more of the known approaches, but I think it might be possible to create a 4x helix if a high forward displacement turner can be found that is faster than and of comparable size to the recent one I found that chains at 16c/43... There's ones I've found that would work but are too big just because they refuse to clean up nicely...
Sphenocorona
 
Posts: 471
Joined: April 9th, 2013, 11:03 pm

Previous

Return to Patterns

Who is online

Users browsing this forum: No registered users and 6 guests