Smallest Spaceships Supporting Specific Speeds (5s) Project

Macbi · Post by **Macbi** » June 24th, 2019, 1:29 am

LaundryPizza03 wrote:Might the development version of LLS be faster?

Probably not much. It produces the SAT instance more quickly, but the SAT solver will still take the same amount of time.

wildmyron · Post by **wildmyron** » June 25th, 2019, 4:34 am

@AforAmpere and LaundryPizza03: Thank you for the contributions, these have been included in the latest update of the *.sss.txt and *.rle.txt files. I haven't updated the wiki or the *.wiki.txt files though. Also included in this update is the next batch of ships from my sporadically ongoing 2c/180d matchPatt search - a total of 5566 new and updated speeds including 646 new orthogonal, 698 new diagonal, and 1694 new oblique speeds. I will be posting an updated version of the matchPatt script on the rule search thread later today.

LaundryPizza03 wrote:There is already a (2,1)c/3 ship in the database, but this has a smaller (likely minimal) 4*4 bounding box:
Code: Select all
x = 4, y = 4, rule = B2-en3ej4an5j/S01c2-en4irt5ae
3bo$3bo$3bo$obo!

When I first automated the update process for the 5S collection I made the decision to not automatically update existing ships unless the minimum population was reduced. If there are multiple competing ships for a new record (with the same min pop) then I do take the bounding box of the minimum population phase into account. [Although I recently found that while this was my intention all along, that specific functionality was not present in the update script until I implemented it a few weeks ago!] I made this decision because it was in line with the original goal of this project and using additional tie breaking criteria would mean many more updates and changes to the collection as well as introduce a conundrum about which other criteria might be used as tie-breakers, e.g. minimum average population, minimum rulestring length, etc. For this very specific case I'm open to the idea of manually updating it if other people feel strongly about it.

LaundryPizza03 wrote:This should prove that all speeds with period 5 are optimal:
Code: Select all
<snip>

I suspect you are correct that there are no ships of those speeds in the 2-state isotropic Moore neighbourhood rulespace (without B0). I ran a few other searches with slightly larger bounding boxes and didn't find anything either. I'm not sure what the criteria for the colour coding on the wiki is though, so I'll leave that to AforAmpere.

LaundryPizza03 wrote:Tomorrow I hope to uncover two or three new speeds, though it is taking a very long time. (This one took 52107.6581359 seconds, or nearly 14½ hours, to find.) Might the development version of LLS be faster?

These higher period, fast spaceships can take a long time to find, but there are a few tricks you can use in some cases to get quicker results.

First off, you can restrict the rulespace a bit for the speeds close to c by excluding B1e and requiring B2ac. I don't think this will have a very big impact, but it won't hurt. You can add other requirements such as including or excluding S0, but I don't have any hard and fast recommendations - this is something I do on a case by case basis.
The biggest gain can be made by "windowing" the bounding box of the ship, i.e. each phase of the ship is restricted to a smaller bounding box. I use make_lls_grid.py for this purpose. E.g.

This search for a 3-cell (6,5)c/12 ship has the smallest possible bbox (10x9) and takes 76s with glucose-syrup
Code: Select all
```
./lls -r pB2ac345678/S012345678 -s p12 x6 y5 -p "=3" -b 10 9
```
This search finds a similar ship in 7x6 moving window and takes 32s
Code: Select all
```
./make_lls_grid.py -p 12 -x 6 -y 5 7 6 | ./lls -r pB2ac345678/S012345678 -
p "=3"
```
There are some cases where this technique hinders rather than helps (very fast oblique ships), and there are some cases where it can work really well, e.g. fast ships with glide reflect symmetry.
2718281828 uses a custom script to generate input patterns to LLS which works in a similar way and for certain searches is much more efficient, e.g. this 10c/30 diagonal ship.

LaundryPizza03 · Post by **LaundryPizza03** » June 25th, 2019, 10:39 am

Anyawy, two more results came in:

(9, 3)c/14, 5 cells. Elapsed time: 75978.576926 s: