Spaceship Discussion Thread

[Entity Valkyrie 2]

Based on Caterloopilar?

[wwei23]

Well, it's best if the period is a factor of 96 so that it works well with Corderships.
EDIT: From JSeeker, an even longer c/4 partial:

Code: Select all

.O.O..
.O....
.O....
...OO.
.....O
...O..
...OOO
...OO.
.O.OO.
.O.OO.
O.....
OOO...
...O..
O.O...
O..O..
.OOO..
..OO..
..O.O.
..O.O.
......
..O...
......
.OO...
..O...
.O.O..
.O....
OO.O.O
.OO.O.
....O.
...OOO
...OOO
......

[dvgrn]

Based on Caterloopilar?

Sure -- that would certainly allow for a lower-period rake than an Orthogonoid-type design.

[Entity Valkyrie 2]

But I don't think that period 48 is possible at the moment. (Switchwave extender)

[wwei23]

But I don't think that period 48 is possible at the moment. (Switchwave extender)

96 would also work.
On the other hand, the unit tile for switchwave is 27 by 27 if I remember correctly, we might be able to get away with period 768 if that was the case.

[MathAndCode]

Has anyone followed my advice to search for spaceships with speeds between c/2 and c/3? Here are some forward movement mechanisms in that range.

2c/5:

Code: Select all

x = 16, y = 13, rule = B3/S23
6bo$2bo4bo$b2o3bo$obo4b2o$o5bobo$bo5bob2o$5bob2o$5bobo$5bo$6b2o$6b2o6b2o$11b2ob2o$13bo!

Code: Select all

x = 6, y = 9, rule = B3/S23
2b4o$bo3bo$o3b2o$3bo$o$3bo$o3b2o$bo3bo$2b4o!

Code: Select all

x = 8, y = 10, rule = B3/S23
5b2o$5b3o$bo3b2o$3ob3o$5b2o$b3ob2o$2bo2bo2$3bo2bo$4b3o!

4c/11 (first similar to here):

Code: Select all

x = 5, y = 6, rule = B3/S23
2b3o$2bobo$bo2bo$bobo$b3o$o!

Code: Select all

x = 7, y = 8, rule = B3/S23
2b3o$2bo2bo$2o$o2bo2bo$4ob2o$2bob3o$4b2o$4bo!

5c/12:

Code: Select all

x = 15, y = 12, rule = B3/S23
6bo$2bo3bo$3bobo7b2o$9b3o$6bo4bob2o$o3b2ob3o3bo$o5b2ob2ob2o$2o4bobobo$3b7o$6b2obo$8bo$7b3o!

9c/21:

Code: Select all

x = 7, y = 17, rule = B3/S23
3bo$2bobo$bo3bo$4bo2$o2bo$bo$3b2o2$2bo2b2o$6bo$6bo$bo3bo$bob2o$obo$bo$bo!

3c/7:

Code: Select all

x = 10, y = 15, rule = B3/S23
4b3o$4bo2bo$4bob2o$4bob2o$4b2o$2o4bo$2b3ob3o$6bo2bo$7bobo$7b2o$3b5o$3b4obo$2bo5bo$3b5o$3b2o!

4c/9:

Code: Select all

x = 9, y = 15, rule = B3/S23
4bo$3b3o$3bob2o$7bo$o2b2o$o2b2o3bo$ob2obo$6b3o$6b2o2$6bo$b5obo$5bobo$bob2obo$2bo!

Also, the right side of this pattern through generation 18 might be useful for an oblique spaceship.

Code: Select all

x = 11, y = 13, rule = B3/S23
3b2o$3b2o2$10bo$b2o5b2o$o2bob2o3bo$bobo2bob2o$2bo4bo$6bo$5bo$5b2o$5b2o$6bo!

In addition, while searching for forward movement mechanisms between c/2 and c/3, I found one at 2c/7.

Code: Select all

x = 4, y = 4, rule = B3/S23
b2o$2b2o$3o$o!

[yujh]

Are there any c/12 orthogonal glider rakes (forward and backward)?

Are there any elemantary c/12 orthorgonal ships?

[AforAmpere]

Has anyone followed my advice to search for spaceships with speeds between c/2 and c/3?

You are very far from the first to suggest that. If you look earlier in this thread, there are tons of wide searches for those exact speeds, done at widths that make the searches take weeks to months.

[wwei23]

Code: Select all

x = 6, y = 9, rule = B3/S23
2b4o$bo3bo$o3b2o$3bo$o$3bo$o3b2o$bo3bo$2b4o!

I'm throwing this one into JLS. It looks the most promising.
Edit: JLS isn't done yet.

AEDAE2C8-FAF4-4F11-BEB3-24CB3911BF80.jpeg (3.54 MiB) Viewed 4331 times

[MathAndCode]

Has anyone followed my advice to search for spaceships with speeds between c/2 and c/3?

You are very far from the first to suggest that. If you look earlier in this thread, there are tons of wide searches for those exact speeds, done at widths that make the searches take weeks to months.

Then how do we not have more spaceships at those speeds?
Also, I just noticed that the 2c/7 example that I posted also has a 2c/5 downward movement mechanism from generation 12 to generation 20.

Code: Select all

x = 6, y = 9, rule = B3/S23
2b4o$bo3bo$o3b2o$3bo$o$3bo$o3b2o$bo3bo$2b4o!

I'm throwing this one into JLS. It looks the most promising.

Thank you.

[dvgrn]

Then how do we not have more spaceships at those speeds?

We have a lot of 2c/5s. How many do you want?

We don't have a lot of spaceships with speeds c/7 or above, because every time you add one tick to the period, the search difficulty increases exponentially. It's just plain harder to find a complete period-7 spaceship than to find a complete period-5 one, by several orders of magnitude.

So... your period 11, 12, and 21 suggestions aren't going to be too interesting to most people, because they're so incredibly far beyond what it's practical to search for. A period-12 spaceship might actually show up using current search technology sometime before the Sun burns out, but for p21 the odds would be heavily in favor of the Sun winning the race.

However, please feel free to try some period 11/12/21/whatever searches! It's very helpful for building intuition on the difficulty of these problems, to run p3 and p4 searches and get results back just about instantly, run p5 searches and get results pretty quick, run p6 searches and have to wait a while, and run p7 searches for months and be lucky to get anything at all. It's also a fine idea to write new search programs, if you think you can improve on existing ones.

Just be warned that there are lots of ideas floating around about better search programs. Writing a lot of hand-waving description about an idea is not a useful way to prove that it's a good idea. The most likely way for an idea to get much attention around here is if you write the search program and use it to find something new.

Here's a link to Sokwe's LifeWiki table of spaceship searches already done or in progress.

[wwei23]

It's very helpful for building intuition on the difficulty of these problems, to run p3 and p4 searches and get results back just about instantly, run p5 searches and get results pretty quick, run p6 searches and have to wait a while, and run p7 searches for months and be lucky to get anything at all. It's also a fine idea to write new search programs, if you think you can improve on existing ones.

I'd like to disagree with that. I don't get P5 results "pretty quick", and P4 is definitely not instant.

[dvgrn]

I'd like to disagree with that. I don't get P5 results "pretty quick", and P4 is definitely not instant. :P

It's all a matter of perspective, I guess. Any search that gets results in less than a day is "pretty quick" in my book, and less than an hour is "just about instant" -- at least compared to the Sun-will-burn-out-first searches that we're talking about for higher periods.

[MathAndCode]

Then how do we not have more spaceships at those speeds?

We have a lot of 2c/5s. How many do you want?

Yes, but there is only one other speed between c/2 and c/3 that we have spaceships for, and that speed only has one elementary spaceship, which is rather large.

We don't have a lot of spaceships with speeds c/7 or above, because every time you add one tick to the period, the search difficulty increases exponentially. It's just plain harder to find a complete period-7 spaceship than to find a complete period-5 one, by several orders of magnitude.

But then how do c/7 orthogonal and 2c/7 orthogonal each have more elementary spaceships than 3c/7 orthogonal, all of which are smaller than 3c/7 orthogonal's only known elementary spaceship? Also, we have many p96 (and multiples) diagonal spaceships, largely thanks to wwei23.
Also, why does the search difficulty increase exponentially and not linearly (or possibly quadratically) as a function of period?

[dvgrn]

But then how do c/7 orthogonal and 2c/7 orthogonal each have more elementary spaceships than 3c/7 orthogonal, all of which are smaller than 3c/7 orthogonal's only known elementary spaceship?

Why is that surprising, exactly? These are all period-7 searches, so they're about the same amount of work for a search utility. But Life patterns on average tend to stay roughly in the same place and maybe wobble around a bit. Things that keep themselves going at a speed very close to the maximum c/2 spaceship speed limit are apparently rarer than things that move at a more reasonable speed -- more options to work with.

Also, we have many p96 (and multiples) diagonal spaceships, largely thanks to wwei23.

Thanks mostly to Dean Hickerson and David Bell, I'd say, who built dozens or hundreds of switch-engine-based spaceships back in the 1990s.

I'm not sure what this has to do with anything. When there's a small cheap object that travels at some particular speed, then it's naturally much easier to build things that go that speed. This is completely independent of the question of how hard it is to do searches starting from a blank slate, for elementary spaceships of that period.

Also, why does the search difficulty increase exponentially and not linearly (or possibly quadratically) as a function of period?

I think we've been over this ground before. It's very hard to imagine a search utility clever enough to find its way through an exponentially larger search space in only a linear or quadratic amount of time.

The search space is exponentially larger for a fairly simple reason: when you go from let's say c/7 to c/8, there isn't really anything in the search utility that you're "just adding 1" to. What you're adding is a whole MxN patch of additional cells whose states you don't know. If you're hunting for something loafer-sized, you had 9x9x7 = 567 unknown cells to fill in. Now at c/8 you suddenly have 81 more unknown cells, each of which can be either ON or OFF. Your search space didn't just get 81 more possibilities added, it got 2^81 times bigger.

Now, clearly there are all kinds of shortcuts that search utilities use, so that we're a long way from just enumerating 2^567 cell arrangements, vs. 2^(567+81) cell arrangements, and checking to see if any of them happen to be c/7 or c/8 spaceships. But the size of the search space is still a good basic measurement to look at. If you think you can describe a search method that reduces that exponential size increase down to something merely linear or quadratic, then ... well, you'll probably find out where your theory is wrong when you get to writing actual code.

Or possibly you'll have proved that P = NP, and everyone will be very very excited and amazed. Actually finding an elementary spaceship with a period higher than 10 is a hugely impressive feat of mathematical engineering, code optimization, reading tea leaves, or however you manage do it. There's been a lot of talking about doing this over the last decade or two, but that's not nearly as impressive.

[wwei23]

I think we've been over this ground before. It's very hard to imagine a search utility clever enough to find its way through an exponentially larger search space in only a linear or quadratic amount of time.

How would increasing the period affect anything?
If I was searching for a period-137 spaceship in a 10 by 10 bounding box, I have the exact same number of ways to set the cells on or off as a period-2 spaceship in a 10 by 10 bounding box. Therefore, the search space is still the same size.

[bubblegum]

I think we've been over this ground before. It's very hard to imagine a search utility clever enough to find its way through an exponentially larger search space in only a linear or quadratic amount of time.

How would increasing the period affect anything?
If I was searching for a period-137 spaceship in a 10 by 10 bounding box, I have the exact same number of ways to set the cells on or off as a period-2 spaceship in a 10 by 10 bounding box. Therefore, the search space is still the same size.

I really have no idea but you can always fire up a search utility and check.

[dvgrn]

How would increasing the period affect anything?
If I was searching for a period-137 spaceship in a 10 by 10 bounding box, I have the exact same number of ways to set the cells on or off as a period-2 spaceship in a 10 by 10 bounding box. Therefore, the search space is still the same size.

Sure, if you're doing a brute-force search of possibilities for just one phase of spaceship, that's absolutely true.

But if you try to do that brute-force enumeration on a 10x10 bounding box, you have 2^95-ish different patterns to run for 137 ticks each. There you really will have just a linear increase in difficulty if you bump up the target speed to 138 instead of 137. But on the other hand, if you try to run 2^95 patterns for 137 ticks each, you really won't be done by the time the Sun burns out.

And you might well not find anything more interesting than the loafer. So that seems like a waste of an awful lot of time.

Brute-force is not really viable for searches (that produce actual interesting results) except for very small sizes or special situations. Existing search utilities build a model of all phases of a spaceship, not just one phase, and then apply all kinds of clever logic to reduce the number of possibilities down to something much more tractable than 2^95. "If this cell is ON in this phase, than that cell and this other cell can't possibly be on in the next phase, ..." Every time a cell goes from unknown to known, you cut the remaining search space (in that branch of the search) in half -- and if you prove that a cell can't be either ON or OFF, then you can prune off that whole branch of the tree and backtrack to try your next option.

For that type of search -- which is pretty much what has found all the elementary spaceships that we know about that don't show up in random soup -- increasing the period by one adds some non-trivial number N of unknown cells to the spacetime search region, and therefore multiplies the size of the search space by 2^N... or rather, some tiny fraction of 2^N, thanks to all the clever shortcuts and optimizations, but you're still multiplying the size of the search space by some number, not just adding a constant to it.

Again, anyone is welcome to prove that all of the above is completely wrong -- but don't do it by arguing about it, do it by writing a better search program and finding something new with it.

Existing search utilities build a model of all phases of a spaceship, not just one phase, and then apply all kinds of clever logic to reduce the number of possibilities down to something much more tractable than 2^95.

On the other hand, that has its own downsides as well. My JSeeker search program is way slower than other search programs, but it only requires ONE phase of the spaceship to be at the width you're searching at. For example, it can find the LWSS at width 4.

Exactly right. What happens at small sizes is not really relevant to what works when you're trying really hard to push the boundaries of the field, and discover something new in search space that hasn't been looked at before. It's not clear what JSeeker is going to be able to find that other search utilities can't find as well or faster, just by searching much more efficiently at a slightly higher width setting.

[wwei23]

Existing search utilities build a model of all phases of a spaceship, not just one phase, and then apply all kinds of clever logic to reduce the number of possibilities down to something much more tractable than 2^95.

On the other hand, that has its own downsides as well. My JSeeker search program is way slower than other search programs, but it only requires ONE phase of the spaceship to be at the width you're searching at. For example, it can find the LWSS at width 4.

[HartmutHolzwart]

Dear Weiwei,

1) you'll hardly find too much spaceships in the 10x10 box.
2) You'll quickly get into combinatorial explosion if you increase searchspace
3) Current search programs thus try to restrict the search space by making clever use of the restriction that the pattern will repeat (with an offset) after n generations. The larger the n the less efficient are the restrictions. Generally they restrict width (or height) and number of generations and then work though the strip until the find a solution. This strip is not limited in theory in the other dimension
4) It is more efficient to develop the partial patterns in all generations in parallel (the exact optimal search strategy depends on the velocity), but this quickly breaks down if you increase the number of generations

[wwei23]

1) you'll hardly find too much spaceships in the 10x10 box.
2) You'll quickly get into combinatorial explosion if you increase searchspace
3) Current search programs thus try to restrict the search space by making clever use of the restriction that the pattern will repeat (with an offset) after n generations. The larger the n the less efficient are the restrictions. Generally they restrict width (or height) and number of generations and then work though the strip until the find a solution. This strip is not limited in theory in the other dimension
4) It is more efficient to develop the partial patterns in all generations in parallel (the exact optimal search strategy depends on the velocity), but this quickly breaks down if you increase the number of generations

1. 10 by 10 was just an example.
2. I agree.
3. I have no idea how to implement that so I just wrote the best algorithm that I actually knew how to write, which works by looking at cells with exactly one unknown cell that could affect how they evolve after the period, and trying to set unknown cells.
4. Like I said, I have no idea how to implement this.

Alas, the irony. By increasing the search space into the time dimension, you actually narrow it down.

[MathAndCode]

Brute-force is not really viable for searches (that produce actual interesting results) except for very small sizes or special situations. Existing search utilities build a model of all phases of a spaceship, not just one phase, and then apply all kinds of clever logic to reduce the number of possibilities down to something much more tractable than 2^95. "If this cell is ON in this phase, than that cell and this other cell can't possibly be on in the next phase, ..." Every time a cell goes from unknown to known, you cut the remaining search space (in that branch of the search) in half -- and if you prove that a cell can't be either ON or OFF, then you can prune off that whole branch of the tree and backtrack to try your next option.

For that type of search -- which is pretty much what has found all the elementary spaceships that we know about that don't show up in random soup -- increasing the period by one adds some non-trivial number N of unknown cells to the spacetime search region, and therefore multiplies the size of the search space by 2^N... or rather, some tiny fraction of 2^N, thanks to all the clever shortcuts and optimizations, but you're still multiplying the size of the search space by some number, not just adding a constant to it.

But wouldn't the pruning time be linear? If there are 2¹⁰⁰ or so times as many possibilities, then each time that a cell's state becomes known or a branch is eliminated, then about 2¹⁰⁰ many possibilities will be discarded on average.
Also, the computational power required for any method that is cleverer than a brute force method should be bounded by the computational power for the brute force method, which is linear as a function of period.

It is more efficient to develop the partial patterns in all generations in parallel (the exact optimal search strategy depends on the velocity), but this quickly breaks down if you increase the number of generations

I can't see any benefit to that unless the search program tries to use partials of the same speed to stabilize each other, which I doubt because that could violate the width constraint.

[calcyman]

In its smallest phase, Sir Robin consists of 282 cells in a 31-by-79 box.

Suffice it to say, my search program didn't trawl through all (2449 choose 282) = 1816542579891561316295603424938029274802095354130525469758394163343550228141988777491556527148757232815365841439814075524609380448143349835366086222294538469451778290096666558439353121684851772080924374971250875587196201159927343699373816102263935421483779586294694267983046787036177074919515001221009282754607956760907861537317467526824613979214860525827624782038843939722869568 different ways to populate a 31-by-79 box with 282 live cells and run each of these patterns for 6 generations; this would have taken much longer than eight hours.

Instead, it does something more akin to what Dave and Hartmut have been suggesting: its search space consists of an interleaving of all phases, and it tries to find a solution to the resulting set of Boolean equations using a bunch of heuristics to guide the search.

I'd recommend reading David Eppstein's https://arxiv.org/abs/cs/0004003 article, since many of the ideas in that paper are incorporated into modern spaceship search programs.

[wwei23]

this would have taken much longer than eight hours.

Wait, you found Sir Robin in only eight hours?

[calcyman]

this would have taken much longer than eight hours.

Wait, you found Sir Robin in only eight hours?

Yes, eight hours after feeding Tom Rokicki's partial as input to the original ikpx.