A new spaceship search approach

[mscibing]

The discovery of Sir Robin has prompted me to finish up the next gen version of my own search program.

What I'm trying is basically an extreme divide and conquer approach. An arena for finding a spaceship in can be divided into a left half and a right half with a two-cell overlap region to glue the two sides together. Each half can be divided in turn, and in the end you end up with a collection of two-cell overlap regions and nothing else.

There still are a couple of problems: if you start with overlap regions ("slices") large enough to reasonably reach from head to tail of a spaceship, you'll have far too many slices to handle. The solution to this is to start with a collection of partial slices that are slowly extended from head to tail, and drop slices as you go.

There are more details in the readme: https://gitlab.com/andrew-j-wade/life_slice_ship_search

The other problem is that I only have 4GB of RAM, and that's not enough to hold as many partial slices as I want to. But I do have about 3TB free of disk don't actually need random access to the slices. With some careful sorts and compression I can store an retrieve a few billion slices and do so with reasonable I/O patterns; I've ended up cpu-limited in the search rather than storage-limited.

My other other problems is that with this search I do not have floating rows or adaptive widening. My hope is that with a slice-based representation of partial spaceships I can make the arena wide enough to compensate for the lack of floating rows, but this has yet to be demonstrated.

I have no idea if this approach will work out better or worse than the SAT-solver approach that found Sir Robin; I don't know how SAT-solvers work, and it may be that floating rows are a must for more elusive velocities. I'm in "try it and see" mode right now.

I was very much inspired by this paper: https://arxiv.org/pdf/cs/0004003.pdf, particularly the discussion of de Bruijn graphs.

Here's a (2,1)c/7 partial it found overnight before exhausting the search space I'd set up. Something this small doesn't really demonstrate that the search approach is viable, but it has made me hopeful:

Code: Select all

x = 9, y = 10, rule = B3/S23
o$2o$b2o$2bobo$ob4o$3bo2bo$2o3b3o$3bobobo$bobo2b2o$bob2obo!

[velcrorex]

Have you tried looking for ships that you already know exist, and compare the time your program takes to what other search programs might take?

[Majestas32]

Welcome back lol

[mscibing]

Have you tried looking for ships that you already know exist, and compare the time your program takes to what other search programs might take?

I like this idea, but unfortunately I wasn't able to compile gfind.

The new search was able to find 30P5H2V0 after 6 minutes on a core 2 duo with two threads.

Actually a funny thing happened: I first set up the search with the intention of 44P5H2V0 as a target but it found 30P5H2V0 instead after 35 minutes. It's when I re-did the search with a narrower arena that it found 30P5H2V0 in 6 minutes.

[Sokwe]

I first set up the search with the intention of 44P5H2V0 as a target but it found 30P5H2V0 instead after 35 minutes. It's when I re-did the search with a narrower arena that it found 30P5H2V0 in 6 minutes.

6 minutes is definitely faster than gfind for finding 30P5H2V0. I'm surprised you would find 30P5H2V0 in a search for 44P5H2V0. I suspect that I don't understand the search area that your program covers. Can you give an explanation of the search area for someone who doesn't yet fully understand how your program works?

Edit: I was looking at the readme and wondering what is meant by "The spaceship is restricted to starting after a certain row."

Edit 2: Is there a way to search specifically for symmetric ships? I suppose it wouldn't work quite the same as an empty outer edge, because there is not an inherent vertical extension to the central slice like there is with an empty slice.

I wasn't able to compile gfind.

Are you using the latest gfind release? I've never had a problem compiling with gcc.

[mscibing]

I gave up a little too quickly on compiling gfind; it turns out my gcc is a little weird when it comes to inline functions. It compiles fine with -O3, or with -fgnu89-inline.

For reference this was the error:

Code: Select all

/tmp/ccra9vvZ.o: In function `doCompact':
gfind.c:(.text+0x43d): undefined reference to `qIsEmpty'
...

Re. the search area, I restrict cells that can be alive to a range of columns and after a certain row. But to avoid the trivial spaceship (all cells dead) I need to add an additional constraint. This I do by picking a certain cell in the first row to be specified alive.

So I picked one of the live cells from the first row of 44P5H2V0 and it turned out that 30P5H2V0 also fit into the arena in a position where that cell was alive. It's not really a fair comparison to gfind since there is a bit of extra information specified (the cell that must be alive).

I'm not too concerned about having to specify a position for an alive cell on the first row. What does have me more worried is that I don't have floating rows. i.e. the spaceships need to be in a narrow bounding-box (not just locally narrow), or I need to guess the shape of the spaceship correctly somehow. There's no ability to adjust the margins differently for different partial spaceships, and it's not really possible to do so since the algorithm works with an ensemble of slices, not an ensemble of spaceships. It might be possible to cheaply calculate a "minimum distance to a spaceship edge" metric for each slice and use it to drop slices past a threshold, but I'm not sure doing so is worthwhile.

[Sokwe]

to avoid the trivial spaceship (all cells dead) I need to add an additional constraint. This I do by picking a certain cell in the first row to be specified alive.

Does this only restrict that one cell? Can all other cells in the first row be anything they want?

It's not really a fair comparison to gfind since there is a bit of extra information specified

I still suspect it is faster than gfind. I will have to run some tests once I better understand how your program works.

And again, does your program support symmetric searches? From your description, it doesn't seem like it would be too difficult.

[mscibing]

Does this only restrict that one cell? Can all other cells in the first row be anything they want?

Yes.

And again, does your program support symmetric searches? From your description, it doesn't seem like it would be too difficult.

Not yet. The's no fundamental reason it couldn't, it's just that I started out with the aim of finding a knightship and symmetry's not useful there. The even width case would definitely be easier to add then the odd width case. In the odd-width case the midline slice would require some sort of special mode to ensure consistency with the life rules. Whereas in the even-width case the only additional requirement you need to add to the midline slice is symmetry, and the existing "join" operation sufficient to ensure consistency with the rules of life.

Update: I have symmetric searches working for the even case. Here's a 3c/8 partial:

Code: Select all

x = 30, y = 21, rule = B3/S23
10b2o6b2o$9b2ob6ob2o$10bo3b2o3bo$9b2o8b2o$12bo4bo$5bo4b3o4b3o4bo$3b2ob
2o2bo8bo2b2ob2o$6bo4b2o4b2o4bo$2bo3b4obo6bob4o3bo$8bo12bo$6bobob2o6b2o
bobo$3b2o20b2o$4b4o2bo8bo2b4o$6b2ob2o8b2ob2o$2bo4bo3b2o4b2o3bo4bo$2bo
2bo5b2o4b2o5bo2bo$3bo22bo$3bob2o3bobo4bobo3b2obo$2b3obo2bo2bo4bo2bo2bo
b3o$2b2o4bo2bo6bo2bo4b2o$2o2b2o2bobobo4bobobo2b2o2b2o!

Update: Symmetric searches are now working for the odd case as well.

[Hooloovoo]

How do you set up a seed for a given search?

[mscibing]

How do you set up a seed for a given search?

The seed is a sequence of hex digits where each digit is a bitfield of the allowed patterns for each row. So:
1 = bb
e = bo, ob, oo
f = bb, bo, ob, oo

When I'm setting a seed, I want to avoid constraining the spaceship as much as possible. But I also want to avoid re-doing work on the same partial but with varying numbers of leading blank rows. So what I do is I pick one slice about half-way out from the centre. I start it with a number of blank rows (e.g. 111111 = 6 blank generation+rows). The reason I do this is I don't want to exclude spaceships where some other slice has non-blank cells the farthest forward. And then I have a row that is required to be non-blank (e = some cell is alive). The other slices out to the margin of the search area are unconstrained.

So for the partials found, shifting the partial forward would mean some row I specified as blank in the seed would have to be non-blank and thus be disallowed. And shifting the partial backward would mean the row I specified as non-blank in the seed would be blank and thus be disallowed.

Now there can still be duplicate work where the same partial is searched with a different phase. And for non-symmetric searches, there can be duplicate work for partials shifted left and right. I don't have a way of avoiding this duplicate work.

There is one other benefit of specifying a particular row in a slice as being non-blank: This avoids extracting completely blank space as a partial spaceship.

[Sokwe]

I'm copying my question here from over in the spaceship discussion thread:

For "--starts" of 0,2,3,1,6,0,1,2,4,1 the first 5 rows in the search would be:

Code: Select all

3...
....  ^
.5..  | time
.2..  |
....
..4.
..1.  <-- head  tail -->

And then the pattern will repeat one cell towards the tail and one generation in the past, wrapping around with the period:

Code: Select all

36..
.8..  ^
.5..  | time
.2a.  |
..7.
..4.
..19  <-- head  tail -->

I'm not sure how to read your diagrams. Here is a guess:

Each point in the grid is a single complete row (in a single phase) of the partial spaceship. A row at a grid point evolves into the row at the grid point directly above it (so row 1 evolves into row 4). When you try to advance a row in the last phase, you go back to the first phase, but shift towards the tail by the number of cells forward each period (2 cells forward, so row 3 evolves into row 1).

Starts like the following would also work okay with my program (I'm not sure this is true of gfind), but would probably result in a slower search than the previous pattern:

Code: Select all

....
....  ^
..5.  | time
..4.  |
..3.
..2.
..1.  <-- head  tail -->

So would the next two iterations through the starts look like this?

Code: Select all

.6...
.....  ^
..5..  | time
..4a.  |
..39.
..28.
..17.  <-- head  tail -->

Code: Select all

.6c..
..b..  ^
..5..  | time
..4a.  |
..39f
..28e
..17d  <-- head  tail -->

And a 3c/7 search might look like this ("--starts" of 0,3, 2,2, 4,1, 6,0)?

Code: Select all

45....
.89...  ^
.3c...  | time
..7...  |
..2b..
...6..
...1a.  <-- head  tail -->

Will different starts still essentially cover the same search space? What advantage do you see to one choice of starts over another?

[mscibing]

@Sokwe,

You've got the starts right.

Will different starts still essentially cover the same search space? What advantage do you see to one choice of starts over another?

Yes, it's essentially the same search space. You always want the next row chosen to be the closest to the head of the spaceship after accounting for the spaceship motion. That's because in general it's going to be the most constrained, so instead of a branching factor of, say, 2.2 you might have a branching factor of 2.0 instead. (I do have some statistics from the process and these are the sorts of branching factors you get at the tail. I haven't benchmarked different starts, but I would expect about a 10% spread in search speed.) There are also some choices of starts that won't work at all you can't do this:

Code: Select all

....
....  ^
..5.  | time
..4.  |
..2.
..1.
..3.  <-- head  tail -->

"2" needs both "1" and "3" rows to be filled in first. But normally you wouldn't do something like this anyway.

[mscibing]

If the script finishes with:

Code: Select all

0147/09
error: Os { code: 2, kind: NotFound, message: "No such file or directory" }
0147/10
error: Os { code: 2, kind: NotFound, message: "No such file or directory" }

It means the search was unsuccessful. Try changing the seedcolumn or the margin and restart with an empty data directory.
If you get the NotFound errors but the script continues it just means the partial spaceship extraction didn't complete successfully; it's nothing to worry about.

There is no message when it finds a spaceship, you just need to try the latest partial in the data directory. When it does find a spaceship the disk usage will soon go up drastically so you can look for that.

If the script is using too much memory try to reduce the flush= and mem= variables (they are in bytes). The mem= isn't a hard limit though; the program will use more if it needs to, but it will start reducing the number of running threads. 1000000000 should be enough for all but the most extreme searches.

Re. spaghetti monster, I think it took about a day, I don't remember too well. The center 9 cells of the first row are specified, and I don't know how long it would have taken if the margin wasn't stepped down the way it was in the original search for the spaghetti monster.

Edit: And the numbers printed are the last completed row/column for the current search.

[Sokwe]

Re. spaghetti monster, I think it took about a day, I don't remember too well. The center 9 cells of the first row are specified, and I don't know how long it would have taken if the margin wasn't stepped down the way it was in the original search for the spaghetti monster.

That is insanely fast compared to all other known search methods. I think your approach may represent a paradigm shift in low-period spaceship searching. The next step is to tackle some of the red cells in the spaceship search status page.

Can you clarify what you mean by "the margin wasn't stepped down the way it was in the original search for the spaghetti monster".

Also, can you give a sense of the amount of disk space used in some of these searches (e.g. for scholar and spaghetti monster)?

Edit: When the search finds nothing, does that mean that there do not exist ships that satisfy the given starting constraints? Even if so, since you currently have to (?) specify a few on cells near the head, would it be a bit tricky (involving multiple searches) to eliminate the possibility of a spaceship at a given width?

[mscibing]

The next step is to tackle some of the red cells in the spaceship search status page.

Sounds good. I'd be interested in extrapolating expected ship sizes from the known cells, but the trends don't seem particularly clear. Right now I'm running a search to confirm 23 is minimal for the (2,0)c/7 Odd-Symmetric case, and after that I'm going to add support for gutters. Unfortunately I don't see a good way to force full-period spaceships so speeds like (2,0)c/8 won't be covered. (i.e. If I search for (2,0)c/8 I'll likely get a (1,0)c/4 spaceship.)

The Spaghetti monster search wasn't at the full width of 29th all the way to the tail, and in my search I was also reducing the width part-way through. Because of the constraints on the first row I don't think the search speed is that meaningful when comparing to other programs, but it was giving me confidence that there was nothing too badly wrong with the program. I've had some bad bugs and my fear is a bug that causes spaceships to be missed, because that won't necessarily be obvious.

The scholar search took 60GB of disk space. I have run searches looking for oblique spaceships that go up to 1TB of space, but at that point the search is too slow to complete in a reasonable amount of time.

Edit: When the search finds nothing, does that mean that there do not exist ships that satisfy the given starting constraints? Even if so, since you currently have to (?) specify a few on cells near the head, would it be a bit tricky (involving multiple searches) to eliminate the possibility of a spaceship at a given width?

Right; ruling out a width involves multiple searches, but barring bugs it is possible to rule out widths definitively.

[Sokwe]

How does your search handle repeating components? For example, if you tried to search for a c/6 asymmetric ship at width 12 you would run into these width-10 repeating component:

Code: Select all

x = 50, y = 58, rule = B3/S23
43b4o$42b6o$22b6o13b8o$21bo6bo11b2o6b2o$20bo8bo$20bo8bo$bo6bo14bo2bo
15bo4bo$obob2obobo12bo4bo14b2o2b2o$2o2b2o2b2o12b2o2b2o$4b2o$43b4o$2b2o
2b2o35bo2bo$2b2o2b2o14b6o14bo4bo$3b4o17b2o17b4o$3bo2bo15bo4bo14b2o2b2o
$2bo4bo15bo2bo16b4o$2bo4bo15b4o17b2o$2bob2obo36b2o$3bo2bo36bo2bo$3bo2b
o16b4o15bo4bo$23b4o$22bob2obo2$bo6bo12bo6bo12bo6bo$obob2obobo10bobob2o
bobo10bobob2obobo$2o2b2o2b2o10b2o2b2o2b2o10b2o2b2o2b2o$4b2o18b2o18b2o
2$2b2o2b2o14b2o2b2o14b2o2b2o$2b2o2b2o14b2o2b2o14b2o2b2o$3b4o16b4o16b4o
$3bo2bo16bo2bo16bo2bo$2bo4bo14bo4bo14bo4bo$2bo4bo14bo4bo14bo4bo$2bob2o
bo14bob2obo14bob2obo$3bo2bo16bo2bo16bo2bo$3bo2bo16bo2bo16bo2bo3$23bo2b
o16bo2bo$bo6bo14b4o16b4o$obob2obobo14b2o18b2o$2o2b2o2b2o$4b2o16b6o$21b
o6bo$2b2o2b2o12bo8bo11b8o$2b2o2b2o12bo8bo10bob6obo$3b4o16bo2bo13b3o4b
3o$3bo2bo15bo4bo15bo2bo$2bo4bo14b2o2b2o14bo4bo$2bo4bo34b2o2b2o$2bob2ob
o$3bo2bo$3bo2bo15b6o14b2o2b2o$24b2o$22bo4bo13bo2b2o2bo$23bo2bo17b2o$
23b4o15b6o!

Unfortunately I don't see a good way to force full-period spaceships so speeds like (2,0)c/8 won't be covered. (i.e. If I search for (2,0)c/8 I'll likely get a (1,0)c/4 spaceship.)

There are a few cases where this wouldn't be an issue if one was only trying to expand the results in the table. For example, the thinnest possible period-2 ship has a width of 21, so the asymmetric 3c/6 search could potentially be done up to width 20 without finding p2 ships. I would certainly like to see the results of such a search, although I kind of doubt it would find any new ships.

Right now I'm running a search to confirm 23 is minimal for the (2,0)c/7 Odd-Symmetric case, and after that I'm going to add support for gutters.

Good. I am also running this search with qfind. I suspect your search will be done first, but mine will serve as a double-check.

Edit: another thing we could do is double-check some of the results already in the status table. It's a low priority, of course, but it's good to know that multiple different methods all get the same answer. I keep track of completed searches with various programs on a separate page. We can add a new table for your program. Probably the result most in need of a double-check is that there are no 3c/7 odd-symmetric ships of width 27. This was checked by Paul Tooke many years ago in a year-long gfind search and the result was never replicated.

[mscibing]

How does your search handle repeating components?

Oh, I'd forgotten about that. It doesn't; I think I've just been lucky so far. It'll just keep extending the repeating components indefinitely.

Edit:Starting a 3c/7 width 27 search now.

[Sokwe]

Sorry for inundating you with questions, but that's what you get when you create a great new search tool!

How does your search handle repeating components?

It doesn't; I think I've just been lucky so far. It'll just keep extending the repeating components indefinitely.

From prior experience, such repeating components don't tend to show up before a complete ship at the minimal width (with the exception of the c/6 case above). Since your search is breadth first, I guess it could maybe still power through a repeating component to find a ship if the memory usage doesn't get too great. I do suspect that there is a width-12 c/6 ship, but perhaps you should avoid that particular search for now.

Starting a 3c/7 width 27 search now.

Thanks, although I hope it doesn't take too long. I'm most interested to see your program cover new ground. I'll have to get it running myself one of these days, so that I can test things and not ask all these basic questions.

Also, when you complete unsuccessful searches, it would be nice if you could report your longest partial result in the spaceship discussion thread (as long as that's not too inconvenient).

[HartmutHolzwart]

Would it be possible to search for ships with two lines of on cells in the middle?

These would be a good starting point for grey ships.

[AforAmpere]

I've done some random tests with this program, and it's neat. While it takes about 17 minutes or so to find the copperhead on my machine, it takes about 50 minutes for the weekender, which was pretty fast. For comparison, with 4 threads on qfind, it took about 25. I'll probably run some of the searches for the status table once I fully understand how to set up the speeds.

[mscibing]

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!

[AforAmpere]

How can we know when all possible starts have been reached when searching? Alternatively, how can I verify that I've ruled out speed at a certain width? I also am still confused about exactly what the diagrams mean in relation to the ship.

[Sokwe]

I've done some random tests with this program, and it's neat. While it takes about 17 minutes or so to find the copperhead on my machine, it takes about 50 minutes for the weekender, which was pretty fast. For comparison, with 4 threads on qfind, it took about 25.

Interesting. I take it you used search_P7H2V0EVEN24.sh provided by Andrew. Without testing it myself I can't say much, but perhaps there are some use cases where qfind works better. However, there is no question that the 2c/7 width-21 and width-23 odd-symmetric searches were faster with Andrew's program.

After I finish the 2c/7 width-21 odd-symmetric qfind search (which might take a week or more), I'll move on to the width-22 even-symmetric search, since that is where slice search would struggle. Andrew can cover the width-23 gutter search if he wants.

[AforAmpere]

Interesting. I take it you used search_P7H2V0EVEN24.sh provided by Andrew.

Yes, I did.
Do you understand how starts differ, and can give an example as to how they work? I really don't get what changing starts does, besides changing displacement with the number specified.

EDIT:
Changing starts definitely affects whether the search works or not. I'm not sure why they are said to have the same search space above. For instance, why do these parameters not find 44P5H2V0?

Code: Select all

--period 5 --starts 0,0,1,0,2,0
seedcolumn=2

[Sokwe]

Changing starts definitely affects whether the search works or not. I'm not sure why they are said to have the same search space above. For instance, why do these parameters not find 44P5H2V0?

Code: Select all

--period 5 --starts 0,0,1,0,2,0
seedcolumn=2

Did you find 44P5H2V0 with different starts? I don't think you will. Slice search does not automatically cover the whole search space, but two searches that only differ in their starts (but not the number of starts) should cover the same search space.

I expect that the problem is because of the "seed" mentioned in this post. Slice search needs a few cells to initially be set on to run properly. It seems that Andrew has created a "seedcolumn" variable that simplifies the input so that you don't have to enter a seed manually. Changing the value of seedcolumn should change the search space. I'm not sure if seedcolumn=2 is the correct value for finding 44P5H2V0.

To completely search a particular width you would need to run slice search multiple times. Andrew would need to give details, as I don't understand it well enough to know what searches to run.

Do you understand how starts differ, and can give an example as to how they work? I really don't get what changing starts does, besides changing displacement with the number specified.

Changing starts changes, in some sense, the order in which the search is performed. The only noticeable effect of different starts will probably be in the speed of the search. I tried to explain the starts here and Andrew gave this advice:

You always want the next row chosen to be the closest to the head of the spaceship after accounting for the spaceship motion. That's because in general it's going to be the most constrained, so instead of a branching factor of, say, 2.2 you might have a branching factor of 2.0 instead.

So for a 2c/5 search I would probably choose --starts 0,2,2,1,4,0. Written as one of Andrew's diagrams, it looks like this:

Code: Select all

3...  ^
....  | time
.2..  |
....
..1.  <-- head  tail -->

I don't know exactly how the next row is calculated from the previous rows, so I'm not sure what will work best. I also don't have the program running for myself, as I've been too busy with other projects to tinker with it.