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!