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

A new spaceship search approach

For scripts to aid with computation or simulation in cellular automata.

A new spaceship search approach

Postby mscibing » May 21st, 2018, 1:13 pm

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:

x = 9, y = 10, rule = B3/S23
o$2o$b2o$2bobo$ob4o$3bo2bo$2o3b3o$3bobobo$bobo2b2o$bob2obo!
mscibing
 
Posts: 20
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Postby velcrorex » May 21st, 2018, 4:37 pm

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?
-Josh Ball.
User avatar
velcrorex
 
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: A new spaceship search approach

Postby Majestas32 » May 21st, 2018, 6:15 pm

Welcome back lol
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: A new spaceship search approach

Postby mscibing » May 21st, 2018, 10:22 pm

velcrorex wrote: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.
mscibing
 
Posts: 20
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Postby Sokwe » May 22nd, 2018, 6:45 pm

mscibing wrote: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.

mscibing wrote:I wasn't able to compile gfind.

Are you using the latest gfind release? I've never had a problem compiling with gcc.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1264
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Postby mscibing » May 22nd, 2018, 8:58 pm

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:
/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.
mscibing
 
Posts: 20
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Postby Sokwe » May 22nd, 2018, 9:09 pm

mscibing wrote: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?

mscibing wrote: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.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1264
Joined: July 9th, 2009, 2:44 pm

Re: A new spaceship search approach

Postby mscibing » May 22nd, 2018, 9:37 pm

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

Yes.

Sokwe wrote: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:
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.
mscibing
 
Posts: 20
Joined: May 18th, 2010, 8:30 pm

Re: A new spaceship search approach

Postby Hooloovoo » July 11th, 2018, 9:23 pm

How do you set up a seed for a given search?
Hooloovoo
 
Posts: 18
Joined: July 11th, 2015, 8:59 pm

Re: A new spaceship search approach

Postby mscibing » July 25th, 2018, 6:16 pm

Hooloovoo wrote: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.
mscibing
 
Posts: 20
Joined: May 18th, 2010, 8:30 pm


Return to Scripts

Who is online

Users browsing this forum: No registered users and 2 guests