Spaceship Discussion Thread

Post by **dvgrn** » October 7th, 2020, 4:09 pm

MathAndCode wrote: ↑
October 7th, 2020, 3:23 pm
Also, the computational power required for any method that is cleverer than a brute force method should be bounded by the computational power for the brute force method, which is linear as a function of period.

Here again, in theory you're absolutely right. But in practice you aren't actually suggesting anything that's even vaguely practical.

Brute-force enumeration searches are linear as a function of period, for a given search size. But a "linear" search isn't any use if you can't complete it. Even at tiny sizes like 10x10, you won't even be able to make a decent start before Homo sapiens evolves into something else -- hopefully something with better search technology.

The various shortcuts that people have come up with so far -- lifesrc/WLS/JLS style recursively trying options for each cell in some specific sort order, and pruning where possible, and the various spaceship-specific searchers that enumerate workable options for spaceships row by row -- all use algorithms that sacrifice the linearity of the brute-force solution, in favor of actually being able to find something every now and then.

The fact that you can trim some branches of these searches is what makes it possible to find things. But you can't trim all the branches, and the search tree that is left is at least mildly exponential as a function of period.

wwei23 · Post by **wwei23** » October 7th, 2020, 4:09 pm

calcyman wrote: ↑
October 7th, 2020, 4:07 pm
Yes, eight hours after feeding Tom Rokicki's partial as input to the original ikpx.

Did you try the "almost knightship" from 2004 or so too?

Post by **calcyman** » October 7th, 2020, 4:56 pm

wwei23 wrote: ↑
October 7th, 2020, 4:09 pm

calcyman wrote: ↑
October 7th, 2020, 4:07 pm
Yes, eight hours after feeding Tom Rokicki's partial as input to the original ikpx.
Did you try the "almost knightship" from 2004 or so too?

I did, yes, but it didn't find anything despite many days of searching.

I guess I could try some fresh (2,1)c/6 searches now with ikpx2, but I'm more interested in (2,1)c/7 since we don't have any examples yet and it's the only missing 'spaceship type' of period <= 7.

HartmutHolzwart · Post by **HartmutHolzwart** » October 7th, 2020, 4:58 pm

dvgrn wrote: ↑
October 7th, 2020, 4:09 pm

MathAndCode wrote: ↑
October 7th, 2020, 3:23 pm
Also, the computational power required for any method that is cleverer than a brute force method should be bounded by the computational power for the brute force method, which is linear as a function of period.
Here again, in theory you're absolutely right. But in practice you aren't actually suggesting anything that's even vaguely practical.

Brute-force enumeration searches are linear as a function of period, for a given search size. But a "linear" search isn't any use if you can't complete it. Even at tiny sizes like 10x10, you won't even be able to make a decent start before Homo sapiens evolves into something else -- hopefully something with better search technology.

The various shortcuts that people have come up with so far -- lifesrc/WLS/JLS style recursively trying options for each cell in some specific sort order, and pruning where possible, and the various spaceship-specific searchers that enumerate workable options for spaceships row by row -- all use algorithms that sacrifice the linearity of the brute-force solution, in favor of actually being able to find something every now and then.

The fact that you can trim some branches of these searches is what makes it possible to find things. But you can't trim all the branches, and the search tree that is left is at least mildly exponential as a function of period.

The fundamental flaw in the reasoning is that the brute force method is linear in the number of generation, but is exponential in the other dimension width and height. The complexity analysis actually must take into account all three dimensions at once to come up with a useful estimate for the overall search time.

The task is not to decide whether there is a spacship / oscillator of given witdh height, but to find one with the dimensions not known upfront.

MathAndCode · Post by **MathAndCode** » October 7th, 2020, 5:32 pm

calcyman wrote: ↑
October 7th, 2020, 3:50 pm
In its smallest phase, Sir Robin consists of 282 cells in a 31-by-79 box.

Suffice it to say, my search program didn't trawl through all (2449 choose 282) = 1816542579891561316295603424938029274802095354130525469758394163343550228141988777491556527148757232815365841439814075524609380448143349835366086222294538469451778290096666558439353121684851772080924374971250875587196201159927343699373816102263935421483779586294694267983046787036177074919515001221009282754607956760907861537317467526824613979214860525827624782038843939722869568 different ways to populate a 31-by-79 box with 282 live cells and run each of these patterns for 6 generations; this would have taken much longer than eight hours.

Instead, it does something more akin to what Dave and Hartmut have been suggesting: its search space consists of an interleaving of all phases, and it tries to find a solution to the resulting set of Boolean equations using a bunch of heuristics to guide the search.

I'd recommend reading David Eppstein's https://arxiv.org/abs/cs/0004003 article, since many of the ideas in that paper are incorporated into modern spaceship search programs.

Something else that I don't get is using orthogonal bounding boxes for non-orthogonal spaceships. Looking at this knightship partial, one can see that the left edge of the partial is not straight but instead changes directions several times, which is a consequence of trying to fit a knightship partial into an orthogonal bounding box because the partials tend to be aligned in the direction of travel in order to minimize the leading edge (which is the hardest part), but then have to be spliced together jaggedly in order to fit in a smaller bounding box. Sir Robin demonstrates a similar effect.