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

Half-bakery reaction with glider

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

Re: Half-bakery reaction with glider

Postby dvgrn » July 15th, 2014, 5:41 pm

HartmutHolzwart wrote:Just one question: How fast could HBK ships get?

That's not an easy question. The short summary is that you probably won't ever want to bet on an HBK in a spaceship race, unless it's racing against a bigger HBK (EDIT: or an artificially slowed-down Gemini/Geminoid, I suppose). For current HBK designs, the speed tends to be inversely proportional to the width of the ship, though it's not really quite that simple. It makes a difference what proportion of the ship is taken up by the half-bakery chains, where gliders travel somewhere between c/6 and c/10 on average, and what proportion is mostly empty space where gliders can travel faster.

The current speed and size record, (3,6)c/1165000, can be improved somewhat without changing the design, maybe to around (3/6)c/750000 (but I don't think anyone has really checked my math on that yet).

With significant changes I'm guessing that a period under 250K, and possibly even under 100K, might be achievable -- but that would need a much more complicated design, probably with multiple sets of slow salvos in the pipeline at the same time. In a multi-salvo system it's not clear that it would be trivial to keep Salvo #2 construction gliders from hitting Salvo #1, for example.

Parallel recipes and cheaper 180-degree turner recipes could also help cut things down. But it's not clear that the shortest possible HBK would look all that much different than the current ones... and it still wouldn't win any races against non-HBK spaceships.
dvgrn
Moderator
 
Posts: 3151
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Half-bakery reaction with glider

Postby chris_c » July 17th, 2014, 10:41 pm

Here is a HBK with period 245,912 and bounding box under 33,000 square. It uses all the tricks that I know of:

- Parallel build
- 180 degree turners with correct timing mod 8
- Uses cheap LWSS seed (contortions in order to get correct timing are still reasonably expensive though)
- Supression without using guard gliders
- Compact HB placement

The script produces a nearly working version of the ship but without any supression mechanism. It was only when investigating this at the end that I realised that the suitability of a particular supression mechanism was dependent on the horizontal distance between the input gliders mod 47.

The version of the ship posted here is the same as the output of the script but with the following changes:

Shift entire NW side by (-8,-8).
Shift LWSS targets, 180 degree turners and SE gliders by (8, -8)
Shift all HBs responsible for shooting at the LWSS targets by (-4, 4)

Now that 16 extra squares have been added horizontally between the input gliders, everything is correct mod 47 and
dvgrn's supression mechanism was added by hand.

The script tries to make the shooting range as narrow as possible without causing any collision, except I added an option to give a bit of extra space on the SE side. In the script I have set this value to 50 in order to give enough freedom to shoot the three NW glider pairs with correct timing mod 8. Probably 50 can be reduced and you may end up with a slightly smaller ship. Elsewhere I have tried to fit everything together as tightly as possible but I may have missed a few spots.
Attachments
assemble.py.gz
(2.72 KiB) Downloaded 552 times
hbk_245912.mc.gz
(41.52 KiB) Downloaded 625 times
chris_c
 
Posts: 647
Joined: June 28th, 2014, 7:15 am

Re: Half-bakery reaction with glider

Postby dvgrn » July 17th, 2014, 11:10 pm

chris_c wrote:Here is a HBK with period 245,912 and bounding box under 33,000 square. It uses all the tricks that I know of:

- Parallel build
- 180 degree turners with correct timing mod 8
- Uses cheap LWSS seed (contortions in order to get correct timing are still reasonably expensive though)
- Supression without using guard gliders
- Compact HB placement

Wow, you got down to below 250K in one jump -- this is quite an improvement! The Gemini knightship is still almost five times faster, so I think my prediction about spaceship races is still safe for the moment, but it's a speed demon compared to the original p2621440 HBK anyway.

I notice the 180-turners stick out quite a bit farther than the LWSS+G mechanisms, even though there are only four of them compared to three LWSS+G. Is there any likelihood that two of the gliders in the SE can be done with the LWSS+G mechanism as well? The two pairs are different colors, so to do all four that way would need a different mechanism... but maybe there's no cheap way to invert that LWSS recipe?

-- Not that that would be any more than icing on the cake, anyway; it's plenty impressive enough as it is. I don't see any other likely quick improvements, and am not particularly inclined to hunt for trivial 1fd optimizations. Congratulations!

EDIT: Oops, I missed one possibility. It looks as if it should be possible to reduce the period of the current design by another 40K ticks -- possibly to as low as about 185K, but that's unwarranted optimism -- without reducing the bounding box. This can be done by shuffling the construction recipes so that return gliders from the 180-turners and LWSS+G are sent on an earlier scan, adjusting the initial targets accordingly.

It looks as if the initial scan is a little over 60K long, so it may just barely be possible to change it around to be the last scan instead. It may end up getting interleaved with the first scan in the next cycle unless the bounding box is made bigger, but there should be lots of spacings where the new-glider constructions shoot right through the trailing end of the previous cycle's NE salvo.
dvgrn
Moderator
 
Posts: 3151
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Half-bakery reaction with glider

Postby codeholic » July 18th, 2014, 2:39 am

Exciting! It is Lilliputian! ;)
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1128
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Half-bakery reaction with glider

Postby dvgrn » July 18th, 2014, 7:38 am

codeholic wrote:Exciting! It is Lilliputian! ;)

It's funny to think that there really isn't all that much new technology in the Half-Baked Knightship. Something like this probably would have been built well over a decade ago, long before the Gemini or even the Caterpillar spaceship -- if someone had only thought of rubbing two half-bakery reactions together with gencols...!

The edge-shooting 180-turners needed a fair amount of searching, too, of course, and maybe that idea was easier to think of after experience on the 31c/240 project. But superslow elbows or *WSS+G reactions would have been decent alternatives.

-- Sometimes I find it amusing to speculate about Conway's Life alternate history; my apologies... I'm just waiting for an archaeologist to discover a Neolithic cave painting of a glider. Or should I hope for something more impressive, like a p30 gun or a loafer? A few hundred thousand years of Stone Age Life enthusiasts playing with pebbles on flat rocks in their spare time could have come up with quite a collection of interesting discoveries.

But maybe what would be really interesting would be an unexpected digital communication found by a SETI search, with a stamp collection of all the best stuff the aliens have discovered -- including/not including a Half-Baked Knightship (delete whichever is inapplicable).
dvgrn
Moderator
 
Posts: 3151
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Half-bakery reaction with glider

Postby chris_c » July 18th, 2014, 9:03 am

dvgrn wrote:I notice the 180-turners stick out quite a bit farther than the LWSS+G mechanisms, even though there are only four of them compared to three LWSS+G. Is there any likelihood that two of the gliders in the SE can be done with the LWSS+G mechanism as well? The two pairs are different colors, so to do all four that way would need a different mechanism... but maybe there's no cheap way to invert that LWSS recipe?

Yes the 180 turners are quite fat, especially the one named H_180 which is over 100 lanes wide. You've got me thinking about alternatives... once we have one pair of gliders in the SE other gliders can be generated with the usual classic:
x = 136, y = 32, rule = B3/S23
o2bo$4bo130bo$o3bo128b2o$b4o129b2o12$112bo$112bobo$112b2o5b2o$118bo2bo
$118bobo$116b2obo$115bo2bo$115bobo$116bo2$103b2o$102bo2bo$102bobo$100b
2obo$99bo2bo$99bobo$100bo!

Unfortunately the output color is the same as the input color so this reaction is not useful for creating the B gllders from the C gliders.
dvgrn wrote:This can be done by shuffling the construction recipes so that return gliders from the 180-turners and LWSS+G are sent on an earlier scan, adjusting the initial targets accordingly.

I can't quite understand your proposal here. The thinking behind my current design was that the spaceships needed to come after the NW gliders (you can't recreate the boats until the previous boats have been used), and the targets for the 180 turners need to be further away than the targets for the NW gliders (in order to get the two NW gliders for "free"). Unless I am missing something that means the 180-turners need to be triggered before the NW gliders, so I went with the following "scan plan":
A B C D E F G H I J
0 0 0 0 0 0 0 0 0 0
. . . . . . 1 1 1 1
. . . . . . 2 2 2 2
. . . 1 1 1 3 3 3 3
1 1 1 2 2 2

(A, B, C are the glider targets, D, E, F, are LWSS targets)

Hmmm, I'm still not seeing how to get around these constraints in a cheaper way.... reads on...
dvgrn wrote:It looks as if the initial scan is a little over 60K long, so it may just barely be possible to change it around to be the last scan instead

Oh I see... interesting idea but very scary! Glider color changes on each iteration so if you want to make the first pass become the last pass of the previous iteration I think you need completely new recipes.
chris_c
 
Posts: 647
Joined: June 28th, 2014, 7:15 am

Re: Half-bakery reaction with glider

Postby dvgrn » July 18th, 2014, 9:44 am

chris_c wrote:Hmmm, I'm still not seeing how to get around these constraints in a cheaper way.... reads on...
dvgrn wrote:It looks as if the initial scan is a little over 60K long, so it may just barely be possible to change it around to be the last scan instead

Oh I see... interesting idea but very scary! Glider color changes on each iteration so if you want to make the first pass become the last pass of the previous iteration I think you need completely new recipes.

True enough. If we spend a little time hunting for narrower 180-turners, maybe we could keep this idea in mind.

For example, we could we try completing a few more of the known 180-turner recipes, but set them up so that the second scan triggers the return glider, and the third scan does some initial rebuilding. A small collection of swappable 180-turners should make it easier to match turners up with gliders from the shooting range (?).

The key idea is that there are about 40K ticks between when the last glider goes past the first rake in the shooting range, and when the return gliders get there to activate the next cycle. There are about 60K ticks before the beginning of the Cycle #2 slow salvo would actually interfere with the end of the Cycle #1 slow salvo, but it has yet to be proven that Cycle #2 construction can be successfully started while Cycle #1 gliders are still going by. But at least it should be possible to get the 40K down close to zero without anything getting too scary.
dvgrn
Moderator
 
Posts: 3151
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Half-bakery reaction with glider

Postby chris_c » July 18th, 2014, 12:15 pm

dvgrn wrote:For example, we could we try completing a few more of the known 180-turner recipes, but set them up so that the second scan triggers the return glider, and the third scan does some initial rebuilding. A small collection of swappable 180-turners should make it easier to match turners up with gliders from the shooting range (?).

From memory at least a couple of the 180-turners in my design were "close" to being completely done in 3 scans. Given this, I imagine that it is quite possible to find two pairs of compatible 180-turners that work in the way you describe (3 scans to shoot followed by 1 scan to begin clean up). I'm not volunteering to find them at the moment though :)
chris_c
 
Posts: 647
Joined: June 28th, 2014, 7:15 am

Re: Half-bakery reaction with glider

Postby calcyman » July 19th, 2014, 4:23 am

Chris Cain wrote:Here is a HBK with period 245,912 and bounding box under 33,000 square.


Well done!!! That's an efficiently-engineered knightship (henceforth abbreviated to eek!); I think to qualify as `half-baked' it must be cobbled together without any regard to elegance or minimality, as was the case for my HBK. :P
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1128
Joined: June 1st, 2009, 4:32 pm

Re: Half-bakery reaction with glider

Postby codeholic » July 29th, 2014, 6:09 am

I second the idea of distinguishing a certain spaceship and a class of spaceships, but by my foreign ear these names are too similar. Compare Gemini and Geminoid, for instance, where the difference is on the surface. Also I'm not sure if it is worth to have two distinct articles in the wiki.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1128
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Half-bakery reaction with glider

Postby dvgrn » July 29th, 2014, 6:41 am

codeholic wrote:I second the idea of distinguishing a certain spaceship and a class of spaceships, but by my foreign ear these names are too similar. Compare Gemini and Geminoid, for instance, where the difference is on the surface. Also I'm not sure if it is worth to have two distinct articles in the wiki.

I'm a little worried about that also. I can certainly roll back recent changes if the general feeling is that two separate articles are a bad idea -- or rename Chris' ship (especially if he can come up with a better name, or approve one officially).

On the other hand, I kind of like calling the big awkward ship "half-baked" -- and then not insulting the small parallel-construction version with the same term. The two HBKs are noticeably different in design, even from a distance, so it seems okay to me to include an image of each one on the wiki. Guess I'll just wait for a few more votes to come in.

I tried adding a separate half-bakery knightship page mostly because of the attribution problem. It didn't seem right to leave the HBK family represented by an image of the huge serial-construction model, once a nice efficient parallel version was available. But changing the image and the statistics would mean also changing the discoverer from "Adam P. Goucher" to "Chris Cain", and that seemed sort of okay but not really quite right, either.

I sent a question to Nathaniel about supporting macrocell files as a pattern file type, since the smaller HBK is under 50K in .mc.gz and 112K in plain .mc, smaller than the RLE of some other patterns on the wiki.
dvgrn
Moderator
 
Posts: 3151
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Half-bakery reaction with glider

Postby codeholic » July 29th, 2014, 7:58 am

dvgrn wrote:I tried adding a separate half-bakery knightship page mostly because of the attribution problem.

I don't really see it as a problem. We can make a dedicated section for each spaceship and put a spaceship infobox inside each section.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1128
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Half-bakery reaction with glider

Postby dvgrn » July 29th, 2014, 9:58 am

codeholic wrote:I don't really see it as a problem. We can make a dedicated section for each spaceship and put a spaceship infobox inside each section.

Yeah, that probably makes more sense. I'll try to find time to rework "half-baked knightship" in a couple of days, if no one else gets to it first, and maybe redirect "half-bakery knightship" to it.

I think I got all the right numbers and links into the Spaceship tables, but it would be good to have some fresh eyes to double-check. I adjusted things a little, so that Gemini 2 and 3 are in the same category as the original Gemini, and the two HBKs are also in the same category, making sixteen spaceships/families in all.

It seems odd that it's still not very easy to find minimum populations for the Gemini variants, by the way. It's a trivial script, but takes too long to run on my no-longer-new laptop. Luckily the HBKs are much more predictable... though it turned out the table wasn't quite right about them, either -- there's a phase of the G+HB collision that goes down to 18 cells.
dvgrn
Moderator
 
Posts: 3151
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Half-bakery reaction with glider

Postby chris_c » July 29th, 2014, 6:46 pm

I was just reviewing this thread and then I realised you have created a new page called "Parallel HBK" on the wiki. That all seems very reasonable to me. Thanks for all of your efforts.
chris_c
 
Posts: 647
Joined: June 28th, 2014, 7:15 am

Previous

Return to Patterns

Who is online

Users browsing this forum: No registered users and 5 guests