Smallest Spaceships Supporting Specific Speeds (5s) Project

For discussion of other cellular automata.
User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Macbi » February 4th, 2018, 11:34 am

AforAmpere wrote:Does anyone think adding B0, but putting the B0 ships as a supplement a good idea? This would mean there would be two separate files, but the total would still have all the ships.
This would be ideal, but it's easy for me to say that since I don't maintain the lists!
Majestas32 wrote:Yeah. (Ideally I'd have b0 ships, b2a ships, and non explosive ships but you can't change the past)
Does "nonexplosive" just mean that you don't have B1e, B1c or B2a? Or do you mean that you actually have to test for explosivity, so that for example B34/S34 counts as explosive?

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Majestas32 » February 4th, 2018, 12:03 pm

Just no b1e/b2a.

@AforAmpere I pruned the b2a ships from the non-b2a ships for the orthogonal ships.

Please note that there are two speeds (3c/9 and 3c/18) in the non-b2a (ne) database whose smallest examples currently have b2a. I have marked these speeds with stars.

For the diagonal ships, there are many more starred speeds than for the orthogonal ships (mostly between c/3 and c/4 diagonal).

Hoo boy, the oblique ships are coming up next.

The Google drive link is below.

https://goo.gl/TDeRjs
Last edited by Majestas32 on February 4th, 2018, 12:32 pm, edited 1 time in total.
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by AforAmpere » February 4th, 2018, 12:10 pm

Majestas32 wrote:Just no b1e/b2a.
Why? The point was non-explosive, but a lot of the rules in the database are explosive, that don't have B2a or B1e. I thought the point was engineering, but most of the rules without B2a or B1e are not capable of engineering. I was proposing B0 being a separate category, because it was originally not allowed, and because it was a new kind of rule, but I don't see why to remove B2a and B1e now.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Majestas32 » February 4th, 2018, 12:30 pm

(Ideally I would manually test them but that takes humongous amounts of time so I'm just doing this for now)
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by AforAmpere » February 4th, 2018, 12:34 pm

Majestas32 wrote:(Ideally I would manually test them but that takes humongous amounts of time so I'm just doing this for now)
And that is why I think that should stay included in the main files, it would take an insane amount of time to check the 30,000 ships for explosiveness in the rules, and if it is explosive, there might be a way to change the rule to keep the ship, but become less explosive as well.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

googleplex
Posts: 308
Joined: January 24th, 2018, 4:36 pm
Location: The hertzsprung gap

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by googleplex » February 4th, 2018, 10:49 pm

17c(3,5), 3 cells:

Code: Select all

x = 6, y = 3, rule = B2acn3ar4cenrz5aikry6-kn7e8/S02cen3aeqy4-anqry5cjkry6ikn7c8
o2$3bobo!
Look at me! I make patterns in golly and go on the forums! I wanna be Famous!

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by wildmyron » February 4th, 2018, 11:23 pm

AforAmpere wrote:Does anyone think adding B0, but putting the B0 ships as a supplement a good idea? This would mean there would be two separate files, but the total would still have all the ships.
I'm happy with this idea. I've always felt that patterns in rules with B0 are fascinating in their own right, but different from other 2-state rules on the Moore neighbourhood because they don't travel through a vacuum. I'm aware that's quite arbitrary, but we're also not including signals in this collection either. I feel "smaller" applies in several ways here: first, even though it's applied to the state with minimum population, patterns in rules with B0 have in effect an infinite average population - which makes them less comparable to my mind. Second (and as a consequence of the first), the way we think of the pattern as a ship effectively treats 'On' cells differently in alternating generations allowing it to expand in different directions during the alternate generations. This is directly what allows B0 rules to have smaller ships than possible at some speeds in other rules - c/2 diagonal is a good example of this. This feels qualitatively different to me than photons in rules with B2a.

I think having this supplemental collection will allow showcasing what exists in rules with B0, we just need to determine what will go into it. Obviously ships at all speeds which aren't possible in other rules, and the 3-cell c/2 diagonal ships. There are also the 3-cell examples of 6c/8 and 7c/8 posted by @vyznev which are smaller than the known (or likely possible) ships in the collection. I guess there will be plenty of other B0 ships with speed c/2 < v < c which are smaller than any other ship in a non-B0 rule? In these cases, should ships be removed from the B0 supplement if an equivalent or smaller ship is found in a non-B0 rule? With this scope the supplement will be small enough that it can be stored in a single file - it certainly won't have many (if any) orthogonal ships. The alternative is maintaining a larger parallel collection, but that's a lot more work that I'm not prepared to commit to.

From a maintenance point of view there are a few things required:
  • The ship analysis script needs to support B0 rules - particularly if a ship has a lower population in an odd generation then the equivalent rule should be determined so the ship can be stored in that phase.
  • The update scripts need to include support for the B0 supplement - including reading it in, allowing comparison of the B0 ships with non B0 ships, and writing out the revised supplement.
Additionally, I've still got the following items on my TODO list:
  • Finish and publish 5S_test.py script to check if the current ship (or collection of ships) sets any new records.
  • Adapt Golly's browse-patterns.lua script to preview the 5S collection, or any other collection of ships.
----

With regard to smallest ships in non-explosive rules, I don't see the point for this collection. It has a specific well defined scope - one example ship having the smallest population in it's minimum population phase for every unique speed. If you would like a collection to aid in choosing rules for engineering, then I think you are much better off having a collection of rules rather than a collection of ships. There's little point choosing a rule based solely on the fact that it has a ship at speed (m,n)c/p which happens to have the lowest known minimum population. For example, I have recorded more than 120 unique ships with speed of 2c/7 orthogonal, roughly half with 3 cells and half with 4 cells. One of those 60 3 cell ships happens to be in the collection, but why that one? (It got lucky!) There's nothing to say that any one of those is in a rule which is easier to engineer other patterns in, and it seems to me that the presence or absence of B2a in the rulestring will provide very little benefit in making that determination. I encourage you to maintain a collection of rules that may be more interesting for engineering, and you can readily use this 5S collection as a resource for finding them, but I suggest you don't limit such a collection to only having one rule with a ship of a particular speed, and just because it happens to be the smallest.

----
googleplex wrote:17c(3,5), 3 cells:

Code: Select all

x = 6, y = 3, rule = B2acn3ar4cenrz5aikry6-kn7e8/S02cen3aeqy4-anqry5cjkry6ikn7c8
o2$3bobo!
The collection already includes this ship:

(5,3)c/17, 3 cells

Code: Select all

x = 3, y = 4, rule = B2-an3aceky4jkrty5jkn6i/S02ek3ny4jr5eir
o$2bo2$2bo!
Last edited by wildmyron on February 4th, 2018, 11:27 pm, edited 1 time in total.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

googleplex
Posts: 308
Joined: January 24th, 2018, 4:36 pm
Location: The hertzsprung gap

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by googleplex » February 4th, 2018, 11:26 pm

17c(3,2), 4 cells:

Code: Select all

x = 3, y = 4, rule = B2-a3-iny4arw5akry6-ai7e8/S1c2cek3aceky4cknt5-aery6-an7e8
2bo$o$2bo$bo!
Look at me! I make patterns in golly and go on the forums! I wanna be Famous!

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by wildmyron » February 4th, 2018, 11:31 pm

googleplex wrote:17c(3,2), 4 cells:

Code: Select all

x = 3, y = 4, rule = B2-a3-iny4arw5akry6-ai7e8/S1c2cek3aceky4cknt5-aery6-an7e8
2bo$o$2bo$bo!
As above, such a ship has already been included. The collections are here.

Because it's not obvious: the oblique collection of ships with speed (m,n)c/p is ordered by increasing m, then for each m by increasing n, and then for each (m,n) by increasing p.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Macbi » February 5th, 2018, 5:42 am

wildmyron wrote:I've always felt that patterns in rules with B0 are fascinating in their own right, but different from other 2-state rules on the Moore neighbourhood because they don't travel through a vacuum. I'm aware that's quite arbitrary, but we're also not including signals in this collection either.
This is an excellent point that I hadn't considered. You could say that they weren't "spaceships" at all because they don't travel through "space". Inastead they travel through a strobing agar. They should be called "strobeships" or "strobe crawlers".On the other hand you could argue that they do travel through space since the background returns to the vacuum every other generation.

I'd say that if we view them as strobeships then it would make sense not to include them in the 5S project, but perhaps include them in a seperate project. But if we think they're spaceships then they should be allowed in the 5S project. I think I'm currently leaning towards the former. Two agars are only the same if they're the same in every generation.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Rhombic » February 5th, 2018, 11:33 am

wildmyron wrote:I've always felt that patterns in rules with B0 are fascinating in their own right, but different from other 2-state rules on the Moore neighbourhood because they don't travel through a vacuum. I'm aware that's quite arbitrary, but we're also not including signals in this collection either.
I also agree with this notion because regardless of how they are presented as the opposite cell state every even generation, what it technically is is a strobing background.
Otherwise, one could make a script that simulates stripes agar on Golly but making every other column be the opposite state so that effectively you see vacuum (ironically, it would be explosive!). Calling these patterns "spaceships" would clearly be incorrect.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Majestas32 » February 5th, 2018, 4:13 pm

I sign up for managing the parallel B0 collection. @AforAmpere just PM me when tons of new ships are discovered
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by AforAmpere » February 5th, 2018, 6:02 pm

Majestas32 wrote:I sign up for managing the parallel B0 collection. @AforAmpere just PM me when tons of new ships are discovered
If you can compile a list of all B0 ships from this thread, and some from various locations on the forums, in the same format as the normal 5s project, that would be a good indication you are up to the task, as that is what has been the harder part of this project.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Majestas32 » February 5th, 2018, 7:19 pm

The zip file containing B0 ships from vyznev (and A for Awesome's (7,5)c/8) is here:

https://goo.gl/hNLffW
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by AforAmpere » February 5th, 2018, 7:47 pm

Majestas32 wrote:The zip file containing B0 ships from vyznev (and A for Awesome's (7,5)c/8) is here:
For the most part, it looks good! The orthogonal ships file had a weird decompression error, so maybe try storing it in Drive? If you think you are prepared to handle it, you can handle the B0 stuff. Also, did you create a Wikia just for this?

(6,1)c/12, non-B0:

Code: Select all

x = 3, y = 5, rule = B2-ek3jr4ceijt5-iknq6-ek/S1e2-a3aejkr4jty5nqry67c8
o2$2bo2$2bo!
(6,2)c/12:

Code: Select all

x = 3, y = 5, rule = B2-ek3an4-aeij5cejn6-ce7e8/S1e2i3aejr4ekwy5-akr6-k7
2bo2$2bo2$o!
(6,3)c/12:

Code: Select all

x = 2, y = 4, rule = B2aci3cenr4cejntw5acinr6-ek8/S12-an3cenqy4cijknq5-an6ein7
o$bo2$bo!
(6,4)c/12:

Code: Select all

x = 2, y = 4, rule = B2aci3ak4ceiqtwy5-ekny6akn7e/S1c2ai3n4-ekyz5-y6-e
o$bo2$bo!
(6,5)c/12:

Code: Select all

x = 4, y = 3, rule = B2ack3n4ciktz5q6-a7e8/S1e2kn3-eij4cikq5ackny6cik7c8
3bo2$obo!
6c/12 diagonal, 4 cells:

Code: Select all

x = 3, y = 3, rule = B2ac3an4cnqyz5cqr6-ci7/S02-i3aej4-aqr5anr6ei7e
o$b2o$bo!
(7,1)c/12:

Code: Select all

x = 2, y = 4, rule = B2-ek3j4aceijrz5eik6-i7c/S12-ak3-aijq4-airyz5kny6aei78
o$bo2$bo!
(7,2)c/12:

Code: Select all

x = 3, y = 5, rule = B2-k3c4eikntyz5aejry6kn7c8/S2cik3eknqy4-cknrt5aijr6cin
2bo2$2bo2$o!
(7,3)c/12:

Code: Select all

x = 3, y = 5, rule = B2-ek3akr4-cjnrz5jry6-ik8/S02an3ikr4aeikq5-cijk6aei7
o2$2bo2$2bo!
(7,4)c/12:

Code: Select all

x = 3, y = 5, rule = B2-ek3kn4acjqtwz5-ijkq67e8/S1e2ek3aeknq4cejkqw5cnqry6-ac
o2$2bo2$2bo!
(7,5)c/12, 4 cells:

Code: Select all

x = 3, y = 4, rule = B2acn3an4aijqtwz5cekr6ae/S01e2ei3aiy4aceirz5-ery6ckn8
2bo2$2bo$obo!
Last edited by AforAmpere on February 5th, 2018, 10:41 pm, edited 5 times in total.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Majestas32 » February 5th, 2018, 9:00 pm

AforAmpere wrote:Also, did you create a Wikia just for this?
Wel, also it's gonna be a more OCA focused version of the LifeWiki
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by 77topaz » February 5th, 2018, 10:04 pm

Majestas32 wrote:
AforAmpere wrote:Also, did you create a Wikia just for this?
Wel, also it's gonna be a more OCA focused version of the LifeWiki
That sounds useful, since the LifeWiki itself only has single pages for other rules. It's good to have a site where other rules can be described in more detail, too! :D

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by wildmyron » February 5th, 2018, 11:24 pm

Here are some higher period (6,2)/p results from lls.

(6,2)c/13, 3 cells

Code: Select all

x = 3, y = 4, rule = B2ack3aqr4ijtz5eijy6ace7e/S2ik3acijy4-inqwz5-acej6ac7e
2bo2$2bo$o!
(6,2)c/14, 3 cells

Code: Select all

x = 2, y = 5, rule = B2acn3aqr4aejny5ce6ac/S01e2-ak3ajk4art5cn6ce
bo2$o2$o!
(6,2)c/15, 3 cells

Code: Select all

x = 3, y = 2, rule = B2cei3acij4akqr5inr6n8/S12k3aeijn4n5-ekr6ac7
2bo$2o!
(6,2)c/16, 3 cells

Code: Select all

x = 2, y = 5, rule = B2ckn3-ij4aeityz5e6cn7e8/S01c3aceq4aeiwyz5ajk6ik
bo2$bo2$o!
(6,2)c/17, 3 cells

Code: Select all

x = 3, y = 4, rule = B2cek3cek4cknyz5cjknq6a/S01c2ek3-akny5iq6a8
o$2bo2$2bo!
(6,2)c/18, 3 cells

Code: Select all

x = 2, y = 3, rule = B2cek3ejq4einrty6cn/S01e2cn3acinq4aiqry5ce6ek
bo2$2o!
The search for this last one ran on an 11x7 bounding box, but the result actually fits in 10x6, which allows higher periods in a reasonable time (<10 min in the solver for the next two).
(6,2)c/19, 3 cells

Code: Select all

x = 4, y = 3, rule = B2cen3enq4cijrtyz5aekr6ack/S01e2-cn3jq4einrt5ejr6ac
2o2$3bo!
(6,2)c/20, 3 cells

Code: Select all

x = 3, y = 4, rule = B2ck3-eij4jqwy5ijkn/S02ace3-eir4knrt5-ceij6ek
2bo2$2bo$o!
Edited to add:
(6,2)c/21, 3 cells

Code: Select all

x = 2, y = 4, rule = B2ce3cejkn4aknt5aeqry6ac7/S1e2-ci3aenry4cejry5cnr6e7e
o$bo2$bo!
This last one took an hour in a 10x6 box. It's remarkably compact for the first 10 gens and amazingly fits in a 9x6 box. I think I'll stop now.
[/edit]

----

Unfortunately, I accidentally killed the (9,2)c/11 search that had been running for 3 days [Damn multiple uses of Ctrl-C!!!]. The bounding box used was 13x9, which may be larger than necessary (or too small). I don't think I'll try running it again.

----

@Majestas32: The B0 collection is a good start, though as AforAmpere said the orthogonal file is not a text file - it seems to be something produced by MS Word. Do you intend to compile an entirely parallel collection, or restrict it in some way? If you like, it could be hosted in the same place as the current collection. I can also share the update scripts with you which greatly help in managing updates of large numbers of ships, though as I mentioned some modifications are necessary to support B0 rules.
Last edited by wildmyron on February 5th, 2018, 11:58 pm, edited 1 time in total.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Majestas32 » February 5th, 2018, 11:32 pm

Fixed the orthogonal ships one. Yeah made that one in word. And yeah I plan to make an entirely parallel collection
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by AforAmpere » February 6th, 2018, 7:32 am

wildmyron wrote:]Unfortunately, I accidentally killed the (9,2)c/11 search that had been running for 3 days.
Luckily, we already have a 5-cell example above.

(8,1)c/12:

Code: Select all

x = 2, y = 4, rule = B2-ek3aqy4kqr5aj6c7e/S1c2a3anq4-aeqty5cij6-ek78
o$bo2$bo!
(8,2)c/12:

Code: Select all

x = 2, y = 4, rule = B2aci3acqr4ckqrz5aeknq6a7c8/S1c2a3ej4cijknrz5-akny6a7c8
o$bo2$bo!
(8,3)c/12:

Code: Select all

x = 2, y = 4, rule = B2-ek3ay4aiqw5-inr6k7e8/S1c2ai3aenqy4aijnqz5ej6ae7e8
bo2$bo$o!
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
vyznev
Posts: 27
Joined: April 23rd, 2016, 4:08 am

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by vyznev » February 6th, 2018, 8:28 am

wildmyron wrote:Unfortunately, I accidentally killed the (9,2)c/11 search that had been running for 3 days [Damn multiple uses of Ctrl-C!!!]. The bounding box used was 13x9, which may be larger than necessary (or too small). I don't think I'll try running it again.
In my experience with the B0 ships, starting with a pretty small search box is a good idea to avoid the solver getting lost.

I suspect what happens sometimes, when the solver just seems to get stuck, is that it gets fixated on a partial solution that is really a dead end, such as a front part that cannot be extended to a full ship, but which the solver cannot definitively rule out because there are too many possible extensions to check. Constraining the search area seems to help the solver get past such dead ends, and maybe find an actual solution instead.

In any case, there seem to be plenty of low-hanging fruit to pick even with pretty narrow searches, and the faster you find those (or find that there's no solution with your constraints) the better. Ideally, you'd like to get either a solution or "Unsatisfiable" in a few minutes at most; if the latter, you can then widen the search box and try again.

What I'm really trying to say here is that I'd guess you probably didn't lose much useful progress there, if any at all. Just try that search again, this time with a smaller bounding box.


Unfortunately, AFAIK, LLS still handles spaceship searches in a somewhat suboptimal way, where it basically uses a fixed bounding box for the whole search period and then shifts the box by (x,y) cells at once. For fast ships with a high period, that creates an awkward "bottleneck" between the last and the first generation.

I modified my B0 search script to instead gradually slide the bounding box from the original position to the shifted position over the search period, and it seems to really help when looking for fast ships. If you wanted, you could pretty easily edit the script to make it work for non-B0 rules, too.

Actually, I just did that, and made a bunch of other changes as well while I was at it. The new version now assumes a normal, non-strobing lattice unless explictly told otherwise using the --strobe parameter. You can also tell it to restrict the first generation to a smaller bounding box than other generations, which I've found useful when searching for small ships.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by wildmyron » February 6th, 2018, 11:42 am

AforAmpere wrote:
wildmyron wrote:Unfortunately, I accidentally killed the (9,2)c/11 search that had been running for 3 days.
Luckily, we already have a 5-cell example above.
Indeed, I didn't notice that when reviewing the thread.
vyznev wrote:In my experience with the B0 ships, starting with a pretty small search box is a good idea to avoid the solver getting lost.

I suspect what happens sometimes, when the solver just seems to get stuck, is that it gets fixated on a partial solution that is really a dead end, such as a front part that cannot be extended to a full ship, but which the solver cannot definitively rule out because there are too many possible extensions to check. Constraining the search area seems to help the solver get past such dead ends, and maybe find an actual solution instead.

In any case, there seem to be plenty of low-hanging fruit to pick even with pretty narrow searches, and the faster you find those (or find that there's no solution with your constraints) the better. Ideally, you'd like to get either a solution or "Unsatisfiable" in a few minutes at most; if the latter, you can then widen the search box and try again.
Yes, the search was too unconstrained, I just let it go out of interest. My general approach is in line with what you suggest. Because this speed is so close to c and it was late in the day when I kicked it off, I just set it to something I hoped might be big enough. Evidently it was too big, especially with the lack of tight constraint on population I allowed it. No matter, as you say, not much progress lost, particularly as in the interim a fairly optimal example has been found.

I'm not sure I agree with you about what happens in long running searches though. The SAT solver has no concept of partial patterns and, as I understand it, takes a much more global approach to finding a solution which satisfies the problem, or finding a contradiction which rules out the existence of a solution.
vyznev wrote:Unfortunately, AFAIK, LLS still handles spaceship searches in a somewhat suboptimal way, where it basically uses a fixed bounding box for the whole search period and then shifts the box by (x,y) cells at once. For fast ships with a high period, that creates an awkward "bottleneck" between the last and the first generation.
I'm not sure I agree with you here. Whilst it's a bit hard to say what the majority of all fast, sub-light speed ships look like, I think this shape is a reasonable way of searching and a natural consequence of reducing the search space by constraining the population of a single phase. With the more random search style programs the same sorts of ships tend to emerge too i.e. start small in one phase, increase in size and population and then implode back to the smallest phase right at the edge of the apparent explosion. To find this sort of ship you do need to allow the bounding box to grow in between the phases with minimal population.
vyznev wrote:I modified my B0 search script to instead gradually slide the bounding box from the original position to the shifted position over the search period, and it seems to really help when looking for fast ships. If you wanted, you could pretty easily edit the script to make it work for non-B0 rules, too. ... Actually, I just did that, and made a bunch of other changes as well while I was at it.
Thanks for doing this. I'll take a look at it - I think it could be helpful for setting up a range of custom searches.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by Macbi » February 6th, 2018, 12:00 pm

wildmyron wrote:I'm not sure I agree with you about what happens in long running searches though. The SAT solver has no concept of partial patterns and, as I understand it, takes a much more global approach to finding a solution which satisfies the problem, or finding a contradiction which rules out the existence of a solution.
In particular SAT solvers do "restarts" to avoid getting stuck in dead ends. My understanding is that these don't literally restart the whole process, but they do explore in a different direction

I would also assume that it will never help a SAT solver to stop it and restart it manually.

User avatar
vyznev
Posts: 27
Joined: April 23rd, 2016, 4:08 am

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by vyznev » February 6th, 2018, 12:43 pm

wildmyron wrote:I'm not sure I agree with you about what happens in long running searches though. The SAT solver has no concept of partial patterns and, as I understand it, takes a much more global approach to finding a solution which satisfies the problem, or finding a contradiction which rules out the existence of a solution.
Well, sorta. Unless LLS is doing something really odd in mapping the search to a SAT instance, most of the SAT variables should directly correspond to the states of individual cells. (Some will correspond to rule string bits, and there might be some auxiliary variables used to simplify the encoding of some constraints.) So in that sense, the current variable assignments made by the SAT solver at any given time should in fact be interpretable as a partial pattern of cells (and possibly rule transitions).

Granted, without a way to peek inside the SAT solver to see what it's doing, there's really no way to tell what's actually going on in there. In that sense, my guess is no better than yours.

Going on a bit of a tangent here, I've actually been thinking about writing a custom CDCL-based CA pattern finder (maybe based on an existing solver like MiniSAT) that could display a graphical view of the current partial solution like, say, JLS does. One of these days I might get around to actually doing it. :)

Of course, there's more to a SAT solver's state than just the variable assignments; in particular, the learned conflict clauses are arguably at least as important, if not more so. I'm not sure how to best visualize those, although it's not impossible -- a single CNF clause consisting of cell state variables effectively represents a single forbidden pattern of dead and live cells, and could be visualized as such. The problem is that a typical SAT solver generates a lot of those clauses.

AforAmpere
Posts: 1334
Joined: July 1st, 2016, 3:58 pm

Re: Smallest Spaceships Supporting Specific Speeds (5s) Project

Post by AforAmpere » February 6th, 2018, 5:34 pm

(8,4)c/12, 4 cells:

Code: Select all

x = 3, y = 4, rule = B2-ik3ey4-eiqr5cjry6-ck7e8/S1e2cin3cijkr4cqry5aqr6ck7e8
2bo2$2bo$obo!
(9,1)c/12, 3 cells:

Code: Select all

x = 2, y = 4, rule = B2aci3akry4aceiny5-knqr6-n7c8/S1c2aen3ejqr4ajqyz5-inq6-i7e
o$bo2$bo!
3-cell 9c/12:

Code: Select all

x = 2, y = 5, rule = B2-ei3-cijr4jkqwz5ceijy6ai7e8/S01e3acey4cekryz5-ceq6cik
bo2$o2$bo!
3-cell 6c/8:

Code: Select all

x = 2, y = 5, rule = B2-en3acejq4cikrwyz5eqr6i7e8/S02ae3ajqy4cejkqt5-cn6cn8
bo2$o2$bo!
4-cell (9,2)c/12, there might be a 3-cell, but the search takes forever for large boxes:

Code: Select all

x = 3, y = 4, rule = B2aci3aejn4aceqrw5kqry6-i7e/S1c2a3eijn4-ckqrt5-ciky6cek78
2bo$2bo2$obo!
4-cell (9,3)c/12:

Code: Select all

x = 3, y = 4, rule = B2ac3anq4-cek5-jkn6-ac8/S01e2i3aijky4eijrz5jkry6ain78
2bo2$2bo$obo!
Has anyone done manual searches for a 9c/10 frontend?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

Post Reply