amling search program principles discussion / brain dump

For scripts to aid with computation or simulation in cellular automata.
amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

amling search program principles discussion / brain dump

Post by amling » May 4th, 2022, 6:59 pm

Sokwe wrote:
May 4th, 2022, 3:58 am
amling wrote:
May 4th, 2022, 3:52 am
If I'm gonna invent horrible tools for branching, turning, and stitching searches, I might as well use them:
Okay, that's absolutely incredible! Fair warning: your amazing patterns are going to result in me badgering you for your methods soon.
Oh, goodness, so many questions to decide what to write...

What level of math/CS background do you want it written to? CS is obviously more relevant, but math sort of is, there are a lot of abstract algebra bits surrounding the handling of geometry that I could explain or elide (describing only the special case of the most common sort of geometry used).

Are you looking for like 5 words of explanation? 50? 500? 5000? I am happy to write quite a bit and I have long wanted to get some sort of meeting of minds with other game of life people, but I have very little idea where/how search program authors hang out.

How much do you know about how gfind/lsss work? I only know how much I could understand from skimming the gfind source/docs 20+ years ago and from reading some doc about lsss design principles more recently, but they are both useful points of comparison as my two main search programs are vaguely analogous [to how I think those two programs work].

Do you want just to understand? To know enough to run the same sorts of searches? How much do you want to know about the programs in general versus just what I did to complete quartermax and that other 2c/4 wave? There is a big difference between just wondering about the mechanisms of the search and actually getting searches set up and running.

The code for all my search stuff has long been up on github [1] although it is thoroughly undocumented, user hostile, and extremely "research programming" quality at best. Unless you super love diving into insane other people's code I would spend some time with me on this thread before looking.

[1] https://github.com/amling/rlife

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

Re: amling search program principles discussion / brain dump

Post by Sokwe » May 4th, 2022, 9:24 pm

amling wrote:
May 4th, 2022, 6:59 pm
What level of math/CS background do you want it written to?... Are you looking for like 5 words of explanation? 50? 500? 5000?
However you're most comfortable explaining it. There are a fair number of people here with math and/or CS backgrounds (including myself) so I think any technical level is acceptable. Personally, I welcome as much detail at whatever technical level is necessary to fully understand the concepts.
amling wrote:
May 4th, 2022, 6:59 pm
Do you want just to understand? To know enough to run the same sorts of searches? How much do you want to know about the programs in general versus just what I did to complete quartermax and that other 2c/4 wave? There is a big difference between just wondering about the mechanisms of the search and actually getting searches set up and running.
I'm interested in both understanding the details of the search technique and how to set up useful searches using your program. I suspect I'm not the only one who's curious.
amling wrote:
May 4th, 2022, 6:59 pm
How much do you know about how gfind/lsss work?
Many people (including myself) have a reasonably complete understanding of how gfind works. I don't think very many have a complete idea of how LSSS works, but I do think several people have at least a surface-level understanding. If your program is only "vaguely analogous" to these, then I imagine a surface-level understanding is enough.
amling wrote:
May 4th, 2022, 6:59 pm
I have long wanted to get some sort of meeting of minds with other game of life people, but I have very little idea where/how search program authors hang out.
I think most discussion occurs here on the forums, at least when it comes to spaceship searching. There's also some discussion on the Discord server linked at the top of the page, although that user base overlaps almost completely with the user base here.
-Matthias Merzenich

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 4th, 2022, 10:49 pm

[I'm gonna type notes up and submit in pieces as I go, rather than all at once. Hopefully this is not considered a breach of forum etiquette on a rando stream of conscious thread like this one.]

Part 0: "GOL".

My understanding, based on reading gfind source code and docs, as a highschooler, 20+ years ago, was that gfind operated conceptually by thinking of ships as a path in a graph. Vertices in the graph were were two rows of the ship tall and however wide the search was, and included the values of cells in every generation (were they staggered in later generations for speeds that were not c/N? I did not know.). I think gfind did a breadth-first search through this graph, starting at the all-zeros two row "slice" vertex and looking to get back to that same vertex.

"GOL" was my implementation of this (did stagger rows up/down in later generations based on speed). So named because it was the "game of life" graph part of a more general graph searcher. Also, I wrote it to do depth-first-search originally but because I abstracted the graph part so carefully was able to write BFS implementation(s) later without having to muck around in a bunch of game of life-specific code.

Why does any of this part matter? It doesn't, not really, but it explains why part 1 is gonna be called "LGOL".

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 4th, 2022, 11:04 pm

Part 1a: "LGOL".

"GOL" was fine, but I had a lot of things I wanted to do, many of which the architecture (or lack there of) was struggling to handle. I especially wanted to allow cells off the edge of a row (off to the right or left) to be considered to take values from a "background" agar, like parallel or perpendicular stripes. The "GOL" CA check code was also a total rat's nest of geometry, especially dealing with figuring out which row to pull cell values from.

In the end I wrote a completely separate graph implementation (but remember, due to architecture could reuse for free the DFS and BFS search harnesses).

The original "LGOL" differed mostly from "GOL" in that rather than think of everything in x/y/t coordinates, it was all in u/v/w coordinates and it thought of space as made of a giant lattice with U/V/W being the generators. For LGOL's code only the "W" direction is special, which I would call "up" and "down", and indicates the direction in which the search progresses. The other two vectors must complete a basis for 3-space. Generally when I was configuring it, U would point in the X direction and represent "left" / "right" conceptually and V would point in a time-like direction (e.g. for a 2c/4 search with ship heading "up Y" V would be (0, -2, 4)).

Instead of keeping 2 Y rows as GOL did, LGOL would keep however many W steps were necessary to be able to CA checks. Generally this equates to "two rows", but for interesting values of U/V/W could be quite a few lattice volumes. LGOL allowed fairly general configuration for what U/V meant and how cell values were determined "out of bounds". Every search I have ever run would "wrap" for V values (since it was the translation vector). Most would configure zeros or a background agar (or two) for out of U bounds.

Some examples, perhaps.

If I were searching typical front-to-back 2c/4, I would pick V = (0, -2, 4) and wrap OOB v to make it 2c/4 "up Y". I would pick U = (M, 0, 0) to make "rows" (lattice volumes) however (M) wide. I would pick W = (0, 0, 1). Note not W = (0, 1, 0). The latter works but it makes lattice volumes bigger than necessary. An individual lattice volume would be 2M cells and consist of two "X rows" of M cells each, separates by V/2 (0, -1, 2) from each other. CA checks end up needing 4 "rows" (lattice volumes) of lookback which of course conceptually is "2 Y rows".

If I were searching back-to-front 2c/5 I would pick V = (0, 2, 5) and wrap OOB v to make it 2c/5 "down Y". I would pick U = (M, 0, 0) just the same. Now picking W is tricky. I want it to be "negative time like", which is to say have the same determinant sign UVW as W = (0, 0, -1). But instead I can make lattice volumes smaller by picking W = (0, 1, 2). This trick sort of corresponds to the "row staggering" I was talking about earlier in GOL (and/or gfind?). An individual lattice volume would be M cells. CA checks end up needing 10 "rows" (lattice volumes) of lookback which is, again, "2 Y rows".

Anyway, that is all boring and especially painful but it gets rid of a lot of hideous edge cases in CA check code and bitvector management. Most searches pick V to be translation, U to be (M, 0, 0), W to be some weirdo vector to minimize lattice volume and are set.

The more interesting bit is all the other search-constraining features...

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 4th, 2022, 11:14 pm

Part 1b: "LGOL some more".

I had mentioned earlier that (I believed) gfind started at the all-zeros vertex and searched for a return to it. One problem that came up when I allowed OOB cells to take values from a background is that an all-zeros vertex doesn't really make sense any more, neither as where to start, nor here to hope to end up.

Even very early on LGOL allowed code to load up whatever initial state was desired, e.g. a starting "known joint" when searching for greyship parts. It also has a fairly complex idea of what constitutes an "end" result. All searches will detect and output "cycles", meaning we've return to the same vertex. I have no idea (and am especially interesting) what gfind does about cycles. Searches are also configured with a choice of "ends". Common examples are (a) only the all-zeros vertex, (b) no ends at all, (c) some collection of predefined end slices. The code contains a few more experimental choices, most of which have never really gone anywhere (except the period-dividing one which I'll get to later).

(a) is for normal searches. (b) would be for something like a greyship edge search where only cycles matter. (c) would be for something like trying to solve a back-to-front problem by searching front-to-back.

LGOL also allows "constraints" to be places on lattice volumes. The most common is a limited U-coordinate "width" which all nonzeros cells (or all cells deviating from background) must be within of each other (herein "window"). The second most common is "period dividing" where I've specified K, an integer divisor of V and a maximum number of cohorts of cells mod V/K which are allowed to be non-constant. E.g. I could be searching 6c/12 and pick K=2 to limit the number of 2-cell cohorts which fail to be 3c/6 or I could pick K=3 to limit the number of 3-cell cohorts which fail to be 2c/4 or I could pick K = 6 to limit the number of 6-cell cohorts which fail to be c/2.

Finally one last "edge" trick is an axis (always U in practice) could be configured to "recenter", meaning after completing each lattice volume the position of the "next" (as in one W step later) lattice volume would be shifted in the U direction to recenter the nonzero (or non-matching-background) contents. This recentering is probably the single most important thing LGOL does.

To summarize, describing an LGOL search requires: geometry, start node(s), edge/axis behaviour, ends.
Last edited by amling on May 4th, 2022, 11:24 pm, edited 1 time in total.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 4th, 2022, 11:17 pm

Part 1c: "LGOL implementation errata".

Placeholder for the details of the graph formalization that splits BFS and DFS from GOL and LGOL.

Placeholder for the details of how the BFS search happens, when it saves state, what it does when it realizes it's about to fill memory, how it parallelizes, etc.

Placeholder for the details of how the CA check works and in particular the table-makery and PEXT nonsense that speeds it up.

I assume these are least interesting of anything I'm going to write, but I'll come back and fill them in if someone wants to know.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 4th, 2022, 11:23 pm

Part 1d: "Finally done with LGOL".

So what does it add up to? What has LGOL done? The three biggest tricks not [yet] reproduced in the second, lsss-analogous program are probably:

(*) The recentering means LGOL can be good at finding very wiggly results, sometimes finding things with very thin windows that would take a very large non-recentering search to find. A good (only?) example of this is 232P7H3V0 which was found by loading that very thin arm of the common 3c/7 frontend in as that "start" and running a fairly "thin" search. Even the smaller of the two results it found "wiggles" a lot compared to how wide it is at any give point.

(*) Period dividing constraint. The quartermax solution has an extremely short connection from the 4c/8 still life edge to the the rest of its 2c/4 self. This was found by a 4c/8 b2f LGOL search, configured as: (a) start = a slice of that wall, (b) recentering, although I don't think it mattered as much, (c) OOB = zeros on one side, perpendicular stripes on the other, (d) special ends that would check if the slice was all 2c/4-compatible, and (e) a constraint that limited extremely heavily the number of full-period 4c/8 cell cohorts in each lattice volume (it might have been as low as 1, I don't remember).

(*) Finding cycles. Relevant especially for greyship components where I don't want to have to guess the space-like period in advance, I just want the search to output when it notices it has looped.

It's also good that LGOL is fairly customizable and configurable and so can do other weird things like wrap the U axis as well, or fake up a million starting slices and see how long any of them make it, or any other weird programmatic behavior I can sketch up real fast.

On the flip side, I'm pretty sure it's very slow. I have tried very hard to optimize the CA check code, but the split nature of search harness / graph combined with its essential nature being pretty brute-forcey makes it I suspect slower than anything else out there when doing the same sort of search.

[If anyone is reading live, I'm gonna stop here for a moment. I promise I will move on to the other half, but I need a break.]

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 1:21 am

Part 1.5: "What is LSSS anyway?"

One reason LGOL tends to break down horrible in wider searches is that it keeps in memory a single entry for every current path through the vertex graph, which you can think instead of partial patterns at-and-above a certain row. With wider searches it seems like there are a lot of local choices that don't really affect the rest of the pattern, but LGOL has to store every possible product of them across the entire pattern.

So I read some LSSS docs, but I'm not sure I got it all right. It sounds to me like LSSS proceeds down similarly, and, ignoring intra-row order and business, at the end of each row LSSS should have a similar set of partial results. The difference being that LSSS only stores every 2 column slice that shows up once no matter how many would-be partial patterns it shows up in. I assume it keeps a set of column pairs for each horizontal position and a partial result as kept by LGOL corresponds to a choice from each such collection of pairs subject to some joining conditions between each pair of neighboring sets. In particular, the left column of the right pair must match the right column of the left pair, but also that CA checks must be met by the combined 3 columns. It is very unclear to me how LSSS efficiently does these CA checks to do joins.

I decided to give it a whirl and instead of keeping 2 column slices, I would keep 3 column slices where each neighboring set overlapped by 2 columns. It shuffles around where the CA check happens from during join to during construction of the column sets, but then joins are all easy (just compare the overlapping 2 columns). This makes the code way easier, in the sense that I am not even sure how I'd do the CA check during joins (I had some ideas but they are all extremely painful and unclear how they'd perform). Unfortunately it also blows memory way, way up. Each set of sets of 3 columns slices is way, way bigger than the equivalent set of sets of 2 column slices based on some stats I did and I assume this makes LSSS a lot better.

Something I've skipped over here is what is a 2 column slice anyway? Presumably it's two columns of cells for each generation. I assume they're staggered according to the V analog so that CA checks for 3 column slices can cover all CA checks.

Whether or not this is what LSSS does, it's what "LLSSS" does...
Last edited by amling on May 5th, 2022, 2:57 am, edited 1 time in total.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 1:32 am

Part 2a: "LLSSS plan"

I definitely didn't want to lose all the benefits of the lattice, so I had to make it make sense for what I understood of LSSS. V and W I kept as is from LGOL, but U is no longer the entire width of the pattern, it's just a minimum step. You can then think of the world again as split into lattice volumes (I called them "tiles" this time). Tiles have left/right neighbors in the U direction, up/down neighbors in the W direction, but no neighbors in the V direction (LLSSS hard-codes that V wraps).

It also gets confusing because due to the weird nature of the lattice geometry it is not guaranteed that "3" is the right width to make the column sets in order to force CA checks to be covered. For typical geometries it is, but weirder searches like diagonals, knightship, etc, depending on how it's configured these column widths can be bigger. Below I'll generally be writing "3", but if you go code diving know it's not so simple.

So at the end of each "row" (a step in the W direction), we have a set of 3-column strips at each U position. They are "closed" in that each has neighbors all the way to either edge of the pattern (those with no neighbors one way or another will have been filtered out). The program extends the left edge of 3-column strips "somehow", extends the right edge of 3-column strips, and starts joining/extending a column at a time until they meet in the middle, where they are matched up and anything that isn't matched is dropped, then drops are propagated back outwards all the way to the edges. Most of the details of this mess will not matter unless you are doing some serious code diving.

Similar to LGOL, LLSSS requires a great deal of configuration to define a search:

It needs some start rows ("deep" enough in the W direction to ensure CA consistency, generally "two Y rows"). Multiple sets of start rows doesn't quite make sense since trying to decide at the end whether or not a completed result "came from one consistent start" isn't clear and so I haven't implemented it. If multiple start rows were loaded it would all work, but results could be chimeric combinations of them (that are CA-consistent though!).

It needs to know how to extend an edge. This is always done by some custom behavior to extend the outer two columns and then use CA check to extend all third column choices. Obvious options are (a) always zero, (b) cycle previous values from the columns, e.g. to repeat an agar along the border forever, (c) some single constant set of 2 columns loaded from a file, (d) various symmetry reflections over the edge (odd/even/gutter plain/glide-reflect).

It needs to know how to recognize a result worth printing. Right now this is generally either (a) the last two "Y rows" are all zero or (b) the last some-configurable-number of rows meet some period division (e.g. 2c/4 search, but looking for c/2 ends).

I have quite a few thoughts about other options for all of these. LLSSS is pretty new, as some of my other posts imply.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 1:42 am

Part 2b: "LLSSS problems"

For comparable searches LLSSS absolutely slaughters LGOL. I had written some stats to see what the equivalent LGOL state sizes were for some searches and they were astronomical.

Alas, so many things are wrong/missing...

(*) Cycle detection. LLSSS has no way to know when it's found a cycle. I have a hack to terminate searches if all that's left is a single simple cycle, but it's still wasteful in terms of what repeated searching it does, it doesn't actually output the cycle, and it is very difficult to set up.

(*) Memory/CPU trade-off. The BFS search is pretty good at knowing how much memory it is using and falling back to filtering down by DFS so it can continue. LLSSS has a "bridge" mode where it will start DFSing across a row to avoid having to reify the unfiltered center columns but it is fundamentally limited in that the state after each row is what it would be either way so once that hits memory it's doomed.

(*) Recentering. I'm not even sure what it could mean here. The nature of LLSSS's state just does not lend itself to anything here. I could run a super wide field and try to filter for thinner patterns ("windowing"), but even this won't work. It will force all bits kept to be in a sense part of, sort of, a pattern which was thin but it won't force all the combinations to be thin. Maybe it would be enough? Windowing with a super wide field also seems like a profoundly crappy way to fake recentering.

(*) U wrapping. Dues to the way the edges meet in the middle and filter I see no way to handle any kind of U wrapping. This is not a super common search type, so w/e.

Cycle detection and recentering mostly just prevent me from running greyship edge searches, although I can think of times I probably would have liked recentering.

Memory trade-off is back-breaking right now. So many searches I want to run fill memory and die in under an hour, whereas I've run single LGOL searches for months on end (e.g. the one that found that quartermax 4c/8 -> 2c/4 reduction).

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 2:26 am

Part 2c: "LLSSS methods"

Okay, so that's what LLSSS does and doesn't, but how does it add up to finding patterns? I would say my three big tricks are "branch", "turn", and "period divide". To understand them a little more about how LLSSS is run is necessary.

Originally I was making up edge data and start data manually and it sucked. I kept wanting to take a given partly-known pattern and search from the middle of it, then search one wider, then one wider, etc. Every time the width increases it shifts the edges and so I'd have to hack them apart again. In the end I settled on a "picture" format. In a common configuration searches come in as a picture of each generation all together and some question marks marking where the search goes. E.g...

Code: Select all

  ...................**.*.*.*.*.*.*.*.*.*.*.* |  ...................**.*.*.*.*.*.*.*.*.*.*.* | .*.................*.*.*.*.*.*.*.*.*.*.*.*.  | ..................**.*.*.*.*.*.*.*.*.*.*.*.  
  ......**.**.*.......*.*.*.*.*.*.*.*.*.*.*.* |  .....*.*.***......*.*.*.*.*.*.*.*.*.*.*.*.* | .....**...**.......*.*.*.*.*.*.*.*.*.*.*.*.  | .....*...***.......*.*.*.*.*.*.*.*.*.*.*.*.  
  .....***.**...*..**.*.*.*.*.*.*.*.*.*.*.*.* |  ....**.*.*....**..*.*.*.*.*.*.*.*.*.*.*.*.* | .*..*...*.*......*.*.*.*.*.*.*.*.*.*.*.*.*.  | **..*.**.**......*.*.*.*.*.*.*.*.*.*.*.*.*.  
  *..**......***.****.*.*.*.*.*.*.*.*.*.*.*.* |  .*.****...*******.*.*.*.*.*.*.*.*.*.*.*.*.* | **..*..*...***...**..*.*.*.*.*.*.*.*.*.*.*.  | ...*.......****.**.*.*.*.*.*.*.*.*.*.*.*.*.  
  .***................*.*.*.*.*.*.*.*.*.*.*.* |  *...*.......*.*.....*.*.*.*.*.*.*.*.*.*.*.* | ***..........*.*...*.*.*.*.*.*.*.*.*.*.*.*.  | *.*..........**....*.*.*.*.*.*.*.*.*.*.*.*.  
  .**............******.*.*.*.*.*.*.*.*.*.*.* |  .*.*............***.*.*.*.*.*.*.*.*.*.*.*.* | ................***..*.*.*.*.*.*.*.*.*.*.*.  | .*.............****..*.*.*.*.*.*.*.*.*.*.*.  
  ....................*.*.*.*.*.*.*.*.*.*.*.* |  ...............*....*.*.*.*.*.*.*.*.*.*.*.* | ................*....*.*.*.*.*.*.*.*.*.*.*.  | ................*..*.*.*.*.*.*.*.*.*.*.*.*.  
  ................???.*.*.*.*.*.*.*.*.*.*.*.* |  ................???**.*.*.*.*.*.*.*.*.*.*.* | ................???*.*.*.*.*.*.*.*.*.*.*.*.  | ................???*.*.*.*.*.*.*.*.*.*.*.*.  
  ................???.*.*.*.*.*.*.*.*.*.*.*.* |  ................???.*.*.*.*.*.*.*.*.*.*.*.* | ................???*.*.*.*.*.*.*.*.*.*.*.*.  | ................???*.*.*.*.*.*.*.*.*.*.*.*.  
This is a 2c/4 search traveling leftward. As written it will have 3 columns that can actually vary (plus two bumpers on either side). The common configuration also inputs 3 pads, one to pad "up W", one to pad "left U", and one to pad "right U". They functionally expand the UVW prism of questions marks by the amount specified and let me reconfigure to run wider searches very quickly.

As you can imagine I do a lot of block mode editing and I additionally have a one-off script to rotate a file of this format clockwise so I can turn it around.

Under default configuration after each (W) row is completed, LLSSS will output the "firstest" partial. The exact ordering is complex and weird, but the end result is it's pretty stable from row to row and generally includes a lot of dead cells. It will also output a randomly chosen partial (not uniform over possible partials since there are so many, but in a way that is good enough to be interesting). This is of course generally chaotic, but gives you a sample of sorts of the search space in progress.

I am ashamed to admit it, but quite a few results have relied not on finding something as an end result, but rather from spotting something interesting in partial results and copying it over into a separate search.

I think that's enough to now talk about the techniques. Examples are hard to give since it's all a lot of data. I'm going to simplify my examples to a single generation and going to make their contents up.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 2:30 am

Part 2di: "LLSSS Branching"

For this trick I spot a partial which has a split in the middle. I copy a side over to another search and complete it if I can. Sometimes it'll be clear exactly how to split and I'll complete both separately. Often I'll complete the easier one and paste it back into the original search picture file leaving just the other branch. This allows me to widen the other branch search and step into part of the first branch. It also allows the search to maximally use clearance from the other branch, even for non-rectangular shapes.

So I might start with:

Code: Select all

...AAAAAAAAA...
...AAAAAAAAA...
...?????????...
and spot in the partials

Code: Select all

...AAAAAAAAA...
...AAAAAAAAA...
...B1B...C1C...
...B2B...C2C...
...B3B...C3C...
then copy the "B" part into its own search:

Code: Select all

...B1B...
...B2B...
...???...
That search can be widened one to the right, but if I widen it two to the right it would hit the current best guess for C. In some cases I would allow that and hope that C could sort itself out, but in most cases not. If widened one right this might end up solved like:

Code: Select all

...B1B...
...B2B...
...BDD...
...DDDD..
...DDDD..
Pasted back into the original partial and letting it redo the C side:

Code: Select all

...AAAAAAAAA...
...AAAAAAAAA...
...B1B...???...
...B2B...???...
...BDD...???...
...DDDD..???...
...DDDD..???...
Now the default assumption is to solve B with D, but if I widen it enough it could redo part of it. E.g. widening it 4 left is the equivalent of:

Code: Select all

...AAAAAAAAA...
...AAAAAAAAA...
...B1???????...
...B2???????...
...BD???????...
...DD???????...
...DD???????...
This could easily decide to stick its fingers into the B/D arm and change part of it, but it will be, as widened above, forced to keep those outer two columns. You might end up with something like:

Code: Select all

...AAAAAAAAA...
...AAAAAAAAA...
...B1B...C1C...
...B2EEEEEEC...
...BDE...EEC...
...DDDD..EE....
...DDDD........
I have definitely even had three branches going at once, generally solving as best as possible (with as much clearance) what I can and pasting it back to go on to the next one.

There is also the "unibranch" where I see some partial that has just a thin bit. Maybe it's in a search that is gonna fill memory and die (and thus not finish being searched), maybe it's far to one side or another and I think would really benefit from sliding the search window left or right. In these cases I will often copy the single "branch" into another search (maybe with some context so I can do some widening) and of course if it is solved alone it can be grafted back onto partial it came from.
Last edited by amling on May 5th, 2022, 2:47 am, edited 1 time in total.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 2:40 am

Part 2dii: "LLSSS Turning"

Branching works in LGOL as well, but it is not generally able to run searches wide enough for it to come up and with recentering on you can't stop branches from running into each other. Turning, however, is not a thing at all in LGOL. There is no analog of the forced edge contents and so it just plain isn't a thing.

For turning I will spot a point in partials where it lists in a better direction. Or in some cases I will just force it (e.g. I think quartermax completion started with a turn that was not inspired by any partial). "Better direction" means a direction searches generally are faster in, usually (a) I was doing a b2f search but will turn to s2s or (b) I was doing a s2s search and will turn to f2b. I did however notice that 2c/4 searches, especially thin ones, were doing weirdly well s2s and so I have had a handful of turns f2b -> s2s here or there when a branch has stuck out very prominently in one direction. It also helps that if you turn a branch "away" from a sibling branch it will generally have very, very good clearance.

For example, a search started as:

Code: Select all

...A1A......
...A2A......
...???......
might have a partial like

Code: Select all

...A1A......
...A2A......
....A3A.....
.....A4A....
......A5A...
So I'd rotate it...

Code: Select all

.....
.....
.....
...AA
..A21
.A3AA
A4A..
5A...
A....
.....
.....
.....
and truncate and start the search from where it looked like it was turning.

Code: Select all

.....
.....
.....
...AA
..?21
..?AA
..?..
..?..
..?..
..?..
..?..
..?..
I've written it one wide since I will generally always draw the smallest section of question marks I can that will force the CA checks to fix everything and then let the widening feature handle making the real search.

Now I might widen that left one and end up with:

Code: Select all

.....
.....
.....
...AA
..A21
.B3AA
.BB..
.BB..
.BB..
.BB..

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 2:43 am

Part 2diii: "LLSSS Period Dividing"

This one is the most straight-forward. I configure ends to output partials whose tips are compatible with some division of V. Most often 2c/4 -> c/2 although I have also done 4c/8 -> 2c/4 (not successfully though) and 4c/6 -> 2c/3 ("successful", although obviously only agar crawler nonsense).

I usually configure to require "4 Y rows" of reduced period since 2 Y rows will often be immediately impossible to complete and have a ton of useless duplicates. With 4 Y rows I prune the result back 2 Y rows, dedupe them if necessary, and they are much more often usable.

These are again generally completed at lower period and then pasted back into the bigger search in progress so whatever is left can use whatever clearance they leave exactly.

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 2:55 am

Part 2e: "LLSSS Summary"

The biggest results are of course quartermax and that wacky blinker puffer wave. I think if you look closely at those two you can probably guess the approximate flow of the search in terms of where I branched, turned, and period divided. I would rather not dig through the huge dump of partial search inputs and logs to try to sort it all back out exactly and show. Perhaps next time I solve something and it's fresh in my mind I'll try to dump out the winning path inputs here.

As for actually running the code, it's sort of a mess. You can check it out and `cargo run` if you've got rust, but configuring anything about it is done by editing `main.rs` and/or providing input pictures and both of those things are messy and error-prone. I may have to think of some example search to demo...

In the meantime read over what you want of the above and leave me any questions. Or tell me what I don't know about gfind/lsss! I am especially interested in understanding what the state of search program art is and how other people do what they do.

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

Re: amling search program principles discussion / brain dump

Post by Sokwe » May 5th, 2022, 7:10 am

Wow, thanks for all the details! It will probably take me a while to get through what you've written so far.
amling wrote:
May 4th, 2022, 11:14 pm
I have no idea (and am especially interesting) what gfind does about cycles.
It's very simple. It keeps a hash table pointing to vertices (sets of 2*period rows of the spaceship) in the breadth first search graph. If during the breadth first search it encounters a vertex that's already in the graph, it simply doesn't add it. So basically gfind tries its best to just avoid cycles entirely and is therefore bad at finding repeating components.

The hash function doesn't work completely correctly when gcd(period,translation) > 1, so in such cases you can sometimes have vertices misidentified as already existing, causing it to improperly skip some vertices. I think this happens only very rarely in rules like Life but happens more frequently in other rules (especially some INT rules with very thin ships).
-Matthias Merzenich

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 5th, 2022, 12:13 pm

Sokwe wrote:
May 5th, 2022, 7:10 am
It's very simple. It keeps a hash table pointing to vertices (sets of 2*period rows of the spaceship) in the breadth first search graph. If during the breadth first search it encounters a vertex that's already in the graph, it simply doesn't add it. So basically gfind tries its best to just avoid cycles entirely and is therefore bad at finding repeating components.
Interesting, interesting. That is an interesting trade-off between finding all cycles/diamonds and performance. In particular that means some alternate paths to vertices (that are longer/later) could be dropped, but presumably once a vertex is dropped from active search state if it is found again it won't realize and will re-search it? LGOL keeps full paths (stored as tree with parent pointers) and only checks for duplicate slices on the path in question so it will happily puke out a million alternatives. Sometimes good, sometimes bad. I had written at one point or another versions that either deduped with permanent global dedupe set (very expensive in memory) or just against current paths under consideration (equivalent to what it sounds like gfind does), but neither has figured prominently in my searching history. I think the closest to relevance is the global dedupe was used to choke through the 5c/5 searches that found that "space clearer" corner.
Sokwe wrote:
May 5th, 2022, 7:10 am
The hash function doesn't work completely correctly when gcd(period,translation) > 1, so in such cases you can sometimes have vertices misidentified as already existing, causing it to improperly skip some vertices. I think this happens only very rarely in rules like Life but happens more frequently in other rules (especially some INT rules with very thin ships).
That is absolutely terrifying.

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

Re: amling search program principles discussion / brain dump

Post by Sokwe » May 5th, 2022, 6:38 pm

amling wrote:
May 5th, 2022, 12:13 pm
presumably once a vertex is dropped from active search state if it is found again it won't realize and will re-search it?
That is correct.
amling wrote:
May 5th, 2022, 12:13 pm
That is absolutely terrifying.
It kind of is, but it works well enough in practice in Life-like rules. You just have to accept the fact that such a search might report no spaceships when a spaceship does exist. gfind was great for finding a large number of ships quickly without additional user input at a time when no other search program was really capable of that.
-Matthias Merzenich

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 10th, 2022, 4:55 pm

I took better notes when doing the 4c/8 tub puffer, but it's still a lot of editing work to lay them out here. We'll see how far I get before I run out of steam. For starters, I grabbed the full 4c/8 -> 2c/4 part and prepared to do a b2f (back-to-front) search:

Code: Select all

                                                     |                                                     |                                                     |                                                     
 .........................o.o....................... |                                                     |                                                     |                                                     
 ..........................*........................ | ..........................*........................ | ..........................*........................ |                                                     
 .........................x.x....................... | .........................x.x....................... | .........................x.x....................... | .........................x.x....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................o.o....................... | .........................o.o....................... | .........................o.o....................... | .........................o.o....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................x.x....................... | .........................x.x....................... | .........................x.x....................... | .........................x.x....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................o.o....................... | .........................o.o....................... | .........................o.o....................... | .........................o.o....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................x.x....................... | .........................x.x....................... | .........................x.x....................... | .........................x.x....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................o.o....................... | .........................o.o....................... | .........................o.o....................... | .........................o.o....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................x.x....................... | .........................x.x....................... | .........................x.x....................... | .........................x.x....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................o.o....................... | .........................o.o....................... | .........................o.o....................... | .........................o.o....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................x.x....................... | .........................x.x....................... | .........................x.x....................... | .........................x.x....................... 
 ..........................*........................ | ..........................*........................ | ..........................*........................ | ..........................*........................ 
 .........................o.o....................... | .........................o.o....................... | .........................o.o....................... | .........................o.o....................... 
 .........................o..o...................... | ..........................o........................ | ..........................o........................ | ..........................o........................ 
 ..........................x........................ | ................................................... | ..........................x........................ | .........................xxx....................... 
 ..........................x........................ | .........................xxx....................... | .........................xxx....................... | .........................xxx....................... 
 .........................*..x...................... | ..........................x.x...................... | ............................x...................... | ............................x...................... 
 ...........................**...................... | ..........................**x...................... | .........................x*ox...................... | .........................**o....................... 
 ......................**..*........................ | ......................**..*........................ | ......................*.*.*........................ | ................................................... 
 ......................???????...................... | ......................***.*........................ | ..........................**....................... | ..........................***...................... 
                                                     |                                                     | ......................???????...................... | .......................*....*...................... 
                                                     |                                                     |                                                     |                                                     
                                                     |                                                     |                                                     |                                                     
                                                     |                                                     |                                                     |                                                     
I've collapsed 4c/8 to 2c/4 and put o's and x's where it disagreed. If I accidentally expand the search window to include such a cell it will error. I've also added one "W row" of question marks to indicate where the search starts. I could add more in the W direction if I wanted, but there is no need.

The search expanded 5 left and 3 right had a good-looking split. Unfortunately I think this was a "random partial" output so reproducing it may not be so easy. Here is the part of the output:

Code: Select all

20220507 22:41:43 [INFO] .......**..*....... | .......*.*.*....... |                     |
20220507 22:41:43 [INFO] .......***.*....... | ...........**...... | ...........***..... | ............**.....
20220507 22:41:43 [INFO] ........*.*..*..... | ..........*..**.... | ........*....*..... | .......**..*.......
20220507 22:41:43 [INFO] ........*..****.... | .......*****....... | .......**...***.... | .......**...*.*....
20220507 22:41:43 [INFO] .......*...*.**.... | .......*..**..*.... | ......*......*..... | ..........*........
20220507 22:41:43 [INFO] .......*.*..*...... | ......*.*..**.*.... | ........*****.*.... | .........***..*....
20220507 22:41:43 [INFO] .....*...ss.*.*.... | ........*ss..*..... | ...........*.**.... | ........**.*.**....
20220507 22:41:43 [INFO] .....*.*.ss....*... | ......*..ss*.*..... | .......*.ss........ | .......**ss.*......
20220507 22:41:43 [INFO] ........*.*.*...... | ....*..*...*....... | .......**ss..**.... | .......*.ss..**....
20220507 22:41:43 [INFO] ....***....*....*.. | .....***.*****.*... | ....**.*.*...*..... | ....****.*...**....
20220507 22:41:43 [INFO] .......*..*..**.*.. | ....*..*..**.**.... | ....*....*......... | ......*..*..***....
20220507 22:41:43 [INFO] .....**...*...*.... | ....****.....***... | ...***...**.**.*... | ...*.**....*..***..
20220507 22:41:43 [INFO] ...**..*........... | ...*...***.....*... | ...*.*.*.**....**.. | .....*......**..*..
20220507 22:41:43 [INFO] ...****.**....*.*.. | ...*.....*.*...*... | ..***..*.*.*..**... | ..*..***.*.**......
20220507 22:41:43 [INFO] .....*.*.****...*.. | ...*...*..*.*.*.... | ....*...*...***.*.. | ..*.......*.***....
20220507 22:41:43 [INFO]                     | .....*...**..*.**.. | ...*.*****......... | ....**..**.**...*..
20220507 22:41:43 [INFO]                     |                     |                     | ...*..***..*...**..
I've marked with s's the 2x2 spot where the split goes. Note these are "aligned correctly" between the generations. Now I stitch this back into the original input file, truncate down both sides to indicate the parts still in progress, and rotate in preparation for running s2s (side-to-side) searches:

Code: Select all

  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................   |  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................   | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................    | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................    
  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................   |  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................   | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................    | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...............................    
  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb.**............................   |  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb**.*...........................   | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb**.*...........................    | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb**.*...........................    
  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb.***..xx.......................   |  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...*..xx.......................   | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb*.****..x......................    | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb*....*x..o.....................    
  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb*.*...*.x..o.x.o.x.o.x.o.x.o.x.   |  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb*...*.o.x..o.x.o.x.o.x.o.x.o.x.   | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb.*.*.*.o.xx.o.x.o.x.o.x.o.x.o.x    | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb...*.*....o.x.o.x.o.x.o.x.o.x.o    
  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb.**.***xx.o.*.*.*.*.*.*.*.*.*.*   |  bbbbbbbbbbbbbbbbbbbbbbbbbbbbb***.***.xxo.*.*.*.*.*.*.*.*.*.*   | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb**...*.*.xxo.*.*.*.*.*.*.*.*.*.    | bbbbbbbbbbbbbbbbbbbbbbbbbbbbb**..*..xx..*.*.*.*.*.*.*.*.*.*.    
  ................................*....x..o.x.o.x.o.x.o.x.o.x.   |  ..............................***..x.x..o.x.o.x.o.x.o.x.o.x.   | ..............................*.....*.xx.o.x.o.x.o.x.o.x.o.x    | ..............................**...*..oo.x.o.x.o.x.o.x.o.x.o    
  .............................*...*..........................   |  ...............................*..*.........................   | ..............................*.............................    | .............................**.............................    
  ............................?..****.........................   |  ............................?*.*............................   | ............................?.*.**..........................    | ............................?*..**..........................    
  ............................?**..**.........................   |  ............................?.**..*.........................   | ............................?...*...........................    | ............................?...**..........................    
  ............................?...............................   |  ............................?*..............................   | ............................?..*............................    | ............................?...............................    
  ............................?...............................   |  ............................?...............................   | ............................?...............................    | ............................?...............................    
  ............................?...............................   |  ............................?...............................   | ............................?...............................    | ............................?...............................    

Code: Select all

  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................   |  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................   | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................    | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................    
  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................   |  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................   | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................    | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................    
  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................   |  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa*..............................   | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa..*............................    | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...............................    
  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa**..**.........................   |  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa.**..*.........................   | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...*...........................    | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa...**..........................    
  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa..****.........................   |  aaaaaaaaaaaaaaaaaaaaaaaaaaaaa*.*............................   | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa.*.**..........................    | aaaaaaaaaaaaaaaaaaaaaaaaaaaaa*..**..........................    
  .............................*...*..........................   |  ...............................*..*.........................   | ..............................*.............................    | .............................**.............................    
  ................................*....x..o.x.o.x.o.x.o.x.o.x.   |  ..............................***..x.x..o.x.o.x.o.x.o.x.o.x.   | ..............................*.....*.xx.o.x.o.x.o.x.o.x.o.x    | ..............................**...*..oo.x.o.x.o.x.o.x.o.x.o    
  ............................?.**.***xx.o.*.*.*.*.*.*.*.*.*.*   |  ............................?***.***.xxo.*.*.*.*.*.*.*.*.*.*   | ............................?**...*.*.xxo.*.*.*.*.*.*.*.*.*.    | ............................?**..*..xx..*.*.*.*.*.*.*.*.*.*.    
  ............................?*.*...*.x..o.x.o.x.o.x.o.x.o.x.   |  ............................?*...*.o.x..o.x.o.x.o.x.o.x.o.x.   | ............................?.*.*.*.o.xx.o.x.o.x.o.x.o.x.o.x    | ............................?...*.*....o.x.o.x.o.x.o.x.o.x.o    
  ............................?.***..xx.......................   |  ............................?...*..xx.......................   | ............................?*.****..x......................    | ............................?*....*x..o.....................    
  ............................?.**............................   |  ............................?**.*...........................   | ............................?**.*...........................    | ............................?**.*...........................    
  ............................?...............................   |  ............................?...............................   | ............................?...............................    | ............................?...............................    
  ............................?...............................   |  ............................?...............................   | ............................?...............................    | ............................?...............................    
  ............................?...............................   |  ............................?...............................   | ............................?...............................    | ............................?...............................    
  ............................?...............................   |  ............................?...............................   | ............................?...............................    | ............................?...............................    
I've marked the "other side" with a's and b's so that if I choke up too close it will error.

I'm gonna skip the "b" side since it's less fresh in my memory. Somehow it got solved and I stitched that entire solution back into the other side's input file:

Code: Select all

  ...............................................................   |  ...............................................................   | ...............................................................    | ...............................................................    
  ...............................................................   |  ...............................................................   | ...............................................................    | ...............................................................    
  ..........*....................................................   |  ........*.*....................................................   | ..........*....................................................    | ........*.*....................................................    
  .......****....................................................   |  .......*..*....................................................   | .......****....................................................    | .......*..*....................................................    
  .......**......................................................   |  ......**.......................................................   | .......**......................................................    | ......**.......................................................    
  .....*.........................................................   |  .....*.........................................................   | .....*.........................................................    | .....*.........................................................    
  .....****......................................................   |  ....****.......................................................   | .....****......................................................    | ....****.......................................................    
  ....*..........................................................   |  ...*....*......................................................   | ....*..........................................................    | ...*....*......................................................    
  ...***..*......................................................   |  ...*..*........................................................   | ...***..*......................................................    | ...*..*........................................................    
  ....***........................................................   |  ...*..*........................................................   | ....***........................................................    | ...*..*........................................................    
  .....*.........................................................   |  ....*..........................................................   | .....*.........................................................    | ....*..........................................................    
  ......***.*...................*.*..............................   |  .....****.*....................*...............................   | ......***.*...................*.*..............................    | .....****.*....................*...............................    
  ......*..**..................*..*..............................   |  ......*...*.................****...............................   | ......*..**..................*..*..............................    | ......*...*.................****...............................    
  .......***..................**.................................   |  .......*....................***................................   | .......***..................**.................................    | .......*....................***................................    
  .........*.................*...*...............................   |  .......*.*................*...*................................   | .........*.................*...*...............................    | .......*.*................*...*................................    
  .......*..................***.*................................   |  ..........................***..................................   | .......*..................***.*................................    | ..........................***..................................    
  .......*.*.............**......................................   |  ......***..............*.*....*................................   | .......*.*.............**......................................    | ......***..............*.*....*................................    
  ......*...............*...*****................................   |  ......**..............********.................................   | ......*...............*...*****................................    | ......**..............********.................................    
  .......*.*...........*...*.....................................   |  ......***............**........................................   | .......*.*...........*...*.....................................    | ......***............**........................................    
  .......*.............*.....**..................................   |  ....................**....**...................................   | .......*.............*.....**..................................    | ....................**....**...................................    
  .........*...........***...****................................   |  .......*.*...........**....*..*................................   | .........*...........***...****................................    | .......*.*...........**....*..*................................    
  .......***....................*................................   |  .......*....................*.*................................   | .......***....................*................................    | .......*....................*.*................................    
  ......*..**..........***.......................................   |  ......*...*..........**........................................   | ......*..**..........***.......................................    | ......*...*..........**........................................    
  ......***.*.........*..........................................   |  .....****.*.........**.*.......................................   | ......***.*.........*..........................................    | .....****.*.........**.*.......................................    
  .....*.............*...*.......................................   |  ....*..............**..........................................   | .....*.............*...*.......................................    | ....*..............**..........................................    
  ....***...........*..*.........................................   |  ...*..*...........**..*........................................   | ....***...........*..*.........................................    | ...*..*...........**..*........................................    
  ...***..*.........*....*.......................................   |  ...*..*..........**............................................   | ...***..*.........*....*.......................................    | ...*..*..........**............................................    
  ....*............*.****........................................   |  ...*....*.......*..****........................................   | ....*............*.****........................................    | ...*....*.......*..****........................................    
  .....****.......***..*...**....................................   |  ....****........*.......**.....................................   | .....****.......***..*...**....................................    | ....****........*.......**.....................................    
  .....*...........**...***...*..................................   |  .....*..........*.....***.*....................................   | .....*...........**...***...*..................................    | .....*..........*.....***.*....................................    
  .......**.........****...*...*.................................   |  ......**.........*..**...***.*.................................   | .......**.........****...*...*.................................    | ......**.........*..**...***.*.................................    
  .......****.*......*...*..**.*.................................   |  .......*..*.......**.**...*.*..................................   | .......****.*......*...*..**.*.................................    | .......*..*.......**.**...*.*..................................    
  ..........*.*.........*........................................   |  ........*.*.*......**..........................................   | ..........*.*.........*........................................    | ........*.*.*......**..........................................    
  ............**.....**..........................................   |  .............*.....*...........................................   | ............**.....**..........................................    | .............*.....*...........................................    
  ...........**......***.........................................   |  ...........*......*..*.........................................   | ...........**......***.........................................    | ...........*......*..*.........................................    
  ..........*..*.....**..........................................   |  ..........***......*...........................................   | ..........*..*.....**..........................................    | ..........***......*...........................................    
  .........*............*........................................   |  .........**........**..........................................   | .........*............*........................................    | .........**........**..........................................    
  .........*.........*...*.......................................   |  ........**........**.**........................................   | .........*.........*...*.......................................    | ........**........**.**........................................    
  .........***......****.........................................   |  .........*.*......*..**........................................   | .........***......****.........................................    | .........*.*......*..**........................................    
  ..........*..*....*.**..*......................................   |  .................*....**.*.....................................   | ..........*..*....*.**..*......................................    | .................*....**.*.....................................    
  ..........***.....**..*.*.*....................................   |  .........****.*..**.**.*.*.....................................   | ..........***.....**..*.*.*....................................    | .........****.*..**.**.*.*.....................................    
  .........*...**...*........*...................................   |  .........*.....*.*.......**....................................   | .........*...**...*........*...................................    | .........*.....*.*.......**....................................    
  ........*..*.***..**.....*.....................................   |  ........*.*.*....*......**.....................................   | ........*..*.***..**.....*.....................................    | ........*.*.*....*......**.....................................    
  ........**....**..**....***....................................   |  .......***.***.*.*.....*..*....................................   | ........**....**..**....***....................................    | .......***.***.*.*.....*..*....................................    
  ......*...**......*....**......................................   |  ......*...*..*...*....*........................................   | ......*...**......*....**......................................    | ......*...*..*...*....*........................................    
  ......***....***..**..**.......................................   |  .....***....**.*.***..*........................................   | ......***....***..**..**.......................................    | .....***....**.*.***..*........................................    
  .....*.......**.*......*.*.....................................   |  ....*...*.......*.....***......................................   | .....*.......**.*......*.*.....................................    | ....*...*.......*.....***......................................    
  ....***.*.....*..***...........................................   |  ....*.*.....*...****...*.......................................   | ....***.*.....*..***...........................................    | ....*.*.....*...****...*.......................................    
  ....*.......***.*...*..**......................................   |  ...*....*...*.**.......**......................................   | ....*.......***.*...*..**......................................    | ...*....*...*.**.......**......................................    
  ....*****...*.....*....*..*....................................   |  ....****...*....**..*..*.*.....................................   | ....*****...*.....*....*..*....................................    | ....****...*....**..*..*.*.....................................    
  ............*****..**...*......................................   |  ....*......******...*..**..*...................................   | ............*****..**...*......................................    | ....*......******...*..**..*...................................    
  ....*.*...*......***....****...................................   |  ...***...**......**.....***....................................   | ....*.*...*......***....****...................................    | ...***...**......**.....***....................................    
  ...**....**.****....*..........................................   |  ...*.....***.**...**...........................................   | ...**....**.****....*..........................................    | ...*.....***.**...**...........................................    
  ....**................****.....................................   |  ...*...*....*..*..*...***......................................   | ....**................****.....................................    | ...*...*....*..*..*...***......................................    
  .....******.*.*..******........................................   |  ....*...**.*.*...*****...*.....................................   | .....******.*.*..******........................................    | ....*...**.*.*...*****...*.....................................    
  ......*.*...*..*..*....*.*.....................................   |  .....**...**.*.*.......*.......................................   | ......*.*...*..*..*....*.*.....................................    | .....**...**.*.*.......*.......................................    
  ........**......***.*..**......................................   |  ........**.*......**...*.......................................   | ........**......***.*..**......................................    | ........**.*......**...*.......................................    
  ........*..*****.*......**.....................................   |  ........*.*.****.***...***.....................................   | ........*..*****.*......**.....................................    | ........*.*.****.***...***.....................................    
  .........*..........*.....*....................................   |  ........**.......**............................................   | .........*..........*.....*....................................    | ........**.......**............................................    
  .........***.*****.*..***......................................   |  .........*.******....***.*.....................................   | .........***.*****.*..***......................................    | .........*.******....***.*.....................................    
  ..........*.*.........*...*....................................   |  ..................*...*...*....................................   | ..........*.*.........*...*....................................    | ..................*...*...*....................................    
  ..........**.*.**.*.....***....................................   |  .........**..**........**......................................   | ..........**.*.**.*.....***....................................    | .........**..**........**......................................    
  .........*..**..........****...................................   |  .........*..***.**......*..*...................................   | .........*..**..........****...................................    | .........*..***.**......*..*...................................    
  ..........*......*.........*...................................   |  .........**..**..........*.*...................................   | ..........*......*.........*...................................    | .........**..**..........*.*...................................    
  ..........**.*.*..*............................................   |  ..........***.*.*.*............................................   | ..........**.*.*..*............................................    | ..........***.*.*.*............................................    
  .............*...**............................................   |  ............*..*..*............................................   | .............*...**............................................    | ............*..*..*............................................    
  ...............***.............................................   |  ..............**...............................................   | ...............***.............................................    | ..............**...............................................    
  ...............***.............................................   |  ...............*..*............................................   | ...............****............................................    | ...............*..*............................................    
  ..................*..*........**...............................   |  ................*.*..........*..*..............................   | ...................*...........................................    | ................*..*...........................................    
  ..................*...*.*....****..............................   |  ..................**...*....*..................................   | ..................**...*.....**................................    | ..................***..*....****...............................    
  ...................*....*...**.**..............................   |  ...................***.*....*...*..............................   | ...................*..*.*...**.**..............................    | ..................**.***....*...*..............................    
  ....................**.......**................................   |  ....................*..**...****...............................   | ....................**.......****..............................    | ....................**......*..................................    
  .......................**......................................   |  ......................**.*.....................................   | ......................**..*...**...............................    | ......................**.....*..*..............................    
  .......................***.....................................   |  ......................*...*....................................   | ......................*..*.....................................    | ......................*..*.....*...............................    
  ......................*..**....................................   |  ......................**.......*...............................   | .......................**.......*..............................    | .........................*.....................................    
  .....................*...**...***.*............................   |  ....................**.......***...............................   | ....................*****....**................................    | ....................**..*....*****.............................    
  ...................**...***.**.................................   |  ...................**...*...**.***.............................   | ...................*..*......*..**.............................    | ...................*....*...*...**.............................    
  ...................*.....*.*.*...*.............................   |  ..................**...*.....*.................................   | ...................*..**..*.*.*.*.*............................    | ..................**...*..*.*.*.*..............................    
  ...................*..**..**.*.*...............................   |  ...................**.***.**.*..*..............................   | ...................***.*..**..*................................    | ...................***...***..*.*..............................    
  ....................*..*.....*.*...............................   |  .......................*.*...*.*...............................   | .......................**.....*.**.............................    | ....................**......*.*................................    
  .......................*.****..**..............................   |  .........................*****..*..............................   | ......................**.****.*................................    | ......................*..***..*................................    
  ......................****....**...............................   |  ....................***......*.................................   | ....................*..*..*...*................................    | ......................***.....*................................    
  ...................***..*.*...**...............................   |  ...................****...*....................................   | ...................*......**.*.................................    | ...................**....*...*.................................    
  ...................*.....**..**................................   |  ..................**.*...****..................................   | ...................*......***..................................    | ..................**.....*...*.................................    
  ...................*.*......****...............................   |  ...................*.**........*...............................   | ...................**.**..*..*.................................    | ...................**....**..**................................    
  ....................**.***.***...**............................   |  .....................*..*..*.....*.*...........................   | .........................*...**.**.*...........................    | ....................*..****.*...**.*...........................    
  .....................*........**.***..xx.......................   |  ....................**.**...****...*..xx.......................   | .....................**..*...**.**.***..x......................    | .....................**......**.*....*x..o.....................    
  ......................*........**.*...*.x..o.x.o.x.o.x.o.x.o.x.   |  ......................**......**....*.o.x..o.x.o.x.o.x.o.x.o.x.   | ......................*...........**.*.o.xx.o.x.o.x.o.x.o.x.o.x    | .....................**.*......*...*.*....o.x.o.x.o.x.o.x.o.x.o    
  .......................**........**.***xx.o.*.*.*.*.*.*.*.*.*.*   |  .......................*........***.***.xxo.*.*.*.*.*.*.*.*.*.*   | .......................**.......**...*.*.xxo.*.*.*.*.*.*.*.*.*.    | .......................*........**..*..xx..*.*.*.*.*.*.*.*.*.*.    
  ...................................*....x..o.x.o.x.o.x.o.x.o.x.   |  .................................***..x.x..o.x.o.x.o.x.o.x.o.x.   | .................................*.....*.xx.o.x.o.x.o.x.o.x.o.x    | .................................**...*..oo.x.o.x.o.x.o.x.o.x.o    
  ................................*...*..........................   |  ..................................*..*.........................   | .................................*.............................    | ................................**.............................    
  ...............................?..****.........................   |  ...............................?*.*............................   | ...............................?.*.**..........................    | ...............................?*..**..........................    
  ...............................?**..**.........................   |  ...............................?.**..*.........................   | ...............................?...*...........................    | ...............................?...**..........................    
  ...............................?...............................   |  ...............................?*..............................   | ...............................?..*............................    | ...............................?...............................    
  ...............................?...............................   |  ...............................?...............................   | ...............................?...............................    | ...............................?...............................    
  ...............................?...............................   |  ...............................?...............................   | ...............................?...............................    | ...............................?...............................    
I ran this expanded 1 up, 1 left, and 4 right and somewhere in the partials spotted this:

Code: Select all

20220509 16:41:50 [INFO]  ........**........**.** |  ........*........***.** | ........**.......**...*  | ........*........**..*.
20220509 16:41:50 [INFO]  ....................*.. |  ..................***.. | ..................*....  | ..................**...
20220509 16:41:50 [INFO]  .................*...*. |  ...................*..* | ..................*....  | ................*.*....
20220509 16:41:50 [INFO]  .......*.*......*..**** |  .......*.*......**.*... | ........*.**...****.**.  | ........*.*.*...***.**.
20220509 16:41:50 [INFO]  .....*****...**..*.*.** |  .....***.**..***..**..* | ......***.***......**..  | .....****.*.*...**...*.
20220509 16:41:50 [INFO]  ....*......*..*........ |  ....*......****.*...... | ....**.............*...  | ....**......*..........
20220509 16:41:50 [INFO]  ....*..**.**...**...... |  ...**..**.***.****..... | ....*..***.*.....***...  | ...**.**.**...*........
20220509 16:41:50 [INFO]  ....**..*.*..*..**.**.. |  ....***.*.*...*...**... | ....*..*.*...***...**..  | ....*..*.*.*****.*.**..
20220509 16:41:50 [INFO]  ......*....*.*..*.*.... |  .....*...*.*...**.*.... | .....**...*.*..*.*.....  | .....**...*.*..*..*....
20220509 16:41:50 [INFO]  .........*.*....*..**.. |  .......**..*...**.**... | .......**.*.**.*...**..  | ......***.*....*..***..
20220509 16:41:50 [INFO]  ....****.*.**...**..... |  ....*..*.*..*..*..*.... | ........*.****..*..**..  | ....*..**.*.....**.....
20220509 16:41:50 [INFO]  ...*.**.*.**....**..... |  ...*......*..*.*.*..... | ...***.....*..*.*.**...  | ...**.....*.....*.*....
20220509 16:41:50 [INFO]  ...*..***ss.**.*....... |  ..**.....ss**.**..*.... | ...*.....ss.*...*..*...  | ..**..*..ss**...*......
20220509 16:41:50 [INFO]  ...******ss....****.... |  ...**...*ss.**.*.**.... | ...*.**..ss.**..*****..  | ...*..**.ss.******..*..
20220509 16:41:50 [INFO]  ......*......*...*..... |  ....*.*.......*...*.... | ....***.*....*.*...*...  | ....*.......**......*..
20220509 16:41:50 [INFO]  ...............**...... |  .......*....*..**...... | ......*..*....*****....  | ......**......*........
20220509 16:41:50 [INFO]  .......**..*.*.*....... |  ......***...*..*.*..... | ................*.**...  | ..........*...*.*......
20220509 16:41:50 [INFO]  ......**.*...*.*.**.... |  ......**.*.......**.... | ..........**.*....**...  | ......*...*****.*...*..
20220509 16:41:50 [INFO]  .....*...*.*.....*..... |  .....**..*.*.*...*..... | .....***..*.*.***.**...  | .....******.*...*......
20220509 16:41:50 [INFO]  ....*....*.**.***..*... |  ...**...**.**.***...... | ....*..**.....***.*....  | ....**..*....**.*.*....
20220509 16:41:50 [INFO]  ..*.*.*..*.....*....... |  ..*.**..****...*.*..... | ...*...*............*..  | ..*.**.....*.*....***..
Again, I've marked with s's where I see the split. Both sides of this were quite big so I looked at a lot of other branchings first, but in the end this was solvable while the others eluded me.

I decided to tackle the left side first. I truncated the input all the way down to just two rows although it wasn't necessary:

Code: Select all

  .......................*..***.............. |  ......................**................... | .......................*...................  | ......................**..*................  
  .......................******.............. |  .......................**...*.............. | .......................*.**................  | .......................*..**...............  
  ........................?????.............. |  ........................?????.............. | ........................?????..............  | ........................?????..............  
Note I've filled in a lot of space on the right which isn't really correct. Any searches that use that space would encroach on any solution to the right half.

I ran the search expanded 6 on the left and somewhere in the output it had found a c/2-compatible slice (this is what it was configured to output since most c/2 things are pretty solvable):

Code: Select all

20220510 11:49:36 [INFO]  .......*..***.. |  ......**....... | .......*.......  | ......**..*.... 
20220510 11:49:36 [INFO]  .......******.. |  .......**...*.. | .......*.**....  | .......*..**... 
20220510 11:49:36 [INFO]  ..........*.... |  ........*.*.... | ........***.*..  | ........*...... 
20220510 11:49:36 [INFO]  ............... |  ...........*... | ..........*....  | ..........**... 
20220510 11:49:36 [INFO]  ........*..**.. |  ........*...... | .......*.*.....  | .......*....... 
20220510 11:49:36 [INFO]  ......***...... |  .....****...... | .....******....  | .....***..*.... 
20220510 11:49:36 [INFO]  ....**...****.. |  ....**....**... | ....*.....*....  | ....*.....*.... 
20220510 11:49:36 [INFO]  ....*..**.*.... |  ...**..**...... | ....*..***.....  | ...**.**.*.*... 
20220510 11:49:36 [INFO]  ....*...*.*.... |  ....*.*.*.**... | ....**.*.*.**..  | ....**.*.*..... 
20220510 11:49:36 [INFO]  .....**.*.*.... |  .....**.*.*.... | .......*.*.....  | .....*.*.*..... 
20220510 11:49:36 [INFO]  .......**.**... |  ......*.*.**... | ......**.*.....  | ......**.**.... 
20220510 11:49:36 [INFO]  ........*...... |  .......**.**... | ........**.....  | .........*..... 
20220510 11:49:36 [INFO]  ..........*.... |  .........**.... | ........*......  | ........*.*.... 
20220510 11:49:36 [INFO]  .........*.*... |  ........*..*... | ..........**...  | ............... 
20220510 11:49:36 [INFO]  ........***.... |  ............... | ...............  | ........***.... 
20220510 11:49:36 [INFO]  ........**..... |  .......*....... | .......***.....  | .......**...... 
20220510 11:49:36 [INFO]  .......*.*..... |  ......**.*..... | .......*.......  | ......*........ 
20220510 11:49:36 [INFO]  ....**.*....... |  ...*...**...... | .......***.....  | ......*..*..... 
20220510 11:49:36 [INFO]  ...****........ |  ..*............ | ...**..**......  | ..****...*..... 
20220510 11:49:36 [INFO]  ..**.*......... |  ..*..**........ | ..**.***.......  | ..*............ 
20220510 11:49:36 [INFO]  ...*........... |  ..**.*......... | ...**.**.......  | ..*............ 
20220510 11:49:36 [INFO]  ....**....**... |  ....*.......... | ....*****......  | ...**....*..... 
20220510 11:49:36 [INFO]  .......**...... |  ......***.**... | .......*.**....  | ....*....**.... 
20220510 11:49:36 [INFO]  .......*...*... |  .......**...... | ....*.*...*....  | ...********.... 
20220510 11:49:36 [INFO]  ...*........... |  ..***.**....... | ...**..*.......  | ..*.*..**...... 
20220510 11:49:36 [INFO]  ..**.*.***..... |  ..*.....*...... | ..**..**.*.....  | ..*..*.*....... 
20220510 11:49:36 [INFO]  ...**.......... |  ..*...*.*...... | ...*.*.*.......  | ..**........... 
20220510 11:49:36 [INFO]  ....**......... |  ...****........ | ....*****......  | ........*...... 
20220510 11:49:36 [INFO]  ......**.*..... |  ............... | .....*.*.......  | ....**......... 
20220510 11:49:36 [INFO]  ......***...... |  ......*..*..... | .......**......  | ......***...... 
20220510 11:49:36 [INFO]  ........*...... |  ....***.*...... | ....*..........  | ............... 
20220510 11:49:36 [INFO]  ...***......... |  ...***.***..... | ...*...........  | ...**.......... 
20220510 11:49:36 [INFO]  ...*..*.**..... |  ..**..*.**..... | ...*...*..*....  | ..**....*...... 
20220510 11:49:36 [INFO]  ...*.**.**..... |  ...*..*........ | ...**..*.*.....  | ...**.**.*..... 
20220510 11:49:36 [INFO]  ....**...***... |  .......*...*... | ......*.*......  | ....*.......... 
20220510 11:49:36 [INFO]  .....*.*.**.... |  .....**........ | .....*******...  | .....**.*.**... 
20220510 11:49:36 [INFO]  ....*....**.... |  ....**..***.... | ....*.....*....  | ....*.***...... 
20220510 11:49:36 [INFO]  ....*.......... |  ...***......... | ....*.....*....  | ...***......... 
20220510 11:49:36 [INFO]  ....*..*....... |  ....***........ | ....*..*.......  | ....***........ 
20220510 11:49:36 [INFO]  .....*.*....... |  ......*........ | .....*.*.......  | ......*........ 
20220510 11:49:36 [INFO]  ..........**... |  ...*......**... | ..........**...  | ...*......**... 
20220510 11:49:36 [INFO]  ..*****....*... |  ..*..*..**..... | ..*****....*...  | ..*..*..**..... 
I trimmed a bit of the crap off the bottom and stitched this back into the above and placed question marks for the right side:

Code: Select all

  ........*......*..*............................ |  ........*......****.*.......................... | ........**.............*.......................  | ........**......*..............................  
  ........*..**.**...**.......................... |  .......**..**.***.****......................... | ........*..***.*.....***.......................  | .......**.**.**...*............................  
  ........**..*.*..*..**.**...................... |  ........***.*.*...*...**....................... | ........*..*.*...***...**......................  | ........*..*.*.*****.*.**......................  
  ..........*....*.*..*.*........................ |  .........*...*.*...**.*........................ | .........**...*.*..*.*.........................  | .........**...*.*..*..*........................  
  .............*.*....*..**...................... |  ...........**..*...**.**....................... | ...........**.*.**.*...**......................  | ..........***.*....*..***......................  
  ........****.*.**...**......................... |  ........*..*.*..*..*..*........................ | ............*.****..*..**......................  | ........*..**.*.....**.........................  
  .......*.**.*.**....**......................... |  .......*......*..*.*.*......................... | .......***.....*..*.*.**.......................  | .......**.....*.....*.*........................  
  .......*..***..??????????...................... |  ......**.......??????????...................... | .......*.......??????????......................  | ......**..*....??????????......................  
  .......******..??????????...................... |  .......**...*..??????????...................... | .......*.**....??????????......................  | .......*..**...??????????......................  
  ..........*....??????????...................... |  ........*.*....??????????...................... | ........***.*..??????????......................  | ........*......??????????......................  
  ...............??????????...................... |  ...........*...??????????...................... | ..........*....??????????......................  | ..........**...??????????......................  
  ........*..**..??????????...................... |  ........*......??????????...................... | .......*.*.....??????????......................  | .......*.......??????????......................  
  ......***......??????????...................... |  .....****......??????????...................... | .....******....??????????......................  | .....***..*....??????????......................  
  ....**...****..??????????...................... |  ....**....**...??????????...................... | ....*.....*....??????????......................  | ....*.....*....??????????......................  
  ....*..**.*....??????????...................... |  ...**..**......??????????...................... | ....*..***.....??????????......................  | ...**.**.*.*...??????????......................  
  ....*...*.*....??????????...................... |  ....*.*.*.**...??????????...................... | ....**.*.*.**..??????????......................  | ....**.*.*.....??????????......................  
  .....**.*.*....??????????...................... |  .....**.*.*....??????????...................... | .......*.*.....??????????......................  | .....*.*.*.....??????????......................  
  .......**.**...??????????...................... |  ......*.*.**...??????????...................... | ......**.*.....??????????......................  | ......**.**....??????????......................  
  ........*......??????????...................... |  .......**.**...??????????...................... | ........**.....??????????......................  | .........*.....??????????......................  
  ..........*....??????????...................... |  .........**....??????????...................... | ........*......??????????......................  | ........*.*....??????????......................  
  .........*.*...??????????...................... |  ........*..*...??????????...................... | ..........**...??????????......................  | ...............??????????......................  
  ........***....??????????...................... |  ...............??????????...................... | ...............??????????......................  | ........***....??????????......................  
  ........**.....??????????...................... |  .......*.......??????????...................... | .......***.....??????????......................  | .......**......??????????......................  
  .......*.*.....??????????...................... |  ......**.*.....??????????...................... | .......*.......??????????......................  | ......*........??????????......................  
  ....**.*.......??????????...................... |  ...*...**......??????????...................... | .......***.....??????????......................  | ......*..*.....??????????......................  
  ...****........??????????...................... |  ..*............??????????...................... | ...**..**......??????????......................  | ..****...*.....??????????......................  
  ..**.*.........??????????...................... |  ..*..**........??????????...................... | ..**.***.......??????????......................  | ..*............??????????......................  
  ...*...........??????????...................... |  ..**.*.........??????????...................... | ...**.**.......??????????......................  | ..*............??????????......................  
  ....**....**...??????????...................... |  ....*..........??????????...................... | ....*****......??????????......................  | ...**....*.....??????????......................  
  .......**......??????????...................... |  ......***.**...??????????...................... | .......*.**....??????????......................  | ....*....**....??????????......................  
  .......*...*...??????????...................... |  .......**......??????????...................... | ....*.*...*....??????????......................  | ...********....??????????......................  
  ...*...........??????????...................... |  ..***.**.......??????????...................... | ...**..*.......??????????......................  | ..*.*..**......??????????......................  
  ..**.*.***.....??????????...................... |  ..*.....*......??????????...................... | ..**..**.*.....??????????......................  | ..*..*.*.......??????????......................  
  ...**..........??????????...................... |  ..*...*.*......??????????...................... | ...*.*.*.......??????????......................  | ..**...........??????????......................  
  ....**.........??????????...................... |  ...****........??????????...................... | ....*****......??????????......................  | ........*......??????????......................  
  ......**.*.....??????????...................... |  ...............??????????...................... | .....*.*.......??????????......................  | ....**.........??????????......................  
  ......***......??????????...................... |  ......*..*.....??????????...................... | .......**......??????????......................  | ......***......??????????......................  
  ........*......??????????...................... |  ....***.*......??????????...................... | ....*..........??????????......................  | ...............??????????......................  
  ...***.........??????????...................... |  ...***.***.....??????????...................... | ...*...........??????????......................  | ...**..........??????????......................  
  ...*..*.**.....??????????...................... |  ..**..*.**.....??????????...................... | ...*...*..*....??????????......................  | ..**....*......??????????......................  
  ...*.**.**.....??????????...................... |  ...*..*........??????????...................... | ...**..*.*.....??????????......................  | ...**.**.*.....??????????......................  
  ....**...***...??????????...................... |  .......*...*...??????????...................... | ......*.*......??????????......................  | ....*..........??????????......................  
  .....*.*.**....??????????...................... |  .....**........??????????...................... | .....*******...??????????......................  | .....**.*.**...??????????......................  
  ....*....**....??????????...................... |  ....**..***....??????????...................... | ....*.....*....??????????......................  | ....*.***......??????????......................  
  ....*..........??????????...................... |  ...***.........??????????...................... | ....*.....*....??????????......................  | ...***.........??????????......................  
  ....*..*.......??????????...................... |  ....***........??????????...................... | ....*..*.......??????????......................  | ....***........??????????......................  
  .....*.*.......??????????...................... |  ......*........??????????...................... | .....*.*.......??????????......................  | ......*........??????????......................  
  .....!.........??????????...................... |  .....*.........??????????...................... | .....!.........??????????......................  | .....*.........??????????......................  
  ...............??????????...................... |  ...............??????????...................... | ...............??????????......................  | ...............??????????......................  
Nothing came of this quickly, so I rotated it and redid the question marks to search f2b (front-to-back):

Code: Select all

                                                   |                                                   | ................................................. | ................................................. 
 ................................................. | ................................................. | ................................................. | ................................................. 
 ................................................. | ................................................. | ................*.....*.......................... | .........*.....***...***......................... 
 ................*.....*.......................... | .........*.....***...***......................... | ........***....***...***......................... | ....*...***....*..*.*..*..........*.............. 
 ........***....***...***......................... | ....*...***...*..*...*..*.........*.............. | ...***..*..*..*..**.**.*.........***............. | ...***.**.*..*...****..*.........***............. 
 ...***.*..*...**....*..**........***............. | ...***....**..*..*..*............***............. | .!*...*......***....*.*..........*..*............ | .*.**.*......*..*.*....*........**..*............ 
 .!*...***.*...*.*...*.***.......*..*............. | .*.****...**..*......**.........*..**............ | ......**......*.*.*.***........*....*............ | ..**.**.*...*.....*.....**.....*..*.*....*....... 
 ........**..**.........*........*...*............ | ..**..*.**.**.**.*.*..*..*.....***..*....*....... | ..**..*.**..******.********....****.**..***...... | .....*..*...*...***.......*....****.**..***....*. 
 ..**..*.....**..*.**....**.....*..*.*...***...... | .......*..*......***....***...*...*.*...***....*. | ......**....*.*.....*..**.*..**...*.*..*..*...*** | .....**..*..*.*..**.......**.*.........*..**..*** 
 ........**.**...*..*......**..*****.**..*..*..*** | .....*...***...**.**....*...*.*****.**.**..*..*** | ......*.*.......*..*....*.*...*****.**.**.*..*..* | ........*.........***..**..*..*****..........*..* 
 .....*****...*..*........****......*....*.**..*.. | .....*...**.*............*...*...............**.. | ....***..*........**........*......**.***....*... | ......*...........**.......*.*.*...**.*.**..**.*. 
 .....***............*......*.*.*****...*****.*... | .....*.............*.........*****.*...*......*.. | ......*.....................*....*..........*.**. | ......*...........................*...*.*..**.**. 
 .......*..........*.*.......*..*...*.*..**.*...*. | .......*...........*........*.**.*.*..*....**..*. | .................................*.....*...**..*. | ...........................................**.... 
 ...................................*.*..***...**. | ........................................*...*.**. | ..............................................**. | ..............................................**. 
 ...........................................**.... | ...........................................*.*... | ...........................................***... | ..........................................****.*. 
 ..........................................*...**. | ..........................................*...**. | .........................................?**...*. | .........................................?....*.. 
 .........................................?****.** | .........................................?..**.** | .........................................?.***... | .........................................?...**.* 
 .........................................?.*..... | .........................................?.*...** | .........................................?.**.*.. | .........................................?....*.. 
 .........................................?...**.. | .........................................?*.....* | .........................................?*...*.. | .........................................?....**. 
 .........................................?......* | .........................................?....*** | .........................................?..***.. | .........................................?..***.. 
 .........................................?.....*. | .........................................?****.*. | .........................................?**..... | .........................................?**..... 
 .........................................?******. | .........................................?..**.** | .........................................?...*.*. | .........................................?.*..*.. 
 .........................................?**..*.. | .........................................?*....*. | .........................................?*....*. | .........................................?*.**... 
 .........................................?...*... | .........................................?.****.. | .........................................?***.*** | .........................................?..*.*.. 
 .........................................?..*.*.. | .........................................?..*.*.. | .........................................?.**.*.. | .........................................?..*.*.. 
 .........................................?..*.*.. | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... | .........................................?....... | .........................................?....... 
 .........................................?....... | .........................................?....... |                                                   |                                                   
Expanded 3 in every direction this output a c/2 solution:

Code: Select all

20220510 13:08:26 [INFO]                 |                 |                 | .*...**........
20220510 13:08:26 [INFO]                 | .....*.***..... | *...**....*.... | ....*....**....
20220510 13:08:26 [INFO] *..*.*...*..... | ...*.***.**.... | ....**...**.... | ...*..*.*..*...
20220510 13:08:26 [INFO] ....*.**.**.... | .......*....... | ....*..*.**.... | ....*..*.......
20220510 13:08:26 [INFO] ...***.****.... | ...*...*..*.... | ......**.*..... | ......**.*.....
20220510 13:08:26 [INFO] .....*......... | .......***..... | .........*..... | ......*.*......
20220510 13:08:26 [INFO] .....**........ | .....***....... | .....*......... | ...............
20220510 13:08:26 [INFO] ......*.*...... | ......**....... | ....*.......... | ....**.........
20220510 13:08:26 [INFO] .....*......... | ....***........ | ....*.......... | ...***....*....
20220510 13:08:26 [INFO] ...*.*......... | ....***...*.... | ...*..*..***... | ...**..*.***...
20220510 13:08:26 [INFO] ......*..***... | ....*....***... | ....*.*.*..*... | .....*.*.*.**..
20220510 13:08:26 [INFO] ...*.....*..*.. | .....*..**.*... | ...........*... | ..........***..
20220510 13:08:26 [INFO] ....*.*..*..... | ........***.... | ...........*... | ..........**...
20220510 13:08:26 [INFO] .........*..... | .........**.... | ........*.*.... | ...............
20220510 13:08:26 [INFO] ..........*.*.. | ............... | ............... | ...............
20220510 13:08:26 [INFO] ............... | ............... | .....*......... | ....***....*...
20220510 13:08:26 [INFO] .....*......... | ....***....*... | ....***...***.. | ....*..*..***..
20220510 13:08:26 [INFO] ....***...***.. | ....*..*..***.. | ......**.*..*.. |
20220510 13:08:26 [INFO] ......**.*..*.. |                 |                 |
The c/2 part is of course unnecessary and somewhere in all its output it presumably had the all zeros option.

At this point I went back to do a c/2 s2s search (which I'm not gonna document here) to complete the last arm, although I bet veterans could have supplied a completion just from looking at the slice.

A few things to note:

The code blocks with question marks are generally the exact inputs I fed to the program. The code blocks with timestamps and "INFO" are part of the outputs, sometimes edited slightly to mark something.

This does not include the dozens of setups that nothing came of. Spotting splittable partials is more art than science and most often goes nowhere. That split that solved the one s2s side of the original split looked so bad it had been sitting in my notes to look at for dozen of intervening searches. Generally very thin slices are good, but sometimes thin slices will be weirdly resistant to solution and sometimes wide slices will solve easily.

This does not even include some of the successful branches. I doubt it's useful for illustration since they're all similar tricks.

I generally configure 2c/4 to output c/2 compatible slices of "4 Y rows" as most c/2 slices that survive 4 Y rows will be solvable (just 2 Y rows is often enough unsolvable in the lower period). I generally configure c/2 searches to only output all-zero slices (of "2 Y rows").

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

Re: amling search program principles discussion / brain dump

Post by Sokwe » May 22nd, 2022, 7:17 pm

amling wrote:
May 5th, 2022, 2:55 am
As for actually running the code, it's sort of a mess. You can check it out and `cargo run` if you've got rust, but configuring anything about it is done by editing `main.rs` and/or providing input pictures and both of those things are messy and error-prone. I may have to think of some example search to demo...
I would like to see an example of how to set up and run a simple side-to-side search to extend a partial result. No pressure and no hurry, of course.
-Matthias Merzenich

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 23rd, 2022, 12:42 pm

Sokwe wrote:
May 22nd, 2022, 7:17 pm
amling wrote:
May 5th, 2022, 2:55 am
As for actually running the code, it's sort of a mess. You can check it out and `cargo run` if you've got rust, but configuring anything about it is done by editing `main.rs` and/or providing input pictures and both of those things are messy and error-prone. I may have to think of some example search to demo...
I would like to see an example of how to set up and run a simple side-to-side search to extend a partial result. No pressure and no hurry, of course.
Here is a slightly more detailed guide to reproducing the last arm of the 4c/8 tub puffer. The arm, in all 4 phases, looks like this:

Code: Select all

|  ...................... |  .....................* | ......................  | ......................  |
|  .............*.**...** |  .............*.*.*...* | ............*.*......*  | ............*.*......*  |
|  ...........***.***.... |  ..........****.*.*...* | ..........*****...**..  | ..........***.**..***.  |
|  .........**........... |  .........**......*.... | .........*......*..*..  | .........*......****.*  |
|  .........*..***.*..... |  ........**.**.**...*.. | .........*..**.**...**  | ........**..**.***.***  |
|  .........*..*.*...***. |  .........*..*.*.*****. | .........**..*.*..*..*  | .........***.*.*...*..  |
|  ..........**...*.*..*. |  ..........**...*.*..*. | ...........*....*.*..*  | ..........*...*.*...**  |
|  ............**.*.**.*. |  ...........***.*....*. | ..............*.*....*  | ............**..*...**  |
|  .............*.****..* |  .........*..**.*.....* | .........****.*.**...*  | .........*..*.*..*..*.  |
|  ........***.....*..*.* |  ........**.....*.....* | ........*.**.*.**....*  | ........*......*..*.*.  |
|  ........*........*...* |  .......**..*....**...* | ........*..***...**..*  | .......**.......***..*  |
|  ........*.**.....*.*.* |  ........*..**.....*..* | ........******....*...  | ........**...*...**..*  |
|  .........***.*.......* |  .........*..........** | ...........*.........*  | .........*.*.........*  |
|  ...........*.......... |  ...........**........* | .....................*  | ............*........*  |
|  ........*.*......*..*. |  ........*............. | .........*..**........  | .........*.......**...  |
|  ......******....*..... |  ......***..*....**.... | .......***......****..  | ......****......****..  |
|  .....*.....*....*...*. |  .....*.....*...**.**.. | .....**...****..*...*.  | .....**....**..**.**..  |
|  .....*..***.....****.. |  ....**.**.*.*...****.. | .....*..**.*....*.....  | ....**..**......**....  |
|  .....**.*.*.**........ |  .....**.*.*......**... | .....*...*.*.....*..*.  | .....*.*.*.**.........  |
|  ........*.*........... |  ......*.*.*........... | ......**.*.*..........  | ......**.*.*..........  |
|  .......**.*........... |  .......**.**.......... | ........**.**.........  | .......*.*.**.........  |
|  .........**..*........ |  ..........*........... | .........*............  | ........**.**.........  |
|  .........*...*........ |  .........*.***........ | ..........*..*........  | ..........*...........  |
|  ..........*.*......... |  .........***.......... | .........**...........  | .........***..........  |
|  ..........*........... |  .........*.*.......... | .........*..*.........  | .........*.*..........  |
|  ........*............. |  ........*.*........... | ...........*..........  | ...........**.........  |
|  ......*****...*....... |  ......****............ | .......*****..........  | ......*******.........  |
|  .....*.......*........ |  .....*.....*.......... | .....**.....*.........  | .....**....**.........  |
|  .....*..****.......... |  ....**.**.**.......... | .....*..**...*........  | ....**..**............  |
|  .....**.*.*........... |  .....**.*.**.......... | .....*...*............  | .....*.*.*............  |
|  ........*............. |  ......*.*.*........... | ......**.*.*..........  | ......**..............  |
|  .......**.***......... |  .......**...*......... | ........***...........  | .......*...**.........  |
|  .........****......... |  ...................... | .........*..**........  | ........***...........  |
|  .........*.*.......... |  .........*.**......... | ......................  | ......................  |
|  ...................... |  ...................... | ......................  | .........*............  |
|  ...................... |  ...................... | ........***...........  | .......*...*..........  |
|  .......**............. |  ......*****........... | .......*****..........  | ......*...............  |
|  ......**.***.......... |  ......*....*.......... | ......**.***..........  | ......*....*..........  |
|  .......*****.......... |  ......*............... | .......**.............  | ......*****...........  |
|  ........***........... |  .......*...*.......... | ......................  | ......................  |
|  ...................... |  .........*............ | ......................  | ......................  |
Note that grid is shifted one left in generations 3 and 4. The program's grid parser requires that the grid be so shifted and that the input be a complete rectangular prism of non-blanks. The shifting is dependent on the geometry of the search (speed and direction). If you have trouble guessing up what it wants for a given geometry let me know and I can provide a sample input file. Maybe some day I'll make the errors intelligible.

For today's search we're gonna redo this arm, so let's strip it off and cut the picture down to size.

Code: Select all

  ...................... |  .....................* | ......................  | ......................  
  .............*.**...** |  .............*.*.*...* | ............*.*......*  | ............*.*......*  
  ...........***.***.... |  ..........****.*.*...* | ..........*****...**..  | ..........***.**..***.  
  .........**........... |  .........**......*.... | .........*......*..*..  | .........*......****.*  
  .........*..***.*..... |  ........**.**.**...*.. | .........*..**.**...**  | ........**..**.***.***  
  .........*..*.*...***. |  .........*..*.*.*****. | .........**..*.*..*..*  | .........***.*.*...*..  
  ..........**...*.*..*. |  ..........**...*.*..*. | ...........*....*.*..*  | ..........*...*.*...**  
  ............**.*.**.*. |  ...........***.*....*. | ..............*.*....*  | ............**..*...**  
  .............*.****..* |  .........*..**.*.....* | .........****.*.**...*  | .........*..*.*..*..*.  
  ........***.....*..*.* |  ........**.....*.....* | ........*.**.*.**....*  | ........*......*..*.*.  
  .......???????...*...* |  .......???????..**...* | .......???????...**..*  | .......???????..***..*  
  .......???????...*.*.* |  .......???????....*..* | .......???????....*...  | .......???????...**..*  
  .......???????.......* |  .......???????......** | .......???????.......*  | .......???????.......*  
  .......???????........ |  .......???????.......* | .......???????.......*  | .......???????.......*  
  .......???????...*..*. |  .......???????........ | .......???????........  | .......???????...**...  
  .......???????..*..... |  .......???????..**.... | .......???????..****..  | .......???????..****..  
  .......???????..*...*. |  .......???????.**.**.. | .......???????..*...*.  | .......???????.**.**..  
  .......???????..****.. |  .......???????..****.. | .......???????..*.....  | .......???????..**....  
  .......???????........ |  .......???????...**... | .......???????...*..*.  | .......???????........  
  .......???????........ |  .......???????........ | .......???????........  | .......???????........  
  .......???????........ |  .......???????........ | .......???????........  | .......???????........  
Note this is the actual input file we'll use below (`1.in`). Again, the question marks must be a complete rectangular prism.

Check out the code and build. Note I've pushed a `origin/20220523-demo` demo branch containing the above input file and configuring the program for the type of search we want to do here.

Code: Select all

$ git clone git@github.com:amling/rlife.git
Cloning into 'rlife'...
remote: Enumerating objects: 17214, done.
remote: Counting objects: 100% (17214/17214), done.
remote: Compressing objects: 100% (5133/5133), done.
remote: Total 17214 (delta 12265), reused 16931 (delta 11982), pack-reused 0
Receiving objects: 100% (17214/17214), 3.29 MiB | 0 bytes/s, done.
Resolving deltas: 100% (12265/12265), done.
$ cd rlife
$ git checkout origin/20220523-demo
HEAD is now at ac2735005d1b... input file
$ cargo build --release
(a bunch of build output and a long, long wait)
   Compiling rlife v1.0.0 (<path>/rlife)
    Finished release [optimized + debuginfo] target(s) in 1m 06s
$
Set a memory limit. Optional, but w/o it bigger searches will happily fill memory and depending on your OS and configuration you might not like what happens (thrash in swap, get oomkilled, etc.). This is 4GB which is more than enough to find this arm.

Code: Select all

$ ulimit -v 4194304
$
Now run it. I generally recommend saving output to a file and watching it in a pager, but we'll do it live here. `1.in` is the input file, `0 3 1` are how much to pad the question marks by (top, left, right). As marked in the input file nothing would be found and I happen to know `0 3 1` is the minimum to find this arm. In real searches I would generally start small and increase all three paddings together until it fills memory and dies and then fiddle with the exact padding values (trading off between them) to see if I can find anything interesting.

Code: Select all

$ ./target/release/rlife 1.in 0 3 1
20220523 09:22:52 [INFO] Compiling [checks3 1/2] table of 17 + 4 = 21 bits
20220523 09:22:52 [INFO] Compiling [checks3 2/2] table of 17 + 4 = 21 bits
20220523 09:22:52 [INFO] Compile tables took 41.539288ms
20220523 09:22:52 [INFO] Compiling [checks3 1/2] table of 20 + 4 = 24 bits
20220523 09:22:52 [INFO] Compiling [checks3 2/2] table of 20 + 4 = 24 bits
20220523 09:22:52 [INFO] Compile tables took 314.051779ms
20220523 09:22:52 [INFO] Compile check_engine took 356.204179ms
20220523 09:22:52 [INFO] Compile left edge took 2.637µs
20220523 09:22:52 [INFO] Compile right edge took 1.678µs
20220523 09:22:52 [INFO] Compile monitor took 46ns
20220523 09:22:52 [INFO] VmPeak:          689188 kB
20220523 09:22:52 [INFO] Memory: spine store old_gens 80 B, spine store cur_gen 160 B, cols 156 B
20220523 09:22:52 [INFO] Spine store sizes: old_gens [10], cur_gen 10
20220523 09:22:52 [INFO] Firstest:
20220523 09:22:52 [INFO]  ...........*.** |  .......*..**.*. | .......****.*.*  | .......*..*.*..
20220523 09:22:52 [INFO]  ......***.....* |  ......**.....*. | ......*.**.*.**  | ......*......*.
20220523 09:22:52 [INFO] Random partial:
20220523 09:22:52 [INFO]  ...........*.** |  .......*..**.*. | .......****.*.*  | .......*..*.*..
20220523 09:22:52 [INFO]  ......***.....* |  ......**.....*. | ......*.**.*.**  | ......*......*.
...
The program does a bunch of precompilation to make the main search faster, then outputs its first status including a bunch of stats about memory and, as configured, the "first" partial (for complex values of "first") and a random partial. Right now these are both the same as there is only one partial to start. Later in the earch they'll vary and as described earlier in the thread it can be configured to output quite a few different statusey things.

Eventually it outputs a result like this:

Code: Select all

...
20220523 09:23:27 [INFO] End ("LlsssEndsZero"):
20220523 09:23:27 [INFO]  ...........*.** |  .......*..**.*. | .......****.*.*  | .......*..*.*..
20220523 09:23:27 [INFO]  ......***.....* |  ......**.....*. | ......*.**.*.**  | ......*......*.
20220523 09:23:27 [INFO]  ......*........ |  .....**..*....* | ......*..***...  | .....**.......*
20220523 09:23:27 [INFO]  ......*.**..... |  ......*..**.... | ......******...  | ......**...*...
20220523 09:23:27 [INFO]  .......***.*... |  .......*....... | .........*.....  | .......*.*.....
20220523 09:23:27 [INFO]  .........*..... |  .........**.... | ...............  | ..........*....
20220523 09:23:27 [INFO]  ......*.*...... |  ......*........ | .......*..**...  | .......*.......
20220523 09:23:27 [INFO]  ....******....* |  ....***..*....* | .....***......*  | ....****......*
20220523 09:23:27 [INFO]  ...*.....*....* |  ...*.....*...** | ...**...****..*  | ...**....**..**
20220523 09:23:27 [INFO]  ...*..***.....* |  ..**.**.*.*...* | ...*..**.*....*  | ..**..**......*
20220523 09:23:27 [INFO]  ...**.*.*.**... |  ...**.*.*...... | ...*...*.*.....  | ...*.*.*.**....
20220523 09:23:27 [INFO]  ......*.*...... |  ....*.*.*...... | ....**.*.*.....  | ....**.*.*.....
20220523 09:23:27 [INFO]  .....**.*...... |  .....**.**..... | ......**.**....  | .....*.*.**....
20220523 09:23:27 [INFO]  .......**..*... |  ........*...... | .......*.......  | ......**.**....
20220523 09:23:27 [INFO]  .......*...*... |  .......*.***... | ........*..*...  | ........*......
20220523 09:23:27 [INFO]  ........*.*.... |  .......***..... | .......**......  | .......***.....
20220523 09:23:27 [INFO]  ........*...... |  .......*.*..... | .......*..*....  | .......*.*.....
20220523 09:23:27 [INFO]  ......*........ |  ......*.*...... | .........*.....  | .........**....
20220523 09:23:27 [INFO]  ....*****...*.. |  ....****....... | .....*****.....  | ....*******....
20220523 09:23:27 [INFO]  ...*.......*... |  ...*.....*..... | ...**.....*....  | ...**....**....
20220523 09:23:27 [INFO]  ...*..****..... |  ..**.**.**..... | ...*..**...*...  | ..**..**.......
20220523 09:23:27 [INFO]  ...**.*.*...... |  ...**.*.**..... | ...*...*.......  | ...*.*.*.......
20220523 09:23:27 [INFO]  ......*........ |  ....*.*.*...... | ....**.*.*.....  | ....**.........
20220523 09:23:27 [INFO]  .....**.***.... |  .....**...*.... | ......***......  | .....*...**....
20220523 09:23:27 [INFO]  .......****.... |  ............... | .......*..**...  | ......***......
20220523 09:23:27 [INFO]  .......*.*..... |  .......*.**.... | ...............  | ...............
20220523 09:23:27 [INFO]  ............... |  ............... | ...............  | .......*.......
20220523 09:23:27 [INFO]  ............... |  ............... | ......***......  | .....*...*.....
20220523 09:23:27 [INFO]  .....**........ |  ....*****...... | .....*****.....  | ....*..........
20220523 09:23:27 [INFO]  ....**.***..... |  ....*....*..... | ....**.***.....  | ....*....*.....
20220523 09:23:27 [INFO]  .....*****..... |  ....*.......... | .....**........  | ....*****......
20220523 09:23:27 [INFO]  ......***...... |  .....*...*..... | ...............  | ...............
20220523 09:23:27 [INFO]  ............... |  .......*....... | ...............  | ...............
20220523 09:23:27 [INFO]  ............... |  ............... | ...............  | ...............
20220523 09:23:27 [INFO]  ............... |  ............... | ...............  | ...............
...
After that it can be killed since it will keep padding that with zeros and various shapes of *WSS forever.

User avatar
May13
Posts: 395
Joined: March 11th, 2021, 8:33 am

Re: amling search program principles discussion / brain dump

Post by May13 » May 24th, 2022, 1:13 am

Is there any way to compile program using Cygwin? After any of "$ cargo build --release" and "$ cargo run", console returns these errors:

Code: Select all

   Compiling ars_rctl_main v1.0.0 (D:\CGoL\cygwin64\home\rlife\ars\rctl\main)
error[E0433]: failed to resolve: could not find `unix` in `os`
  --> ars\rctl\main\src\lib.rs:11:14
   |
11 | use std::os::unix::net::UnixListener;
   |              ^^^^ could not find `unix` in `os`

error[E0433]: failed to resolve: could not find `unix` in `os`
  --> ars\rctl\main\src\lib.rs:12:14
   |
12 | use std::os::unix::net::UnixStream;
   |              ^^^^ could not find `unix` in `os`

error[E0433]: failed to resolve: use of undeclared type `UnixListener`
  --> ars\rctl\main\src\lib.rs:64:16
   |
64 |     let sock = UnixListener::bind(sock)?;
   |                ^^^^^^^^^^^^ use of undeclared type `UnixListener`

error[E0412]: cannot find type `UnixStream` in this scope
  --> ars\rctl\main\src\lib.rs:78:41
   |
78 | fn handle1(rs: RctlServer, sock: Result<UnixStream, StringError>) -> Result<(), StringError> {
   |           -                             ^^^^^^^^^^ not found in this scope
   |           |
   |           help: you might be missing a type parameter: `<UnixStream>`

error[E0412]: cannot find type `UnixStream` in this scope
   --> ars\rctl\main\src\lib.rs:112:34
    |
112 | fn handle2(rs: RctlServer, sock: UnixStream) -> Result<(), StringError> {
    |                                  ^^^^^^^^^^ not found in this scope

error[E0412]: cannot find type `UnixStream` in this scope
   --> ars\rctl\main\src\lib.rs:148:43
    |
148 | fn handle3<'a>(rs: RctlServer, mut sockr: UnixStream, log: RctlLog<'a>) -> Result<Option<Value>, StringError> {
    |                                           ^^^^^^^^^^ not found in this scope
Can we complete 14-in-9 and 15-in-10 in CGoL?

The latest version of hex-gliders.db have 249 spaceships from OT hexagonal rules.

My CA

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 24th, 2022, 12:01 pm

May13 wrote:
May 24th, 2022, 1:13 am
Is there any way to compile program using Cygwin? After any of "$ cargo build --release" and "$ cargo run", console returns these errors:

Code: Select all

(snip)
That is because sadly I had written this all for myself, with no intent or effort for that level of portability. It is totally "safe" to rip out rctl, and I have pushed a quick sketch of doing so (20220523-demo2). "Safe" in the sense of what rctl does you don't need (allows sending requests to process later like "checkpoint your state" or "change how much memory you limit yourself to"), not safe in the sense of "amling is keen on maintaining this". Unfortunately even if you get past that I have no idea what is going to happen when you reach a `libc::mmap` call (or `mremap`). Will it work? Die immediately? Return successfully but then do something broken and insane later?

User avatar
May13
Posts: 395
Joined: March 11th, 2021, 8:33 am

Re: amling search program principles discussion / brain dump

Post by May13 » May 24th, 2022, 8:11 pm

amling wrote:
May 24th, 2022, 12:01 pm
Unfortunately even if you get past that I have no idea what is going to happen when you reach a `libc::mmap` call (or `mremap`). Will it work? Die immediately? Return successfully but then do something broken and insane later?
Compilation stopped at 10 errors "cannot find ? ? in crate `libc`":

Code: Select all

$ cargo build --release
   Compiling autocfg v1.0.0
   Compiling lazy_static v1.4.0
   Compiling cfg-if v1.0.0
   Compiling proc-macro2 v1.0.9
   Compiling unicode-xid v0.2.0
   Compiling scopeguard v1.1.0
   Compiling libc v0.2.68
   Compiling syn v1.0.17
   Compiling cfg-if v0.1.10
   Compiling maybe-uninit v2.0.0
   Compiling rayon-core v1.9.1
   Compiling serde v1.0.105
   Compiling winapi v0.3.8
   Compiling ryu v1.0.3
   Compiling byteorder v1.3.4
   Compiling either v1.6.1
   Compiling ppv-lite86 v0.2.16
   Compiling bitintr v0.3.0
   Compiling ars_macro v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\macro)
   Compiling itoa v0.4.5
   Compiling ars_sync v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\sync)
   Compiling getrandom v0.2.4
   Compiling crossbeam-utils v0.8.4
   Compiling crossbeam-utils v0.7.2
   Compiling memoffset v0.6.3
   Compiling memoffset v0.5.4
   Compiling num-traits v0.2.11
   Compiling crossbeam-epoch v0.8.2
   Compiling num-integer v0.1.42
   Compiling rayon v1.5.0
   Compiling itertools v0.10.3
   Compiling ars_ds v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\ds)
   Compiling rand_core v0.6.3
   Compiling ars_aa v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\aa)
   Compiling rand_chacha v0.3.1
   Compiling num_cpus v1.13.0
   Compiling quote v1.0.3
   Compiling rand v0.8.4
   Compiling crossbeam-channel v0.5.1
   Compiling crossbeam-epoch v0.9.4
   Compiling crossbeam-queue v0.2.1
   Compiling crossbeam-channel v0.4.2
   Compiling time v0.1.42
   Compiling crossbeam-deque v0.8.0
   Compiling crossbeam-deque v0.7.3
   Compiling chrono v0.4.11
   Compiling crossbeam v0.7.3
   Compiling serde_derive v1.0.105
   Compiling bincode v1.2.1
   Compiling serde_json v1.0.48
   Compiling rlife v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife)
error[E0425]: cannot find function `mmap` in crate `libc`
  --> src\mmap.rs:28:19
   |
28 |             libc::mmap(
   |                   ^^^^ not found in `libc`

error[E0425]: cannot find value `PROT_READ` in crate `libc`
  --> src\mmap.rs:31:23
   |
31 |                 libc::PROT_READ | libc::PROT_WRITE,
   |                       ^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `PROT_WRITE` in crate `libc`
  --> src\mmap.rs:31:41
   |
31 |                 libc::PROT_READ | libc::PROT_WRITE,
   |                                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_PRIVATE` in crate `libc`
  --> src\mmap.rs:32:23
   |
32 |                 libc::MAP_PRIVATE | libc::MAP_ANON,
   |                       ^^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_ANON` in crate `libc`
  --> src\mmap.rs:32:43
   |
32 |                 libc::MAP_PRIVATE | libc::MAP_ANON,
   |                                           ^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_FAILED` in crate `libc`
  --> src\mmap.rs:37:25
   |
37 |         if ptr == libc::MAP_FAILED {
   |                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find function `mremap` in crate `libc`
  --> src\mmap.rs:59:19
   |
59 |             libc::mremap(
   |                   ^^^^^^ not found in `libc`

error[E0425]: cannot find value `MREMAP_MAYMOVE` in crate `libc`
  --> src\mmap.rs:63:23
   |
63 |                 libc::MREMAP_MAYMOVE,
   |                       ^^^^^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_FAILED` in crate `libc`
  --> src\mmap.rs:66:25
   |
66 |         if ptr == libc::MAP_FAILED {
   |                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find function `munmap` in crate `libc`
   --> src\mmap.rs:102:19
    |
102 |             libc::munmap(self.ptr, len as libc::size_t)
    |                   ^^^^^^ not found in `libc`

For more information about this error, try `rustc --explain E0425`.
error: could not compile `rlife` due to 10 previous errors
Can we complete 14-in-9 and 15-in-10 in CGoL?

The latest version of hex-gliders.db have 249 spaceships from OT hexagonal rules.

My CA

amling
Posts: 152
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling » May 24th, 2022, 8:58 pm

May13 wrote:
May 24th, 2022, 8:11 pm
amling wrote:
May 24th, 2022, 12:01 pm
Unfortunately even if you get past that I have no idea what is going to happen when you reach a `libc::mmap` call (or `mremap`). Will it work? Die immediately? Return successfully but then do something broken and insane later?
Compilation stopped at 10 errors "cannot find ? ? in crate `libc`":

Code: Select all

$ cargo build --release
   Compiling autocfg v1.0.0
   Compiling lazy_static v1.4.0
   Compiling cfg-if v1.0.0
   Compiling proc-macro2 v1.0.9
   Compiling unicode-xid v0.2.0
   Compiling scopeguard v1.1.0
   Compiling libc v0.2.68
   Compiling syn v1.0.17
   Compiling cfg-if v0.1.10
   Compiling maybe-uninit v2.0.0
   Compiling rayon-core v1.9.1
   Compiling serde v1.0.105
   Compiling winapi v0.3.8
   Compiling ryu v1.0.3
   Compiling byteorder v1.3.4
   Compiling either v1.6.1
   Compiling ppv-lite86 v0.2.16
   Compiling bitintr v0.3.0
   Compiling ars_macro v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\macro)
   Compiling itoa v0.4.5
   Compiling ars_sync v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\sync)
   Compiling getrandom v0.2.4
   Compiling crossbeam-utils v0.8.4
   Compiling crossbeam-utils v0.7.2
   Compiling memoffset v0.6.3
   Compiling memoffset v0.5.4
   Compiling num-traits v0.2.11
   Compiling crossbeam-epoch v0.8.2
   Compiling num-integer v0.1.42
   Compiling rayon v1.5.0
   Compiling itertools v0.10.3
   Compiling ars_ds v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\ds)
   Compiling rand_core v0.6.3
   Compiling ars_aa v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife\ars\aa)
   Compiling rand_chacha v0.3.1
   Compiling num_cpus v1.13.0
   Compiling quote v1.0.3
   Compiling rand v0.8.4
   Compiling crossbeam-channel v0.5.1
   Compiling crossbeam-epoch v0.9.4
   Compiling crossbeam-queue v0.2.1
   Compiling crossbeam-channel v0.4.2
   Compiling time v0.1.42
   Compiling crossbeam-deque v0.8.0
   Compiling crossbeam-deque v0.7.3
   Compiling chrono v0.4.11
   Compiling crossbeam v0.7.3
   Compiling serde_derive v1.0.105
   Compiling bincode v1.2.1
   Compiling serde_json v1.0.48
   Compiling rlife v1.0.0 (D:\CGoL\cygwin64\home\rlife\d2\rlife)
error[E0425]: cannot find function `mmap` in crate `libc`
  --> src\mmap.rs:28:19
   |
28 |             libc::mmap(
   |                   ^^^^ not found in `libc`

error[E0425]: cannot find value `PROT_READ` in crate `libc`
  --> src\mmap.rs:31:23
   |
31 |                 libc::PROT_READ | libc::PROT_WRITE,
   |                       ^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `PROT_WRITE` in crate `libc`
  --> src\mmap.rs:31:41
   |
31 |                 libc::PROT_READ | libc::PROT_WRITE,
   |                                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_PRIVATE` in crate `libc`
  --> src\mmap.rs:32:23
   |
32 |                 libc::MAP_PRIVATE | libc::MAP_ANON,
   |                       ^^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_ANON` in crate `libc`
  --> src\mmap.rs:32:43
   |
32 |                 libc::MAP_PRIVATE | libc::MAP_ANON,
   |                                           ^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_FAILED` in crate `libc`
  --> src\mmap.rs:37:25
   |
37 |         if ptr == libc::MAP_FAILED {
   |                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find function `mremap` in crate `libc`
  --> src\mmap.rs:59:19
   |
59 |             libc::mremap(
   |                   ^^^^^^ not found in `libc`

error[E0425]: cannot find value `MREMAP_MAYMOVE` in crate `libc`
  --> src\mmap.rs:63:23
   |
63 |                 libc::MREMAP_MAYMOVE,
   |                       ^^^^^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find value `MAP_FAILED` in crate `libc`
  --> src\mmap.rs:66:25
   |
66 |         if ptr == libc::MAP_FAILED {
   |                         ^^^^^^^^^^ not found in `libc`

error[E0425]: cannot find function `munmap` in crate `libc`
   --> src\mmap.rs:102:19
    |
102 |             libc::munmap(self.ptr, len as libc::size_t)
    |                   ^^^^^^ not found in `libc`

For more information about this error, try `rustc --explain E0425`.
error: could not compile `rlife` due to 10 previous errors
Not sure what to tell you, I guess `libc` crate on cygwin has less stuff in it? My ability and willingness to debug cygwin remotely is not super high and I'm not very much not excited to make any real changes to the code to make it portable to such a strange place. Is Microsoft's "WSL" a better linux? Can you dig up a linux box? Can you rent one from EC2?

I guess you could also try ripping out all the mmap code although that is going to be a much more complex edit. I left the pre-mmap versions in, but generally don't use them (they're faster but fragment memory horribly and given how memory-bound this is I always make that trade). You'd want to look at switching `MmapVec<SL>` to `Vec<SL>` where it's configured in `main_llsss` but then also delete all the remaining compiler errors in the now-unused mmap code. Unless you are yourself a programmer with modest to advanced knowledge of rust I can't encourage this path.

EDIT: Ripped out mmap and pushed `20220523-demo3` branch. Still gonna require modest rust knowledge or a great ability to mimic surrounding code to actually configure to run, even if this branch works out.

Post Reply