Half-bakery reaction with glider

[codeholic]

Excellent result! Congratulations!

Did you ask your employer if they would agree to release the script under an open source license, like MIT, BSD, Apache or at least GNU GPL?

EDIT: It seems to me that the bounding box could be significantly reduced, if you used the full width between NW and SE half-bakeries.

[chris_c]

Attached is a script to build a (-3, -6)c/P knightship for any sufficiently large P. xxx

Most excellent work! Congratulations!

[chris_c]

Hadn't thought about the adjustable delay between successive rake gliders at all -- you get +8N delay just by moving a rake unit N full diagonals southwest, which is pretty much equivalent to moving the target by N fd northeast, but sometimes one will be more convenient than the other. Guess I'll have to adjust my input format to allow for that. More eventually --

Well I was worried that it may not be possible to shift to the north east for the inner 180 degree turners because the higher HB trails get in the way. This could very well turn out to be a non-issue.

[codeholic]

I've created an article in the LifeWiki about the half-baked spaceship. Feel free to expand it.

[lukebradford]

Could somebody post an RLE of the spaceship?

[calcyman]

An RLE would be massive, but here's the MC for the p2621440 version of the knightship:

http://golly.sourceforge.net/patterns/h ... ghtship.mc

[Kazyan]

Congratulations on another big Life project completed, and fast!

Now that there's the HBK series, the Caterpillar, and the WIP 31c/240 spaceship, it would be useful to have a name for this type of reaction (A + B -> displaced A + displaced B) that can be used to create mega-spaceships. The HBK reaction is clearly in a different subcategory than the 17c/45 and 31c/240 reactions, but we don't have a lot of examples. How about "monomer"?

[dvgrn]

Excellent result! Congratulations!

Yes indeed -- and thanks for getting it finished so quickly. Maybe I should spend a day traveling more often...

EDIT: It seems to me that the bounding box could be significantly reduced, if you used the full width between NW and SE half-bakeries.

There's definitely a lot of potential for reducing the size of this construction. The smallest knightship that the script can build seems to be period 2167477 (if you adjust a few details a little bit, like the gliders' starting positions). So the smallest prime period available with this design is 2167549.

However, Calcyman used an 8-glider system instead of a 7-glider one, and the MWSS+gliders reaction on the A side instead of the probably-cheaper LWSS+gliders one... and the distance between A and BC is probably about twice as wide as it needs to be, and it's a serial recipe instead of a massively parallel one.

Even so, the smallest Calcyman-HBK is only about 400K cells on a side. Sure is impressive to see the whole system actually working!

[codeholic]

Another way to reduce the bounding box (and the period, as a consequence), that I noticed, is to add half-bakeries also to the NW salvo. You would need to increase the distance between MWSS and glider synthesis targets (or LWSS and 2 glider targets, doesn't matter) in order synthesize NW salvo a little bit farther to the NW, but in return it would significantly reduce the most NE part of the ship, that currently takes about a third of the whole spaceship's length, due to glider-delaying ability of the HB-reaction.

On the other hand, what are we trying to achieve? Surprisingly, or maybe not so surprisingly, optimizing constructed patterns for a smaller bounding box, population, period etc. appears to be not as rewarding (in different aspects), as finding, for instance, a smaller "natural" (sensu lato) spaceship of certain speed, though usually it requires much less amount of human effort to find one, having in mind that there are specialized search programs, such as gfind.

Having said that, is it really worth to find better designs for the 31c/240 spaceship's front, when there is already a working one? Is it worth to find cheaper syntheses for *WSS seeds, when there is a proof, that you can use those more expensive, but already found ones?

I'm sorry for such a melancholy post, but that's something I've reflected on a lot.

[calcyman]

Having said that, is it really worth to find better designs for the 31c/240 spaceship's front, when there is already a working one? Is it worth to find cheaper syntheses for *WSS seeds, when there is a proof, that you can use those more expensive, but already found ones?

I'm not sure I would have attempted the (-3, -6)c/P project with the original 90° + 90° reflectors, instead of the new 180° and MWSS-based reflectors. So yes.

[codeholic]

I'd say it's different. Switching from the design, that required slow-elbow construction and that would eventually require a more complicated algorithm for an assembly script, was a qualitative leap. That's something we should really take care of before the assembly.

On the other hand, building 27 or only 4 *WSS salvos with the same slow salvo techniques is just about quantity. (Actually, following the bleeding-edge optimised design for the 31c/240 spaceship would require even a more complicated assembly script, because it involves different types of rakes.)

[dvgrn]

I'd say it's different. Switching from the design, that required slow-elbow construction and that would eventually require a more complicated algorithm for an assembly script, was a qualitative leap. That's something we should really take care of before the assembly.

On the other hand, building 27 or only 4 *WSS salvos with the same slow salvo techniques is just about quantity. (Actually, following the bleeding-edge optimised design for the 31c/240 spaceship would require even a more complicated assembly script, because it involves different types of rakes.)

Yes, it's a tricky balancing act deciding what's really worth the effort. For 31c/240, it has been "trivial" for quite a while to produce a complete spaceship using codeholic's perfectly good 27-*WSS front end.

That would end up being about two orders of magnitude longer than a more recent design, which would build fewer *WSSes with lower-cost recipes using more efficient rakes on a narrower set of trails. But in many ways the 27-*WSS design is more elegant -- it manages to close the construction cycle with a smaller set of components.

Based on my experiment with the 31c/240 HWSS forward rake, which is built with a similarly minimal toolkit, I guessed that a full 27-*WSS implementation wouldn't run too well in Golly -- maybe about the same as the original Caterpillar.

Now, I definitely prefer

• A) patterns that Golly can run very quickly,
  B) patterns that don't just look like a boring straight line when you're zoomed out, and
  C) patterns that showcase new Life technology that may come in handy again elsewhere.

I think oblique's 'sscs' slow-salvo search utility is shaping up to be a decent replacement for Glue, so that's one good result of continuing the 31c/240 project. We're pretty close to being able to use slow-salvo *WSS recipes to cut down the original Caterpillar by an order of magnitude or two, as well, if anyone decides that that's worth reconstructing! I'd love to see 17c/45 and 31c/240 caterpillars that Golly can really run away with... but unfortunately my spare time is somewhat limited these days.

Luckily the script-generated HBKs satisfy A, B, and C very nicely already. Probably that means I'll put further HBK improvements on the back burner for a while. I am tempted to build a period-2124679 HBK, since that's within easy reach -- the current semibake script doesn't pack nonshoots together quite as tightly as it could -- and 2124679 is very slightly famous (the biggest known Wolstonholme prime).

But the various optimizations mentioned above could probably cut down the minimum HBK period to something under a million, at which point 2124679 becomes irrelevantly large... So for now I'll stop after my own bit of pointless corollary-sniping. Attached is the lowest-period HBK that anyone has bothered to build so far:

Half-baked knightship-p2167469.zip

Period 2167469 (prime) half-baked knightship, not quite buildable by the semibake script

(47.05 KiB) Downloaded 997 times

In case anyone is curious, the script can build HBKs of period 2167621+8N with very minor adjustments (just move the initial eight gliders 10K southwest), and any number strictly above 2242020 should work fine, with the same 10K adjustment in a few cases.

In general I try not to worry about whether pattern optimizations are worthwhile -- I just work on them if they continue to look like interesting unsolved puzzles. Some time ago I officially renounced cryptic crosswords, on the grounds that somebody else already knew the answers to those, and took up Life research instead as a vaguely equivalent form of mental exercise. That's good enough for my purposes... and if anyone else takes an interest the results of these questionably useful investigations, so much the better.

[codeholic]

Another challenge for optimising the half-baked knightship could be to beat Gemini in terms of minimum population, and the gap is pretty surmountable (1,049K versus 846K). This can be probably done solely by switching to the 7-glider design and cheaper seeds for the NW salvo gliders.

[codeholic]

I am tempted to build a period-2124679 HBK, since that's within easy reach -- the current semibake script doesn't pack nonshoots together quite as tightly as it could

Another fairly simple way to reduce (probably almost halve) the period of the half-baked knightship would be to run two glider salvos through the circuit at the same time. But in this case you would need to rewrite the "tape" to aim to the targets displaced by (-6, -12).

[calcyman]

Another challenge for optimising the half-baked knightship could be to beat Gemini in terms of minimum population, and the gap is pretty surmountable (1,049K versus 846K).

Okay, that's actually a good reason for optimising: create the smallest known knightship.

This can be probably done solely by switching to the 7-glider design and cheaper seeds for the NW salvo gliders.

Even that's unnecessary. The attached pattern has period 1500000 and 610 kilocells, just by 5 minutes of changing some parameters in the Python script.

[dvgrn]

Another challenge for optimising the half-baked knightship could be to beat Gemini in terms of minimum population, and the gap is pretty surmountable (1,049K versus 846K). This can be probably done solely by switching to the 7-glider design and cheaper seeds for the NW salvo gliders.

And we have to do the usual run-down of related object for Jason Summers' Life Status page:

Spaceship? Done. Puffer? Trivial. Versatile puffer? ... Still fairly trivial. Wick-stretcher? Theoretically, but we'd need another elbow and a little more length.

Gun? Ouch!

-- Well, just make a seed for the seven or eight gliders, feed the whole HBK-plus-seed into a universal-constructor pattern compiler (which nobody has quite written yet), build a really big data loop to hold the resulting recipe, and there you are. _Much_ easier than guns for either of the caterpillars...!

Now that there's the HBK series, the Caterpillar, and the WIP 31c/240 spaceship, it would be useful to have a name for this type of reaction (A + B -> displaced A + displaced B) that can be used to create mega-spaceships. The HBK reaction is clearly in a different subcategory than the 17c/45 and 31c/240 reactions, but we don't have a lot of examples. How about "monomer"?

Seems to me that HBKs may be in a category of their own, pretty much indefinitely. Could there still be an undiscovered small object or constellation that can be shifted by a glider or spaceship in a similar way? The closest thing I can think of is the old three-block switch, which can be made by hitting a half-blockade with a glider:

Code: Select all

x = 42, y = 25, rule = B3/S23
23bo$24bo$22b3o7$40b2o$40b2o3$b2o$b2o$33b2o5b2o$33b2o5b2o$2o$2o4$9b2o$
9bobo$9bo!

But that's not nearly as clean as the half-bakery reaction; a 90-degree reset glider would be needed, so I haven't seen any plausible way to close that loop.

I'm not sure about "monomer" -- the HBK is almost completely made out of half-bakeries, but there's some scattered target junk up at the northeast end also, not to mention the gliders. The best wording I could come up with was that where Gemini is a self-constructing spaceship, the caterpillars and the HBK are merely "self-supporting" or "self-sustaining".

The Gemini and the HBK are variable-speed, where the caterpillars are fixed-speed. So the HBK is the only variable-speed spaceship that is not a self-constructor... Yup, it would be nice to have a better word for "non-self-constructing."

[dvgrn]

This can be probably done solely by switching to the 7-glider design and cheaper seeds for the NW salvo gliders.

Even that's unnecessary. The attached pattern has period 1500000 and 610 kilocells, just by 5 minutes of changing some parameters in the Python script.

This period-1.5M knightship is part of an infinite series of period 1359704+8N, with a bounding box of (297401+N, 301639+N). Good Golly, when did a bounding box area under 9x10^10 cells start looking like a reasonable size? Minimum population is 609659 for every ship in this series, in the obvious phases when only eight gliders are moving.

N can be slightly negative if someone wants to take the extra 1fd (or more with chris_c's optimal arrangements) out of the first umpteen hundred nonshoots, up to the first NE trigger glider, where the timing and not just the phase really matters. Looks like it shouldn't be too difficult to get the script to do the packing properly, but I'm not volunteering to figure out the details this week...!

Calcyman's new version of the script should again produce eight separate infinite series of HBKs, a few of which will start smaller than this series. I seem to more or less understand how these script-built HBKs work now, so I'll stop playing around with them unless I can come up with more interesting improvements...!

[codeholic]

These reductions are quite impressive! It's now not only smaller than Gemini in terms of the number of cells, but also shorter than the caterpillar!

[calcyman]

These reductions are quite impressive! It's now not only smaller than Gemini in terms of the number of cells, but also shorter than the caterpillar!

Indeed! Attached is a period-1165000 HBK with 507792 cells, which fits in a 244017 by 248929 box.

Getting the period below 10^6 would require some actual reworking (e.g. optimising the slow salvos), I imagine, although it should be possible. Also, 10^6 seems nicely out of reach for Geminoid knightships; Demonoids are ruled out since they move diagonally instead of obliquely.

The 31c/240 project seems to similarly be going well, although the design I have at the moment would be period-480 or period-720 rather than period-240.

Also, what ever happened to (13,1)c/31? That was all the rage when I was growing up...

http://www.gabrielnivasch.org/fun/life/ ... C-Epilogue

[codeholic]

Also, what ever happened to (13,1)c/31? That was all the rage when I was growing up...

Well, it's stalled more or less. The reason for that is that its velocity 13/31=0.4193... is too close to 11/24=0.4583... which is the current asymptotic limit for caterpillar-like ships. As a result, the corresponding helix is p496 (×16), consists of 40 spaceship salvos and may still be too tight to be built with known (reasonably efficient) syntheses (nobody has tried yet, though). You could also build a less tight helix, but then it would contain more ships and be of higher period, thus you would need more fanout devices and more spaceships to synthesise. There is no way it will beat the HBK

I've also found some possible filters, that don't destroy the template, in order to build (×16) helix. And that's where it currently is.

[codeholic]

The hypothetical (23,5)c/79 spaceship seems more promising, especially because it already has a relatively small p158 (×2) helix with a fanout device, and a plausible method to build glider filters, but it has some problems with geometry, that don't seem insuperable, but still set some challenge (in the worst case, you can synthesise the spaceship stream with the use of an orthogonal *WSS).

A more serious obstacle, in my opinion, is that there is still no known way to adjust tracks arbitrarily -- ironically, for (13,1)c/31 it's trivial.

EDIT: Would you please share the latest version of the semibake script?

[dvgrn]

Getting the period below 10^6 would require some actual reworking (e.g. optimising the slow salvos), I imagine, although it should be possible.

Actually it might be fairly simple. There's 1fd extra space between individual nonshooting HB rake units, but that's peanuts compared to what you get when you optimize the really long nonshooting chains. As chris_c mentioned, above 4 units each new unit only has to cost 11fd. The period-1165K HBK always uses 24fd per unit:

Code: Select all

#C sample comparison between current HBK and optimal HB placements,
#C with 5 rake units.  Cost savings are 13fd per unit from here on.
x = 187, y = 144, rule = B3/S23
9$135b2o$134bo2bo$134bobo$132b2obo$131bo2bo$131bobo$132bo7$172b2o$171b
o2bo$171bobo$169b2obo$168bo2bo$168bobo$169bo3$155b2o$154bo2bo$154bobo$
112b2o38b2obo$111bo2bo36bo2bo$111bobo37bobo$109b2obo39bo$108bo2bo$108b
obo$109bo7$149b2o$148bo2bo$148bobo$146b2obo$145bo2bo$145bobo$146bo3$
132b2o$131bo2bo$131bobo$89b2o38b2obo$88bo2bo36bo2bo$88bobo37bobo$86b2o
bo39bo$85bo2bo$85bobo$86bo7$126b2o$125bo2bo$125bobo$123b2obo$122bo2bo$
122bobo$123bo3$109b2o$108bo2bo$108bobo$66b2o38b2obo$65bo2bo36bo2bo$65b
obo37bobo$63b2obo39bo$62bo2bo$62bobo$63bo7$103b2o$102bo2bo$102bobo$
100b2obo$99bo2bo$99bobo$100bo3$86b2o$85bo2bo$85bobo$43b2o38b2obo$42bo
2bo36bo2bo$42bobo37bobo$40b2obo39bo$39bo2bo$39bobo$40bo7$80b2o$79bo2bo
$79bobo$77b2obo$76bo2bo$76bobo$77bo3$63b2o$62bo2bo$62bobo$60b2obo$59bo
2bo$59bobo$60bo!

There are almost 5000 HB shooting and nonshooting rake units in the HBK -- 4963, I think, but I didn't look to see how many are before the last that shoots a timed glider; after that, tighter packing will only improve the bounding box but not the period. There are 234 rake units that actually shoot gliders, leaving something like 4700 nonshooters. If we could save 13fd for each of 4000 nonshooters, that would reduce the period to roughly

1165000 - ( 4000 * 13 * 8 ) = 749000 ticks.

It's not really that simple, of course, because different +8N HBK series need to shoot gliders from different scans, so the script has to wait around and pick the next available glider with a workable timing. But the average savings should be somewhere in this range -- enough to drop the period below a million, at the very least (?).

Then... if all of the actual trigger gliders were sent during a final short series of scans, as close to each other as possible, then wouldn't that get rid of most of the empty space in the northeast? For that matter, if the trigger gliders were sent in a group in the middle of the HBK, or maybe even right at the beginning, wouldn't that reduce the period by quite a bit? That's just a matter of cycling the recipes so that every target is ready for the trigger glider right away, and the rebuilding gets done immediately afterward.

This is somewhat similar to codeholic's suggestion about a (-6,-12)-offset HBK, which would also reduce the period but not the bounding box, by delivering the next activating glider salvo more quickly. In either case it should be possible to move all of the targets just far enough NE to allow the last slow salvos to pass before the next round begins.

I think you can get somewhat bigger savings from sending most of the slow salvos in parallel instead of in series, but that's trickier to sort out. Quite a lot of the gains are lost again because you need wider scans and more resets. The optimal method might turn out to be pairing up slow salvo recipes in a single-reset scan; that way you can get twice as much done with hardly any extra cost at all -- if narrow enough recipes can be found, anyway.

[calcyman]

EDIT: Would you please share the latest version of the semibake script?

Sure, see attached. The default parameters are really overclocked, though, so you might want to increase width by 940, lane by 470 and period by 200000 before experimenting. Important: width and lane should be multiples of 94.

The only instructions at the lowest level are shoots, nonshoots and delays (as well as vacuums, which are essentially NOPs that just increase the retardation by multiples of eight), so Dave's suggestion could be implemented by holding the nonshoots in a stack until either a shoot or delay is called.

[HartmutHolzwart]

Congratulations!

Just one question: How fast could HBK ships get?

[NickGotts]

Many congratulations to all concerned! The catalog of known ship velocities is getting quite complicated.