Page 1 of 1

### Four new almost-knightships CGOL

Posted: 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/S233b3o\$3bo2bo\$3bob2ob2o\$2b2o7b2o\$bo5bo4bo\$bo5bob2o3bo\$o5bo3bobobo\$o4b2o3bobobo\$bo3bo3bo\$bobobobo2bobo\$8bobob2o\$6b2o5bo2b2o\$13b5o\$10bo2bo4bo\$10bobob2o\$9b2ob2o3b2o\$12bo2b2o\$12b2obobo\$13bo2b2obo\$10b2obo5bo\$11b4ob3o\$15bo2bobo\$18bobo\$19b2o\$11b3o5bo2bo\$22bo\$16b2o4bo\$11bo4bo3bo\$11b3o2bobo\$14bo2b2obo\$11bo2bo2b2o\$19bo\$12b3o\$12b2o!`

Population 149:

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

Population 182:

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

Population 278:

`x = 38, y = 68, rule = B3/S233b3o\$3bo2bo\$3bob2ob2o\$2b2o7b2o\$bo5bo4bo\$bo5bob2o3bo\$o5bo3bobobo\$o4b2o3bobobo\$bo3bo3bo\$bobobobo2bobo\$8bobob2o\$6b2o5bo2b2o\$13b5o\$10bo2bo4bo\$10bobob2o\$9b2ob2o3b2o\$12bo2b2o\$12b2obobo\$13bo2b2obo\$10b2obo5bo\$11b4ob3o\$15bo2bobo\$18bobo\$19b2o\$11b3o5bo2bo\$22bo\$16b2o4bo\$11bo4bo3bo\$11b3o2bobo\$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\$21bo9bo3b3o\$21b3o3bo2bo2b2ob2o\$21b2ob2obo2bo2b2o\$23b3obobo3b2o\$29bobobo\$25b7obo\$25bobo6bo\$31b4o2bo\$33bo2b2o!`

### Re: Four new almost-knightships CGOL

Posted: 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.

### Re: Four new almost-knightships CGOL

Posted: 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/S233b3o\$3bo2bo\$3bob2ob2o\$2b2o7b2o\$bo5bo4bo\$bo5bob2o3bo\$o5bo3bobobo\$o4b2o3bobobo\$bo3bo3bo\$bobobobo2bobo\$8bobob2o\$6b2o5bo2b2o\$13b5o\$10bo2bo4bo\$10bobob2o\$9b2ob2o3b2o\$12bo2b2o\$12b2obobo\$13bo2b2obo\$10b2obo5bo\$11b4ob3o\$15bo2bobo\$18bobo\$19b2o\$11b3o5bo2bo\$22bo\$16b2o4bo\$11bo4bo3bo\$11b3o2bobo\$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\$21bo9bo3b3o8b2o\$21b3o3bo2bo2b2ob2o6b3ob2o\$21b2ob2obo2bo2b2o8b2obobo\$23b3obobo3b2o7bo2bo2bo\$29bobobo7b3o4bo\$25b7obo8bo7bo\$25bobo6bo7bobo5bo\$31b2obo2bo4bobo2bo3bo\$35b2ob2o3bo4b3ob2o\$36bob3o4bo7bo\$38bo5bo3b3o\$45bo3bo2b2o\$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.

### Re: Four new almost-knightships CGOL

Posted: 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/S233b3o\$3bo2bo\$3bob2ob2o\$2b2o7b2o\$bo5bo4bo\$bo5bob2o3bo\$o5bo3bobobo\$o4b2o3bobobo\$bo3bo3bo\$bobobobo2bobo\$8bobob2o\$6b2o5bo2b2o\$13b5o\$10bo2bo4bo\$10bobob2o\$9b2ob2o3b2o\$12bo2b2o\$12b2obobo\$13bo2b2obo\$10b2obo5bo\$11b4ob3o\$15bo2bobo\$18bobo\$19b2o\$11b3o5bo2bo\$22bo\$16b2o4bo\$11bo4bo3bo\$11b3o2bobo\$14bo2b3ob2o\$11bo2bo2b4obo\$19b2obo\$12b3o7bo\$12b2o3b2o\$17b2o4b2o\$15b3obo5bo\$15b2ob2o5bo\$16b2obo6bo\$18bo5bo2bo\$19bo4bo2bo\$19bob2o2bob2o\$20b3o4b2o\$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).

### Re: Four new almost-knightships CGOL

Posted: 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/S233b2o\$2b2o\$4b2obo\$2bo3b3ob2o\$b6ob2o2bo\$2ob2o4bo\$o4bo6bobo\$5o4b3o2bo\$3obo4b2o\$5b2o2bobo\$bo3b2o3b2o\$6bo3bo2bobo\$9b3o2b3o\$9b2obo\$11bob3ob2o\$9bo2bo\$8b2obo2bobo\$8b2o2b3o\$9bo2bo2bobo\$9b2obob2o2b2o\$11bob3o\$17b3o\$18b2o2\$10b2o6bo2bo\$10b2obo4b4o\$11b2o3b5o\$11bo3b2o\$11b2o4bo\$11bo4b2o\$9b5o2bo2bo\$12bo5b2o\$11b2o6bob3o\$12bo4b2o3b2o\$15b4o\$18b2o\$19bo3bo\$20b2o\$21bo\$18b2o!`

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

### Re: Four new almost-knightships CGOL

Posted: 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).

### Re: Four new almost-knightships CGOL

Posted: 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.

### Re: Four new almost-knightships CGOL

Posted: February 15th, 2018, 6:16 pm
Is it possible to fuse any of these partials?

### Re: Four new almost-knightships CGOL

Posted: 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?

### Re: Four new almost-knightships CGOL

Posted: 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).

### Re: Four new almost-knightships CGOL

Posted: 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.

### Re: Four new almost-knightships CGOL

Posted: 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.

### Re: Four new almost-knightships CGOL

Posted: 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?

### Re: Four new almost-knightships CGOL

Posted: 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.

### Re: Four new almost-knightships CGOL

Posted: February 16th, 2018, 11:42 am
Here are two related near-misses for (1,2)c/7:

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

`x = 9, y = 13, rule = B3/S232bo\$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/S233bo\$2b2o\$b3o\$2o2bobo\$3b3o2bo\$8b2o\$5bo4b2obobobo\$2b4ob2o6bobo\$8bo3bo4bo\$15b2o\$9b7o\$8b2o\$8b2o2b5ob3o\$8b4o2b4o\$12bo8bo\$12b3ob2ob2o\$14b2o3b7o\$15bobo3bo4bo\$15bobo3bo2bo\$26bo\$23b3o\$24b3obo\$26bo!`