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

Smallest Spaceships Supporting Specific Speeds (5s) Project

For discussion of other cellular automata.

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

Postby 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
Macbi
 
Posts: 650
Joined: March 29th, 2009, 4:58 am

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

Postby 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.
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

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

Postby 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.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 986
Joined: July 1st, 2016, 3:58 pm

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

Postby 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)
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

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

Postby 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.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 986
Joined: July 1st, 2016, 3:58 pm

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

Postby googleplex » February 4th, 2018, 10:49 pm

17c(3,5), 3 cells:
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!
googleplex
 
Posts: 219
Joined: January 24th, 2018, 4:36 pm

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

Postby 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:
x = 6, y = 3, rule = B2acn3ar4cenrz5aikry6-kn7e8/S02cen3aeqy4-anqry5cjkry6ikn7c8
o2$3bobo!

The collection already includes this ship:

(5,3)c/17, 3 cells
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.
wildmyron
 
Posts: 1072
Joined: August 9th, 2013, 12:45 am

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

Postby googleplex » February 4th, 2018, 11:26 pm

17c(3,2), 4 cells:
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!
googleplex
 
Posts: 219
Joined: January 24th, 2018, 4:36 pm

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

Postby wildmyron » February 4th, 2018, 11:31 pm

googleplex wrote:17c(3,2), 4 cells:
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.
wildmyron
 
Posts: 1072
Joined: August 9th, 2013, 12:45 am

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

Postby 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
Macbi
 
Posts: 650
Joined: March 29th, 2009, 4:58 am

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

Postby 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
Rhombic
 
Posts: 1056
Joined: June 1st, 2013, 5:41 pm

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

Postby 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
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

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

Postby 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.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 986
Joined: July 1st, 2016, 3:58 pm

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

Postby 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
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

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

Postby 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:
x = 3, y = 5, rule = B2-ek3jr4ceijt5-iknq6-ek/S1e2-a3aejkr4jty5nqry67c8
o2$2bo2$2bo!


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


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


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


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


6c/12 diagonal, 4 cells:
x = 3, y = 3, rule = B2ac3an4cnqyz5cqr6-ci7/S02-i3aej4-aqr5anr6ei7e
o$b2o$bo!


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


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


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


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


(7,5)c/12, 4 cells:
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.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 986
Joined: July 1st, 2016, 3:58 pm

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

Postby 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
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

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

Postby 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
User avatar
77topaz
 
Posts: 1345
Joined: January 12th, 2018, 9:19 pm

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

Postby wildmyron » February 5th, 2018, 11:24 pm

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

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

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

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

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

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

(6,2)c/18, 3 cells
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
x = 4, y = 3, rule = B2cen3enq4cijrtyz5aekr6ack/S01e2-cn3jq4einrt5ejr6ac
2o2$3bo!

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

Edited to add:
(6,2)c/21, 3 cells
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.
wildmyron
 
Posts: 1072
Joined: August 9th, 2013, 12:45 am

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

Postby 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
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

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

Postby 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:
x = 2, y = 4, rule = B2-ek3aqy4kqr5aj6c7e/S1c2a3anq4-aeqty5cij6-ek78
o$bo2$bo!


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


(8,3)c/12:
x = 2, y = 4, rule = B2-ek3ay4aiqw5-inr6k7e8/S1c2ai3aenqy4aijnqz5ej6ae7e8
bo2$bo$o!
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 986
Joined: July 1st, 2016, 3:58 pm

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

Postby 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.
User avatar
vyznev
 
Posts: 27
Joined: April 23rd, 2016, 4:08 am

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

Postby 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.
wildmyron
 
Posts: 1072
Joined: August 9th, 2013, 12:45 am

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

Postby 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
Macbi
 
Posts: 650
Joined: March 29th, 2009, 4:58 am

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

Postby 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.
User avatar
vyznev
 
Posts: 27
Joined: April 23rd, 2016, 4:08 am

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

Postby AforAmpere » February 6th, 2018, 5:34 pm

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


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


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


3-cell 6c/8:
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:
x = 3, y = 4, rule = B2aci3aejn4aceqrw5kqry6-i7e/S1c2a3eijn4-ckqrt5-ciky6cek78
2bo$2bo2$obo!


4-cell (9,3)c/12:
x = 3, y = 4, rule = B2ac3anq4-cek5-jkn6-ac8/S01e2i3aijky4eijrz5jkry6ain78
2bo2$2bo$obo!

Has anyone done manual searches for a 9c/10 frontend?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 986
Joined: July 1st, 2016, 3:58 pm

PreviousNext

Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 2 guests