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

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Sokwe
Moderator
Posts: 2644
Joined: July 9th, 2009, 2:44 pm

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

Post by Sokwe » January 17th, 2016, 8:40 pm

I used Nicolay's modification of WLS to confirm that no width-15 odd-symmetric (4,0)c/8 ships exist. Thus, the following width-17 odd-symmetric (4,0)c/8 ship has minimal width:

Code: Select all

x = 17, y = 28, rule = B3/S23
5bo5bo$4b3o3b3o$3b2obo3bob2o$3bob2o3b2obo$b2o2b7o2b2o$4bob5obo$3bo4bo
4bo2$3o11b3o$3b2o7b2o$3o11b3o$2ob2o7b2ob2o$2bo5bo5bo$3bo3b3o3bo$6b5o$
2bo11bo$3b4o3b4o$6b2ob2o$7b3o$3bob2o3b2obo$2bobobo3bobobo$5b2o3b2o$2b
2o2bo3bo2b2o$8bo2$6b2ob2o$7bobo$5bobobobo!
Edit: to be clear, I didn't find the above ship. It was found by Jason Summers.

I also created a series of tables that record the searches done with various programs. This way, if one of the programs is found to have a bug, we will know what searches will have been done with the other programs.
-Matthias Merzenich

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 » January 18th, 2016, 6:16 am

Is modified wls faster?

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

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

Post by Sokwe » January 18th, 2016, 3:05 pm

Saka wrote:Is modified wls faster?
No, not in general. It mostly helps in searches that contain small spaceships. For example, in a (1,1)c/4 search the standard WLS will find large fields of gliders, but Nicolay's modification will detect the first glider and will skip any solutions that don't interact with that glider.
-Matthias Merzenich

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

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

Post by Sokwe » January 18th, 2016, 4:06 pm

Here is a (4,0)c/8 width-17 glide-symmetric spaceship found with gfind:

Code: Select all

x = 35, y = 58, rule = B3/S23
2$13bo5bo$12b3o3b3o$11b2obo3bob2o$11bob2o3b2obo$9b2o2b7o2b2o$12bob5obo
$11bo4bo4bo2$8b3o11b3o$11b2o7b2o$8b3o11b3o$8b2ob2o7b2ob2o$10bo5bo5bo$
11bo3b3o3bo$14b5o$10bo11bo$11b4o3b4o$14b2ob2o$15b3o$13b2obob2o$11b2obo
bobob2o$11b2ob2ob2ob2o$10bo2bo5bo2bo$9b2o3bo3bo3b2o$10bo11bo$14b2ob2o$
12b3o2bo$13b3ob3o$12b2o2b4o2$12b2o$12b2o5bo$12b2o3b2obo$11b2o4bo2b2o$
12bo2b3o2b2o$13bo5b3o$11bo5bo2b2o$10bobo4bo2b2o$10b5o5b3o$11b2o$10bo$
10b3o2b3o$14bo2bo4bo$11b3o4b2o2bo$9bo2b2o6bobo$13bobo5b2o$8bo7bo5bo$
17bo$18bobo$10b2o!
I am currently running the width-15 (4,0)c/8 glide-symmetric search with Nicolay's WLS modification.

Edit: Removing the back end of the above ship gives a new p16 ship:

Code: Select all

x = 17, y = 44, rule = B3/S23
4b3o3b3o$4bo2bobo2bo$2bo11bo$2bo2b2o3b2o2bo$2bobo2b3o2bobo$4bo7bo2$bob
o9bobo$2o13b2o$2ob2o7b2ob2o2$bobo9bobo$3bo3b3o3bo$bob2obo3bob2obo$2bob
2o5b2obo$4b2obobob2o2$7b3o$6bobobo$4bobo3bobo$3b2ob2ob2ob2o$2bo4bobo4b
o$2bo3b5o3bo$bo5bobo5bo$3bo3bobo3bo$7bo2bo$5b3o3b2o$4bo3b2o$12bo$12bo$
6bo4bo$4bobo5bo$4b2o2bo3bo$4bo3bo4bo$4bo3bo2bo$4bo2b5obo$3bo4b3obobo$
3bo6bo2bo$3bo9bo$13b2o$12b2o$2b2o$bo2bo$2b2o!
-Matthias Merzenich

Jackk
Posts: 116
Joined: March 13th, 2012, 3:49 pm

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

Post by Jackk » January 18th, 2016, 5:00 pm

A very much not optimised p32 forward glider rake from the new ship:

Code: Select all

x = 32, y = 173, rule = B3/S23
18b3o3b3o$18bo2bobo2bo$16bo11bo$16bo2b2o3b2o2bo$16bobo2b3o2bobo$18bo7b
o2$15bobo9bobo$14b2o13b2o$14b2ob2o7b2ob2o2$15bobo9bobo$17bo3b3o3bo$15b
ob2obo3bob2obo$16bob2o5b2obo$18b2obobob2o2$21b3o$20bobobo$18bobo3bobo$
17b2ob2ob2ob2o$16bo4bobo4bo$16bo3b5o3bo$15bo5bobo5bo$17bo3bobo3bo$21bo
2bo$19b3o3b2o$18bo3b2o$26bo$26bo$20bo4bo$18bobo5bo$18b2o2bo3bo$18bo3bo
4bo$18bo3bo2bo$18bo2b5obo$17bo4b3obobo$17bo6bo2bo$17bo9bo$9b3o15b2o$9b
o2bo13b2o$9bo6b2o$9bo3bobo2bo$9bo5bo2bo$10bobo2bo2bo$15bo2bo$15bo2bo$
8bo7b2o$7b3o$7bob2o$8b3o10b2o$8b2o3b2o6b2o6bo$13b2o13b3o$28bob2o$29b3o
$29b3o$29b3o$29b2o31$2b3o$bo2bo$4bo$4bo$bobo5$21b3o$21bo2bo$21bo$21bo$
22bobo15$19b3o$18bo2bo$21bo$21bo$18bobo13$2b3o18bo$bo2bo17b3o$4bo16b2o
bo$o3bo16b3o$4bo17b2o$bobo2$26b3o$25bo2bo$28bo$24bo3bo$24bo3bo$28bo$
25bobo22$b3o$o2bo$3bo$3bo$obo!

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

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

Post by Sokwe » January 18th, 2016, 5:29 pm

The width-16 asymmetric (3,0)c/6 search finished with a negative result. It only reached a depth of 97. Here is the longest partial result:

Code: Select all

x = 16, y = 14, rule = B3/S23
8b3o4bo$5b2o4b2obo$2b2o3bobo3bo$bo2b2o4bo2bo$5obob2obo$2bobobo3b2o$2bo
7b2o$10bo$3b2ob2o$4bo2bo2b2o$5bo3b3o$6b2ob2o$7b3o$8bo!
I don't currently have plans to run the width-17 search.
Jackk wrote:A very much not optimised p32 forward glider rake from the new ship
Nice!

Edit: I tried to extend the fully-p6 bilaterally symmetric width-19 partial to a width of 31, but it didn't get much farther than the width-29 search:

Code: Select all

x = 75, y = 29, rule = B3/S23
64bo4b2o$34b2o9bo13b2obob2o3b3ob2o$32b2o2b2o2b2obo3bo7b2o9b2o2b2o$26bo
2b4o4bobobo6bo8bo2bo3bo2bo2bo3bo$26bo2b3o7b2ob2o2bobo2bo2bo5bo4bob4o$
4bo2bo17bo6b2obo2b3o10bo2b3o4bo2b4o2bo$3b2o2bo3b2o7b2o3b3o2b3o2bobobo
4bo3b2obo2b2o6bo6bo$2bo2b2ob5o6bob2o8bo4b2obobo2bobo3bo3b2o12bob3obo$b
o2bo3bo2b2o3b2obobob3ob5o5b3o4b3o4bo4bobobobobobo4bob2o$2ob2o3b3o5b3o
2b2o5b2o9b2o10bobob10ob2ob2o3bo$o3bob2o6bo3b4o2bo6bo2b2o5bo5b2o3bo7b5o
9bo$3obob3o3b2o2bob2obob3o5bo10bobo8b2o11b2o$9bob5o5b2o5b2o2bob3o21b2o
4bo2bo2b2o$b7obob2o2bo2b3o2b5o4bobo18bo2bo3b2ob3o$o32bo19bo2bobo4bo$b
7obob2o2bo2b3o2b5o4bobo18bo2bo3b2ob3o$9bob5o5b2o5b2o2bob3o21b2o4bo2bo
2b2o$3obob3o3b2o2bob2obob3o5bo10bobo8b2o11b2o$o3bob2o6bo3b4o2bo6bo2b2o
5bo5b2o3bo7b5o9bo$2ob2o3b3o5b3o2b2o5b2o9b2o10bobob10ob2ob2o3bo$bo2bo3b
o2b2o3b2obobob3ob5o5b3o4b3o4bo4bobobobobobo4bob2o$2bo2b2ob5o6bob2o8bo
4b2obobo2bobo3bo3b2o12bob3obo$3b2o2bo3b2o7b2o3b3o2b3o2bobobo4bo3b2obo
2b2o6bo6bo$4bo2bo17bo6b2obo2b3o10bo2b3o4bo2b4o2bo$26bo2b3o7b2ob2o2bobo
2bo2bo5bo4bob4o$26bo2b4o4bobobo6bo8bo2bo3bo2bo2bo3bo$32b2o2b2o2b2obo3b
o7b2o9b2o2b2o$34b2o9bo13b2obob2o3b3ob2o$64bo4b2o!
Edit 2: I finished the (4,0)c/8 width-15 glider symmetric search, confirming that the width-17 ship has minimal width.
-Matthias Merzenich

Jackk
Posts: 116
Joined: March 13th, 2012, 3:49 pm

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

Post by Jackk » January 18th, 2016, 6:34 pm

Much nicer p32 backrake:

Code: Select all

x = 21, y = 67, rule = B3/S23
5bo5bo$4b3o3b3o$3bo2b2ob2o2bo$2b3o2b3o2b3o$3b2o3bo3b2o2$2bobo7bobo$bo
13bo$bobo9bobo$bobo9bobo$bobo9bobo2$ob2o4bo4b2obo$b3o3b3o3b3o$5b2obob
2o$5bobobobo$3bo4bo4bo$6b5o$3bo9bo$6bo3bo$4b3o3b3o$3b2o3bo3b2o$b2ob3o
3b3ob2o$4b2obobob2o$o3b2obobob2o3bo$bobo2bo3bo2bobo$5b2o4bo$6bo2bobo$
4b5ob3o$6b4obo$6bob3o$4b2o3bobo$4b2o3b4o$9b2obo$3bo4bo2bobo$3bobo2bo2b
o$8bo2bob3o$3b2o4bo$2bo8bobo$12b2o4b3o$13bo3bo2bo$2b2o9b2o5bo$2b2o9b2o
bo3bo$2b2o8bobo5bo$12bo4bobo$12bobo$13b2o6$3o$o2bo$o16bo$o3bo11b3o$o3b
o10b2obo$o14b3o$bobo11b3o$15b3o$16b2o3$8b2o$6bo$7bobo$8bo!
And thus the forerake:

Code: Select all

x = 26, y = 83, rule = B3/S23
9b3o3b3o$8bo2bo3bo2bo$8bo3bobo3bo$8bo4bo4bo$7b2o9b2o$7b3o7b3o$13bo$6b
2o11b2o$6b3o9b3o$8bo9bo$5bo15bo$5bo2bo9bo2bo$6b2obo2b3o2bob2o$11bo3bo$
11bo3bo$8b2o3bo3b2o$8b5ob5o$9bo7bo$10bo5bo$9b3o3b3o$8bo4bo4bo$7bo3b5o
3bo$6b2ob2obobob2ob2o$6b3o9b3o$6b2o3b2ob2o3b2o$11b5o$10bo6bo$10bo3bo$
10bo2b2ob2o$11b2o$16b2o$10b2o3bo2bo$8b2ob2o$18bo$7bo3b3o2b3o$7bo2b3o4b
o$7bo3bo5b2o$10bo8bo$7bobo9bo4bo$8bo14b3o$19bo2b2obo$18b2o2b3o$7b2o9bo
3b3o$5bo4bo12b2o2$4bo6bo2$5bo4bo$7b2o$17bo$18b2o$6bo$5b3o$5bob2o$6b3o
12b3o$6b3o12bo2bo$6b3o3bob2o5bo$6b2o8bo4bo3bo$17bo3bo3bo$12bob2o5bo$
12bobo7bobo$12b2o4$6bo$5b3o$5bob2o$6b3o$6b2o9b3o$16bo2bo$19bo$15bo3bo$
2bo12bo3bo$b3o7bo7bo$2obo6bobo3bobo$3o10bo$3o7b2o$3o$b2o$8bo$7bo$8bo!

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

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

Post by praosylen » January 18th, 2016, 7:01 pm

Jackk wrote:A very much not optimised p32 forward glider rake from the new ship
A p64 double backrake:

Code: Select all

x = 25, y = 124, rule = B3/S23
6b3o3b3o$6bo2bobo2bo$4bo11bo$4bo2b2o3b2o2bo$4bobo2b3o2bobo$6bo7bo2$3bo
bo9bobo$2b2o13b2o$2b2ob2o7b2ob2o2$3bobo9bobo$5bo3b3o3bo$3bob2obo3bob2o
bo$4bob2o5b2obo$6b2obobob2o2$9b3o$8bobobo$6bobo3bobo$5b2ob2ob2ob2o$4bo
4bobo4bo$4bo3b5o3bo$3bo5bobo5bo$5bo3bobo3bo$9bo2bo$7b3o3b2o$6bo3b2o$
14bo$14bo$8bo4bo$6bobo5bo$6b2o2bo3bo$6bo3bo4bo$6bo3bo2bo$6bo2b5obo$5bo
4b3obobo$5bo6bo2bo$5bo9bo5bo$15b2o3b3o$14b2o3b2obo$4b2o13b3o$3bo2bo13b
2o$4b2o3$16bo6bo$15b3o4b3o$21b2obo$21b3o$21b3o$21b3o$22b2o7$7b3o$6bo2b
o$9bo$9bo$6bobo$13bo3b3o$12bobo2bo2bo$12bobo6bo$12b2o4bobo$19bo5$bo$3o
$ob2o$b3o$b2o$10bo$5b2o5bo$4bobo3bo2bo$4bobo$4bo5b3o2$7b3o9bo$8bo10bo$
18bo$11bo$11bo$11bo22$o$obo$2o4$5bo$4b3o$3b2obo4bo$3b3o5bo11bo$3b3o3bo
bo12bo$3b3o16b3o$4b2o!
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

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

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

Post by Scorbie » January 18th, 2016, 8:30 pm

Here are the interesting results from

Code: Select all

./gencols -pat myobj/p16puff obj/allss_n.list -nph 4 -tc 1 16 -gen 33 -del1 -del2 -filt ap
I think the results should have two copies of each (due to the glide symmetry of LWSS and p16 puffer) But there are some patterns that have only one copy. I may have missed something.

Code: Select all

x = 432, y = 47, rule = B3/S23
9b3o3b3o59b3o3b3o63b3o3b3o56b3o3b3o76b3o3b3o50b3o3b3o47b3o3b3o$9bo2bob
o2bo59bo2bobo2bo63bo2bobo2bo56bo2bobo2bo76bo2bobo2bo50bo2bobo2bo47bo2b
obo2bo$7bo11bo55bo11bo59bo11bo52bo11bo72bo11bo46bo11bo43bo11bo$7bo2b2o
3b2o2bo55bo2b2o3b2o2bo59bo2b2o3b2o2bo52bo2b2o3b2o2bo72bo2b2o3b2o2bo46b
o2b2o3b2o2bo43bo2b2o3b2o2bo$7bobo2b3o2bobo55bobo2b3o2bobo59bobo2b3o2bo
bo52bobo2b3o2bobo72bobo2b3o2bobo46bobo2b3o2bobo43bobo2b3o2bobo$9bo7bo
59bo7bo63bo7bo56bo7bo76bo7bo50bo7bo47bo7bo2$6bobo9bobo53bobo9bobo57bob
o9bobo50bobo9bobo70bobo9bobo44bobo9bobo41bobo9bobo$5b2o13b2o51b2o13b2o
55b2o13b2o48b2o13b2o68b2o13b2o42b2o13b2o39b2o13b2o$5b2ob2o7b2ob2o51b2o
b2o7b2ob2o55b2ob2o7b2ob2o48b2ob2o7b2ob2o68b2ob2o7b2ob2o42b2ob2o7b2ob2o
39b2ob2o7b2ob2o2$6bobo9bobo53bobo9bobo57bobo9bobo50bobo9bobo70bobo9bob
o44bobo9bobo41bobo9bobo$8bo3b3o3bo57bo3b3o3bo61bo3b3o3bo54bo3b3o3bo74b
o3b3o3bo48bo3b3o3bo45bo3b3o3bo$6bob2obo3bob2obo53bob2obo3bob2obo57bob
2obo3bob2obo50bob2obo3bob2obo70bob2obo3bob2obo44bob2obo3bob2obo41bob2o
bo3bob2obo$7bob2o5b2obo55bob2o5b2obo59bob2o5b2obo52bob2o5b2obo72bob2o
5b2obo46bob2o5b2obo43bob2o5b2obo$9b2obobob2o59b2obobob2o63b2obobob2o
56b2obobob2o76b2obobob2o50b2obobob2o47b2obobob2o2$12b3o65b3o69b3o62b3o
82b3o56b3o53b3o$11bobobo63bobobo67bobobo60bobobo80bobobo54bobobo51bobo
bo$9bobo3bobo59bobo3bobo63bobo3bobo56bobo3bobo76bobo3bobo50bobo3bobo
47bobo3bobo$8b2ob2ob2ob2o57b2ob2ob2ob2o61b2ob2ob2ob2o54b2ob2ob2ob2o74b
2ob2ob2ob2o48b2ob2ob2ob2o45b2ob2ob2ob2o$7bo4bobo4bo55bo4bobo4bo59bo4bo
bo4bo52bo4bobo4bo72bo4bobo4bo46bo4bobo4bo43bo4bobo4bo$7bo3b5o3bo55bo3b
5o3bo59bo3b5o3bo52bo3b5o3bo72bo3b5o3bo46bo3b5o3bo43bo3b5o3bo$6bo5bobo
5bo53bo5bobo5bo57bo5bobo5bo50bo5bobo5bo70bo5bobo5bo44bo5bobo5bo41bo5bo
bo5bo$8bo3bobo3bo57bo3bobo3bo61bo3bobo3bo54bo3bobo3bo74bo3bobo3bo48bo
3bobo3bo45bo3bobo3bo$12bo2bo64bo2bo67bo2bo62bo2bo81bo2bo55bo2bo52bo2bo
$10b3o3b2o60b3o3b2o63b2o3b3o58b3o3b2o77b3o3b2o51b3o3b2o48b3o3b2o$9bo3b
2o62bo3b2o69b2o3bo56bo3b2o79bo3b2o53bo3b2o50bo3b2o$17bo67bo63bo72bo84b
o58bo55bo$17bo67bo63bo72bo84bo58bo55bo$11bo4bo62bo4bo65bo4bo60bo4bo79b
o4bo53bo4bo50bo4bo$9bobo5bo59bobo5bo63bo5bobo56bobo5bo76bobo5bo50bobo
5bo47bobo5bo$9b2o2bo3bo59b2o2bo3bo63bo3bo2b2o56b2o2bo3bo76b2o2bo3bo50b
2o2bo3bo47b2o2bo3bo$9bo3bo4bo58bo3bo4bo61bo4bo3bo56bo3bo4bo75bo3bo4bo
49bo3bo4bo46bo3bo4bo$9bo3bo2bo60bo3bo2bo65bo2bo3bo56bo3bo2bo77bo3bo2bo
51bo3bo2bo48bo3bo2bo$9bo2b5obo58bo2b5obo61bob5o2bo56bo2b5obo75bo2b5obo
49bo2b5obo46bo2b5obo$8bo4b3obobo56bo4b3obobo59bobob3o4bo54bo4b3obobo
73bo4b3obobo47bo4b3obobo44bo4b3obobo$8bo6bo2bo57bo6bo2bo55bo5bo2bo6bo
54bo6bo2bo4b3o67bo6bo2bo48bo6bo2bo45bo6bo2bo$8bo9bo57bo9bo54b3o4bo9bo
54bo9bo3bo2bo67bo9bo42bo5bo9bo45bo9bo5bo$b3o14b2o66b2o52b2obo3b2o74b2o
5bo59b3o15b2o40b3o14b2o54b2o3b3o$o2bo13b2o50bo15b2o53b3o5b2o72b2o6bo
59bo2bo13b2o41bob2o12b2o54b2o4bob2o$3bo3b2o59b3o4b2o63b3o15b2o52b2o13b
obo60bo6b2o52b3o2b2o54b2o15b3o$3bo2bo2bo58bob2o2bo2bo62b3o14bo2bo50bo
2bo75bo3bobo2bo51b2o2bo2bo52bo2bo14b3o$obo4b2o60b3o3b2o64b2o15b2o52b2o
76bo6b2o57b2o54b2o15b2o$69b3o219bobo$69b3o$69b2o!
The p16 backrake seems to be the most interesting, although we have a smaller candidate there.

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 » January 19th, 2016, 4:08 am

wildmyron wrote:
Sokwe wrote:
wildmyron wrote:I have previously considered an alteration to wls/jls which may allow a complete enumeration of all solutions and partials up to a given length within a practical timeframe. Minimal details here. Essentially it would prevent jls from exploring the combinatoric realm of non-interacting solutions, although as described it wouldn't reject all of them.
I think this is a property of Nicolay Beluchenko's modification of WLS (assuming I understand you correctly). The modified WLS is available here.
Wow, that is very much like what I was thinking of. I recall reading of it being used for excluding gliders from c/4 searches but I didn't realise that that feature was generalised to all searches. I'm still trying to work out what some of the options do and precisely how the search space is pruned, but I'm running a 2c/6 search at width 16 with it now to see what comes out.
The search completed with no new results found - in particular there were no p6 results. I ran the search on a 16x80 grid and there were 836 individual results. These results all consisted of one of the known ships posted in the 2c/6 thread - either standalone or as a "pseudo tagalong" to one or more turtles, e.g.:

Code: Select all

x = 16, y = 48, rule = B3/S23
4b2o4b2o$bo4bo2bo4bo$obob3o2b3obobo$b3o2b4o2b3o$6bo2bo$7b2o2$3b2o6b2o$
4b8o2$4bo6bo$4bo6bo$6bo2bo$4b2ob2ob2o$5b2o2b2o$3bobo4bobo$3b2o6b2o$3b
2obo2bob2o$7b2o3$3b2ob4ob2o$3b10o$4bob4obo2$5bo4bo$4bob4obo$4bo2b2o2bo
$7b2o$3bob2o2b2obo$2bo10bo$3b3ob2ob3o$7b2o4$3b2o6b2o$4b8o2$4bo6bo$4bo
6bo$6bo2bo$4b2ob2ob2o$5b2o2b2o$3bobo4bobo$3b2o6b2o$3b2obo2bob2o$7b2o!
I won't make any claims about this result but I do believe that it makes a stronger case than the result from gfind did for the absence of p6 ships.
Sokwe wrote:I also created a series of tables that record the searches done with various programs. This way, if one of the programs is found to have a bug, we will know what searches will have been done with the other programs.
Great idea. Thanks again for maintaining these records.
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.

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

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

Post by Sokwe » January 19th, 2016, 5:11 am

It's not elegant, but here's a width-12 (2,0)c/6 spaceship:

Code: Select all

x = 12, y = 66, rule = B3/S23
7b2o$4b2ob2o$b4o2bobo$o4bo4bo$b2o7bo$10bo$6b3o$5bo$6bob2o$10bo$6b2o$5b
o3bo$8bo$6bo$8bo2$7b2o$5bo$4bobo$3bo$2bo$b3ob2o$2o4b2o$bo6b2o$2o6b2o$
8b2o$7bo2b2o2$7bo3bo$6b4o$4b2o$4b2o2$3bo2bo$2b6o$2b2o2b2o2$2bobo$2bo3b
o$6b2o$4bobo2$5b2o$5b2o$6b2o$7b2obo$7bo2bo$6b2ob2o$7bo2bo$4b2obo$2b2ob
obobo$bo3bobob2o$bob5o$2ob2ob2ob2o$2bobo$5bo3bo$b2ob2o4bo$b2ob2o3bo$2b
obo3bobo$5b2o$9b2o2$9bo$9bo$8bobo$10bo!
I have already confirmed that there are no width-11 2c/6 ships.
-Matthias Merzenich

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

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

Post by Scorbie » January 19th, 2016, 6:58 am

Sokwe wrote:It's not elegant, but here's a width-12 (2,0)c/6 spaceship:
Did you make it by assembling parts?
Edit: Wow... I didn't know spaceship searching could be this smart. Congrats!
Last edited by Scorbie on January 19th, 2016, 7:36 am, edited 2 times in total.

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

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

Post by Sokwe » January 19th, 2016, 7:29 am

Scorbie wrote:Did you make it by assembling parts?
Yes. I first found this partial result during a gfind search:

Code: Select all

x = 37, y = 11, rule = B3/S23
b3o7bo$b2o2bob2ob2o$3b3o4bo$bo2bobo3bo3b2o8b2o5bo2bo$o4bo4bo3b3o6b3o4b
o3b2o$o4bo4bo3b5ob2o2bo4b2o$bo2bobo3bo6bo4bobo4b2o3bo$3b3o4bo20b4obo$b
2o2bob2ob2o6b2o3bo3b2o3b2o2bo$b3o7bo8b2obobobo$24bo3bo!
I then found a width-12, p3 back end, but it didn't line up with the turtle:

Code: Select all

x = 50, y = 15, rule = B3/S23
b3o7bo$b2o2bob2ob2o$3b3o4bo$bo2bobo3bo3b2o8b2o5bobo$o4bo4bo3b3o6b3o4bo
4b2o4bo3bo2b2o$o4bo4bo3b5ob2o2bo4b2o2bob3obobobobo2bo$bo2bobo3bo6bo4bo
bo4b2o7b3obo4bobo$3b3o4bo20b5ob2obo$b2o2bob2ob2o6b2o3bo3b2o3bo3bo2b2o$
b3o7bo8b2obobobo5b3o3b2ob3o$24bo3bo7bo$34b3ob2o2bo$34b2o5bo$36b2o3bo$
38bobo!
I removed the turtle and started searching for a new front end. When it reached a point I recognized (the small symmetric part just above the p6 piece), I stopped the search. Finally, I looked through Jason Summers' "lots of spaceships" collection to find a suitable front end that was properly aligned with the back end:

Code: Select all

x = 66, y = 32, rule = B3/S23
4b2o21b2o$9bo16b3o$2b2o2bo2b3o12bo2bo$bo6bobo2bobobo4b2obob3obo$2o4b2o
2bobo2bo10bobo6bo$bo4b3o2b3o4bo2bo10bob2o$b3o7bo6b4obo5b2o3bo$2bo15b2o
bobo7bo2bo$4bo15b2o10bob2o$2b2o17bo13bo$2b2o18b2obo$4bo17bobo9$4b2o21b
2o18bobo$9bo16b3o17bo4b2o4bo3bo2b2o$2b2o2bo2b3o12bo2bo17b2o2bob3obobob
obo2bo$bo6bobo2bobobo4b2obob3obo8bo4b2o7b3obo4bobo$2o4b2o2bobo2bo10bob
o6bo3bo7b5ob2obo$bo4b3o2b3o4bo2bo10bob2o2bo4b2o3bo3bo2b2o$b3o7bo6b4obo
5b2o3bo4bobobo5b3o3b2ob3o$2bo15b2obobo7bo2bo3b3o3bo7bo$4bo15b2o10bob2o
b2o11b3ob2o2bo$2b2o17bo13bob2o11b2o5bo$2b2o18b2obo26b2o3bo$4bo17bobo
29bobo!
-Matthias Merzenich

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

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

Post by Sokwe » January 19th, 2016, 10:43 pm

Here is another width-12 (2,0)c/6 spaceship that is smaller than the previous one, and has a more substantial p6 part:

Code: Select all

x = 12, y = 52, rule = B3/S23
3b2o$3b2ob2o$2bobo2b4o$bo4bo4bo$bo7b2o$bo$3b3o$6bo$2b2obo$bo$4b2o$2bo
3bo$3bo$5bo$3bo2$3b2o2$2b3o$2b2o$3bob2o$3bo3bo$8bo2$3bob2obo$2b3o3bo$b
o3bo$7bo$4bobo$2b3ob2o$b2obobobo$o3bobob2o$6bo$4bobob2o$4bo$3bo4bo$b2o
2bo2bo$2b3o3$6b2o$4b2o2bo$4b2o$4bo2$4bo2b2o$5b3o$6bo$4bobo$4bobo$6bo$
5bo!
It was initially found as a turtle tagalong:

Code: Select all

x = 12, y = 68, rule = B3/S23
5b2o$b3ob2ob3o$o10bo$bob2o2b2obo$5b2o$2bo2b2o2bo$2bob4obo$3bo4bo2$2bob
4obo$b10o$b2ob4ob2o2$6bo$5bobo$4bo$4bob2o$3b2o$2b3o$4bobo$6b2o$5bo2bo$
5bobo$4b2o$5bobo$2b2obob2o$bo3bo$bo5b2o$3bobo2$3bo2$3b2o2$2b3o$2b2o$3b
ob2o$3bo3bo$8bo2$3bob2obo$2b3o3bo$bo3bo$7bo$4bobo$2b3ob2o$b2obobobo$o
3bobob2o$6bo$4bobob2o$4bo$3bo4bo$b2o2bo2bo$2b3o3$6b2o$4b2o2bo$4b2o$4bo
2$4bo2b2o$5b3o$6bo$4bobo$4bobo$6bo$5bo!
Edit: I completed a width-11 (2,1)c/7 search using knight2. Here is the longest partial:

Code: Select all

x = 10, y = 24, rule = B3/S23
b2o2bob2o$3bo4bo$bob2o3bo$bo3b3o$3bo2bo$b2o3bo$b2o4b3o$2bo3bob2o$4bobo
b2o$b2o$2bob3o$2b2obo$3b2o$5b2o$3obo$3obo$2bobo2bo$2o2b3o$2o2bo$3b3o$
8b2o$5b4o$6b2o$6bo!
Edit 2: a slight variant of the above (2,0)c/6:

Code: Select all

x = 12, y = 54, rule = B3/S23
3b2o$3b2ob2o$2bobo2b4o$bo4bo4bo$bo7b2o$bo$3b3o$6bo$2b2obo$bo$4b2o$2bo
3bo$3bo$5bo$3bo2$3b2o2$2b3o$2b2o$3bob2o$3bo3bo$8bo2$3bob2obo$2b3o3bo$b
o3bo$7bo$4bobo$2b3ob2o$b2obobobo$o3bobob2o$6bo$4bobob2o$4bo$3bo4bo$b2o
2bo2bo$2b3o3$6b2o$4b2o2bo$4b2o$4bo2$4bo2b2o$5b3o$6bo$4bobo$4bobo$6bo$
6b2o$4bobo$4bobo!
-Matthias Merzenich

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

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

Post by moebius » January 30th, 2016, 11:27 am

I have some negative results to report. I do not have access to the final partials right now.

2c/7 odd symmetric width 19 - no ships found, longest partial - ~300 knight2 phases, length ~75

3c/7 asymmetric width 14 - no ships found, longest partial - 90 knight3 phases, length ~30

3c/6 asymmetric width 18 - no ships found, longest partial - 36 knight3 phases, length ~18

The actual length of the longest partial is several beyond what I report, but my search program forgets it before printing it out.

I wrote a variation of my knight2 program I call knight3. Knight3 is base architected to check every 3rd phase. This gives me the ability to search for c/3 and 3c/6 ships. I then check for every 2nd phase some of the time and this allows me to search for 3c/7 and 2c/5 ships. Knight3 is very preliminary and can currently only search for asymmetric and doubled period glide symmetric ships. Getting the odd, even, and gutter modes working will occur as time permits.

I checked for glide symmetric 4c/10 ships using knight3. I was all excited that I had found the following new type of ship. Then I checked the 2c/5 thread and I guess it has been known for a while.

Code: Select all

x = 15, y = 20, rule = B3/S23
4bo5bo$3b3o3b3o$2bo2bo3bo2bo$b3o7b3o$2bobo5bobo$4b2o3b2o$o4bo3bo4bo$5b
o3bo$2o3bo3bo3b2o$2bo2bo3bo2bo$4bo5bo2$6b3o$4b2o3b2o$7bo3bo$2bo2b2o$5b
o3bo$bo3bo3b2o$10bo$2b2o5bo!
I suspect my search programs are sometimes faster and sometimes slower than glife. I am curious about what some example benchmarks for glife are. For knight2 I can report the following execution times to first ship found:

c/4 asymmetric width 10 - 90 seconds
c/5 gutter width 19 - 2 hours
c/5 asymmetric - 24 hours

These are all single thread scalar core numbers and as far as I can tell all cores run about the same speed today.

The searches I reported at the beginning of this post all took between 2 and 4 weeks of total CPU time. I chopped the last two searches into pieces and distributed them among ~8 cores do to my impatience.

I am currently developing "knightcuda" which will be massively parallel and run on graphics cards. This is slow going, as I have never programmed a massively parallel graphics card before and great care must be taken in order to get decent performance.

Have a happy day,

-Tim Coe

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

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

Post by Sokwe » January 30th, 2016, 7:43 pm

moebius wrote:I wrote a variation of my knight2 program I call knight3. Knight3 is base architected to check every 3rd phase.
I wondered if this was possible when you first described knight2. Could this be generalized to higher numbers? If so, do you think it would continue to give performance increases?
moebius wrote:I checked for glide symmetric 4c/10 ships using knight3. I was all excited that I had found the following new type of ship. Then I checked the 2c/5 thread and I guess it has been known for a while.
Does this mean that you have eliminated the possibility of width-13 and width-14 glide-symmetric (4,0)c/10 ships?
moebius wrote:I am currently developing "knightcuda" which will be massively parallel and run on graphics cards. This is slow going, as I have never programmed a massively parallel graphics card before and great care must be taken in order to get decent performance.
This is exciting to hear! I've played around with the idea of doing this with gfind, but I've never gotten very far. As you probably know, gfind keeps a queue of rows to be extended. When it fills up the space available for the queue, it performs a depth-first search to eliminate rows that can't be extended very far (basically the same, I think, as the depth-first look-ahead done by knight2). This depth-first stage is what takes the most time for gfind, but I think it shouldn't be too difficult to split the task up, since it's just a bunch of independent searches.

Is there a reason you chose CUDA over OpenCL? I don't know enough about GPU programming to really understand the advantages and disadvantages of each.

It's great to see progress on your program!

Edit:
moebius wrote:The searches I reported at the beginning of this post all took between 2 and 4 weeks of total CPU time. I chopped the last two searches into pieces and distributed them among ~8 cores do to my impatience.
Can you provide any details on how you did this? Did you just split the search once and let each core run its piece to completion, or did you do something more sophisticated?
moebius wrote:The actual length of the longest partial is several beyond what I report, but my search program forgets it before printing it out.
How does it determine what partial pattern to report? Does it just report the partial pattern associated to the last item removed from the queue?
-Matthias Merzenich

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

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

Post by moebius » February 1st, 2016, 10:27 am

Sokwe,
I wondered if this was possible when you first described knight2. Could this be generalized to higher numbers? If so, do you think it would continue to give performance increases?
The farther the phases are apart, the faster the ship goes. For example, a ship with 3 knight3 full phases would travel at 5c/9. That is not going to happen ;-).

The strength of the constraint propagation is higher the farther the phases are apart. The computational cost also increases by a factor of 4 for each step of distance the phases are apart. For slow ships I have to have more 1 step phases where the constraint propagation is not so strong. This is why I suspect gfind is faster than knight2 at the slower ship speeds.
Does this mean that you have eliminated the possibility of width-13 and width-14 glide-symmetric (4,0)c/10 ships?
Yes it does.

4c/10 glide width 13 - no ships found
4c/10 glide width 14 - no ships found
4c/10 glide width 15 - previously know ship found and any others must be very close relatives
4c/10 glide width 16 - no ships found
This is exciting to hear! I've played around with the idea of doing this with gfind, but I've never gotten very far. As you probably know, gfind keeps a queue of rows to be extended. When it fills up the space available for the queue, it performs a depth-first search to eliminate rows that can't be extended very far (basically the same, I think, as the depth-first look-ahead done by knight2). This depth-first stage is what takes the most time for gfind, but I think it shouldn't be too difficult to split the task up, since it's just a bunch of independent searches.
I know practically nothing about gfind other than skimming the paper David Eppstein wrote in about 2000. I believe he does a different form of what I call constraint propagation that gives his program its strength. Knight2 also does the breadth first global architecture with the local depth first process. I am currently working out the details of splitting the work up. Great care must be taken with regard to how the job distribution interacts with the hardware memory architecture, which is why I want to program in CUDA rather than OpenCL, for that gives me more visibility into the hardware.
Can you provide any details on how you did this? Did you just split the search once and let each core run its piece to completion, or did you do something more sophisticated?
I am going to provide a usable description of how to chop a job up over under the scripts thread for knight2.
How does it determine what partial pattern to report? Does it just report the partial pattern associated to the last item removed from the queue?
More or less the last item in the breadth first portion of the queue. That is why it misses the depth first portion in what it reports.

Have a happy day,

-Tim Coe

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

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

Post by HartmutHolzwart » February 18th, 2016, 4:33 pm

Any new results since?

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Post by muzik » February 18th, 2016, 4:46 pm

I'm an idiot, can someone explain why the spaceships posted here are c/3?

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

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

Post by Sokwe » February 18th, 2016, 4:56 pm

muzik wrote:I'm an idiot, can someone explain why the spaceships posted here are c/3?
There are spaceships of many different speeds that have been posted in this topic. This topic has been treated as the de facto place for spaceship discussion, despite the restrictive name. In fact, the first reply in this topic doesn't talk about 3c/7 orthogonal or 2c/9 diagonal spaceships. In an attempt to remedy this, I created a spaceship discussion thread that I hope will become the new place to discuss low-period spaceship searches.
-Matthias Merzenich

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Post by muzik » February 18th, 2016, 5:06 pm

Sokwe wrote:
muzik wrote:I'm an idiot, can someone explain why the spaceships posted here are c/3?
There are spaceships of many different speeds that have been posted in this topic. This topic has been treated as the de facto place for spaceship discussion, despite the restrictive name. In fact, the first reply in this topic doesn't talk about 3c/7 orthogonal or 2c/9 diagonal spaceships. In an attempt to remedy this, I created a spaceship discussion thread that I hope will become the new place to discuss low-period spaceship searches.
Oh, that definitely makes more sense.

(in that case, can you rename this thread?)

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

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

Post by Sokwe » February 18th, 2016, 5:11 pm

muzik wrote:in that case, can you rename this thread?
I would prefer that people just start using the new thread. The reason I created that thread was to consolidate discussion from a number of different spaceship search threads (that's why I provided all of those links in the first post).
-Matthias Merzenich

User avatar
muzik
Posts: 5612
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

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

Post by muzik » June 14th, 2016, 1:02 pm

Looks like we finally have a 3c/7. Success! (now for the 2c/9)


Some of the partials for other speeds in this thread look quite promising, to say the very least. My personal favourite is the 3c/8, which certaintly needs some looking into. There are some nice c/8s here as well, but I feel the discovery of the first caterloopillar kind of put off the search for a c/8 elementary...

One disappointment was the lack of decent 2c/9 diagonal partials. Oh well. I feel like we won't be finding a spaceship of that description for long time.

It just kind of pains me to see some of these fatanstic partials lying in this old, abandoned thread... should I repost them in the new spaceship discussion thread?

Post Reply