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

Four new almost-knightships CGOL

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Four new almost-knightships CGOL

Postby rokicki » February 14th, 2018, 12:13 am

Here are four more "almost-knightships" (1,2)c/6 that leave only two pixels wrong.
These are larger, but maybe someone can be clever enough to fix them . . . they
all share much of each other's prefixes.

Population 129:

x = 23, y = 34, rule = B3/S23
3b3o$3bo2bo$3bob2ob2o$2b2o7b2o$bo5bo4bo$bo5bob2o3bo$o5bo3bobobo$o4b2o
3bobobo$bo3bo3bo$bobobobo2bobo$8bobob2o$6b2o5bo2b2o$13b5o$10bo2bo4bo$
10bobob2o$9b2ob2o3b2o$12bo2b2o$12b2obobo$13bo2b2obo$10b2obo5bo$11b4ob
3o$15bo2bobo$18bobo$19b2o$11b3o5bo2bo$22bo$16b2o4bo$11bo4bo3bo$11b3o2b
obo$14bo2b2obo$11bo2bo2b2o$19bo$12b3o$12b2o!


Population 149:

x = 25, y = 39, rule = B3/S23
3b3o$3bo2bo$3bob2ob2o$2b2o7b2o$bo5bo4bo$bo5bob2o3bo$o5bo3bobobo$o4b2o
3bobobo$bo3bo3bo$bobobobo2bobo$8bobob2o$6b2o5bo2b2o$13b5o$10bo2bo4bo$
10bobob2o$9b2ob2o3b2o$12bo2b2o$12b2obobo$13bo2b2obo$10b2obo5bo$11b4ob
3o$15bo2bobo$18bobo$19b2o$11b3o5bo2bo$22bo$16b2o4bo$11bo4bo3bo$11b3o2b
obo$14bo2b3o$11bo2bo2bo2bo$19b2o2bo$12b3o3bob3obo$12b2o6bobobo$17bo$
17bo2bo$19b2o$21b3o$20bobo!


Population 182:

x = 32, y = 47, rule = B3/S23
3b3o$3bo2bo$3bob2ob2o$2b2o7b2o$bo5bo4bo$bo5bob2o3bo$o5bo3bobobo$o4b2o
3bobobo$bo3bo3bo$bobobobo2bobo$8bobob2o$6b2o5bo2b2o$13b5o$10bo2bo4bo$
10bobob2o$9b2ob2o3b2o$12bo2b2o$12b2obobo$13bo2b2obo$10b2obo5bo$11b4ob
3o$15bo2bobo$18bobo$19b2o$11b3o5bo2bo$22bo$16b2o4bo$11bo4bo3b2o$11b3o
2bobo$14bo2b3o2bo$11bo2bo2b4o7bo$20bob2ob3obo$12b3o5bobo2b2o2bo$12b2o
8bobo2bo$22bo2bobo$22bo2b4o$23b2o2b2o$28bo$25bobo$25bo3b2o$25bo2$25bob
obo$24b2ob2ob2o$24b2ob2o2bo2$28bo!


Population 278:

x = 38, y = 68, rule = B3/S23
3b3o$3bo2bo$3bob2ob2o$2b2o7b2o$bo5bo4bo$bo5bob2o3bo$o5bo3bobobo$o4b2o
3bobobo$bo3bo3bo$bobobobo2bobo$8bobob2o$6b2o5bo2b2o$13b5o$10bo2bo4bo$
10bobob2o$9b2ob2o3b2o$12bo2b2o$12b2obobo$13bo2b2obo$10b2obo5bo$11b4ob
3o$15bo2bobo$18bobo$19b2o$11b3o5bo2bo$22bo$16b2o4bo$11bo4bo3bo$11b3o2b
obo$14bo2b3o$11bo2bo2bo2bo$19b2o2bo$12b3o3bob3obo$12b2o6bobobo$17bo$
17bo3bo$23bob2o$20b4o$19bo3bo3bo$20b3ob4o$22bob4o$18b5ob5o$18bo2bo5bo$
18bob2o5b2o$18bo3bo4bob2o$22bo3bo$19b3o2$20b3o$20bo$21b3o$24bo$22b3o$
21bo3b2o$21b3obo$25bob2o$20bo5bo2bo$20bo2b2o2b2obo$20b3o5bo2bo$21bo9bo
3b3o$21b3o3bo2bo2b2ob2o$21b2ob2obo2bo2b2o$23b3obobo3b2o$29bobobo$25b7o
bo$25bobo6bo$31b4o2bo$33bo2b2o!
rokicki
 
Posts: 46
Joined: August 6th, 2009, 12:26 pm

Re: Four new almost-knightships CGOL

Postby Sokwe » February 14th, 2018, 2:05 am

rokicki wrote:Here are four more "almost-knightships" (1,2)c/6 that leave only two pixels wrong.
These are larger, but maybe someone can be clever enough to fix them.

These are great! How did you find them?

rokicki wrote: they all share much of each other's prefixes.

I have actually seen the front of these partials before, but I never found anything as long as your last partial. I was originally interested in this partial, because it splits into two "strands" around rows 23 to 26. In your partials the strands quickly come back together to form a single strand again. It may be possible to find completions to each of these strands separately by searching in different directions (with WLS or something similar). I tried this several years ago, but did not get very far.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1254
Joined: July 9th, 2009, 2:44 pm

Re: Four new almost-knightships CGOL

Postby rokicki » February 14th, 2018, 1:22 pm

I found them using some ideas in other search programs, but using a SAT solver to do the actual searching.

Instead of row-by-row though, I kept a queue of partials, where here I define a partial as a pattern that, when advanced 6 generations and shifted by (-1, -2), had all differences (error bits) in a small (6x6, 7x7) rectangle on the lower right. For each partial, I put a square of "unknowns" that completely encompassed the error region (typically 9x9, 10x10, 11x11, and 12x12, but I've used as large as 15x15) and asked the SAT solver to find another (or rather, all) partials based on that. And then I just keep going. I run the small unknown squares first because they are fastest, but if I get stuck I'll run larger unknown regions.

At first I was excited because I was getting all of these partials really quickly and many of them seemed very promising. But after running things for about a week, I'm realizing that just because a partial is "close" doesn't mean it's necessarily actual progress towards a knightship.

Some of the partials get pretty big:

x = 54, y = 73, rule = B3/S23
3b3o$3bo2bo$3bob2ob2o$2b2o7b2o$bo5bo4bo$bo5bob2o3bo$o5bo3bobobo$o4b2o
3bobobo$bo3bo3bo$bobobobo2bobo$8bobob2o$6b2o5bo2b2o$13b5o$10bo2bo4bo$
10bobob2o$9b2ob2o3b2o$12bo2b2o$12b2obobo$13bo2b2obo$10b2obo5bo$11b4ob
3o$15bo2bobo$18bobo$19b2o$11b3o5bo2bo$22bo$16b2o4bo$11bo4bo3bo$11b3o2b
obo$14bo2b3o$11bo2bo2bo2bo$19b2o2bo$12b3o3bob3obo$12b2o6bobobo$17bo$
17bo3bo$23bob2o$20b4o$19bo3bo3bo$20b3ob4o$22bob4o$18b5ob5o$18bo2bo5bo$
18bob2o5b2o$18bo3bo4bob2o$22bo3bo$19b3o2$20b3o$20bo$21b3o$24bo$22b3o$
21bo3b2o$21b3obo$25bob2o$20bo5bo2bo$20bo2b2o2b2obo$20b3o5bo2bo$21bo9bo
3b3o8b2o$21b3o3bo2bo2b2ob2o6b3ob2o$21b2ob2obo2bo2b2o8b2obobo$23b3obobo
3b2o7bo2bo2bo$29bobobo7b3o4bo$25b7obo8bo7bo$25bobo6bo7bobo5bo$31b2obo
2bo4bobo2bo3bo$35b2ob2o3bo4b3ob2o$36bob3o4bo7bo$38bo5bo3b3o$45bo3bo2b
2o$49b4o$49b2obo!


but then don't seem to extend easily any more.

I have thousands of partials with small error regions; it's not impossible that any
single one might be fixable. But the technique I'm using is probably running out
of steam and might need some refinements.

(I actually have many more partials than this; I canonicalize all partials that differ
only in the lower-right 8x8 square, and then ensure my "unknown" region overlaps
this fully.)

Based on this work over the past week, I'd have to say there's a good chance there's
an elementary (1,2)c/6 knightship out there, and it may well be found by someone
pretty soon using SAT solvers or other techniques. But at present based on the
results I have so far I probably would need to continue another two years before finding
an actual knightship.

And I believe the knightship found by this technique may well be extremely large;
perhaps a population of 1000 or more.

I'm a novice at these searches and have been helped tremendously by some suggestions
by a couple of members of this board. Maybe there are some other ideas out there that
will allow us progress.
rokicki
 
Posts: 46
Joined: August 6th, 2009, 12:26 pm

Re: Four new almost-knightships CGOL

Postby calcyman » February 15th, 2018, 9:59 am

I'd like to congratulate Tom for what is probably the first non-trivial progress on finding a knightship since Eugene Langvagen's almost-knightship and Tim Coe's partial.

Sokwe wrote:I have actually seen the front of these partials before, but I never found anything as long as your last partial. I was originally interested in this partial, because it splits into two "strands" around rows 23 to 26. In your partials the strands quickly come back together to form a single strand again. It may be possible to find completions to each of these strands separately by searching in different directions (with WLS or something similar). I tried this several years ago, but did not get very far.


Interestingly, my current knightship search (which has been running continuously for about 3 days) has also found exactly the same front as the one you mention. The current longest partial it has emitted is this one (about 2 hours ago, I estimate):

x = 40, y = 53, rule = B3/S23
3b3o$3bo2bo$3bob2ob2o$2b2o7b2o$bo5bo4bo$bo5bob2o3bo$o5bo3bobobo$o4b2o
3bobobo$bo3bo3bo$bobobobo2bobo$8bobob2o$6b2o5bo2b2o$13b5o$10bo2bo4bo$
10bobob2o$9b2ob2o3b2o$12bo2b2o$12b2obobo$13bo2b2obo$10b2obo5bo$11b4ob
3o$15bo2bobo$18bobo$19b2o$11b3o5bo2bo$22bo$16b2o4bo$11bo4bo3bo$11b3o2b
obo$14bo2b3ob2o$11bo2bo2b4obo$19b2obo$12b3o7bo$12b2o3b2o$17b2o4b2o$15b
3obo5bo$15b2ob2o5bo$16b2obo6bo$18bo5bo2bo$19bo4bo2bo$19bob2o2bob2o$20b
3o4b2o$22bo5bo$20bo3b2obob3o$21b2o4b2o2bo$22bo2b2o2bobo$21bo4bo2bo3bo$
21bobob2o3b4o$21bob2ob2o6bo$22b3o2bo2bobo2b3o$22bo3bo7b4o$23bo2b2o2b2o
$24bob3o2b3o3b3o!


My search program uses a hybrid of David Eppstein's gfind methodology together with deep lookaheads using tom-iglucose (Tom Rokicki's interactive version of Marijn Heule's incremental version of Glucose 3.0).
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1620
Joined: June 1st, 2009, 4:32 pm

Re: Four new almost-knightships CGOL

Postby A for awesome » February 15th, 2018, 11:18 am

Note that the second almost-knightship in the original post trivially leads to another one with two cells difference:
x = 24, y = 40, rule = B3/S23
3b2o$2b2o$4b2obo$2bo3b3ob2o$b6ob2o2bo$2ob2o4bo$o4bo6bobo$5o4b3o2bo$3ob
o4b2o$5b2o2bobo$bo3b2o3b2o$6bo3bo2bobo$9b3o2b3o$9b2obo$11bob3ob2o$9bo
2bo$8b2obo2bobo$8b2o2b3o$9bo2bo2bobo$9b2obob2o2b2o$11bob3o$17b3o$18b2o
2$10b2o6bo2bo$10b2obo4b4o$11b2o3b5o$11bo3b2o$11b2o4bo$11bo4b2o$9b5o2bo
2bo$12bo5b2o$11b2o6bob3o$12bo4b2o3b2o$15b4o$18b2o$19bo3bo$20b2o$21bo$
18b2o!


Also, has anyone tried searching for (2,1)c/7 using a similar approach?
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1616
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: Four new almost-knightships CGOL

Postby calcyman » February 15th, 2018, 12:41 pm

A for awesome wrote:Also, has anyone tried searching for (2,1)c/7 using a similar approach?


I'm in the process of modifying my search program to accept arbitrary velocities (a, b)c/p such that gcd(a, b, p) = 1. Then searching for p7 knightships and suchlike will be routine (although I imagine computationally harder than finding a p6 knightship).
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1620
Joined: June 1st, 2009, 4:32 pm

Re: Four new almost-knightships CGOL

Postby Macbi » February 15th, 2018, 12:45 pm

Obviously I can't tell anyone what to care about, but I think (2,1)c/7 ships are a bit less interesting than (2,1)c/6 ships, because it's already known that ships with speed (2,1)c/7 exist (with a much higher period). So a more interesting speed to search might be (3,1)c/8.
User avatar
Macbi
 
Posts: 455
Joined: March 29th, 2009, 4:58 am

Re: Four new almost-knightships CGOL

Postby Gamedziner » February 15th, 2018, 6:16 pm

Is it possible to fuse any of these partials?
Gamedziner
 
Posts: 466
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: Four new almost-knightships CGOL

Postby 77topaz » February 15th, 2018, 6:27 pm

Gamedziner wrote:Is it possible to fuse any of these partials?


No, I don't think that would work, because all of these partials share the same front end. It's the fact that there isn't a stable (2,1)c/6 back end that's preventing the construction of a proper knightship. If there was a partial with a stable front end and a partial with a stable back end, then, sure, trying to fuse them could lead to a solution; however, with these partials it wouldn't be beneficial.

So, has anyone tried to search (or is it even possible to search) for a partial that has a stable back end, with any misalignments occurring at the front of the ship?
User avatar
77topaz
 
Posts: 657
Joined: January 12th, 2018, 9:19 pm

Re: Four new almost-knightships CGOL

Postby rokicki » February 15th, 2018, 6:33 pm

I have tried to find a partial back end, and not been successful; for whatever reason my
programs are running so much slower for the back end. I do not know why; might be a bug.

The partials I have for the tail are so laughably small they are not worth posting (and the
bit error count is high too). But there *are* some partials (for some definition of partials).
rokicki
 
Posts: 46
Joined: August 6th, 2009, 12:26 pm

Re: Four new almost-knightships CGOL

Postby Sokwe » February 15th, 2018, 7:37 pm

rokicki wrote:I have tried to find a partial back end, and not been successful; for whatever reason my
programs are running so much slower for the back end. I do not know why; might be a bug.

Searches for back ends always seem much slower, at least in Life. You will probably see this if you try running gfind with the 'r' parameter or searching for a spaceship from the back end with WLS. Of course, you might still have bugs in your program, but I would expect a reverse search to be slower even with a bug-free program.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1254
Joined: July 9th, 2009, 2:44 pm

Re: Four new almost-knightships CGOL

Postby 77topaz » February 15th, 2018, 7:50 pm

Hmm... the fact that back end searches are slower than front end ones might have to do with the fact that, when it is the front end that is stable, the stable part moves away from the instability, while with a stable back end the stable part moves towards the instability, and thus wouldn't last as long before being caught up in it. I can see why that would make it more difficult to find a stable back end.
User avatar
77topaz
 
Posts: 657
Joined: January 12th, 2018, 9:19 pm

Re: Four new almost-knightships CGOL

Postby AforAmpere » February 15th, 2018, 7:56 pm

Will these programs become public? Also, will they only work with glucose, or will they work with things like lingeling?
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: 656
Joined: July 1st, 2016, 3:58 pm

Re: Four new almost-knightships CGOL

Postby rokicki » February 15th, 2018, 11:41 pm

AforAmpere wrote:Will these programs become public? Also, will they only work with glucose, or will they work with things like lingeling?


You really don't want me to release them in their current state. They use the filesystem as a poor-man's database, creating literally millions of files, spawning hundreds of processes. They aren't tied to glucose other than we do use an incremental version of glucose that's been modified so we can make the subsequent subproblems depend on the solutions to the prior subproblems; most SAT solvers can probably be modified in similar ways or else a C API used.

Truly, most everything I'm doing you can do with a few Python scripts and the LLS program (though you do need changes to support incremental so you can pull more solutions more rapidly).

I suspect calcyman's code will be strictly more powerful and more useful than anything I've put together; I'm just trying some very opportunistic exploration of the space. But if something comes of this be assured I'll ensure others can duplicate the work, one way or the other.
rokicki
 
Posts: 46
Joined: August 6th, 2009, 12:26 pm

Re: Four new almost-knightships CGOL

Postby rokicki » February 16th, 2018, 11:42 am

Here are two related near-misses for (1,2)c/7:

x = 11, y = 11, rule = B3/S23
3bo$2b3o$b3obo$2ob3o$bob2o$b3o4b3o$8bo$3b2o2b2o$3b2o4bo2$5bobo!


x = 9, y = 13, rule = B3/S23
2bo$bobo$o3bo$o2b2o$3o$bo4bo$6bo$2bo$2bob3obo$b2obo3bo$4b2o$bo2bo$2bo!


And another near-miss; maybe somebody can complete it.

x = 29, y = 23, rule = B3/S23
3bo$2b2o$b3o$2o2bobo$3b3o2bo$8b2o$5bo4b2obobobo$2b4ob2o6bobo$8bo3bo4bo
$15b2o$9b7o$8b2o$8b2o2b5ob3o$8b4o2b4o$12bo8bo$12b3ob2ob2o$14b2o3b7o$
15bobo3bo4bo$15bobo3bo2bo$26bo$23b3o$24b3obo$26bo!
rokicki
 
Posts: 46
Joined: August 6th, 2009, 12:26 pm


Return to Patterns

Who is online

Users browsing this forum: No registered users and 2 guests

cron