Page 2 of 4

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

Posted: November 4th, 2015, 6:12 am
by Saka
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!

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

Posted: December 3rd, 2015, 9:37 pm
by Kazyan
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.

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

Posted: December 3rd, 2015, 11:46 pm
by velcrorex
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?

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

Posted: December 4th, 2015, 4:52 am
by Kazyan
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.

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

Posted: December 4th, 2015, 5:38 am
by Scorbie
Umm... Is there a way to generate and reload dumpfiles in an unmodified gfind? Or is it Paul Tooke's version of gfind?

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

Posted: December 4th, 2015, 7:33 am
by Kazyan
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.

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

Posted: December 10th, 2015, 11:03 am
by moebius
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.

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

Posted: December 10th, 2015, 5:51 pm
by towerator
It's worth trying, computers are 1000 times as fast as they were. (And it would be awesome...)

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

Posted: December 10th, 2015, 6:21 pm
by Scorbie
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.

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

Posted: December 10th, 2015, 10:15 pm
by Sokwe
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?

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

Posted: December 11th, 2015, 9:23 am
by moebius
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

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

Posted: December 11th, 2015, 7:31 pm
by velcrorex
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?

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

Posted: December 16th, 2015, 1:37 am
by Kazyan
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!

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

Posted: December 18th, 2015, 6:40 am
by David
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?

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

Posted: December 18th, 2015, 7:53 am
by Sokwe
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.

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

Posted: December 18th, 2015, 9:37 am
by moebius
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

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

Posted: December 18th, 2015, 9:44 am
by Scorbie
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 :)

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

Posted: December 18th, 2015, 9:56 am
by moebius
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

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

Posted: December 18th, 2015, 10:13 am
by Scorbie
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.

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

Posted: December 18th, 2015, 7:18 pm
by Saka
How much is 100 hours?

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

Posted: December 18th, 2015, 7:20 pm
by towerator
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...

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

Posted: December 18th, 2015, 7:26 pm
by Saka
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)

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

Posted: December 18th, 2015, 7:47 pm
by Scorbie
@Saka o5n1 would only search for c/5 ships. Read gfind c for general explanation on the params.

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

Posted: December 19th, 2015, 4:40 am
by Sokwe
I think discussion of the program (knight2) itself should move to the scripts forum. I've started a topic for this purpose.

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

Posted: December 21st, 2015, 2:47 am
by wildmyron
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!