31c/240 caterpillar working notes

oblique · Post by **oblique** » January 24th, 2014, 1:52 am

dvgrn wrote:
oblique wrote:Lanes are always defined such that lane 0 would hit exactly the top left corner of the bounding box.
Lane 0 would hit the top left corner -- is that with a 3o$o$bo! glider or a 2o$obo$o! glider? They're actually on different lanes. Other than that, your definitions seem clear, and I think the math would all work as you've outlined it.

The whole article was more like an outline, then a stone-hard definition. For an exact definition I would (reandomly) one of the 4 phases and define a "hot spot" that should reach (0,0) - and call that gliders lane "0".
As long as the definition is known by those who actually try to use the results that would be fine.
Besides: as long as the definition is well defined (even if randomly so) the results would work just fine. All that maybe has to be done is adjust the target by one or even two cells.

dvgrn wrote:
oblique wrote:We could then use the weighted q algorithm and the function above, to search for a specific result.

(start with one state (pat,lane), q all reactions coming from there, then iteratively take the cheapest queued reaction r from the q, add any possible reaction starting with the end pattern of r back to the q, until one is found that yields the desired result)
Ah, this is the exciting part! The original Glue built a database of all the reactions it found that didn't explode -- Paul Chapman called them "simple outcomes", and recently I've been calling them "intermediate targets", or just "targets". The idea was to do the actual search just once and query the database later. But as I mentioned a while back, *WSS generators were among the reactions that Glue automatically threw away.

I seem to recall that even forbidding output gliders and *WSSes, Glue had a hard time getting past about nine gliders -- the database went over 2GB at that point, so doing a complete search with up to ten gliders would have exploded the size to dozens of gigabytes at least.

Space does not matter that much any more. Besides to my experience pattern-DBs seem to be vary well compressable.

OK, sharing actually GBs of uncompressable or already compressed Data is a pain still.

dvgrn wrote: For example, an eight-glider 0 +9 +18 +27 +5 +14 +23 +1 recipe would cost 1+1+2+3+4+5+6+7 = 29 rephaser/rakes, less than a two-glider 0 +0 recipe (second glider following the first on the same lane -- 1+31 = 32 rephaser/rakes).

That is the base idea, yes. Besides: with my "definition" of lane there would be lanes with negative indices.
Maybe "top most lane that comes close enough to the bounding box to interact" would be better.

dvgrn wrote: Anyway, it will be very interesting to see how long it takes to boil this search space down into useful information. I could imagine designing either an initial exhaustive search stage, to produce a huge database to be re-searched later -- or an optimized utility that you'd run over and over again with different parameters, each time you want to find something different. (?)

Not sure yet. For a "cheap first" search you actually need at least the weights. I bet that each constructor has it's own definition of "cheap".
Therefore it might be better to include other limits like "do not collided with my copy 31 places away of me" from the begining.

HartmutHolzwart · Post by **HartmutHolzwart** » January 24th, 2014, 5:24 am

Btw.: If we could later manage the complexity of interleaving the construction of multiple targets, this should reduce the average cost for adjusters. If we assume equal independent distribution of the requested gliders mod 31, then for two targets the average cost would be significantly reduced from 16 (I have to do the exact math).

Post by **dvgrn** » January 24th, 2014, 9:58 am

HartmutHolzwart wrote:Btw.: If we could later manage the complexity of interleaving the construction of multiple targets, this should reduce the average cost for adjusters. If we assume equal independent distribution of the requested gliders mod 31, then for two targets the average cost would be significantly reduced from 16 (I have to do the exact math).

Do you mean two targets right next to each other, inside the same 31-stripe for the 31c/240 spaceship? Otherwise I don't see how you'd avoid hitting one target with the backrake stream intended for the other target. But 31-stripes are not very wide; even within one stripe, I think you would usually end up with unwanted interactions between the two recipes.

It probably works better to think of a two-target construction as a construction of a single constellation. This worked out very well for the Geminoid replicator construction: I had a database of half a million constellations to look through (the attached recipes in the link, plus their mirror images). So the odds were pretty good that the constellation I wanted was in there somewhere... and much larger constellation databases are within easy reach of a NewGlue search.

I suggested an optimization similar in some ways to your multi-target idea, that I still think might be worth pursuing: have two or more (but probably just two) rephaser tracks, six block trails each, running next to each other, both firing rightward backrakes. The track on the right would be the primary one, of course, but whenever a glider was required that would need a dozen or more rephasers, send a stream through from the "backup" left-hand track instead. This will be especially effective when skipping one lane in a recipe would mean that the next required lane would be cheap instead of expensive.

[If you can get the +6 glider from somewhere else in a 0 +6 +1 series, for example, then +1 is only half a dozen rephasers away from the original 0 lane -- whereas you'd need ten rephasers to get to the +6, and then another 25 to get back to +1.]

With the current trail spacing there are eight lanes on which a backrake stream can pass through, so it should only take a few rephasers to reach a permeable configuration.

The difficult part of this design is that you might simultaneously want to use the left track as a primary lane for left-shooting backrakes, with the right track as the backup. Optimizing the two tracks for those conflicting purposes is definitely non-trivial -- but it may produce a shorter spaceship than a four-track version with dedicated primary and backup tracks for the left and right sides.

... I wouldn't be surprised if a three-track design turned out to be a good compromise.

But once we have one track at the front of the spaceship, it may turn out that it costs very little to build as many additional tracks as we want -- maybe even two backup tracks for each primary. That seems like it might create more problems than it solves, though, since the innermost track would have to shoot through two sets of block trails.

HartmutHolzwart · Post by **HartmutHolzwart** » January 24th, 2014, 12:00 pm

Why in the same 31 strip? Unless you define a strip different than me. In every column you are rextrcuted to a length of 31, but it need not be the same height where you start. So you can build a block slightly above the normal range if there is no other target that would collide.

So if you have two *WSS that are very near to each other, the idea would be to bild the seeds for them simultaneously and then fire them off together. Can you duplicate gliders with slow salvos in a controlled manner or is that too costly?

Post by **dvgrn** » January 24th, 2014, 2:10 pm

HartmutHolzwart wrote:Why in the same 31 strip? Unless you define a strip different than me. In every column you are rextrcuted to a length of 31, but it need not be the same height where you start. So you can build a block slightly above the normal range if there is no other target that would collide.

True enough. My definition of 31-stripe is fairly informal -- I'm visualizing it as a width-31 diagonal stripe, but it can certainly wander a little out of the normal range as you say. My experience so far is that width-31 isn't a lot of room to put together a slow salvo in: a traffic light fills up a third of the width, and a simple honeyfarm explosion takes up closer to half of it. If you try to manage two simultaneous constructions in that width, the odds are good that some of the intermediate states of one construction will get in the way of the next glider needed for the other construction -- so then you're back to having to pay the full price for the next glider again.

Now, even for a single construction, there are usually multiple recipes (often dozens) that produce the same result. If you have to get rid of a block, for example, you can shoot it down with any of six adjacent lanes... some of those lanes will be cheap, and some will be expensive. Or you might have to move two blocks in the current target constellation, one with a (+2,+1) pull and one with a (+1,+2) -- you can usually fire those two gliders in either order, and generally one order will be cheaper than the other.

HartmutHolzwart wrote:So if you have two *WSS that are very near to each other, the idea would be to bild the seeds for them simultaneously and then fire them off together. Can you duplicate gliders with slow salvos in a controlled manner or is that too costly?

I'd say it's not too costly anywhere that it absolutely has to be done, but it will almost always make sense to avoid it. We can certainly string together a glider splitter and some one-time turners to get any relative spacing and timing we want for two output gliders, within the width-31 constraints. And no doubt somewhere out there are two *WSS seeds that can be built very close to each other, and can be triggered simultaneously to get a helix spacing that we can't get otherwise.

However, between the splitter, the turners, and the seeds, we probably have a dozen-object constellation (at least) to construct with a slow-salvo recipe. Somewhere out there in the search space is the incredibly lucky recipe that places all of these objects exactly right, with the minimum cost -- maybe a dozen gliders or so. But that minimum-cost recipe is out of reach of any likely search utility, at least for the moment; there are just too many quadrillions of possible recipes to sort through.

So in practice we'd have to build each object separately, or in groups of two or three -- and that does get pretty expensive, especially when you compare it to simply building a standalone *WSS seed and triggering it immediately, with no extra glider splitters or OTTs needed.

Seems like we'll almost certainly end up with a shorter spaceship if we restrict helix searches to *WSSes that can be constructed by inexpensive slow-salvo seed mechanisms. Which brings us back to the search project that oblique is looking at, to expand our list of inexpensive slow-salvo *WSS seeds. I'm betting there are good *WSS edge-shooters eight gliders from a block, or seven gliders from a blinker... and that is within reach of an exhaustive search!

oblique · Post by **oblique** » January 25th, 2014, 4:04 am

dvgrn wrote:And no doubt somewhere out there are two *WSS seeds that can be built very close to each other, and can be triggered simultaneously to get a helix spacing that we can't get otherwise.

I'd rather be looking for a differnt helix in that case.

Post by **codeholic** » January 27th, 2014, 5:42 pm

Nice LWSS edge-shooting seed: