A new spaceship search approach

For scripts to aid with computation or simulation in cellular automata.
AforAmpere
Posts: 1155
Joined: July 1st, 2016, 3:58 pm

Re: A new spaceship search approach

Post by AforAmpere » January 3rd, 2020, 11:33 pm

According to a comment in the .sh file:
"For an exhaustive search re-run the search with seedcolumn changed to all the values from 00 to the margin."

I tested with both your and my starts and all seedcolumns from 00 to 09 for a margin = 9 odd-symmetric search, and nothing came up. Maybe something's wrong on my end, but I don't see why that wouldn't work. I do think that different starts, even if not intentionally, do havee somee eeffect on the space searched. For instance, every single speed I searched with starts in the 0,0,1,0,2,0,3,0...n,0 pattern had the ship not move past the leftmost column until the generation n+2. There were no partials with different movement patterns.

On a different note, I used the starts for the built-in weekender search, but at width 9, and it actually did end up being faster than qfind, at a bit under 13 minutes. For some reason the file for the weekender search was at width 11 instead of 9.
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 4th, 2020, 12:08 am

AforAmpere wrote:
January 3rd, 2020, 11:33 pm
According to a comment in the .sh file:
"For an exhaustive search re-run the search with seedcolumn changed to all the values from 00 to the margin."

I tested with both your and my starts and all seedcolumns from 00 to 09 for a margin = 9 odd-symmetric search, and nothing came up. Maybe something's wrong on my end, but I don't see why that wouldn't work.
I don't know why that wouldn't work either. I guess we'll have to wait for Andrew's input.
AforAmpere wrote:
January 3rd, 2020, 11:33 pm
On a different note, I used the starts for the built-in weekender search, but at width 9, and it actually did end up being faster than qfind, at a bit under 13 minutes. For some reason the file for the weekender search was at width 11 instead of 9.
That sounds more reasonable. I wonder how it does on searches for slower spaceships (e.g., c/6 or c/7). I expect the memory use and time will be significantly more for c/7 than for 2c/7.
-Matthias Merzenich

HartmutHolzwart
Posts: 520
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: A new spaceship search approach

Post by HartmutHolzwart » January 4th, 2020, 9:58 am

mscibing wrote:
January 2nd, 2020, 10:03 pm
HartmutHolzwart wrote:
January 2nd, 2020, 12:55 pm
Would it be possible to search for ships with two lines of on cells in the middle?
Just added an option for doing that.

3c/7 partial (it didn't get very far):

Code: Select all

x = 31, y = 12, rule = B3/S23
11bo7bo$10bobo5bobo$9bo3bo3bo3bo$8bo4bo3bo4bo$11b4ob4o$5b2o4bo2bobo2bo
4b2o$3bo2b2o6bobo6b2o2bo$2b2o3bobo3b2ob2o3bobo3b2o$b5o2b2ob2obobob2ob
2o2b5o$3o4bobo2bobobobo2bobo4b3o$2o3bo6bobobobo6bo3b2o$3b2o5bobobobobo
bo5b2o!
Could you give c/5 or 2c/5 a try? Or c/6?

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 4th, 2020, 11:21 pm

AforAmpere wrote:
January 3rd, 2020, 11:33 pm
I do think that different starts, even if not intentionally, do havee somee eeffect on the space searched. For instance, every single speed I searched with starts in the 0,0,1,0,2,0,3,0...n,0 pattern had the ship not move past the leftmost column until the generation n+2. There were no partials with different movement patterns.
Sorry I think this is something I ran into and then completely forgot about. The idea with seeding is to specify something about the first row of the spaceship. Rows before the first row are blank, and rows after the first row should be unspecified except for the midline and margins. But before or after are before and after in the shifted grid as described here, not before and after in the row search order. For some patterns of starts the two concepts of before and after match up, and for others the rows can jump around a bit as the search progresses.
So for a 0,0,1,0,2,0,3,0...n,0 pattern it should still be possible to search for ships, but for anything other than 1c/p ships the seed pattern would need to be adjusted to match up with the right concept of before and after. It's not really worth it; it's best to just use starts where the search rows move monotonically toward the tail.
I think the way I've set up the starts the partial shown will always be for the phase where the spaceship has advanced the furthest forward. So it will have just advanced and won't be advancing again in the next generation. The movement patterns of the partials should be similar, but not necessarily all identical; for instance the weekender falls back and not all the partials for that velocity do. But for 2c/7 partials that lead with a pre traffic-light, it will always be the same phase of the pre traffic-light shown.
Velocities where gcd(k,p)≠1 are going to be more complicated, I'm not worrying about them yet as I'm going to need a scheme to throw out lower-period spacehips anyway.
-- Andrew Wade

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 5th, 2020, 8:50 pm

Is there an easy way to set up a complete search for a desired speed at a specific width? For example, how would one set up the 2c/5 search that AforAmpere was trying to run?

Edit: how well does this program handle a c/6 width-19 odd-symmetric search? It should find the following spaceship:

Code: Select all

x = 17, y = 40, rule = B3/S23
4b2o5b2o$5bo5bo$3bobo5bobo$3bo9bo$b2o3bo3bo3b2o$2b2o2b2ob2o2b2o$3bo3bo
bo3bo$6b2ob2o$7bobo$3bob3ob3obo$2ob2o7b2ob2o$b4o2bobo2b4o$5bobobobo2$
4bo2b3o2bo2$2b4obobob4o$2b6ob6o$4b2o5b2o$2bo2bo5bo2bo2$2b3o7b3o2$o15bo
$2o13b2o$2o13b2o$b4o7b4o$5bo5bo$4bo7bo2$b3o9b3o3$b3o9b3o$4b2o5b2o$3b2o
2b3o2b2o$3o2b2obob2o2b3o$8bo$7bobo$7bobo!
How much memory does it take? How long does it take? I am curious to see how fast this program is for slower speeds. Another possible test is c/7 width-19 odd-symmetric, which should also find a ship. I don't know if there is a shorter ship than this one:

Code: Select all

x = 17, y = 96, rule = B3/S23
5b2o3b2o$3b2o2bobo2b2o2$7bobo$2bo4bobo4bo$2bo3bo3bo3bo$2bo2bo5bo2bo2$
2bo11bo$2bo2b2o3b2o2bo$bo3b2o3b2o3bo$2bo2bobobobo2bo$2b2o3bobo3b2o$5bo
bobobo$5bobobobo$4b2obobob2o$7bobo$6b2ob2o3$8bo$4bob2ob2obo$4b2obobob
2o$3bob2obob2obo$4bo7bo$4bo7bo$2b2o3b3o3b2o$2bo11bo$b2o11b2o$8bo$o2b3o
5b3o2bo$bo13bo2$5bo5bo$5b2obob2o$b4o7b4o$b3o2b5o2b3o$5bo5bo$b2ob3obob
3ob2o$2bo2bo5bo2bo$2bo11bo2$3bo4bo4bo$4b2o5b2o$4b2o5b2o2$2bo3bo3bo3bo$
bo4bo3bo4bo$b3obo5bob3o3$4bo7bo$3b2o7b2o$4bo7bo$2b3o7b3o$bobo9bobo2$b
3o9b3o$2bo11bo$2b3o7b3o3$3bo9bo$b2obo7bob2o$bo3bo5bo3bo$3obo7bob3o$3b
2o7b2o$bob2o7b2obo$2b3o7b3o$4bo7bo$2bobo7bobo$5b2o3b2o$4b4ob4o$2bo2bob
obobo2bo$6bo3bo$5b2o3b2o$5b2o3b2o2$6bo3bo$5bobobobo$4bo7bo$4bo7bo$5bo
5bo2$6b2ob2o$6bo3bo$6bo3bo$7b3o$6bo3bo$5b2o3b2o4$b2o3bo3bo3b2o$2b4o5b
4o$3b2o7b2o!
Edit 2: with regard to the c/6 width-19 search mentioned above, if you choose a certain seedcolumn you would run into this repeating component:

Code: Select all

x = 19, y = 66, rule = B3/S23
9bo$2bo13bo$b2o2bo7bo2b2o$o4bo7bo4bo$3ob2ob5ob2ob3o$2bo13bo$4b2obo3bob
2o$5bobo3bobo$5bo3bo3bo$7bobobo$7bo3bo$8b3o$9bo$8bobo$2bo13bo$b2o2bo7b
o2b2o$o4bo7bo4bo$3ob2ob5ob2ob3o$2bo13bo$4b2obo3bob2o$5bobo3bobo$5bo3bo
3bo$7bobobo$7bo3bo$8b3o$9bo$8bobo$2bo13bo$b2o2bo7bo2b2o$o4bo7bo4bo$3ob
2ob5ob2ob3o$2bo13bo$4b2obo3bob2o$5bobo3bobo$5bo3bo3bo$7bobobo$7bo3bo$
8b3o$9bo$8bobo$2bo13bo$b2o2bo7bo2b2o$o4bo7bo4bo$3ob2ob5ob2ob3o$2bo13bo
$4b2obo3bob2o$5bobo3bobo$5bo3bo3bo$7bobobo$7bo3bo$8b3o$9bo$8bobo$2bo
13bo$b2o2bo7bo2b2o$o4bo7bo4bo$3ob2ob5ob2ob3o$2bo13bo$4b2obo3bob2o$5bob
o3bobo$5bo3bo3bo$7bobobo$7bo3bo$8b3o$9bo$8bobo!
I don't know how that might impact our judgement of performance.
-Matthias Merzenich

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 6th, 2020, 10:27 pm

Sokwe wrote:
January 5th, 2020, 8:50 pm
Is there an easy way to set up a complete search for a desired speed at a specific width?
Not yet. I need to work on making the program more user-friendly. That's going to take some time, right now it's still more of a proof of concept. And I'll get back to you on your proposed searches.
-- Andrew Wade

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 6th, 2020, 11:34 pm

mscibing wrote:
January 6th, 2020, 10:27 pm
I'll get back to you on your proposed searches.
No pressure! I've been a bit badgering. Do the searches you find most compelling!

Edit: the proposed searches above are just to test your search's functionality. They don't push any boundaries. If I ever bother to get your search working I can do them myself. Again, do the searches you think are interesting. The spaceship search status page is good for both testing your program against known results and for knowing where to look for new ships.
-Matthias Merzenich

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 9th, 2020, 1:57 am

How difficult would it be to start a a search based on a partial result? If you had, say 2 rows in every phase from the middle of a partial result, could those be forced in as the starting rows for your program (rather than starting from empty rows, as it currently is)?
-Matthias Merzenich

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 12th, 2020, 8:30 pm

I have added a --velocity option to replace the use of --starts, I recommend all users upgrade to the latest version. The script still had a bug for (3,0)c/10 and with --velocity that sort of thing shouldn't be a problem anymore.
Sokwe wrote:
January 5th, 2020, 8:50 pm
Edit: how well does this program handle a c/6 width-19 odd-symmetric search?
Funny thing; I was seeing how the search would handle a repeating component and whether I could tell from the statistics that only the repeating component was remaining in the search, when it found a different spaceship. This one was found after about 12 hours total runtime:

Code: Select all

x = 19, y = 56, rule = B3/S23
9bo$2bo13bo$b2o2bo7bo2b2o$o4bo7bo4bo$3ob2ob5ob2ob3o$2bo13bo$4b2obo3bob
2o$5bobo3bobo$5bo3bo3bo$7bobobo$7bo3bo$8b3o$9bo$8b3o$7b2ob2o$7b2ob2o2$
6bo5bo$5bobo3bobo$5bo2bobo2bo$5b2obobob2o$b3o4bobo4b3o$8bobo$5bobo3bob
o2$4b2o7b2o$6bo5bo$4b2ob2ob2ob2o2$4b2o7b2o2$7bo3bo$2b3obobobobob3o$bo
3bo2bobo2bo3bo$2bobo9bobo$4bobo5bobo$7bo3bo$8bobo$5b2obobob2o$5b2obobo
b2o$4b3obobob3o$4bo3bobo3bo$3b2o9b2o$2b3o9b3o$3b2o2b2ob2o2b2o$6b2o3b2o
$bo3b2o5b2o3bo$2bob3o5b3obo$3bo11bo$3bo11bo$3b3o7b3o$6bo2bo2bo$2b3o3b
3o3b3o$2b6o3b6o$2bo4bobobo4bo$8bobo!
This spaceship will obviously be extensible using the repeating component. Disk usage at the time of the discovery was about 8GB.
Sokwe wrote:
January 9th, 2020, 1:57 am
How difficult would it be to start a a search based on a partial result? If you had, say 2 rows in every phase from the middle of a partial result, could those be forced in as the starting rows for your program (rather than starting from empty rows, as it currently is)?
Not as it currently is; there is no way to tell the program to ignore the rules of life at the head. The way to do something like this would be to start the search from the head but use --extend_mask to steer the search to a particular partial. Working out the right masks is a very manual and rather ugly process. The left and right edges are different in this regard; except for --odd_midline the program makes no assumptions as to what's beyond the edge. Which now that I think about it means --gutter is specific to B3/S23 and won't necessarily work for other rules.
-- Andrew Wade

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 12th, 2020, 9:15 pm

mscibing wrote:
January 12th, 2020, 8:30 pm
I was seeing how the search would handle a repeating component and whether I could tell from the statistics that only the repeating component was remaining in the search, when it found a different spaceship. This one was found after about 12 hours total runtime:

Code: Select all

x = 19, y = 56, rule = B3/S23
9bo$2bo13bo$b2o2bo7bo2b2o$o4bo7bo4bo$3ob2ob5ob2ob3o$2bo13bo$4b2obo3bob
2o$5bobo3bobo$5bo3bo3bo$7bobobo$7bo3bo$8b3o$9bo$8b3o$7b2ob2o$7b2ob2o2$
6bo5bo$5bobo3bobo$5bo2bobo2bo$5b2obobob2o$b3o4bobo4b3o$8bobo$5bobo3bob
o2$4b2o7b2o$6bo5bo$4b2ob2ob2ob2o2$4b2o7b2o2$7bo3bo$2b3obobobobob3o$bo
3bo2bobo2bo3bo$2bobo9bobo$4bobo5bobo$7bo3bo$8bobo$5b2obobob2o$5b2obobo
b2o$4b3obobob3o$4bo3bobo3bo$3b2o9b2o$2b3o9b3o$3b2o2b2ob2o2b2o$6b2o3b2o
$bo3b2o5b2o3bo$2bob3o5b3obo$3bo11bo$3bo11bo$3b3o7b3o$6bo2bo2bo$2b3o3b
3o3b3o$2b6o3b6o$2bo4bobobo4bo$8bobo!
That ship was found in April 2016 by Tim Coe (see here). The only search I can think of with a repeating component but no spaceships is a width 10 or 11 c/6 asymmetric search (or width-16 even symmetric but that would probably run too fast to be a good test). If you are still interested in testing this, those are the searches I recommend.
-Matthias Merzenich

AforAmpere
Posts: 1155
Joined: July 1st, 2016, 3:58 pm

Re: A new spaceship search approach

Post by AforAmpere » January 13th, 2020, 11:16 am

I ran a search for the loafer (seedcolumn = 3) to see how long it took, and it took about 2 hours and 50 minutes to find it. I'm not sure what to compare to, but that seems really fast.
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 13th, 2020, 6:16 pm

AforAmpere wrote:
January 13th, 2020, 11:16 am
I'm not sure what to compare to.
The only programs that are reasonable for comparison are zfind and qfind. To simulate the choice of seedcolumn=3 you could set initial rows in qfind. Unfortunately, that option is broken in zfind.

For qfind you could save initrows.txt with the following contents:

Code: Select all

..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......o..
Then run something like

Code: Select all

./qfind p7 k1 w10 a d m3 q21 e initrows.txt t3
Here I used t3 which runs the search with 3 threads. You might want to change this based on your hardware.
-Matthias Merzenich

User avatar
Moosey
Posts: 3883
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

Re: A new spaceship search approach

Post by Moosey » January 15th, 2020, 8:10 am

So obviously it seems like this search program has obsoleted many others, but I'm curious about how far that obsoleting went.
How fast is it and what are it's strong points--is it better at finding lower- or higher-period ships, for instance?
For instance, how long does it take to find, say, copperhead?
Can it search for oblique ships, and if so, has anyone tried to search for Sir Robin to see how fast it is there?
My CA rules can be found here

Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
Nanho walåt derwo esaato?

Code: Select all

x = 4, y = 5, rule = B34e5e67c/S23ce45
4o2$b2o$o2bo$b2o!
[[ TRACK 0 -7/325 ZOOM 16 THEME 0 ]]

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 16th, 2020, 1:39 am

Moosey wrote:
January 15th, 2020, 8:10 am
How fast is it and what are it's strong points--is it better at finding lower- or higher-period ships, for instance?
I haven't tested it myself, but I'll try to give what perspective I've gathered from other people's tests.

Ultimately, I think this search is faster than just about all others for most searches, but it has some major limitations that keep other programs useful.
  • It currently has no way to effectively continue a search after it finds a ship, so it isn't good for finding large numbers of ships like gfind, qfind, or knightt.
  • It is difficult to set up the search to continue from a partial result, so it is not good at completing ships.
  • The search is row-by-row, so it probably isn't any good for finding short, wide ships like LifeSearch, WLS, and JLS.
  • It isn't configured to search for diagonal symmetric ships, although I think there might be some potential here.
  • (Edit: Apparently it is multi-threaded in some way. I would probably need Andrew to explain it.) I don't think it's multi-threaded like ikpx and qfind, and I'm not sure how well the search space can be split up. It does require a seedcolumn, so you could still split the search up based on that.
  • It can use a lot of disk space, so if you don't have that available you might not be able to run useful searches.
Moosey wrote:
January 15th, 2020, 8:10 am
how long does it take to find, say, copperhead?
AforAmpere posted here that it took about 17 minutes to find copperhead on their machine, but this is before they realized that the weekender search they did was at width 11 instead of width 9, so I'm not sure if they set that search up correctly. I don't believe they could have found the copperhead in a width-11 search in only 17 minutes, because it took them almost 3 hours to find loafer, which is only width-10 and period-7.

17 minutes for copperhead is substantially slower than qfind or zfind, but a fair bit faster than other programs (not sure about ikpx). This might indicate that slow speeds or low widths could be faster with qfind or zfind, but more testing needs to be done to really determine that.

For fast, mid-period orthogonal ships this is unquestionably the fastest program. It may also be the fastest for oblique ships. I am fairly certain that this is the only current search program with a viable chance of finding a (3,0)c/8 spaceship for example.
Moosey wrote:
January 15th, 2020, 8:10 am
Can it search for oblique ships?
Yes. It also uses floating rows, so the ship is not restricted to being rectangular. Adam P. Goucher proved how essential this was for oblique ship searches with his discovery of Sir Robin and its minstrels.
-Matthias Merzenich

Hooloovoo
Posts: 37
Joined: July 11th, 2015, 8:59 pm

Re: A new spaceship search approach

Post by Hooloovoo » January 16th, 2020, 1:47 am

Sokwe wrote:
January 16th, 2020, 1:39 am
  • I don't think it's multi-threaded like ikpx and qfind, and I'm not sure how well the search space can be split up. It does require a seedcolumn, so you could still split the search up based on that.
The shell scripts have a $threads variable which is passed to the rust program. Often, however, one thread will take longer than the others.

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 19th, 2020, 1:54 pm

Hooloovoo wrote:
January 16th, 2020, 1:47 am
The shell scripts have a $threads variable which is passed to the rust program. Often, however, one thread will take longer than the others.
By default it spawns worker threads equal to the number of hardware threads, but it's not always good at keeping them busy with work.

On another topic, I'm trying out c/6. There are multiple repeating elements that combine in various ways, and that means the search will eventually bog down. But the search can get quite far in a reasonable amount of time (a week). I'm not going to be able to rule out a width 12 spaceship, but if one exists I stand a good chance of finding it. Here's the longest partial so far:

Code: Select all

x = 12, y = 94, rule = B3/S23
2bo$bobo$4bo$bo$3b2o$2b3o$9bo$5b6o$5b3o$7b2o$7bo$7bo$7bo$8b2o$8b2o2$9b
2o$11bo2$6b3ob2o$4bobo$3bobo$3bobo$3bobo$4b2ob2o$4b2o$3bo2b4o$3bobo$5b
o$3bobo$b2o5bo$b3ob3ob2o$2o4b2o$b2o$b3o2$b3o$2b2o$3bo$b2obo$4bob2o$o2b
obo2bo$o4bo2bo$6b2o$2b4obo$8bo$2b2o3bobo$5bobo2bo$5b3obo$2bo2bo$2b3o4$
3b2o$b2ob2obo$4b2ob2o$4bo$5b2o$3b2o2bo$6bo3bo$3b2obo3bo$6bo3bo$4b4o2bo
$4bo2bobo$6b2o$5bo$4bobo$4bo2bo$7bo$4bo$3b2o$2b4o$4bo2bo$2bob2obo$4bo
2bo$4b3o2bo$5bo4bo$4bobo3bo$3bo$6bobo$2bo5bo$4bo$b2ob2o$3b2o$bob2o$2bo
$2bo2b2o$9bo$3b2o2b2obo$7b2ob2o$8bobo$8bobo$10b2o!
-- Andrew Wade

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 19th, 2020, 9:21 pm

mscibing wrote:
January 19th, 2020, 1:54 pm
I'm not going to be able to rule out a width 12 spaceship, but if one exists I stand a good chance of finding it.
I'm certainly hopeful. You're getting close to the length of the longest width-11 partial (not counting the extensible front end). Based on the length at width-11, I expect there to be a complete spaceship at width-12.
mscibing wrote:
January 19th, 2020, 1:54 pm
Here's the longest partial so far
I was under the impression that your search was breadth first. Wouldn't all of your partials at any given time be the same length?
-Matthias Merzenich

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » January 19th, 2020, 10:40 pm

Sokwe wrote:
January 19th, 2020, 9:21 pm
I was under the impression that your search was breadth first. Wouldn't all of your partials at any given time be the same length?
Yup. The seedcolumn complicates things slightly, but in this case the longest partial is also the latest partial.

I'm not sure if this is already known, or of interest, but the front of the partial you linked to can be turned into another pushalong for a known spaceship:

Code: Select all

x = 18, y = 92, rule = B3/S23
5bo$4bobo$7bo$4bo$8bo3bo$5b2obo3bo$9bo2bo$6b3o$6b2o$7bobo$10bo$9b2o$8b
o$8bo$7bo$7bo$6bo$6b2o$7b2o$4b2o$5bo2$6b2o$6bo$5bo$5bob4o$9b2o$5b2o$5b
2ob2o$6bo2bo$5bobo$4bobo3bo$3bo3b3o$5b2o$8b2o$5bo3b2o$6bo4bo$6bo3bo$6b
o$6bo$5b2o3b2o$5b2o2b3o$6bobo2bo3$10b2o$6b2obobo$9bo2bo$6bo4bo$7bo3bo$
10bo$8bo2bo$7b2ob2o$8bo3bo$8bo$8bo$8bo2bo$10bo3$5bo6bo$4bob6obo$4b2o6b
2o$8b2o$7b4o$6b2o2b2o3$6b2o2b2o$6b2o2b2o$5b2o4b2o$6bob2obo$6b2o2b2o3$b
2o12b2o$3o4bo2bo4b3o$bobo3bo2bo3bobo$2b2o3bo2bo3b2o$3b2o8b2o$5bo6bo$2b
o2b8o2bo$2bo3b2o2b2o3bo2$7bo2bo$6bo4bo$7b4o$5bo6bo$3b3o6b3o$3bobo6bobo
$5bo6bo$2b2o10b2o!
-- Andrew Wade

Sokwe
Moderator
Posts: 1682
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Post by Sokwe » January 19th, 2020, 11:29 pm

mscibing wrote:
January 19th, 2020, 10:40 pm
I'm not sure if this is already known, or of interest, but the front of the partial you linked to can be turned into another pushalong for a known spaceship:

Code: Select all

x = 18, y = 92, rule = B3/S23
5bo$4bobo$7bo$4bo$8bo3bo$5b2obo3bo$9bo2bo$6b3o$6b2o$7bobo$10bo$9b2o$8b
o$8bo$7bo$7bo$6bo$6b2o$7b2o$4b2o$5bo2$6b2o$6bo$5bo$5bob4o$9b2o$5b2o$5b
2ob2o$6bo2bo$5bobo$4bobo3bo$3bo3b3o$5b2o$8b2o$5bo3b2o$6bo4bo$6bo3bo$6b
o$6bo$5b2o3b2o$5b2o2b3o$6bobo2bo3$10b2o$6b2obobo$9bo2bo$6bo4bo$7bo3bo$
10bo$8bo2bo$7b2ob2o$8bo3bo$8bo$8bo$8bo2bo$10bo3$5bo6bo$4bob6obo$4b2o6b
2o$8b2o$7b4o$6b2o2b2o3$6b2o2b2o$6b2o2b2o$5b2o4b2o$6bob2obo$6b2o2b2o3$b
2o12b2o$3o4bo2bo4b3o$bobo3bo2bo3bobo$2b2o3bo2bo3b2o$3b2o8b2o$5bo6bo$2b
o2b8o2bo$2bo3b2o2b2o3bo2$7bo2bo$6bo4bo$7b4o$5bo6bo$3b3o6b3o$3bobo6bobo
$5bo6bo$2b2o10b2o!
This is definitely of interest, and as far as I can tell it wasn't previously known. Most known low-period spaceship technology is contained in the jslife-moving collection, which I keep constantly updated. This pushalong doesn't appear to be anywhere in the velocity-c6o folder.

Did you find this as part of your current search? Do you have any more results along these lines?

Edit: If you do have other results, post them in the spaceship discussion thread. I think these are all of the known thin components that are part of complete spaceships (including your new pushalong):

Code: Select all

x = 175, y = 102, rule = B3/S23
162b3o$162b3o$163b2o$164bobob2o$163b2ob5o$164bo2bo2bo$164b2o$165bo$
166b2o$166b2o$167bo$165bobo$164bo$167bo$164bobo$164bo$165bo$163bo2bo$
163bobo$163bo$164bo2$164b2o$163bo$163b3o2bo$164b2ob2o$164bo2bo$164bob
2o$164bo$165bobo$161bob2o$108b5o21b5o22bo3b4o$107bo2bo2bo19bo2bo2bo22b
obo$107b2obobo20b2obobo25b3o$111bo25bo26b2ob2o$110bo25bo27bo4bo$58b4o
47b2o24b2o28b2obo$57b6o46b2obo22b2obo26b3o$31b6o19b8o46bo25bo28b2o$30b
o6bo17b2o6b2o46bobo23bobo24bo3bo$29bo8bo73bo25bo24b2ob4o$29bo8bo125bo
5bo$4bo6bo20bo2bo21bo4bo47b3o23b3o25bo2bo$3bobob2obobo18bo4bo20b2o2b2o
19b3o23b2ob2o21b2ob2o29bo$3b2o2b2o2b2o18b2o2b2o48bob3o18b2obo22b2obo$
7b2o72bo3bo21b2o2bo21b2o2bo27bobob2o$58b4o19bo3bo23bo25bo28b2ob2o$5b2o
2b2o47bo2bo46bo5bo19bo5bo23b2obobo$5b2o2b2o20b6o20bo4bo22bo27b3o23b3o
24b3o$6b4o23b2o23b4o21b2o23b3o23b3o30b2o$6bo2bo21bo4bo20b2o2b2o20bo26b
3o23b3o27bo$5bo4bo21bo2bo22b4o22b3o24b2o24b2o27bob2o$5bo4bo21b4o23b2o
22bobobo23b5o21b5o24bob2o$5bob2obo48b2o23bob3o24bo25bo27b3o$6bo2bo48bo
2bo24bobo24bo25bo27b2o$6bo2bo22b4o21bo4bo23b2o25bo25bo27b2o$32b4o49bob
o24bo23b2o3b2o23bobo$31bob2obo97bo9bo$134bo9bo$4bo6bo18bo6bo18bo6bo18b
o6bo18bo6bo17bo11bo17bo6bo$3bobob2obobo16bobob2obobo16bobob2obobo16bob
ob2obobo16bobob2obobo17b2ob5ob2o17bobob2obobo$3b2o2b2o2b2o16b2o2b2o2b
2o16b2o2b2o2b2o16b2o2b2o2b2o16b2o2b2o2b2o18bo7bo18b2o2b2o2b2o$7b2o24b
2o24b2o24b2o24b2o22bobobobobo22b2o$135bo7bo$5b2o2b2o20b2o2b2o20b2o2b2o
20b2o2b2o20b2o2b2o20bo7bo20b2o2b2o$5b2o2b2o20b2o2b2o20b2o2b2o20b2o2b2o
20b2o2b2o18b2o9b2o18b2o2b2o$6b4o22b4o22b4o22b4o22b4o19b2o4bo4b2o19b4o$
6bo2bo22bo2bo22bo2bo22bo2bo22bo2bo19b2ob2o3b2ob2o19bo2bo$5bo4bo20bo4bo
20bo4bo20bo4bo20bo4bo49bo4bo$5bo4bo20bo4bo20bo4bo20bo4bo20bo4bo22b2ob
2o22bo4bo$5bob2obo20bob2obo20bob2obo20bob2obo20bob2obo21b3ob3o21bob2ob
o$6bo2bo22bo2bo22bo2bo22bo2bo22bo2bo18b2o3b2ob2o3b2o18bo2bo$6bo2bo22bo
2bo22bo2bo22bo2bo22bo2bo18b2o11b2o18bo2bo2$o14bo10bo14bo10bo14bo10bo
14bo10bo14bo13bobo7bobo13bo14bo$2o4bo2bo4b2o10b2o4bo2bo4b2o10b2o4bo2bo
4b2o10b2o4bo2bo4b2o10b2o4bo2bo4b2o14bo9bo14b2o4bo2bo4b2o$o5b4o5bo10bo
5b4o5bo10bo5b4o5bo10bo5b4o5bo10bo5b4o5bo39bo5b4o5bo$b2o4b2o4b2o12b2o4b
2o4b2o12b2o4b2o4b2o12b2o4b2o4b2o12b2o4b2o4b2o14b2o9b2o14b2o4b2o4b2o$2b
o10bo14bo10bo14bo10bo14bo10bo14bo10bo14bo13bo14bo10bo$obo10bobo10bobo
10bobo10bobo10bobo10bobo10bobo10bobo10bobo12b2o11b2o12bobo10bobo$b5o4b
5o12b5o4b5o12b5o4b5o12b5o4b5o12b5o4b5o14b2o9b2o14b5o4b5o$3bo2b4o2bo16b
o2b4o2bo16bo2b4o2bo16bo2b4o2bo16bo2b4o2bo45bo2b4o2bo$2bo4b2o4bo14bo4b
2o4bo14bo4b2o4bo14bo4b2o4bo14bo4b2o4bo13bo3bo7bo3bo13bo4b2o4bo$6bo2bo
22bo2bo22bo2bo22bo2bo22bo2bo21bo7bo21bo2bo$7b2o24b2o24b2o24b2o24b2o18b
2o13b2o18b2o$4b2ob2ob2o18b2ob2ob2o18b2ob2ob2o18b2ob2ob2o18b2ob2ob2o17b
3o7b3o17b2ob2ob2o$133b3o7b3o$3bo8bo16bo8bo16bo8bo16bo8bo16bo8bo18b4ob
4o18bo8bo$2b3o6b3o14b3o6b3o14b3o6b3o14b3o6b3o14b3o6b3o18bobobobo18b3o
6b3o$2bo2bo4bo2bo14bo2bo4bo2bo14bo2bo4bo2bo14bo2bo4bo2bo14bo2bo4bo2bo
17bo2bobo2bo17bo2bo4bo2bo$b2o10b2o12b2o10b2o12b2o10b2o12b2o10b2o12b2o
10b2o18b2ob2o18b2o10b2o$134bobobobobobo$135b3o3b3o$135b3o3b3o$136b2o3b
2o2$132bob2o7b2obo$132bo2bo7bo2bo$132bo2bo7bo2bo2$131bobo11bobo$132bo
13bo!
-Matthias Merzenich

AforAmpere
Posts: 1155
Joined: July 1st, 2016, 3:58 pm

Re: A new spaceship search approach

Post by AforAmpere » February 29th, 2020, 3:46 pm

Can LSSS not function at or above c/2 as an inherent result of how the program works? If not, is there a way to change that?
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » March 2nd, 2020, 9:01 pm

I haven't tested this out but any v < c should work. But only life-like cellular automata are supported; the two states and the outer totalistic rules are baked deep in the data structures.

For life specifically, the lack of an automatic way to exclude known spaceship or lower-period spaceships means that running c/2 searches doesn't have much point.
-- Andrew Wade

AforAmpere
Posts: 1155
Joined: July 1st, 2016, 3:58 pm

Re: A new spaceship search approach

Post by AforAmpere » March 2nd, 2020, 9:34 pm

mscibing wrote:
March 2nd, 2020, 9:01 pm
I haven't tested this out but any v < c should work. But only life-like cellular automata are supported; the two states and the outer totalistic rules are baked deep in the data structures.

For life specifically, the lack of an automatic way to exclude known spaceship or lower-period spaceships means that running c/2 searches doesn't have much point.
I tried running c/2 in Life, and it crashed instantly. Same with trying speeds like 2c/3 in some life-like rules.
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule

mscibing
Posts: 74
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Post by mscibing » March 4th, 2020, 9:25 am

AforAmpere wrote:
March 2nd, 2020, 9:34 pm
I tried running c/2 in Life, and it crashed instantly. Same with trying speeds like 2c/3 in some life-like rules.
Thanks for the bug report. I've pushed out some fixes and c/2 in Life at least should now be working.
-- Andrew Wade

globins
Posts: 6
Joined: March 11th, 2020, 2:07 pm

Re: A new spaceship search approach

Post by globins » March 14th, 2020, 8:34 pm

Could someone give an example of how you might format the input to exclude known spaceships? I’m kinda confused on how to do that.

User avatar
LaundryPizza03
Posts: 1088
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: A new spaceship search approach

Post by LaundryPizza03 » March 20th, 2020, 4:18 am

How can I run LSSS on a Mac?

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

The latest edition of new-gliders.db.txt and oscillators.db.txt have 31150 spaceships and 1205 oscillators from outer-totalistic rules. You are invited to help!

Post Reply