Idea for new spaceship search program

[Rhombic]

Let's accept it. Most "generate-previous cell row" spaceship search programs end up with massive 690x6 ships tha look more like a stupidly long self-sustained reaction.

After reading about those "stator" cells for spaceships, I realised that stator cells and those that last for >N generations (N = period), reappear after being translated (a,b) in a (a,b)c/N spaceship - by definition.
Obviously, the environment around under the same environments.these cells once translated is the same, and for a given spaceship speed, it can be expected for these cells to be translated (a,b) in N generations rereating the same environment.

A Stator-Translation-Assisted Retro Synthesis search program would allow to find possible combinations of cells that die off at the edges to regenerate the same environment around the next cell (by adding cells to an initial stator input). This might help to find C1-symmetry spaceships.

Ideas? Sorry for poor wording.

[Rhombic]

Just to complement the poorly worded description:

- Assume cell c to be stable throughout a period T of an xqT spaceship.
- From the speed, determine c', the equivalent cell that becomes c in the next period of the spaceship
- Generate environment around c so that c survives into generation 1 (out of T) -- define first environment as E1
- Assume parent to c' with same environment as E1' to coexist in generation T-1
- Repeat

This is a rough idea of the structure of the algorithm, as you can tell, but the fundamental part is to simultaneously optimise the forward evolution keeping cell c alive as well as the parent generation for cell c'.

I think it's straightforward enough to give it a go. Asymmetric (C1) spaceships should be predicted very easily. Instead of huge 6x182 spaceships, more 5x6ish spaceships could be found in this way, because it is not dependent on row-evolution scripting.
This also improves the search for knightships.

[dvgrn]

This is a rough idea of the structure of the algorithm, as you can tell, but the fundamental part is to simultaneously optimise the forward evolution keeping cell c alive as well as the parent generation for cell c'.

I think it's straightforward enough to give it a go...

Can't say definitely that this wouldn't work, because I don't understand how the optimizing algorithm would work in any detail.

But it does seem as if this idea is still firmly stuck in the "hand-waving" stage -- the stage where all new ideas look good because nobody has tried to implement the details in a working search utility yet.

Can you be a little more specific? In what way would this algorithm be significantly different from a lifesrc/WLS/JLS search where you set the period to N and the offset to (x,y), and then choose a specific cell in the center of the search region (let's say) and set it to ON in every one of the N phases, and then pick an appropriate sort order?

Asymmetric (C1) spaceships should be predicted very easily. Instead of huge 6x182 spaceships, more 5x6ish spaceships could be found in this way, because it is not dependent on row-evolution scripting.

If there were really 5x6ish or even 8x8ish spaceships out there at any reasonable speed, with the "stator cell" constraint you specified, then I think WLS/JLS could be set up to find them without too much trouble.

The problem shows up when the smallest spaceship is something like an asymmetric 15x15 or 20x20. That might perfectly well be true for 3c/7, for example, where we know about the mirror-symmetric 27x137 spaghetti monster because it's the only thing within reach of a search (so far). WLS/JLS can't get anywhere near 20x20 asymmetric, with or without a stator-cell constraint, because the search space isn't sufficiently constrained. Without more constraints you don't know where to look first, and there isn't enough time before the Sun burns out to look everywhere.

-- Yeah, clearly you know all this already. The "6x182" and "5x6" numbers are a little too extreme, but you're looking for a solution to the right problem, and maybe you're looking in the right place. Really the only way to tell is to write a working search utility and run it until it finds something. Just not sure that your description amounts to a spec for a new workable search utility yet -- it seems like it might be a disguised WLS/JLS...?

It might be worth doing a test against known technology here. Looks like there are at least five cells along the front edge of a loafer that would count as "stator cells" according to your definition. If you can set up a search with the ON-cell constraints described above, and it finds a loafer in a reasonable amount of time, then maybe the same approach could be used to help WLS/JLS find a small c/8 or whatever.

If your algorithm will be significantly different from WLS/JLS and you can show that it finds the loafer a whole lot faster, then you'll really have something!

[Rhombic]

dvgrn,

Unfortunately, this is beyond my programming skills -entirely-. The idea with this is not to set a cell in the middle as a stator, but to set the cell that is analysed as one. This should allow much more flexibility, because it can be interpreted as a wave from the final position (where the target cell starts at generation T) to the initial position (generation 0).
The sparks would be a way to kill the wave at one end and the front bit would be a (non-c) growing portion that creates the cell within its environment (as studied with the initial cell) at generation T. It basically optimises that, and I can tell it's not the same idea in terms of its basic script form as the WLS or JLS, as far as I know.

[dvgrn]

The idea with this is not to set a cell in the middle as a stator, but to set the cell that is analysed as one. This should allow much more flexibility, because it can be interpreted as a wave from the final position (where the target cell starts at generation T) to the initial position (generation 0).

Hmm, okay. In that case, whereas I thought maybe I kind of understood the idea before, now I just have to admit I have no idea. This "set the cell that is analysed [as a stator]" just isn't specific enough for my simple mind, I think.

My suggestion didn't involve programming anything. Based on my previous idea of what your algorithm was about, it seemed possible to set up WLS/JLS to specify leaving a particular cell ON for an entire cycle, and also to start a search from generation T and work backwards to generation 0.

The sparks would be a way to kill the wave at one end and the front bit would be a (non-c) growing portion that creates the cell within its environment (as studied with the initial cell) at generation T. It basically optimises that, and I can tell it's not the same idea in terms of its basic script form as the WLS or JLS, as far as I know.

How much searching have you done with WLS/JLS? I just read through all of your algorithm descriptions again, and I don't see -- or at least, I don't understand -- any specifics about how the optimization would work differently from what WLS/JLS do to enumerate possible cell combinations and eliminate impossible ones. It depends a lot on what your search settings are; for example, you can choose to enumerate all cells in one generation, then move to an adjacent phase, or you can choose to try to build progressively larger self-consistent patches in all generations simultaneously.

The part about c and c' in this --

the fundamental part is to simultaneously optimise the forward evolution keeping cell c alive as well as the parent generation for cell c'.

-- is done automatically in WLS/JLS, because there is no such thing as a c' cell separate from c -- both are represented by the same set of N bits. Is there a reason to treat c and c' as different cells? Seems like for a successful search they have to be identical in every way, which is what WLS/JLS assume.

Could you maybe patch up the errors in your first post? There are currently some mysterious sentence fragments there. Also, maybe a specific example would help me understand your idea...? The six yellow cells in this loafer

Code: Select all

x = 9, y = 9, rule = LifeHistory
2A4.AE$3A.2A2.E$5.A.E$6.A$A$3A$3.E$.AE$.E!

seems like they're the kind of thing you're talking about, in that they stay ON for an entire period of the spaceship. How would a search start from one of those cells and proceed more efficiently than WLS/JLS could, by enumerating combinations of neighbor cells and discarding ones that cause contradictions?

[Rhombic]

True, treating c' and c in the same way is obviously better, I just separated them for the explanation.

Could you maybe patch up the errors in your first post? There are currently some mysterious sentence fragments there. Also, maybe a specific example would help me understand your idea...? The six yellow cells in this loafer

Code: Select all

x = 9, y = 9, rule = LifeHistory
2A4.AE$3A.2A2.E$5.A.E$6.A$A$3A$3.E$.AE$.E!

seems like they're the kind of thing you're talking about, in that they stay ON for an entire period of the spaceship. How would a search start from one of those cells and proceed more efficiently than WLS/JLS could, by enumerating combinations of neighbor cells and discarding ones that cause contradictions?

So for the bottom one, let the environment be 2a (in fact, the position of the 2a matters for spaceships due to orientation). The formation of the cell for the next period would be (after checking other environments) by 3a, and would actually happen in generation 2 - this cell can die later on even if in this particular case it doesn't, the important thing is that it ends up being the same cell in the same environment by the end of the period. For c to survive into two generations. The script would keep c alive by keeping a 2k environment and kills it in generation 7 by leaving a 1c environment in generation 6.*

*I've over-simplified the mechanism, since the only way to do this over 7 generations is via a self-sustained reaction from the top (otherwise, the loafer would be a 6-cell spaceship).

To be fair, it does sound a lot like WLS, but, as far as I know, WLS does not account for the same sustained environment and branches out quicker leading to a slower search?

[dvgrn]

To be fair, it does sound a lot like WLS, but, as far as I know, WLS does not account for the same sustained environment and branches out quicker leading to a slower search?

Depends on how you set up the search. I'm not sure I understand everything else you wrote here -- the 2a, 3a, 2k, 1c are the shapes of the neighborhoods using Hensel's notation, but I'm not clear on why something must happen in generation 2 -- partly because you haven't specified if we're counting from generation 0 or generation 1.

Pictures of all 7 generations might help me out a lot here, with helpful boxes and arrows and labels and suchlike.

Anyway, WLS/JLS doesn't ordinarily account for the same sustained environment, so it ordinarily searches a lot more branches that don't include a static cell or cells. However, you can really easily set up a search with the stator-cell condition, for any period and speed you want to try -- just turn on the same cell in each phase before you start searching. Takes about five seconds to set up that condition; there's even a helpful modifier key to turn on the same cell in all generations.

In that case, WLS/JLS automatically reduces its search tree, and doesn't even look at any neighborhood combinations that contradict the assumption that those cells are on. I think that that might well amount to "accounting for the same sustained environment" with the same level of efficiency as your proposal, in which case there's no need to re-invent the wheel.

Just try some searches with a pre-set ON cell in every phase -- it's not that hard! (And for all I know, it might be a good approach for reducing the search space and finding new spaceships. You might turn up a new 10x10 period 8 knightship that way.) (But probably not...)

-- I can't contribute any more to this thread, because I've already said a good bit more than I actually know. Can someone with a few months or years more of practical spaceship-searching experience weigh in here and confirm or deny my vague summaries of WLS/JLS behavior?

[Rhombic]

I greatly appreciate all your input, it has helped me think through it in a more detailed way.

For all I know, it seems to me that after all it seems more like an extra functionality to WLS more than anything else, because as you said, WLS already allows similar things to be done.
My only major issue was to do with the excessive branching of the search program instead of focusing on allowing certain combinations to remain stable over a number of generations, which is the more intuitive way to do it.

[Rhombic]

Hello.
WLS consistently calculates the spaceship gradually though, without starting from the stator cell itself. Wouldn't it be more interesting to start from there? If this is possible, how can it be done?

[dvgrn]

Hello.
WLS consistently calculates the spaceship gradually though, without starting from the stator cell itself. Wouldn't it be more interesting to start from there? If this is possible, how can it be done?

Just set up the search that way, and WLS will run it that way.

For example, start with a cell ON in all phases at the leading edge of (what you know will become) a loafer -- set all cells left of that cell to OFF, pick a bounding box size big enough to contain a loafer, turn on OFF cells all around the edges in all phases, let WLS run and see if you get anything in a reasonable amount of time.