3c/7 othogonal and 2c/9 diagonal spaceships

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Saka » November 4th, 2015, 6:12 am

Current result:

Code: Select all

x = 20, y = 20, rule = B3/S23
7bob5obob3o$2b2o2b2o2b3o2b5o$b2obo6bob3o$bob2obobo2bo$2b3o6bo$6b3o3b3o
$bobobobo3bob2o$2o3b2obo2bobo$3bobobo5bo$o8b2o2bo$2o7bo$5ob2o$2o3bo$ob
o2b5o$2bo2b2o$3o$bo$2o$2o$2o!

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Kazyan » December 3rd, 2015, 9:37 pm

I've just completed a gfind search for 3c/8 orthogonal with bilateral symmetry at width 22. Negative result.

I a few partials that suggested a front-end distinct from the symmetrical one I posted earlier, but those were filtered out along with mirror-image asymmetrical engines, leaving only variants of this:

Code: Select all

x = 18, y = 17, rule = B3/S23
bo3bo6bo3bo$bo4bo4bo4bo$2bo3bo4bo3bo$3b4o4b4o$5bo6bo$3b3o6b3o$bob3o6b
3obo$o2bo4b2o4bo2bo$b2o5b2o5b2o$b2o12b2o$2bo12bo$2b3o8b3o2$3bo2bo4bo2b
o$4b10o$5b3o2b3o$8b2o!
Disappointingly, there were few width-20 partials, and none of the last few dumps contained any width-22 partials. So I'm not too keen on doing the l192 search anytime soon.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by velcrorex » December 3rd, 2015, 11:46 pm

Kazyan wrote:I've just completed a gfind search for 3c/8 orthogonal with bilateral symmetry at width 22. Negative result.
Roughly how long did this search take to complete?
-Josh Ball.

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Kazyan » December 4th, 2015, 4:52 am

velcrorex wrote:
Kazyan wrote:I've just completed a gfind search for 3c/8 orthogonal with bilateral symmetry at width 22. Negative result.
Roughly how long did this search take to complete?
I broke it up enough that I can't give a firm estimate, but looking at the dump file dates, it's between 2 and 2.5 weeks of CPU time.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Scorbie » December 4th, 2015, 5:38 am

Umm... Is there a way to generate and reload dumpfiles in an unmodified gfind? Or is it Paul Tooke's version of gfind?

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Kazyan » December 4th, 2015, 7:33 am

Scorbie wrote:Umm... Is there a way to generate and reload dumpfiles in an unmodified gfind? Or is it Paul Tooke's version of gfind?
It's Paul Tooke's gfind. I'd gotten annoyed with losing a bunch of search time when my OS froze or the power cut out.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by moebius » December 10th, 2015, 11:03 am

This seems to be the place to report negative results.

After 20 years I decided to take another go at finding a period 6 knightship. I had an idea for a constraint propagation algorithm that would be significantly faster than my old algorithm for searches. So I gutted "knight" and started writing "knight2". The search program is still under development, but it is up and running for period 6 knightship searches.

In the search for a period 6 knightship I can report failure at widths 11, 12, 13, and 14. These searches failed to extend at approximately rows 24, 26, 28, and 30. The maximum extension pattern was approximately the same in each case. This is not encouraging.

I am two weeks into the search for a width 15 period 6 knightship, and it will either fail in about another two weeks or show signs of life and take months to complete. We will see what happens.

I really appreciate the search status page the Ivan started. I am using it to validate my search program as I develop it.

towerator
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by towerator » December 10th, 2015, 5:51 pm

It's worth trying, computers are 1000 times as fast as they were. (And it would be awesome...)
This is game of life, this is game of life!
Loafin' ships eaten with a knife!

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Scorbie » December 10th, 2015, 6:21 pm

Does that n-1/2n formula you mentioned in the other thread still hold in (2,1)c/6? And how did you set the overall pattern's shape? If the rows are aligned I think slanting the row (so that the pattern itself would be slanted at slope 2) would also be a good idea, I think.

Sokwe
Moderator
Posts: 2644
Joined: July 9th, 2009, 2:44 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Sokwe » December 10th, 2015, 10:15 pm

moebius wrote:In the search for a period 6 knightship I can report failure at widths 11, 12, 13, and 14.... I am two weeks into the search for a width 15 period 6 knightship
A knightship can be oriented in two ways: the "long end" can extend in either the 1-cell or 2-cell direction of travel. Which case do you mean here? Or does your search cover both cases? Also, does your program extend the pattern in only one generation, or does it consider the pattern over its full period?
-Matthias Merzenich

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by moebius » December 11th, 2015, 9:23 am

Towerator,

As near as I can tell a single core today is 30 to 50 times as fast as a Pentium-90 from 20 years ago. Cores have hardly gotten faster at all over the last 10 years. There are of course many more CPU cores around.

Scorbie,

The (n-1)/(2n) I mentioned in the other thread does apply to knightship searches. My search works by adding and testing horizontal rows of a defined width to my partially generated ship. The ship will ultimately move in the vertical direction at the (n-1)/(2n) speed. My new rows are always added directly aligned with the rows above. I have considered but not implemented playing with that alignment in order to get sloped ships. Ship movement in the horizontal direction is accomplished by occasionally shifting the check for validity.

Sokwe,

I extend the ship along the 2-cell direction of travel. As a program under development, my algorithm is currently incompatible with extending the ship in the other direction. The slick part of my algorithm is that I collect and analyse the ship on every other phase, so it does neither only one phase or all phases. So for a period 6 ship I am considering the pattern over 3 phases. It gets weird for c/5 ships where I degrade the one of the 3 checks, so I collect and analyse 3 out of 5 phases.

Have a happy day,

-Tim Coe

User avatar
velcrorex
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by velcrorex » December 11th, 2015, 7:31 pm

moebius wrote:In the search for a period 6 knightship I can report failure at widths 11, 12, 13, and 14. These searches failed to extend at approximately rows 24, 26, 28, and 30. The maximum extension pattern was approximately the same in each case. This is not encouraging.

I am two weeks into the search for a width 15 period 6 knightship, and it will either fail in about another two weeks or show signs of life and take months to complete. We will see what happens.
Paul Tooke made some modifications to gfind which, among many things, enable searching for knightships (see here.) I believe I've searched up to width 14 for period 6 knightships. I estimated using gfind to search width 15 would take on the order of a year (or more.) I never tried the search. So, your estimate of time to complete the search with your program sounds encouraging to me.

Like everyone else I'd like all the details of your program, or at least the key idea which got the ball rolling. Still, I understand it takes time to develop a program and get it polished enough to release.

Have you tried any searches at 3c/8?
-Josh Ball.

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Kazyan » December 16th, 2015, 1:37 am

Completed a gfind search for 1c/8 orthogonal, width 17, bilateral symmetry with gutter. Negative result. It took about 244 hours of CPU time.

Interesting partials, though:

Code: Select all

x = 77, y = 29, rule = B3/S23
2b2o3bobo3b2o$2bobob2ob2obobo$2bo3bo3bo3bo$2bo2bo5bo2bo$3bobo5bobo$30b
3o11b3o$3bobo5bobo17bobo9bobo$2bo2bo5bo2bo17bo11bo$3o11b3o14bo13bo$31b
3o9b3o$obo11bobo13b2ob4o3b4ob2o15b6ob6o$2bo2b2o3b2o2bo20bo5bo20bo4bobo
4bo$bo13bo19b2o3b2o22bob2ob2obo$bo3bobobobo3bo17bo9bo21bo5bo$4bo2bobo
2bo20bo9bo20bobo3bobo$4b2obobob2o19b2o3bobo3b2o16b7ob7o$5b3ob3o20b2obo
bobobob2o17bo4bobo4bo$bo13bo17bo3bobo3bo20b2o5b2o$2bobo7bobo18b2o7b2o
20bo7bo$3b2o7b2o23bobo25bo5bo$3bob2o3b2obo21b2o3b2o21b2o7b2o$2b2obobob
obob2o48b2o7b2o$3bo3bobo3bo21bo5bo20b3ob2ob2ob3o$5bobobobo19b2obobo3bo
bob2o$3bobobobobobo20bobo3bobo17b2ob2obo3bob2ob2o$3bobobobobobo20b3o3b
3o18bob4o3b4obo$5bobobobo54bo3bo$4bo2bobo2bo19b2obo5bob2o17bob2o5b2obo
$5b2o3b2o21b2o7b2o19b2o7b2o!
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by David » December 18th, 2015, 6:40 am

Kazyan wrote:Completed a gfind search for 1c/8 orthogonal, width 17, bilateral symmetry with gutter. Negative result. It took about 244 hours of CPU time.
Does that mean c/8 orths don't exist within 17 width?
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

Sokwe
Moderator
Posts: 2644
Joined: July 9th, 2009, 2:44 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Sokwe » December 18th, 2015, 7:53 am

David wrote:Does that mean c/8 orths don't exist within 17 width?
No width-17 bilaterally-symmetric c/8 orthogonal ships with an empty column down the center exist.

By the way, that first partial looks especially promising, because the connection at the back is so weak. It might be worthwhile to look for wings (using WLS or JLS) to complete the ship.
-Matthias Merzenich

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by moebius » December 18th, 2015, 9:37 am

I have several results to report:

Width 15 period 6 knightship (2,1)/6 -- No ships found

The longest extension that occurred was ~42 rows long of which the search program reported 37 rows. This is more encouraging than the width 11-14 results, but means to me that unless incredible luck occurs no period 6 knightships exist at widths less than 17 or 18. The search ran about 500 CPU hours.

Code: Select all

x = 15, y = 37, rule = B3/S23
7bo$5b5o$5bo4b2o$3bo3b3obo$3bo3b2obo$2bo3bo$2b2obo$2b4o2bo$4bo$2b4o3b
2o$2b3o2bob2o$6b2obobo$6b3o2b2o$b3o6b3o$2b2o5b2o2$7b3o2b2o$9bob3o$4b3o
3b3o$4bo6bo$3bo3b3ob2o$b2obo5b2obo$4bob3obo$o5bo2bo$4bob2o4bo$2bobo5b
2o$2bo5b2o$2bo$2bo3bobo$o3bo2b2o$o2b2o2b2o$3b3o$2ob2ob2o$2obo4b4o$bobo
b2o3b2o$2bo4bo5b2o$2b2o4bob2o!
Width 12 period 5 diagonal (1,1)/5 -- No ships found
Width 13 period 5 diagonal (1,1)/5 -- Ship found

I believe this ship is new and at a 63 pip minimum count it would be the second smallest c/5 diagonal ship.

Code: Select all

x = 25, y = 12, rule = B3/S23
2b2obo3b4o$bo2b3ob2ob5o$o3b2o2b2obo2bobo$o$o3bo5bo3bo$5bo4bo$2b2o10b2o
2b2o$5b2o6b2ob2o2bo2bo$5bobo10b5obo$12bo4b2o5bo$12bobobo$13bo!
Width 9 Asymmetric (2,0)/7 -- No ships found
Width 10 Asymmetric (2,0)/7 -- No ships found
Width 17 Odd (2,0)/7 -- No ships found
Width 18 Even (2,0)/7 -- Weekender found
Width 19 Gutter (2,0)/7 -- No ships found
Width 21 Gutter (2,0)/7 -- No ships found

I have included the source code for my search program "knight2". My coding style has not changed in 20 years and there are no comments, no subroutines, no libraries used, and no files opened or closed. The program communicates to the outside world through stdin, stdout, and command line options. Searches can be run to extend a partial by providing a hex representation of the partial's phases to stdin. If you attempt this remember that "knight2" works on only every other phase approximately. This is a command line program. It can be compiled from a developer prompt in Windows with "cl /O2 knight2.c". It can be compiled from a unix prompt with "gcc -O3 knight2.c -o knight2". If you just type "knight2" a screen describing the command line options comes up and an example search is run.

Note that the width that is provided to "knight2" after the -w option is the internal search width. So what is commonly referred to as a width 18 even symmetry search would use "-w 9" when run with this program.

This is a program that is under development, and there are a number of different capabilities that I will be adding in the near term. I will be happy to answer questions and over time I will post a description of the algorithm.

Have a happy day,

-Tim Coe
Attachments
knight2.c
(101.79 KiB) Downloaded 564 times
Last edited by moebius on December 18th, 2015, 9:59 am, edited 1 time in total.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Scorbie » December 18th, 2015, 9:44 am

moebius wrote:Width 15 period 6 knightship (2,1)/6 -- No ships found
:(
moebius wrote: but means to me that unless incredible luck occurs no period 6 knightships exist at widths less than 17 or 18.
Hmm... Could you tell me why? I don't have that intuition.
moebius wrote:Width 13 period 5 diagonal (1,1)/5 -- Ship found

I believe this ship is new and at a 63 pip minimum count it would be the second smallest c/5 diagonal ship.

Code: Select all

x = 25, y = 12, rule = B3/S23
2b2obo3b4o$bo2b3ob2ob5o$o3b2o2b2obo2bobo$o$o3bo5bo3bo$5bo4bo$2b2o10b2o
2b2o$5b2o6b2ob2o2bo2bo$5bobo10b5obo$12bo4b2o5bo$12bobobo$13bo!
Wow! That does seem new! Congrats! And this tells me i) Nobody searched this with gfind or ii) We have a new fast program!
EDIT: Ahh, the search space can be a little different from gfind. This one seems to be a "height-13".

Have a good day too :)

moebius
Posts: 45
Joined: December 10th, 2015, 9:07 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by moebius » December 18th, 2015, 9:56 am

Scorbie,

I have run many searches over the years and I have noted that for almost any search as I increase the width the final partials get very long (5 to 10 times the width) at the widths just below where ships start being found.

The c/5 diagonal search at width 13 ran 400 hours before it found that ship.

-Tim Coe

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Scorbie » December 18th, 2015, 10:13 am

moebius wrote: I have run many searches over the years and I have noted that for almost any search as I increase the width the final partials get very long (5 to 10 times the width) at the widths just below where ships start being found.
Aha! Good to know :) Thanks!
moebius wrote:The c/5 diagonal search at width 13 ran 400 hours before it found that ship.
:o No wonder you got something new and exciting. It sure is worth that 400 hours.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Saka » December 18th, 2015, 7:18 pm

How much is 100 hours?

towerator
Posts: 328
Joined: September 2nd, 2013, 3:03 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by towerator » December 18th, 2015, 7:20 pm

Saka wrote:How much is 100 hours?
4 days and 4 hours, if that's what you're asking. And we're talking about non-stop here...
This is game of life, this is game of life!
Loafin' ships eaten with a knife!

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Saka » December 18th, 2015, 7:26 pm

towerator wrote:
Saka wrote:How much is 100 hours?
4 days and 4 hours, if that's what you're asking. And we're talking about non-stop here...
Ok, then I have been searching for a 2c/9 with wls for about a 5 days, so 125 hours of cpu, and it's still halfway! Also, what is the smallest width for c/8 diagonal? Also, how do you get gfind to search for "specific" speeds? I can only enter the period of the spaceship and then let gfind scroll through the translations (I do not know how to make gfind search specifically for 2c/5, but I can enter o5v and wait until it finishes c/5 and starts 2c/5)

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Scorbie » December 18th, 2015, 7:47 pm

@Saka o5n1 would only search for c/5 ships. Read gfind c for general explanation on the params.

Sokwe
Moderator
Posts: 2644
Joined: July 9th, 2009, 2:44 pm

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by Sokwe » December 19th, 2015, 4:40 am

I think discussion of the program (knight2) itself should move to the scripts forum. I've started a topic for this purpose.
-Matthias Merzenich

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

Re: 3c/7 othogonal and 2c/9 diagonal spaceships

Post by wildmyron » December 21st, 2015, 2:47 am

Kazyan wrote:Completed a gfind search for 1c/8 orthogonal, width 17, bilateral symmetry with gutter. Negative result. It took about 244 hours of CPU time.

Interesting partials, though:

Code: Select all

<snip>
Are you currently running searches with the other symmetries, because Codeholic's table of Known spaceships by width has some fairly small numbers on the row for (1,0)c/8. I just ran width 13 (l112) for odd bilateral symmetry which took less than 12 hours. I expect the l128 search will take a similar time to the one above. I'm currently running 'gfind o8n1vl112' just to have a look at the even symmetry partials as well. If no one else is running them yet, I'll run the l128 searches over the next week or two.

Here are partials from the odd bilateral symmetry search. They are all hive pushers and one of them even has a gutter. I'm surprised there were no hive pushers amongst the width 17 with gutter partials.

Code: Select all

x = 112, y = 20, rule = B3/S23
2bo3bo3bo40bob2obob2obo39bo2b2ob2o2bo$51bo3bobo3bo42b2ob2o$2b2obobob2o
40bo3bobo3bo$bobobobobobo43bobo43bob2o3b2obo$2ob2o3b2ob2o39bo2bobo2bo
40bo2bo3bo2bo$b3obobob3o41b2o3b2o43b2o3b2o$b5ob5o$4b2ob2o45bo3bo45bo3b
o$2bob5obo42bobobobo43bobobobo$2b2o5b2o44bobo47bobo$4bo3bo46bobo47bobo
$4b2ob2o43bo2bobo2bo41bo2bobo2bo$o4bobo4bo38bobobobobobo39bobobobobobo
$bo2b2ob2o2bo40b3o3b3o41b3o3b3o$2b2o5b2o2$6bo46bo5bo43bo5bo$5bobo44bob
o3bobo41bobo3bobo$5bobo44bobo3bobo41bobo3bobo$6bo46bo5bo43bo5bo!
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.

Post Reply