amling search program principles discussion / brain dump

[amling]

Edit: would there be any negative consequences to setting LLSSS_MAX_TABLE_SIZE?

Just the implied ones, namely that the non-precompilation part of the search will likely be slower. The hottest, innermost part of the core search is: (1) PEXT some chunks of bits out of a few places and shift and bitwise or them together into one big scalar, (2) PEXT some subsets of that big scalar out, (3) look up those subsets in these tables, and (4) bitwise and all table results together.

The bigger you allow the tables to be the longer they (might) take to precompile but the fewer there might be able to be. So bigger tables means: longer precompiles (exponentially bigger tables), more memory (exponentially bigger tables), but faster main execution (fewer table lookups to run). I stress "might" in that it will allow tables to be as large as the max but won't necessarily make them that big. In fact, it tries pretty hard to make them as small as possible while still attaining whatever count of tables it decided it could get down to.

I don't have a particularly principled way to decide what size is acceptable to users. I had played with it a bit when developing it and in the end I picked 27 for release builds and 15 for debug builds, which were generally palatable to wait out and captured most of the possible speedup for reduced table counts.

[Sokwe]

Amling, I'm about to inundate you with questions once again. Answer them at your leisure.

Is "raw:1:0:2:02:0:0:1" just "raw:U:W:I" where U=1:0:2, W=02, and I=0:0:1?

Close. The first three specify U in XYT coordinates as you've suggested. The second three specify V (the vector that wraps) and the last three specify W (the direction the search builds in).

The "UWI" in "to-uwi" and "from-uwi" is not quite the same thing. The problem with trying to view a file in UVW coordinates (really it would be UWV as V is the bounded/wrapped one) is that they can be fractions and the valid points (which are integers in XYT) are not necessarily an axis-aligned lattice so it would be very gappy. UWI is much weirder to explain but generally handles well for my horrible grid editing adventures: the first coordinate is the floor of the U coordinate, the second W is the floor of the W coordinate and the third coordinate (which corresponds to T/generation in the usual view) is the build order within a tile (all the fractional UVW values are sorted, by default in WVU order (sorted by fractional W, ties broken by fractional V, ties broken by fractional U)).

Amling, I've been trying to use LLSSS to see which Life-like rules support p1 photons, and I've had to do a lot of trial-and-error setting up searches with different slopes. I would like to understand this UWI/UVW/XYT business if I can. Perhaps I'm wrong to consider UWI as a coordinate system? Let me state my thoughts and hopefully you can see where I might be going wrong.

Consider the following geometry (?) file:

Code: Select all

| ab | d. |
| c. | e. |

If I viewed it in XYT coordinates does that mean a->b is +X, a->c is +Y, and a->d is +T? Is d->a also +T? Does grid-tool from-uwi give an output in XYT coordinates?

Now as an example, suppose I run "./rlife grid-tool from-uwi raw:1:0:2:0:1:2:1:1:0" on the following input:

Code: Select all

| .a | b. | c. | d. |
| e. | .. | .. | .. |

This gives the following output:

Code: Select all

|      |      |
|  a.  |   .  |
| .c.. |  b.. |
|  e.  |  d.. |
|      |   .  |

If I viewed UWI as a coordinate system and the input file as being in UWI coordinates, then I would think, for example, b->c is +I. Looking at the output and considering V=(0,1,2), I would think a->c is +V. Looking at the input, a->c would be 2I+U, so I would guess that V=2I-U. But then the output indicates that b->d is +V, but the input indicates that b->d is just 2I != 2I-U. It seems like there must be something wrong in my assumptions or understanding.

This appears to be a valid geometry for a c/2 orthogonal b2f-like diagonally oriented search, but I only say so because LLSSS seems to run it with no problem. On the other hand, if I use something like raw:0:2:3:1:0:1:0:0:1 I can generate an input geometry file with from-uwi, but trying to run it gives the following error:

Code: Select all

20241012 02:55:00 [INFO] WAO error window #0 (included):
20241012 02:55:00 [INFO] |               ..... |
20241012 02:55:00 [INFO] |             .....   |
20241012 02:55:00 [INFO] |            .....    |
20241012 02:55:00 [INFO] |          .....      |
20241012 02:55:00 [INFO] |         x....       |
20241012 02:55:00 [INFO] |       x....         |
20241012 02:55:00 [INFO] |      .....          |
20241012 02:55:00 [INFO] |    .....            |
20241012 02:55:00 [INFO] |   .....             |
20241012 02:55:00 [INFO] | .....               |
thread 'main' panicked at src/llsss/env.rs:40:9:
assertion `left == right` failed
  left: 2
 right: 3

On the other other had, raw:0:2:3:1:0:1:0:1:4 appears to be valid. I only discovered these things by trial-and-error, not by some fundamental understanding of what I'm doing.

Other unrelated questions:

My laptop has fairly limited memory. Is there a way to sacrifice speed or completeness (e.g., by dropping random slices) to extend the length of my llsss-recentering-wao searches? When searching for p1 photons, I often find that one width will complete without using much memory, while the next larger width will suddenly use too much. An example rule is B2467/S134568 (Edit: corrected rule), where a width-30 c1-s2s search completes very quickly, but a width-31 search gets to around w_pos 50, at which point the memory usage starts to balloon, and I can't get beyond w_pos 53.

Suppose a rule has no p1 photons. If that rule has an extensible p1 wave with a single-sided stabilization, an extensible p1 f2b wick and an extensible p1 b2f wick, does that mean that LLSSS wouldn't be able to prove nonexistence? For example, the unsolved rule has the following wave:

Code: Select all

| .......................................... |
| .......................................... |
| .....................................*.... |
| ...................................*...... |
| ...................................***.*.. |
| ..................................***..... |
| .................................*.***.... |
| ................................*......... |
| ................................*..*.*.*.. |
| ...........................*.....*........ |
| .........................*.....**..***.... |
| .........................***.*....***..... |
| ........................***....*...***.*.. |
| .......................*.***.......*...... |
| ......................*..............*.... |
| ......................*..*.*.*............ |
| .................*.....*.................. |
| ...............*.....**..***.............. |
| ...............***.*....***............... |
| ..............***....*...***.*............ |
| .............*.***.......*................ |
| ............*..............*.............. |
| ............*..*.*.*...................... |
| .......*.....*............................ |
| .....*.....**..***........................ |
| .....***.*....***......................... |
| ....***....*...***.*...................... |
| ...*.***.......*.......................... |
| ..*..............*........................ |
| ..*..*.*.*................................ |

f2b wick:

Code: Select all

| .......... |
| .......... |
| ....**.... |
| ...*..*... |
| ..*....*.. |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |
| ...****... |

and b2f wick:

Code: Select all

| .................. |
| .....*...*...*.... |
| .................. |
| ...*.*.*.*.*.*.*.. |
| .....***...***.... |
| ....****.*.****... |
| ......*.....*..... |
| .......*..*....... |
| ........**.*...... |
| ...........*.*.... |
| .................. |
| ....*...*...*..... |
| .................. |
| ..*.*.*.*.*.*.*... |
| ....***...***..... |
| ...****.*.****.... |
| .....*.....*...... |
| .......*..*....... |
| ......*.**........ |
| ....*.*........... |
| .................. |
| .....*...*...*.... |
| .................. |
| ...*.*.*.*.*.*.*.. |
| .....***...***.... |
| ....****.*.****... |
| ......*.....*..... |
| .......*..*....... |
| ........**.*...... |
| ...........*.*.... |

Assuming this rule has no p1 photons, would there be any way to potentially use LLSSS to prove this? I would think that any slanted f2b-like search would find infinite extensions of the f2b, and any slanted b2f search would find infinite extensions of the b2f wick.

I have added "--ends zero_and_halt".

Would it be difficult or easy to add halting for symmetric ends? I looked at the changes, but didn't immediately understand them, so I was unsure how to implement it myself.

[amling]

Amling, I've been trying to use LLSSS to see which Life-like rules support p1 photons, and I've had to do a lot of trial-and-error setting up searches with different slopes. I would like to understand this UWI/UVW/XYT business if I can. Perhaps I'm wrong to consider UWI as a coordinate system?

UWI is not a coordinate system in the vector space/lattice sense, but it is a coordinate system in the sense of naming all points in XYT space mod the velocity. UVW is a coordinate system in the vector space sense of things but what 3-tuples of UVW coordinates do or do not correspond to integer lattice points in XYT is not always nice.

Let me state my thoughts and hopefully you can see where I might be going wrong.

Consider the following geometry (?) file:

Code: Select all

| ab | d. |
| c. | e. |

If I viewed it in XYT coordinates does that mean a->b is +X, a->c is +Y, and a->d is +T? Is d->a also +T

Yes, yes, yes, and not really. d->a in the sense of "left" is -T. d->a in the sense of "right, wrapping around" isn't really anything.

Does grid-tool from-uwi give an output in XYT coordinates?

Yeah, in the input left/right is interpreted as X, up/down as Y, and bigger left/right as T, then the parsed XYT tuples are converted to UWI tuples and output where U determines left/right position, W determines up/down position, and I determines bigger left/right position.

Now as an example, suppose I run "./rlife grid-tool from-uwi raw:1:0:2:0:1:2:1:1:0" on the following input:

Code: Select all

| .a | b. | c. | d. |
| e. | .. | .. | .. |

This gives the following output:

Code: Select all

|      |      |
|  a.  |   .  |
| .c.. |  b.. |
|  e.  |  d.. |
|      |   .  |

If I viewed UWI as a coordinate system and the input file as being in UWI coordinates, then I would think, for example, b->c is +I. Looking at the output and considering V=(0,1,2), I would think a->c is +V. Looking at the input, a->c would be 2I+U, so I would guess that V=2I-U. But then the output indicates that b->d is +V, but the input indicates that b->d is just 2I != 2I-U. It seems like there must be something wrong in my assumptions or understanding.

"I" isn't a sensible linear coordinate like all the rest, it's just the index in the search order's enumeration of all the possible fractional UVW values. In pleasant geometries there is only one bit per tile and so I is identically 0. As an example, in this geometry the fractional values, in order, are:

Code: Select all

(Vec3(0, 0, 0), Vec3Uvw(0, 0, 0))
(Vec3(1, 1, 3), Vec3Uvw(3, 3, 1))
(Vec3(1, 1, 2), Vec3Uvw(2, 2, 2))
(Vec3(1, 1, 1), Vec3Uvw(1, 1, 3))

To keep everything integers the UVW "fractional" coordinates are stored as numerator over tile bits (4 here) so e.g. that "Vec3Uvw(3, 3, 1)" is actually (3/4, 3/4, 1/4). Working backwards, as an example:

A UWI coordinate of (5, 7, 2) is UVW (5, 0, 7) + (2, 2, 2)/4 (at least mod integral V). It is also XYT of 5 * (1, 0, 2) + 7 * (1, 1, 0) + (1, 1, 2). 5 * (1, 0, 2) contributed by 5U, 7 * (1, 1, 0) contributed by 7W, and (1, 1, 2) contributed by I2.

This is all completely terrible to try to understand and manage for interesting geometries. I have never really interacted with it other than by programming it all and then by using to-uwi and from-uwi to view or block edit things in that aligned form.

This appears to be a valid geometry for a c/2 orthogonal b2f-like diagonally oriented search, but I only say so because LLSSS seems to run it with no problem. On the other hand, if I use something like raw:0:2:3:1:0:1:0:0:1 I can generate an input geometry file with from-uwi, but trying to run it gives the following error:

Code: Select all

20241012 02:55:00 [INFO] WAO error window #0 (included):
20241012 02:55:00 [INFO] |               ..... |
20241012 02:55:00 [INFO] |             .....   |
20241012 02:55:00 [INFO] |            .....    |
20241012 02:55:00 [INFO] |          .....      |
20241012 02:55:00 [INFO] |         x....       |
20241012 02:55:00 [INFO] |       x....         |
20241012 02:55:00 [INFO] |      .....          |
20241012 02:55:00 [INFO] |    .....            |
20241012 02:55:00 [INFO] |   .....             |
20241012 02:55:00 [INFO] | .....               |
thread 'main' panicked at src/llsss/env.rs:40:9:
assertion `left == right` failed
  left: 2
 right: 3

Yeah, this is a miserable, miserable detail most often hidden. In raw:0:2:3:1:0:1:0:0:1 the U neighborhood size (how wide of a U window is needed for every CA check to fall completely within one) is 2, rather than 3. All named geometries have 3 and while the search engine generally can work for other values it requires a recompile and most searches I have done this for have seemed to perform worse (e.g. I did some U=T searches with much wider U neighborhood sizes in finding the 2c/6 greyship). "sl2_size" is the magic string to search for in "src/entry.rs" if you want to try making it work. Usually if the neighbood size is too big I will multiply U up until it's 3 but if it's 2 I'm not sure what to do other than recompile.

U neighborhood sizes are a real source of headache when trying to rig other slopes and I have mostly not had much success with making such searches perform acceptably. They are of course also a minefield of confusion and madness and very few search projects have gone here before.

My laptop has fairly limited memory. Is there a way to sacrifice speed or completeness (e.g., by dropping random slices) to extend the length of my llsss-recentering-wao searches? When searching for p1 photons, I often find that one width will complete without using much memory, while the next larger width will suddenly use too much. An example rule is B2467/S134568 (Edit: corrected rule), where a width-30 c1-s2s search completes very quickly, but a width-31 search gets to around w_pos 50, at which point the memory usage starts to balloon, and I can't get beyond w_pos 53.

I have no implementation of anything like that. In similar situations I usually cope by skimming random partials and running separate searches to try to complete them. LGOL is much more capable of trading off time for memory although not much more capable of anything else and I assume other gfind-like programs would do better than it anyway.

Suppose a rule has no p1 photons. If that rule has an extensible p1 wave with a single-sided stabilization, an extensible p1 f2b wick and an extensible p1 b2f wick, does that mean that LLSSS wouldn't be able to prove nonexistence?

Yeah. Specifically I would say that the rule has "almost half planes" at any angle where "almost half plane" has a very specific definition I've given before and is fulfilled both by half lines (as you give above) but also by pyramids and who knows what else. LLSSS arbitrary width searches will extend any "almost half plane" forever and so be unable to terminate. If these things exist for every angle then I don't see how to make current techniques cut it.

I am somewhat interested in the existence of such a case. I of course knew it was hypothetically possible but am at least a little surprised to find one. If there is no finite photon then the way in which that is true is very weird.

I have added "--ends zero_and_halt".

Would it be difficult or easy to add halting for symmetric ends? I looked at the changes, but didn't immediately understand them, so I was unsure how to implement it myself.

It's not overly hard to implement although it is different enough from zero ends, it's just a bunch more duplicated ends types and maybe-halt checks after showing ends. This is part why I wanted to figure out a better way to integrate this sort of feature rather than hacking up that "zero_and_halt".

[amling]

My laptop has fairly limited memory. Is there a way to sacrifice speed or completeness (e.g., by dropping random slices) to extend the length of my llsss-recentering-wao searches? When searching for p1 photons, I often find that one width will complete without using much memory, while the next larger width will suddenly use too much. An example rule is B2467/S134568 (Edit: corrected rule), where a width-30 c1-s2s search completes very quickly, but a width-31 search gets to around w_pos 50, at which point the memory usage starts to balloon, and I can't get beyond w_pos 53.

Is this the right combination of rule and result? For me a c/1 s2s search appears to find the known wave forever starting at mid_steps=18.

[amling]

"I" isn't a sensible linear coordinate like all the rest, it's just the index in the search order's enumeration of all the possible fractional UVW values. In pleasant geometries there is only one bit per tile and so I is identically 0. As an example, in this geometry the fractional values, in order, are:

Code: Select all

(Vec3(0, 0, 0), Vec3Uvw(0, 0, 0))
(Vec3(1, 1, 3), Vec3Uvw(3, 3, 1))
(Vec3(1, 1, 2), Vec3Uvw(2, 2, 2))
(Vec3(1, 1, 1), Vec3Uvw(1, 1, 3))

To keep everything integers the UVW "fractional" coordinates are stored as numerator over tile bits (4 here) so e.g. that "Vec3Uvw(3, 3, 1)" is actually (3/4, 3/4, 1/4). Working backwards, as an example:

A UWI coordinate of (5, 7, 2) is UVW (5, 0, 7) + (2, 2, 2)/4 (at least mod integral V). It is also XYT of 5 * (1, 0, 2) + 7 * (1, 1, 0) + (1, 1, 2). 5 * (1, 0, 2) contributed by 5U, 7 * (1, 1, 0) contributed by 7W, and (1, 1, 2) contributed by I2.

This is all completely terrible to try to understand and manage for interesting geometries. I have never really interacted with it other than by programming it all and then by using to-uwi and from-uwi to view or block edit things in that aligned form.

I was thinking about this a bit more and realized geometries like 3c/6 are misleading where it will look like I is just V. In 3c6-f2b the fractional values are:

Code: Select all

(Vec3(0, 0, 0), Vec3Uvw(0, 0, 0))
(Vec3(0, -1, 2), Vec3Uvw(0, 1, 0))
(Vec3(0, -2, 4), Vec3Uvw(0, 2, 0))

And so I=0 corresponds to 0 shift, I=1 to V/3 and I=2 to 2V/3. You might be tempted to conclude it acts as a normal linear sort of coordinate even though it's just an accident.

Perhaps easier to draw the right intuition from is something like 2c5d-down:

Code: Select all

(Vec3(0, 0, 0), Vec3Uvw(0, 0, 0))
(Vec3(-1, -1, 3), Vec3Uvw(1, 3, 1))
(Vec3(0, 0, 1), Vec3Uvw(2, 1, 2))
(Vec3(-1, -1, 4), Vec3Uvw(3, 4, 3))
(Vec3(0, 0, 2), Vec3Uvw(4, 2, 4))

You can see them more visually by running something like:

Code: Select all

| 00 | 11 | 22 | 33 | 44 |
| 00 | 11 | 22 | 33 | 44 |

through from-uwi and getting:

Code: Select all

|     |     |     | 11  | 33  |
|  00 |  22 |  44 | 11  | 33  |
|  00 |  22 |  44 |     |     |

You can see I=0 is the first generation, but then I=1 is the fourth (and shifted up and left one), I=2 is the second (not shifted), etc. This matches the search order you'd get if you ran searches in this geometry and is a manifestation of this "staggering" business I'm always talking about.

It is good for building intuition since U=X and W=Y makes it easy to see multiple tiles relative to each other but it's bad in that each I step 0-1, 1-2, 2-3, and 3-4 are all the same vector (mod V anyway) and it thus looking like I is tracking fractional W is a similar sort of lucky accident.

A perhaps even better example would be something like 2c/4 with W=Y (raw:1:0:0:0:-2:4:0:1:0). We'd probably never want to run a search this way, but it can show some of the lattice machinery. Here this UWI:

Code: Select all

| 00 | 11 | 22 | 33 |
| 00 | 11 | 22 | 33 |

becomes this XYT:

Code: Select all

|    |    | 11 | 33 |
| 00 | 22 | 11 | 33 |
| 00 | 22 |    |    |

Here you can see that the step from I0 to I1 is not like the step from I1 to I2 at all. This case is sort of a product of the above two: we have two fractional V values (0 and 1/2) and two fractional W values (0 and 1/2). All four combinations are there and they get sorted in a particular order but it means the relationships between neighboring I values are jumpy and it's not just a single straight line.

[Sokwe]

Thanks for the responses. You've given me a lot to ruminate on. I'm sure I'll have more questions as I continue experimenting.

\An example rule is B2467/S134568 (Edit: corrected rule), where a width-30 c1-s2s search completes very quickly, but a width-31 search gets to around w_pos 50, at which point the memory usage starts to balloon, and I can't get beyond w_pos 53.

Is this the right combination of rule and result? For me a c/1 s2s search appears to find the known wave forever starting at mid_steps=18.

Oops! I got lost in the length of my own post and "corrected" the correct rule to an incorrect rule that I used elsewhere. The correct rule is 'B26!8/S02567', which I think very likely has a spaceship, but I've been unable to find one at least in part due to memory constraints. I've tried extending partial results (that's how I found a very large photon in B256/S02357), but it can be a bit cumbersome, and I can only extend the few random partial results that I'm shown. I was hoping maybe I could just discard a random bunch of slices and continue the search, but I'm not sure if there would be an elegant way to do that.

Another possibility would be to reduce the width of the search after a certain depth is reached. Sometimes a short middle is only supported by large wings. This is generally how the known ships in B23 rules have been found (find a large outer wing that narrows, then reduce width and look for symmetric or glide-symmetric centers). Of course, reducing the search width during the search might be difficult or nonsensical for LLSSS.

Edit:

Suppose a rule has no p1 photons. If that rule has an extensible p1 wave with a single-sided stabilization, an extensible p1 f2b wick and an extensible p1 b2f wick, does that mean that LLSSS wouldn't be able to prove nonexistence?

Yeah. Specifically I would say that the rule has "almost half planes" at any angle where "almost half plane" has a very specific definition I've given before and is fulfilled both by half lines (as you give above) but also by pyramids and who knows what else. LLSSS arbitrary width searches will extend any "almost half plane" forever and so be unable to terminate. If these things exist for every angle then I don't see how to make current techniques cut it.

I am somewhat interested in the existence of such a case. I of course knew it was hypothetically possible but am at least a little surprised to find one. If there is no finite photon then the way in which that is true is very weird.

As another example, I'm fairly sure that B25/S13457 and B25/S134578 have no p1 photons, but it probably has almost half planes at all angles. A side-to-side search quickly gives a growing pyramid and absolutely nothing else, so it seems like there couldn't possibly be a solution. However f2b-like searches run into a simple wickstretcher, and b2f-like searches seem to either run into the s2s pyramid or an even simpler b2f pyramid.

Because the side-to-side pyramid is built so quickly, I imagine that there is some sort of local restriction that forces the pyramid to continue. It could possibly be proven that the pyramid is forced in an arbitrary-width s2s search, but it might be difficult.

[amling]

Thanks for the responses. You've given me a lot to ruminate on. I'm sure I'll have more questions as I continue experimenting.

This entire lattice business almost didn't happen. All named geometries either use U=X, W=Y (anything "s2s", diagonal, or knightship) or have U=X, and W a fraction of Y (mod V) and so can be treated that way in input files anyway. I knew that would be true before I started but the arbitrary geometries had helped a few victories in LGOL (especially allowing arbitrary vector doubly-periodic searches to look for greyship edges at specific offsets) so I kept it. Here in LLSSS there are no doubly-periodic searches but there have still been a few times it has helped (specifically U=T for floating alignment, and U=X+kT for exhaustive searches in the presence of some almost half planes).

Generally the codebase has been moving in the direction of hiding its existence where possible (e.g. inventing named geometries so you can let the code pick W and pretend it's all X/Y grids anyway) and so this is all uncommon ground you're digging in with "raw" geometries.

This is all to say sorry this part of the tool as confusing and weird as it is and thanks for helping test it and work through its issues. And thank you for your work on this thread (and threads like it) in general. There have been a lot of good ideas come out and I am grateful both for the feature increases and for the tiny, tiny steps towards easier (or at least less difficult) usability.

Oops! I got lost in the length of my own post and "corrected" the correct rule to an incorrect rule that I used elsewhere. The correct rule is 'B26!8/S02567', which I think very likely has a spaceship, but I've been unable to find one at least in part due to memory constraints

It is of course not helpful in general but I'll run s2s to 60 GB real quick and see if something shows up.

I can only extend the few random partial results that I'm shown

It's probably worth mentioning explicitly that by "random partials" I don't really mean (just) the "random" partials view. I mean I would configure seam ripper V2 (`--partials srv2` or `--partials srv2:4:8`) and skim those partials (well, I'd probably skim the actual random view as well). Especially the "choke width" ones which are the thinnest "at the bottom" (where what "bottom" counts is defined by the two specified W positions, see release notes way, way up thread if you want to know horrible details). Especially finding the thinnest that were found over the entire search.

Srv2 can be expensive (I've easily seen it take more than 50% of total search time) but I find it's worth it on most search projects. I of course wouldn't include it on searches I expect to produce a negative result.

I've tried extending partial results (that's how I found a very large photon in B256/S02357), but it can be a bit cumbersome, and I can only extend the few random partial results that I'm shown. I was hoping maybe I could just discard a random bunch of slices and continue the search, but I'm not sure if there would be an elegant way to do that.

I had had some very, very prototypical ideas about automatically "choking" down searches when the memory ceiling was believed to be near. Unfortunately nothing ever worked out.

One problem is the memory ceiling detection is a nightmare. I have no way to tell that the next expand step is going to hit the configured `ulimit` (or even a hypothetical configured limit on internal view of memory) to decide to reduce first. Instead I started working on guessing right before the most memory expensive part of the expand step ("reify"). This means any potential reduction algorithm has to work on the weird partly-expanded state which is unfortunate but it's only code.

The real problem though is deciding what to reduce. I was working on a fixed board search implementation and decided we'd pick some as-of-yet-not-uniquely-determined cell, do some hand-waving math to estimate which value was more common (live or dead), and then filter the search to that value. We'd of course repeat until we thought we had filtered enough to survive the rest of the expand step.

This is all written and shipped as `--pre-reify-autochoke[-type]` and despite verifying/believing it works as intended, I've never really used it. It seemed like it was going to be a pain figuring out what internal memory limit corresponded to external `ulimit` although I would probably try to fight that estimating fight if I thought it was the only problem.

The real problem is that none of this really makes sense for recentering and the vast majority of my searches these days are recentering. Recentering has a "unique" partial view and so could reasonably compute or limit by cell values, but only in those columns, and searches tend to wander left/right (the whole point of recentering). In the end I could not figure out a way to do it and didn't think implementing a version only capable of choking on cell values in the "u" columns was worth it. Note that in from zero WAO searches there are no "u" columns and so none of this applies, at all. You could maybe instead write (with wildcards) a more explicit version of WAO and make some "u" columns that way? E.g. for c/1 searches I think something like...

Code: Select all

| LLLuuuuuRRRRR |
| ............. |
| ............. |
| .....*WWWWW.. |

...would enable it to choke down on cell values in the five columns centered around the topmost, leftmost on cell.

I never convinced myself it was worth doing all the work (rebuilding all the autochoke stuff for recentering, then running searches with "u"-unrolled inputs and fighting the fight to figure out the relationship between internal and external memory limits), but I guess I'll try to think about it some more...

Another possibility would be to reduce the width of the search after a certain depth is reached. Sometimes a short middle is only supported by large wings. This is generally how the known ships in B23 rules have been found (find a large outer wing that narrows, then reduce width and look for symmetric or glide-symmetric centers). Of course, reducing the search width during the search might be difficult or nonsensical for LLSSS.

From a code perspective this is borderline trivial and there is no reason expand's mid_steps has to be the same at every W position other than that's just what it has been historically. The only problem is figuring out how to best convey human will, through commandline arguments, all the way down into the expand step code. Unfortunately it's sort of a big problem.

Do you have a notion of how you'd like to determine/specify mid_steps, even forgetting how we would encode it on the commandline? Like are you thinking you'd say something like "31 until w_pos 50, then 30"? Or something more automatic like "31 until internal memory hits 4 GB, then 30"?

At the risk of anchoring the brainstorming maybe we'd want to just let you run arbitrary code in some dynamic language that can be embedded in rust and make available enough APIs to read the relevant data and reach into the expand step and change mid_steps according to whatever logic you want? This is pleasingly general although I'm a little unsure about what language to embed, how to make mutating steps possible dynamically, etc.

It occurs to me now that reducing mid_steps dynamically during expand based on estimated memory is probably possible. There is no analog of reducing mid_steps in fixed board so I hadn't thought if it when I was writing the autochoke stuff. I will also think more on this idea specifically... The worst problem is probably that I'm not sure we'd be able to salvage anything so if we decided we had a memory problem right before reify we'd have to toss everything we had done and start the expand step over from scratch with mid_steps reduced one. Even so a slow search is better then no search. We might be cooking something here.

I am somewhat interested in the existence of such a case. I of course knew it was hypothetically possible but am at least a little surprised to find one. If there is no finite photon then the way in which that is true is very weird.

I ran B2467/S134568 searches f2b, s2s, and b2f to 60 GB and the resulting partials are crazy. I guess I agree that there is unlikely to be a finite photon, but the grammar of parts that can be stitched together to make almost half planes seems actually rather complicated, e.g. here is a random partial from near the end of f2b:

Code: Select all

x = 185, y = 48, rule = B2467/S134568History
F.181B.F$F.181B.F$F.166B2A13B.F$F.13B2A139B2A9BA2BA12B.F$F.12BA2BA9B
2A10B2A8B2A8B2A8B2A8B2A8B2A8B2A8B2A8B2A8B2A8B2A14BA2BA7BA4BA11B.F$F.
11BA4BA7BA2BA8BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6B
A2BA6BA2BA12BA4BA7B4A12B.F$F.12B4A7BA4BA6BA4BA4BA4BA4BA4BA4BA4BA4BA4B
A4BA4BA4BA4BA4BA4BA4BA4BA4BA4BA4BA4BA12B4A6BA6BA10B.F$F.10BA6BA6B4A8B
4A6B4A6B4A6B4A6B4A6B4A6B4A6B4A6B4A6B4A6B4A11BA6BA6B4A12B.F$F.12B4A6BA
6BA4BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA
11B4A4B4A4B4A8B.F$F.8B4A4B4A4B4A8B4A6B4A6B4A6B4A6B4A6B4A6B4A6B4A6B4A
6B4A6B4A13B3A2BABA12BA7B.F$F.7BA12BABA2B3A4B4A4B6A4B6A4B6A4B6A4B6A4B
6A4B6A4B6A4B6A4B6A4B4A9B3AB3A5BA2BA5BA6B.F$F.6BA5BA2BA5B3AB3A3BA112BA
4B2A2BABAB3A12BA2BA5B.F$F.5BA2BA12B3ABABA2BA5BA2BA6BA2BA6BA2BA6BA2BA
6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA6BA2BA5BA2BA2BA5B3A14B4A3B.F$F.3B
4A14B3A5BA2BA112B7A3BABABA2B2A4B2A4B3A4B.F$F.4B3A4B2A4B2A2BABABA3B2A
114B7A9BA2BA2BA2BA3BABABA2B.F$F.2BABABA3BA2BA2BA2BA9B2A114B7A5BA3B12A
8B.F$F.8B12A3BA5B2A114B7A9B12A3BA4B.F$F.4BA3B12A9B2A19B2A77B2A14B7A9B
12A8B.F$F.8B12A9B2A18BA2BA9B2A10B2A8B2A8B2A8B2A11B2A9BA2BA13B7A9B12A
8B.F$F.8B12A9B2A17BA4BA7BA2BA8BA2BA6BA2BA6BA2BA6BA2BA9BA2BA7BA4BA12B
7A9B12A8B.F$F.8B12A9B2A18B4A7BA4BA6BA4BA4BA4BA4BA4BA4BA4BA7BA4BA7B4A
13B7A9B12A8B.F$F.8B12A9B2A16BA6BA6B4A8B4A6B4A6B4A6B4A9B4A6BA6BA11B7A
9B12A8B.F$F.8B12A9B2A18B4A6BA6BA4BA6BA2BA6BA2BA6BA2BA6BA5BA6BA6B4A13B
7A9B12A8B.F$F.8B12A9B2A14B4A4B4A4B4A8B4A6B4A6B4A6B4A9B4A4B4A4B4A9B7A
9B12A8B.F$F.8B12A9B2A13BA12BABA2B3A4B4A4B6A4B6A4B6A4B4A5B3A2BABA12BA
8B7A9B12A8B.F$F.8B12A9B2A12BA5BA2BA5B3AB3A3BA42BA4B3AB3A5BA2BA5BA7B7A
9B12A8B.F$F.8B12A9B2A11BA2BA12B3ABABA2BA5BA2BA6BA2BA6BA2BA6BA2BA5BA3B
ABAB3A12BA2BA6B7A9B12A8B.F$F.8B12A9B2A9B4A14B3A5BA2BA42B3A5B3A14B4A4B
7A9B12A8B.F$F.8B12A9B2A10B3A4B2A4B2A2BABABA3B2A44B3A3BABABA2B2A4B2A4B
3A5B7A9B12A8B.F$F.8B12A9B2A8BABABA3BA2BA2BA2BA9B2A44B3A9BA2BA2BA2BA3B
ABABA3B7A9B12A8B.F$F.8B12A9B2A14B12A3BA5B2A44B3A5BA3B12A9B7A9B12A8B.F
$F.8B12A9B2A10BA3B12A9B2A44B3A9B12A3BA5B7A9B12A8B.F$F.8B12A9B2A14B12A
9B2A28B2A14B3A9B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A27BA2BA13B3A9B
12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A26BA4BA12B3A9B12A9B7A9B12A8B.F$
F.8B12A9B2A14B12A9B2A27B4A13B3A9B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B
2A25BA6BA11B3A9B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A27B4A13B3A9B12A
9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A16B2A5B4A4B4A9B3A9B12A9B7A9B12A8B.
F$F.8B12A9B2A14B12A9B2A15BA2BA3BA12BA8B3A9B12A9B7A9B12A8B.F$F.8B12A9B
2A14B12A9B2A14BA4BA3BABA4BA5BA7B3A9B12A9B7A9B12A8B.F$F.8B12A9B2A14B
12A9B2A12B4ABA2BAB2A12B3A5B3A9B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A
13B3A3B2A15B2A6B3A9B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A11BABABABA
5B3A10B2ABA4BABA2B2A5B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A19B2ABA3B
A9B2ABAB2A5BA2BA4B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A13BA3BA2B2A5B
A8B2A2BA2B3AB2ABA5B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A10B2ABAB4AB
2A5B3A6B2AB7A5B3A2B12A9B7A9B12A8B.F$F.8B12A9B2A14B12A9B2A11B3AB4AB2A
4B3A7B2AB5ABAB2A2B2A3B12A9BABABABA9B12A8B.F!

I struggle to even imagine how a general program to try to prove no finite photons in such a case might operate.

[amling]

...maybe we'd want to just let you run arbitrary code in some dynamic language that can be embedded in rust...

The more I think about it the more I like this idea. Then instead of having to implement "zero_and_halt" I'd probably have done something like let you react to logged lines and let you mark the search to halt. Then people can implement whatever specific logic they want without needing an LLSSS code change or even a recompile.

[amling]

Oops! I got lost in the length of my own post and "corrected" the correct rule to an incorrect rule that I used elsewhere. The correct rule is 'B26!8/S02567', which I think very likely has a spaceship, but I've been unable to find one at least in part due to memory constraints

It is of course not helpful in general but I'll run s2s to 60 GB real quick and see if something shows up.

...

...seam ripper V2...

It's not done but there is no need to wait. I noticed this in the SRV2 outputs already:

Code: Select all

20241013 10:23:06 [INFO] LlsssMonitorSeamRipperV2(2, 4) (choke width 2):
20241013 10:23:06 [INFO] | .................................................. |
20241013 10:23:06 [INFO] | .................................................. |
20241013 10:23:06 [INFO] | .......................................*.......... |
20241013 10:23:06 [INFO] | ......................................*........... |
20241013 10:23:06 [INFO] | .....................................*.**....*.... |
20241013 10:23:06 [INFO] | .....................................*****..*..... |
20241013 10:23:06 [INFO] | .......................................*.*.*.**... |
20241013 10:23:06 [INFO] | ...................................*.**..*******.. |
20241013 10:23:06 [INFO] | ..................................*...*********... |
20241013 10:23:06 [INFO] | .................................*.*******........ |
20241013 10:23:06 [INFO] | .................................******.....**.... |
20241013 10:23:06 [INFO] | ................*..................*.....**..**... |
20241013 10:23:06 [INFO] | ..............*..******************...**..****.... |
20241013 10:23:06 [INFO] | .......*......*....................**..******..... |
20241013 10:23:06 [INFO] | ......*.........**...............*********........ |
20241013 10:23:06 [INFO] | .....*.**........**..............*.*****....**.... |
20241013 10:23:06 [INFO] | .....*************................*......**..**... |
20241013 10:23:06 [INFO] | .......**********.....*............*.**...****.... |
20241013 10:23:06 [INFO] | ......**.............*................*******..... |
20241013 10:23:06 [INFO] | ....*...........**..*.*********************....... |
20241013 10:23:06 [INFO] | ..*..**........*....*******************.....**.... |
20241013 10:23:06 [INFO] | ..*............**.....*.................**...**... |
20241013 10:23:06 [INFO] | ....**...........*****...........**.**...*****.... |
20241013 10:23:06 [INFO] | .....*****************..........*....********..... |
20241013 10:23:06 [INFO] | ...***************...*.........*.*********........ |
20241013 10:23:06 [INFO] | ...*.**.............**.........*******......**.... |
20241013 10:23:06 [INFO] | ....*...........***...*..........*.*.....*.*...... |
20241013 10:23:06 [INFO] | .....*.........*....************.*..*...*....**... |
20241013 10:23:06 [INFO] | .........*....*.**...*************.....*.*....**.. |
20241013 10:23:06 [INFO] | ........*.....********........****.....********... |
20241013 10:23:06 [INFO] | .......*.**.....*****.....*.**....*......*****.... |
20241013 10:23:06 [INFO] | .......********.*.*......*...*..********.*.*...... |
20241013 10:23:06 [INFO] | .........********..*....*.****..*.********..*..... |
20241013 10:23:06 [INFO] | ........**....**........******...*..**.***........ |
20241013 10:23:06 [INFO] | ......*.....**............**.*....**...*.*........ |
20241013 10:23:06 [INFO] | ....*..**...*...**********...*......****..*....... |
20241013 10:23:06 [INFO] | ....*........*.*..........*************........... |
20241013 10:23:06 [INFO] | ......**................************.............. |
20241013 10:23:06 [INFO] | .......*******......*...*.**..........**.......... |
20241013 10:23:06 [INFO] | .....**********....*.....*.........*.*............ |
20241013 10:23:06 [INFO] | .....*.**.....**..*.**....*.......*....**......... |
20241013 10:23:06 [INFO] | ......*......**...*****..........*.*....**........ |
20241013 10:23:06 [INFO] | .......*...*........**...........********......... |
20241013 10:23:06 [INFO] | ...........*..******...............*****.......... |
20241013 10:23:06 [INFO] | .............*......***************............... |
20241013 10:23:06 [INFO] | ..................*****************..**........... |
20241013 10:23:06 [INFO] | ..................*.**.............*..**.......... |
20241013 10:23:06 [INFO] | ...................*.............******........... |
20241013 10:23:06 [INFO] | ....................*............*.***............ |
20241013 10:23:06 [INFO] | ..................................*............... |
20241013 10:23:06 [INFO] | ...................................**............. |
20241013 10:23:06 [INFO] | .................................................. |
20241013 10:23:06 [INFO] | ....................................**............ |
20241013 10:23:06 [INFO] | ...................................*.............. |

Code: Select all

#C [[ TRACK 0 -1 ]]
x = 99, y = 47, rule = B26/S02567
79b2o$18b2o55b2o$22b2o40b2o8bobobo2bo$17bo2bobobo8b2o25b2o11bob4obo3b
2o$13b2o3bob4obo11b2o20bobobo2bo8b3o2bobobobo$12bobobobo2b3o8bo2bobobo
18bob4obo3b2o5b2o4b4obo$11bob4o4b2o5b2o3bob4obo19b3o2bobobobo4b2o5b3o$
13b3o5b2o4bobobobo2b3o22b2o4b4obo3b2o5b2o$14b2o5b2o3bob4o4b2o23b2o5b3o
5b2o5b2o$14b2o5b2o5b3o5b2o19b2o2b2o5b2o6b2o5b2o$14b2o5b2o6b2o5b2o2b2o
19b2o2b2ob2o6b2o5b2o$14b2o5b2o6b2ob2o2b2o18bo2bob2obobob2o6b2o5b2o$14b
2o5b2o6b2obobob2obo2bo14bob3o5b3ob2o3b2o5b2o2b2o$10b2o2b2o5b2o3b2ob3o
5b3obo15bo2bo3bo2b2o2bobo2b2ob2o2b2o$14b2o2b2ob2o2bobo2b2o2bo3bo2bo15b
o7bo2b5obob2obobob2obo2bo$9bo2bob2obobob2obob5o2bo7bo15bo7bo4b3obob3o
2bo2b3obo$10bob3o2bo2b3obob3o4bo7bo12b2obob2o4bo3b3o2bo2b2o6bo2bo$10bo
2bo6b2o2bo2b3o3bo4b2obob2o8bobobobobo3bo2bob2o5b2o9bo$10bo9b2o5b2obo2b
o3bobobobobo6bob3ob3obo2bo4b2obobob2ob2o6bo$10bo6b2ob2obobob2o4bo2bob
3ob3obo7b3ob3o4bo5b3ob4obobo5bo$10bo5bobob4ob3o5bo4b3ob3o10b2o2bo5bo6b
3o4b3obo4bo$10bo4bob3o4b3o6bo5bo2b2o11b2o8bo6b2o6b2o6bo$10bo6b2o6b2o6b
o8b2o11b2o5b2obob2o3b2o6b2o6bo$10bo6b2o6b2o3b2obob2o5b2o11b2o4bobobobo
bo2b2o6b2o6bo$10bo6b2o6b2o2bobobobobo4b2o11b2o3bob3ob3obob2o6b2o6bo$
10bo6b2o6b2obob3ob3obo3b2o11b2o5b3ob3o3b2o6b2o6bo$10bo6b2o6b2o3b3ob3o
5b2o11b2o6b2o2b2obob2o6b2o6bo$10bo6b2o6b2obob2o2b2o6b2o11b2o6b8ob2o6b
2o6bo$10bo6b2o6b2ob8o6b2o11b2o6b2o6b3o6b2o6bo$10bo6b2o6b3o6b2o6b2o11b
2o6b2o6b3ob2o3b2o6bo$10bo6b2o3b2ob3o6b2o6b2o11b2o6b2o3b2ob2o2bobo2b2o
6bo$10bo6b2o2bobo2b2ob2o3b2o6b2o8b2ob2ob2o3b2o2bobob6obob2o3b2obob2o$
7b2obob2o3b2obob6obobo2b2o3b2ob2ob2o4bobob2obobo2b2obob3o4b2obob2o2bob
obobobo$6bobobobobo2b2obob2o4b3obob2o2bobob2obobo2bob3o2b3obob2obob2o
4b3o3b2obob3ob3obo$5bob3ob3obob2o3b3o4b2obob2obob3o2b3obobob2o3b2o5b2o
b3o3bob2obob2o3b3o2b2o$7b2o2b3o3b2obob2obo3b3ob2o5b2o3b2obo3b2obob2o2b
o2b2ob3o5b4ob2obob2o3b2obob2o$2b2obob2o3b2obob2ob4o5b3ob2o2bo2b2obob2o
6b3ob2o3bob2o2b2o6b2o2b4ob2obob4obobo$bobob4obob2ob4o2b2o6b2o2b2obo3b
2ob3o8bo2b2obobo2b5ob2o3b2o3b2o2b4o2b2ob3obo$ob3ob2o2b4o2b2o3b2o3b2ob
5o2bobob2o2bo13b3o6b2o2bobo2b2obob2o3b2o3b2o2b2o$2b2o2b2o3b2o3b2obob2o
2bobo2b2o6b3o18bo6b7obob4ob2obob2obob5o$3b5obob2obob2ob4obob7o6bo25bo
4b2o5b2o2b4o2b3o2b2o$5b2o2b3o2b4o2b2o5b2o4bo35b3o2bo2b2o3b2o3b2o3b3o$
4b3o3b2o3b2o3b2o2bo2b3o38bob2o3bob2obob2obob2obob2obo$3bob2obob2obob2o
bob2obo3b2obo39b2obobo2b3o2b3o2b3ob3obo$2bob3ob3o2b3o2b3o2bobob2o42b3o
5bo4bo4bo2b3o$4b3o2bo4bo4bo5b3o44bo20bo$5bo20bo!

Out of curiosity, how much memory do you have? At the time this was output VmPeak was 7.2 GB.

Hopefully this helps make my case about SRV2 being useful.

I also wonder if I should be hacking up some sort of skew gutter end to catch this sort of thing explicitly. I guess I don't use the odd and even ends much myself, often waiting it out or spotting the partial by hand. Of course I have no idea what I might be missing.

[Sokwe]

Thanks! That's a lot more to think about. I hope I'm not being too bothersome with all of my questions.

Out of curiosity, how much memory do you have? At the time this was output VmPeak was 7.2 GB.

I only have about 5 GB free on my craptop, unfortunately.

Do you have a notion of how you'd like to determine/specify mid_steps, even forgetting how we would encode it on the commandline? Like are you thinking you'd say something like "31 until w_pos 50, then 30"? Or something more automatic like "31 until internal memory hits 4 GB, then 30"?

When I made the suggestion I was thinking the former: reduce width at a specified w_pos.

It's probably worth mentioning explicitly that by "random partials" I don't really mean (just) the "random" partials view. I mean I would configure seam ripper V2 (`--partials srv2` or `--partials srv2:4:8`) and skim those partials (well, I'd probably skim the actual random view as well). Especially the "choke width" ones which are the thinnest "at the bottom" (where what "bottom" counts is defined by the two specified W positions, see release notes way, way up thread if you want to know horrible details). Especially finding the thinnest that were found over the entire search.

I'll have to look into this, but it sounds promising. I always thought I might be too ignorant for the seam ripper, but I'll give it a try when I have some time. What is the difference between `--partials srv2` and `--partials srv2:4:8`?

I also wonder if I should be hacking up some sort of skew gutter end to catch this sort of thing explicitly. I guess I don't use the odd and even ends much myself, often waiting it out or spotting the partial by hand. Of course I have no idea what I might be missing.

This could potentially be useful in some cases, as long as it's not too difficult to implement. In Life-like B2 rules, only a 1-cell skew makes sense (and only if certain birth conditions like B2k do not occur along the gutter), but in some INT rules, a skew of 2 cells might make sense, while skews of 1 cell or 0 cells do not. For example, here is a 2-cell skew ship that doesn't work at 1 cell or 0 cells:

Code: Select all

#C Skew-2 ship
x = 13, y = 9, rule = B2ce3aijn4aijrt5ijnqy6a/S3-cr
10bo$9bo$2bo4bob2obo$3bo5b2obo$ob2obo6bo$ob2o5bo2bo$o7b3o$o2bo$2b3o!

I noticed this in the SRV2 outputs already

Nice! Was this from a width-31 search? Can you show me what your command line input was?

[amling]

...seam ripper V2...

I'll have to look into this, but it sounds promising. I always thought I might be too ignorant for the seam ripper, but I'll give it a try when I have some time. What is the difference between `--partials srv2` and `--partials srv2:4:8`?

Those are the amounts (measured in W) that define the lookback window it examines partials in. I dug up the only place I seem to have ever explained this long ago, right after I had written it and I'm not sure its inclusion in `--partials` was ever documented in any sense (or indeed `--partials` existence altogether as this is the only meaningful option for it right now). As it is `--partials srv2:4:8` is lookbacks of 4 and 8 (W rows). The default `--partials srv2` is "one W overlap" to "two W overlaps" where "one W overlap" is the completely geometry-generalized equivalent of what we would think of as 2 Y rows. Unless you get bad results I would just stick with that default.

For completion in case it's not obvious: every W row it runs and shows a partial which has the thinnest possible connection in that window. It will also try to find a split with two branches in that window, and if the thicker of the two is strictly thinner than the thinnest single connection it will show the split (so at some depths you might see no split).

...skew gutter end...

This could potentially be useful in some cases, as long as it's not too difficult to implement. In Life-like B2 rules, only a 1-cell skew makes sense (and only if certain birth conditions like B2k do not occur along the gutter), but in some INT rules, a skew of 2 cells might make sense, while skews of 1 cell or 0 cells do not.

I would almost certainly not worry about any of that in the implementation and just require the user to specify the skew(s) they want checked.

I noticed this in the SRV2 outputs already

Nice! Was this from a width-31 search? Can you show me what your command line input was?

Yes, I believe this was:

Code: Select all

rlife llsss-recentering-wao c1-s2s --rule 'B26!8/S02567' s2s.in 00 --wao-left-pad 00 --wao-right-pad 00 --wao-idx ALL --ends zero,odd,even --partials srv2,srv2:4:8 31

I frequently run both the srv2 defaults and a second copy with twice the lookback (in this case srv2:4:8). Sometimes it's interesting to see what results you get instead if you're much more pessimistic about what counts as a thin connection (requiring the thinness to last twice as long and the partial to be extended twice as long after it).

[Sokwe]

Can you tell me why I get an explicit panic when running the following at around w_pos 76?

Code: Select all

rlife llsss-recentering-wao --wao-left-pad 00 --wao-right-pad 00 --ends zero,odd,even --wao-idx ALL --partials srv2 --rule 'B246/S02367' c1-s2s c-f2b.in 70

The error message is the following:

Code: Select all

thread '<unnamed>' panicked at src/llsss/recentering.rs:844:35:
explicit panic

It seems to be related to "--partials srv2", because it doesn't happen when that option isn't included.

Edit: another error message question. Why do I get this error

Code: Select all

thread 'main' panicked at src/llsss/init.rs:96:9:
assertion failed: w_size * geom.udet <= TB::VB::SIZE

when running

Code: Select all

rlife llsss-recentering --ends zero,odd,even --rule 'B2478/S013678' c1-s2s partial.in 35

where partial.in is

Code: Select all

| zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz |
| ........................................... |
| ........................................... |
| ...................*....................... |
| ................*..**...................... |
| ...............*.**........................ |
| ...............*..**....................... |
| ..............***.......................... |
| .............*....*........................ |
| ............*....**.*...................... |
| ............*...*...**..................... |
| .....*...*...*..*.*..**.....*.............. |
| ....*.****.**....*.*.....*..**............. |
| ...*..*....**......*..*.*.**............... |
| ...*..**.*...*.....*..**..*.***............ |
| ....*.*.**..*.....****..*....*............. |
| ..**..*********..*......*...*.**........... |
| ..**..*.********..*****.*..*..*............ |
| ....*.**********...*..*..*..*.............. |
| ...*..*.*****..*...*......*.*.............. |
| ...*..***.*..******..**.**..*.............. |
| ....*.*.**..*.....***.*.**..*...*.......... |
| ..**..****...**.**********...*..**......... |
| ..**..*.**....*.********.*....**........... |
| ....*.***.*...********..*****.*.***........ |
| ...*..*.****...**..*..*.....*....*......... |
| ...*..*******.*.*...*..*........*.......... |
| ....*.*.******....**..***.......*.......... |
| ..**..***.****..**.***.......*...*......... |
| ..**..*.******..********.....**.***........ |
| ....*.*******..**********.....**........... |
| ...*..*.****....********.****...**......... |
| ...*..***.*.....**..***...*..*..*.......... |
| ....*.*.**........***....*..*.............. |
| ..**..****.......*...***..*.*.............. |
| ..**..*.**......*....*..*.*..*............. |
| ....*.****......*......*..*.***............ |
| ...*..*.**.......*......*..*......*........ |
| ...*..****.....**........*.***....**....... |
| ....*.*.**.....****.......*...****......... |
| ..**..****....******..........*..**........ |
| ..**..*.**....*.*****........**.......*.... |
| ....*.****...**.*****.*.....*...****..**... |
| ...*..*.**..*.....*..*.*********.*..**..... |
| ...*..***.*..******.*.*..*.....***..*.***.. |
| ....*.*.*****..*....*.....**.*****.....*... |
| ..**..**********...*.......*.*****....*.... |
| ..**..*.********...*.......*******....*.... |
| ....*.***.****..*...*..*....**.*.*..*.*.... |
| ...*..*.***..*.*.....***.*.*.*.******..*... |
| ...*..*****....*...**....**.....*******.... |
| ....*.*.***....*...***.*..****..*******.... |
| ..**..***.*..*.*..*****.*....*.********.... |
| ..**..*.******..*..****..*.....*.****..*... |
| ....*.**********..*.*.***......***..*.*.... |
| ...*..*.**********...****.......**....*.... |
| ...*..************..*****.......**....*.... |
| ....*.*.******.*..*..****.........*....*... |
| ..**..***..*.*.*..*..****........*...**.... |
| ..**..*.*...******..*****........*...**.... |
| ....*.**.*.*******...****.........*....*... |
| ...*..*.*...**.***...****.......**....*.... |
| ...*..***..*.*.***..*****.......**....*.... |
| ....*.*.**********..*.***...*.....*....*... |
| ..**..***********..**.***...**...*...**.... |
| ..**..*.*******..**.....*....**..*...**.... |
| ....*.*******..*..**********......*....*... |
| ...*..*.***..*..*....*.....*..*.**....*.... |
| ...*..***.*..*...*....**.******.**....*.... |
| ....*.*.*****..**......*.*********.....*... |
| ..**..*********.***....***********..*.***.. |
| ..**..*.***.********....****.***.*..**..... |
| ....*.***.*.*********...**..**..****..**... |
| ...*..*.********.*.***....*...*.......*.... |
| ...*..********.*.*.****.*..*..*..**........ |
| ....*.*.***..*.*********.*.*.*****......... |
| ..**..***.*.....*******..*..*.....**....... |
| ..**..*.***....*.*.*..*.*.........*........ |
| ....*.*****...*...**....*.................. |
| ...*..*.***...*..***....*.................. |

[amling]

Can you tell me why I get an explicit panic when running the following at around w_pos 76?

Code: Select all

rlife llsss-recentering-wao --wao-left-pad 00 --wao-right-pad 00 --ends zero,odd,even --wao-idx ALL --partials srv2 --rule 'B246/S02367' c1-s2s c-f2b.in 70

The error message is the following:

Code: Select all

thread '<unnamed>' panicked at src/llsss/recentering.rs:844:35:
explicit panic

It seems to be related to "--partials srv2", because it doesn't happen when that option isn't included.

I'm not positive due to line numbers changing between versions but that is almost certainly what I am also hitting locally occasionally and is due to having tried to cut a corner and save some memory. It's complicated to describe exactly but I assumed I could store a number bounded approximately by the widths of relevant partials in a u8 (8 bits so max 256). My current belief/understanding is that wraps around and all hell breaks loose.

At the time I wrote it a meaningful partial 256 wide was unlikely but for very low period searches it's now happening. I've pushed 6602371f6597 and 83272859afab just now which will fix it if my guess is correct (and surely no one will hit the u16 limit of 65536...). For my part I'm just now waiting for a long, long recompile to restart my own search that hit it.

Edit: another error message question. Why do I get this error

Code: Select all

thread 'main' panicked at src/llsss/init.rs:96:9:
assertion failed: w_size * geom.udet <= TB::VB::SIZE

That is an unfortunate result of my rather lazy implementation of the state initialization code which wants to assume it can store an entire spine of the input in one "VB" scalar. VB by default is u64 so 64 bits and in c1-s2s geometry a spine is just one column of cells.

It's not impossible to fix this, it's just very, very annoying, I run into it so rarely, and it can be fixed so easily in most circumstances by pruning rows off the top until it fits (and this is my official recommendation). If you really want you could replace VB with u128. I believe this will make it run a bit slower and the "spine store" storage take a bit more memory (although spine store memory has never once in all my searches been on my radar as relevant).

EDIT: I should probably make it my policy to put in assertion messages for anything people find that isn't a totally unexpected internal logic error and/or that there is any chance someone could reasonably hit (again). Accordingly I have done nothing about the u8 problem (now a u16 problem) but have put in an actual message for the "Initialization grid too tall" case.

EDIT2: I've realized that input file has more problems. You've only got 2 columns of zeros on the side and so you've actually fixed the edges right there. If you want it to actually be able to extend left/right you need 3 columns. Also with all "z" roots it's going to be able to skip the middle pattern either way.

If I'm extending a partial with recentering my inputs usually look something like...

Code: Select all

| LLLuuuuuRRR |
| ...*.*.*... |
| ....*.*.... |
| ...*.*.*... |
| ....*.*.... |

...with 3 columns of "L" zeros on the left, all pattern columns tagged uniquely ("u" is special and tagged with U coordinate so they're all unique), and 3 columns of "R" zeros on the right. This way partials must pass through LL -> LL transitions some number of times, then LL -> Lu, then Lu -> uu, then a few more uu -> uu (but a fixed number), then uu -> uR, then uR -> RR, then RR -> RR some number of times.

EDIT3: I looked back over the code that "too tall" assert was guarding and the bulk of it is actually fine (I guess I rewrote it to do the difficult thing somewhere in there). The only remaining assumption on VB is the code that runs CA checks on inputs. This is more relevant for when you've got a bunch of wildcards in there and you want them stripped down on init since later CA checks won't cover it. I'm going to leave it on by default but I've pushed a change so you could set LLSSS_INIT_CA_CHECKS=false to skip these checks (and thus that assert).

[amling]

Do you have a notion of how you'd like to determine/specify mid_steps, even forgetting how we would encode it on the commandline? Like are you thinking you'd say something like "31 until w_pos 50, then 30"? Or something more automatic like "31 until internal memory hits 4 GB, then 30"?

When I made the suggestion I was thinking the former: reduce width at a specified w_pos.

It has occurred to me that you can already sort of fake this with saved state. These states, saved either by manual intervention with rctl or automatically by `--state-file`, can be resumed in a differently configured search (ditto `--state-file` to load state instead of doing normal state init). This is not maybe always a great or safe idea but if all you've changed between the searches is mid_steps it should do the right thing.

If you want to reduce the width right before it hits a memory limit and dies you're presumably good to go (since last checkpoint before crash will be where you want it). If you want to stop at a specific w_pos you could use the recently added `--halts w_pos:NN`.

[amling]

...maybe we'd want to just let you run arbitrary code in some dynamic language that can be embedded in rust...

The more I think about it the more I like this idea. Then instead of having to implement "zero_and_halt" I'd probably have done something like let you react to logged lines and let you mark the search to halt. Then people can implement whatever specific logic they want without needing an LLSSS code change or even a recompile.

So here's what I'm thinking, where by "I'm thinking" I mean "I've sketched a functioning prototype of":

I've embedded lua in rust before and so I sort of knew it would work. Unfortunately I think it's a very bad language and I have to google a lot to get anything done but I think it will be serviceable for the level of logic I suspect we're gonna write.

I've instrumented much of the configuration structures to be able to dynamically reflect on them. When the search starts it will dump the configuration so you can easily see what is available:

Code: Select all

20241018 12:24:29 [INFO] Step configuration:
20241018 12:24:29 [INFO]   LlsssMonitorSpineStats:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssMonitorColStats:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssMonitorUniquePartial:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssMonitorShortestPartialRecentering:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssMonitorRandomPartial:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssMonitorRctl:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssStepExpandRecentering:
20241018 12:24:29 [INFO]     mid_steps: 6
20241018 12:24:29 [INFO]   LlsssMonitorSeamRipperV2:
20241018 12:24:29 [INFO]     w_min: 4
20241018 12:24:29 [INFO]     w_max: 8
20241018 12:24:29 [INFO]     include_splits: true
20241018 12:24:29 [INFO]   LlsssMonitorSeamRipperV2_2:
20241018 12:24:29 [INFO]     w_min: 8
20241018 12:24:29 [INFO]     w_max: 16
20241018 12:24:29 [INFO]     include_splits: true
20241018 12:24:29 [INFO]   LlsssEndsZero:
20241018 12:24:29 [INFO]     (nothing)
20241018 12:24:29 [INFO]   LlsssEndsPdLite:
20241018 12:24:29 [INFO]     division[D]: 2
20241018 12:24:29 [INFO]     w_size: 4

So you can see something like "steps.LlsssStepExpandRecentering.mid_steps" can be read/written from lua. If you have multiple copies of the same step configured they may get numeric suffixes and this dump will help make it clear what happened.

Then you set `LLSSS_USER_SCRIPT` to a path to a lua file and write some code that will run at the top of every search loop. In addition to "steps" there is also "state" (although not much API surface there yet) and "gol_log". So you can already do something like...

Code: Select all

if state.w_pos == 6 and state.subtile_pos == 0 then
    gol_log("DEBUG", "Shrinking mid_steps")
    steps.LlsssStepExpandRecentering.mid_steps = 5
end

And then when the search hits w_pos 6 it will log as requested and set mid_steps. You could also do something like...

Code: Select all

if state.subtile_pos == 0 then
    state:save_state("checkpoint-"..state.w_pos..".bin")
end

To save distinct, labelled state files at the beginning of each W position.

Finally, I've added an "events" API where steps can log events and then the collected events since the last user script run will be available in an "events" global for the lua code (I had originally wanted to capture all logged lines but I just don't think it's doable). Coupled with adding a "LlsssHaltPlaceholder" step that holds a boolean and halts the search if it is ever set to true you can halt-on-result, at least for any result logged by "run_ssm_filter_ends":

Code: Select all

for _, e in pairs(events) do
    if e.channel == "run_ssm_filter_ends" then
        gol_log("DEBUG", "Triggering halt")
        steps.LlsssHaltPlaceholder.halt = true
    end
end

I should stress everything above here is written, run, and verified to work as expected so I could ship this now and I believe we would have all the custom behaviors we were thinking of.

Several problems still linger though:

(*) Providing the script sucks. I either have to add options to every distinct command line arguments structure or take it by environment variable. Also having to make a separate file sucks, but I'm not sure how manageable it is to write lua inline as part of the LLSSS command directly.

(*) Performance is tragic. Rust and lua have extremely, extremely different ideas about type systems and ownership models and while my best efforts to make rust data temporarily visible to lua work, they are quite ugly and require more than a few weird copies. I don't think the performance matters on the scale of what we're likely to do with it but I don't really like that part of the code.

(*) Running at the top of each main loop is weird, but I really can't run directly in response to events. Rust is just too picky about ownership. Maybe I could arrange to run after each step, but it just doesn't seem worth the confusion. This mostly means user scripts just need to be aware of their weird lifecycle and planned accordingly.

(*) There is presumably a lot more API surface to expose. Nothing is visible to lua unless I publish it explicitly and while I have done some serious work to make publishing more stuff pretty easy I've only really done the obvious immediate stuff.

My explicit questions for the assembled are mostly: Does this capture what we want to do? Are there any other obvious custom behaviors you want to implement? Are there any other obvious APIs I should add?

[amling]

One of the geometries I've been using is raw:1:1:2:1:0:1:0:-1:0, which I think is functionally equivalent to raw:1:1:0:0:-1:1:0:0:1, but you probably would find it less elegant due to the direction of W. I've mostly used s2s (~3400 rules) and raw:0:1:2:1:0:1:0:0:1 (~2000 rules), but I've had to use a handful of other geometries as well. Here is the full list of geometries I've used:

Code: Select all

f2b
b2f
s2s
raw:0:1:2:1:0:1:0:0:1
raw:0:1:2:1:0:1:0:0:-1
raw:0:1:3:1:0:1:0:0:1
raw:0:2:3:1:0:1:0:1:4
raw:1:1:2:1:0:1:0:1:0
raw:1:1:2:1:0:1:0:-1:0
raw:1:2:2:1:0:1:0:1:0
raw:1:2:2:1:0:1:0:-1:0

Equivalence is a complicated subject. From strongest to weakest:

(1) Swapping X and Y, negating X, and negating Y change only how it is displayed.

(2) Shifting U or W by an integral multiple of V can change the intratile search order at most. For a geometry of tile size one it will have absolutely no effect. For a large tile size and a search of limited (as opposed to unlimited) mid_steps this could change the results ever after a complete W row as it could change the split of left/right expansion and thus what extra recombinations happen (partials whose sizes are arguably above mid_steps in effective width but are found anyway).

(3) Shifting W by an integral multiple of U can change the U neighborhood size. Otherwise sort of similar to (2).

None of these will change what almost half planes do or do not exist so in that sense they are all equivalent.

As for raw:1:1:2:1:0:1:0:-1:0...

(*) Add -2V to U: raw:-1:1:0:1:0:1:0:-1:0.
(*) Negate X: raw:1:1:0:-1:0:1:0:-1:0.
(*) Swap X and Y: raw:1:1:0:0:-1:1:-1:0:0.
(*) Add U to W: raw:1:1:0:0:-1:1:0:1:0.
(*) Add V to W: raw:1:1:0:0:-1:1:0:0:1.

So yeah, they're at least that equivalent.

Really what matters for almost half plane existence is the direction U (mod V) and which of the two directions W points (sign of UVW determinant). I assume the geometries you've cooked up are intended to produce various slopes of U when viewed in the XY plane.

[Sokwe]

I assume the geometries you've cooked up are intended to produce various slopes of U when viewed in the XY plane.

Yes, that's correct. I don't know if there's anything more clever that can be done with LLSSS. I started with sweeps of unsolved rules using s2s searches. When I ran into a block that couldn't be solved with s2s, I would try f2b and b2f. If that didn't work, I would attempt one of the slanted geometries I had already been using. If that still didn't work, I sometimes tried to find new geometries to test. Usually, if there seemed to be a common front or back edge with a particular slope, I would try to construct a geometry with that slope. Some very shallow or very steep slopes seemed to perform poorly, but that may have been a result of a bad choices in the geometry? At any rate, I only managed to eliminate rules with the geometries I provided, and I didn't record what other geometries I haphazardly tried on random rules.

[amling]

...skew gutter end...

This could potentially be useful in some cases, as long as it's not too difficult to implement. In Life-like B2 rules, only a 1-cell skew makes sense (and only if certain birth conditions like B2k do not occur along the gutter), but in some INT rules, a skew of 2 cells might make sense, while skews of 1 cell or 0 cells do not.

Done, e.g. finding skewed MWSS on MWSS both ways with `--ends skew_gutter:2:-2`:

Code: Select all

20241021 11:25:35 [INFO] End [thinnest] ("LlsssEndsSkewGutter", -2):
20241021 11:25:35 [INFO] |  ............ |  ............ | ............  | ............  |
20241021 11:25:35 [INFO] |  ............ |  ............ | ............  | ............  |
20241021 11:25:35 [INFO] |  ............ |  .....*...... | ............  | ............  |
20241021 11:25:35 [INFO] |  ....***..... |  ...*...*.... | ............  | ............  |
20241021 11:25:35 [INFO] |  ...*****.... |  ..*......... | ...**.......  | ..*****.....  |
20241021 11:25:35 [INFO] |  ..**.***.... |  ..*....*.... | ..**.***....  | ..*....*....  |
20241021 11:25:35 [INFO] |  ...**....... |  ..*****..... | ...*****....  | ..*.........  |
20241021 11:25:35 [INFO] |  ............ |  ............ | ....***.....  | ...*...*....  |
20241021 11:25:35 [INFO] |  ............ |  ............ | ............  | ............  |
20241021 11:25:35 [INFO] |  ............ |  ............ | ......***...  | .....*...*..  |
...
20241021 11:25:41 [INFO] End [thinnest] ("LlsssEndsSkewGutter", 2):
20241021 11:25:41 [INFO] |  ........... |  ........... | ...........  | ...........  |
20241021 11:25:41 [INFO] |  ........... |  ........... | ...........  | ...........  |
20241021 11:25:41 [INFO] |  ........... |  ........... | ...........  | ......*....  |
20241021 11:25:41 [INFO] |  ........... |  ........... | .....***...  | ....*...*..  |
20241021 11:25:41 [INFO] |  ....**..... |  ...*****... | ....*****..  | ...*.......  |
20241021 11:25:41 [INFO] |  ...**.***.. |  ...*....*.. | ...**.***..  | ...*....*..  |
20241021 11:25:41 [INFO] |  ....*****.. |  ...*....... | ....**.....  | ...*****...  |
20241021 11:25:41 [INFO] |  .....***... |  ....*...*.. | ...........  | ...........  |
20241021 11:25:41 [INFO] |  ........... |  ........... | ...........  | ...........  |
20241021 11:25:41 [INFO] |  ...***..... |  ..*...*.... | ...........  | ...........  |

Skews must be listed/chosen by user explicitly (and each is run separately as I saw no obvious way to optimize running multiple). Skews must each fit within one "SL2" window, which for normal setups means must be in the range [-2, 2]. Also note that its definition of skew gutter is the "do what I say, not what I mean" one, namely that each cell matches itself across the gutter shifted by the appropriate amount and that's it. In particular, there is nothing to force the two halves of the pattern to be interacting and as an example the search that found the above will go on to spew useless stuff like:

Code: Select all

20241021 11:37:10 [INFO] End [thinnest] ("LlsssEndsSkewGutter", -2):
20241021 11:37:10 [INFO] |  .......... |  .......... | ..........  | ..........  |
20241021 11:37:10 [INFO] |  .......... |  .......... | ..........  | ..........  |
20241021 11:37:10 [INFO] |  .......... |  .......... | ..........  | .....*....  |
20241021 11:37:10 [INFO] |  .......... |  .......... | ....***...  | ...*...*..  |
20241021 11:37:10 [INFO] |  ...**..... |  ..*****... | ...*****..  | ..*.......  |
20241021 11:37:10 [INFO] |  ..**.***.. |  ..*....*.. | ..**.***..  | ..*....*..  |
20241021 11:37:10 [INFO] |  ...*****.. |  ..*....... | ...**.....  | ..*****...  |
20241021 11:37:10 [INFO] |  ....***... |  ...*...*.. | ..........  | ..........  |
20241021 11:37:10 [INFO] |  .......... |  .....*.... | ..........  | ..........  |
20241021 11:37:10 [INFO] |  .......... |  .......... | ..........  | ..........  |
20241021 11:37:10 [INFO] |  .......... |  .......*.. | ..........  | ..........  |

[Sokwe]

I'm now looking at B2568/S134 - B2568/S13478. In these rules, the following chunk seems to force itself to repeat in a c1-f2b search:

Code: Select all

| AAAAAuuuuuuuuuBBBBB |
| ..WWW*..***..*WWW.. |
| ..WWW*..*.*..*WWW.. |

The command line input I used was the following (is this correct?):

Code: Select all

rlife llsss-recentering c1-f2b 1.in --rule 'B2568/S13478' XX

From looking at partial results from an arbitrary-width llsss-recentering-wao c1-f2b search, it seems that this chunk must occur at some point in every partial result, but it doesn't do so in a consistent location relative to the front end, so I wasn't able to use unique cells to determine that it occurs. Is there a way to show that this chunk eventually occurs in every c1-f2b partial in the rules B2568/S1348 and B2568/S13478?

[amling]

It occurs to me now that reducing mid_steps dynamically during expand based on estimated memory is probably possible. There is no analog of reducing mid_steps in fixed board so I hadn't thought if it when I was writing the autochoke stuff. I will also think more on this idea specifically... The worst problem is probably that I'm not sure we'd be able to salvage anything so if we decided we had a memory problem right before reify we'd have to toss everything we had done and start the expand step over from scratch with mid_steps reduced one. Even so a slow search is better then no search. We might be cooking something here.

I sketched this and it's a mixed bag. The implementation details are also complicated:

(*) We compare the provided threshold to an estimate of how big bcol+col will be after reify. This isn't really the amount of memory that program will take at its worst moment, but it should provide some sort of proportional limit.

(*) At each w_pos we restart at the full original value. If we decide we have to reduce unlimited mid_steps we count how many steps it took to exhaust the unlimited case and restart with that. Otherwise we restart with one fewer steps than the last attempt.

To test this I took that c/1 s2s search that had had an interesting partial when VmPeak was at ~7.2 GB. Run with unlimited mid_steps and a 1 MB limit it terminated without finding anything but with a 10 MB limit more interesting stuff happened...

Restarting was expensive and could happen many, many times. The worst was w_pos 27 which choked unlimited to 81 then all the way down to 41 one at a time before finally succeeding. However in total after just a few minutes it did produce:

Code: Select all

20241022 20:26:04 [INFO] End [thinnest] ("LlsssEndsSkewGutter", 1):
20241022 20:26:04 [INFO] | ..................................................... |
20241022 20:26:04 [INFO] | ..................................................... |
20241022 20:26:04 [INFO] | ..........................................*.......... |
20241022 20:26:04 [INFO] | .........................................*........... |
20241022 20:26:04 [INFO] | ........................................*.**......... |
20241022 20:26:04 [INFO] | ........................................*****..*..... |
20241022 20:26:04 [INFO] | ..........................................*.*.*...... |
20241022 20:26:04 [INFO] | ......................................*.**..*****.... |
20241022 20:26:04 [INFO] | .....................................*...*********... |
20241022 20:26:04 [INFO] | ...............................*....*.********...**.. |
20241022 20:26:04 [INFO] | ..............................*.....*******.....**... |
20241022 20:26:04 [INFO] | .............................*.**.....*......**...... |
20241022 20:26:04 [INFO] | ..............*..............********.*...**..***.... |
20241022 20:26:04 [INFO] | .............*...*.............********.*..*******... |
20241022 20:26:04 [INFO] | .......*....*.**..*************..*.*..********...**.. |
20241022 20:26:04 [INFO] | ......*.....****...............*.*...******.....**... |
20241022 20:26:04 [INFO] | .....*.**.....*..**..........*****.....*.....**...... |
20241022 20:26:04 [INFO] | .....********.*...**.........*.***..***...**..***.... |
20241022 20:26:04 [INFO] | .......************...........*....*...**..*******... |
20241022 20:26:04 [INFO] | ......**.....*****.......*.....**....**********..**.. |
20241022 20:26:04 [INFO] | ....*......**...........*.............******....**... |
20241022 20:26:04 [INFO] | ..*..**....*...**......*.**************......*....... |
20241022 20:26:04 [INFO] | ..*.........*.*........***************....*...***.... |
20241022 20:26:04 [INFO] | ....**..........**.......*...............*........... |
20241022 20:26:04 [INFO] | .....********....*******.*..........*...*.******..... |
20241022 20:26:04 [INFO] | ...************************........*....*********.... |
20241022 20:26:04 [INFO] | ...*.**......*****....****........*.**....*.*.**..... |
20241022 20:26:04 [INFO] | ....*.......**.......**...........*******.*..*....... |
20241022 20:26:04 [INFO] | .....*....*......*.*....*...........*******...*...... |
20241022 20:26:04 [INFO] | ........*..**...*...**...*********.**..****.......... |
20241022 20:26:04 [INFO] | ........*.......**....................**..*.......... |
20241022 20:26:04 [INFO] | ..........**......*******......**.**....*.*.*........ |
20241022 20:26:04 [INFO] | ...........***************....*....***********....... |
20241022 20:26:04 [INFO] | .........***********.*...**..*.**************........ |
20241022 20:26:04 [INFO] | .........*.**........*..**...******....*............. |
20241022 20:26:04 [INFO] | ..........*........****........*.....**.....**....... |
20241022 20:26:04 [INFO] | ...........*.......*.**..******...**..*....*......... |
20241022 20:26:04 [INFO] | ....................*...*......**..****...*.***...... |
20241022 20:26:04 [INFO] | .....................*.......**********...******..... |
20241022 20:26:04 [INFO] | .............................*.******.*.....*.*...... |
20241022 20:26:04 [INFO] | ..............................*.......*****.*........ |
20241022 20:26:04 [INFO] | ...............................*....*********........ |
20241022 20:26:04 [INFO] | ....................................*.**..***........ |
20241022 20:26:04 [INFO] | .....................................*...**.*........ |
20241022 20:26:04 [INFO] | ......................................*.....*.*...... |
20241022 20:26:04 [INFO] | ..........................................******..... |
20241022 20:26:04 [INFO] | ..........................................*.***...... |
20241022 20:26:04 [INFO] | ...........................................*......... |
20241022 20:26:04 [INFO] | ............................................**....... |
20241022 20:26:04 [INFO] | ..................................................... |
20241022 20:26:04 [INFO] | ...........................................**........ |

How much memory it used is complicated in that the vast majority of VmPeak is in various overheads. The greatest internal memory estimate was 22.44 MB which shows that the limit can be off a lot even from the internal estimate of all memory at the worst moment, but it's at least in the same order of magnitude.

It's also not quite comparable since this I believe is a different (earlier?) result that the partial I had spotted at 7.2 GB.

[amling]

I'm now looking at B2568/S134 - B2568/S13478. In these rules, the following chunk seems to force itself to repeat in a c1-f2b search:

Code: Select all

| AAAAAuuuuuuuuuBBBBB |
| ..WWW*..***..*WWW.. |
| ..WWW*..*.*..*WWW.. |

The command line input I used was the following (is this correct?):

Code: Select all

rlife llsss-recentering c1-f2b 1.in --rule 'B2568/S13478' XX

From looking at partial results from an arbitrary-width llsss-recentering-wao search, it seems that this chunk must occur at some point in every partial result, but it doesn't do so in a consistent location relative to the front end, so I wasn't able to use unique cells to determine that it occurs. Is there a way to show that this chunk eventually occurs in every c1-f2b partial in the rules B2568/S1348 and B2568/S13478?

I agree that that search shows that that 2x9 chunk forces itself down 2. I had been looking at rules like these earlier and had the same problem though: it didn't seem like that chunk was forced in a specific place from an initial search like:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................*WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW.. |

Another chunk that shows up a lot in unique snapshots and is self-forcing 2 down is:

Code: Select all

*..**.*.
*..*.**.

Now it's possible you could make a constraint file like:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................*WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |

And chip away one bit at a time:

(*) Run that constraint file for a bit, observe forced cells:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................**..WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |

(*) Try a single cell on here:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................**..WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW*WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |

And see a self-forcing chunk in a unique snapshot so conclude it must go the other way in a finite ship:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................**..WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |

(*) Run that for a bit, observe forced cells:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................**..WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW..*..*.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |

etc...

I tried poking around for a bit, trying to guess which cells were important to pivot on or guess more chunks of forced cells that might be self-forcing, but didn't get much farther in the few minutes I gave it:

Code: Select all

| LLLuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuRRRRR |
| ..................................................................... |
| ..................................................................... |
| .................................**....WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW..*..*..WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
| WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW.W**W.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |

If single cell guesses aren't enough you can guess multiples but you have exponentially more cases you need to either rule out or continue on with. The goal of course is ultimately to cobble some tree of choices together where each leaf forces a self-forcing chunk.

EDIT: I tried to poke through single-elimination guesses but couldn't finish it. Eventually I picked a very careful pivot cell and then the two copies with it filled in on and off I was able to complete with single eliminations. I took some notes on the way but it's a mess and a ton of cases and it's very, very error-prone.

The most obvious way to me to try to automate this sort of thing would be to note some self-forcing chunks as we have and then somehow forbid them in searches. Unfortunately the only way I can see to do this requires making SL2s wide enough to cover them. The two types of self-forcing chunks that I used mostly (and might suffice) were 2x9 and 2x8 but unfortunately complex technical reasons make SL2 wider than 7 not really possible.

Maybe I could undo the changes that caused this limit. They are definitely materially faster for normal searches so this would be on a hacked copy of the code just for this project. I guess I shall think some more on it...

[Sokwe]

Thanks for all this! It's amazing that you've been able to finesse proofs out of these difficult cases.

Looking at the unsolved range B246/S157 - B24678/S15678, I think that there are probably no p1 photons based on my searches with raw:0:1:2:1:0:1:0:0:1. With this geometry, the shortest partial quickly becomes extremely long. For example, in B246/S157 the shortest partial after wpos_25 is the following:

Code: Select all

Shortest partial:
|                                                                                                     .......................... |
|                                                                                                   ..........................   |
|                                                                                                 *.........................     |
|                                                                                               **........................       |
|                                                                                             ***.......................         |
|                                                                                           ***.*.....................           |
|                                                                                         ***..*....................             |
|                                                                                       ****......................               |
|                                                                                     ****.*....................                 |
|                                                                                   ****..*...................                   |
|                                                                                 .****.....................                     |
|                                                                               *****.*...................                       |
|                                                                             *****..*..................                         |
|                                                                           ..****....................                           |
|                                                                         .*****.*..................                             |
|                                                                       .*****..*.................                               |
|                                                                     ...****...................                                 |
|                                                                   *.*****.*.................                                   |
|                                                                 ..*****..*................                                     |
|                                                               ....****..................                                       |
|                                                             .*.*****.*................                                         |
|                                                           ...*****..*...............                                           |
|                                                         *....****.................                                             |
|                                                       ..*.*****.*...............                                               |
|                                                     *...*****..*..............                                                 |
|                                                   .*....****................                                                   |
|                                                 ...*.*****.*..............                                                     |
|                                               .*...*****..*.............                                                       |
|                                             ..*....****...............                                                         |
|                                           *...*.*****.*.............                                                           |
|                                         ..*...*****..*............                                                             |
|                                       ...*....****..............                                                               |
|                                     .*...*.*****.*............                                                                 |
|                                   *..*...*****..*...........                                                                   |
|                                 ....*....****.............                                                                     |
|                               ..*...*.*****.*...........                                                                       |
|                             .*..*...*****..*..........                                                                         |
|                           *....*....****............                                                                           |
|                         ...*...*.*****.*..........                                                                             |
|                       *.*..*...*****..*.........                                                                               |
|                     **....*....****...........                                                                                 |
|                   ..*.*...*.*****.*.........                                                                                   |
|                 ....*.*...*****..*........                                                                                     |
|               ....****....****..........                                                                                       |
|             .....**.**.*****.*........                                                                                         |
|           .....*.*.*.*****..*.......                                                                                           |
|         .........**.*****.........                                                                                             |
|       ............*****.*.......                                                                                               |
|     ...............*...*......                                                                                                 |
|   ..........................                                                                                                   |
| ..........................                                                                                                     |

The partial result has a front end with slope 5/3, so I tried to come up with a slope 5/3 geometry. What I ended up with is raw:-3:5:0:0:-1:1:1:0:-1. However, an arbitrary-width search with this geometry quickly fills up my available memory. Was this a poor choice of geometry for a slope 5/3 front end, or is that just naturally going to be a difficult search? Any advice here would be appreciated.

[amling]

...I tried to come up with a slope 5/3 geometry. What I ended up with is raw:-3:5:0:0:-1:1:1:0:-1. However, an arbitrary-width search with this geometry quickly fills up my available memory. Was this a poor choice of geometry for a slope 5/3 front end, or is that just naturally going to be a difficult search? Any advice here would be appreciated.

I have never been able to get very complex slopes to go anywhere performance-wise and I don't have much in the way of wisdom here.

If you haven't updated recently I might try to pick up the change that allows oversize AF2 to run so you can run geometries with U neighborhood 2 without having to fiddle with W to try to artificially twist the search to make the U neighborhood 3.

Also, I've added "grid-tool geom-info" so you can run this...

Code: Select all

$ rlife grid-tool geom-info raw:-3:5:0:0:-1:1:1:0:-1
20241024 11:20:13 [src/utils/grid_tool.rs:249] geom.nh_u_size = 3
20241024 11:20:13 [src/utils/grid_tool.rs:250] geom.nh_w_size = 9
20241024 11:20:13 [src/utils/grid_tool.rs:251] geom.spots = [(Vec3(0, 0, 0), Vec3Uvw(0, 0, 0)), (Vec3(-1, 2, 0), Vec3Uvw(1, 1, 1))]

...and quickly see the U and W neighborhood sizes. I just dumped out the stats about the geometry it had already computed, and just in the most slipshod "debug" format. We could of course add more data here, especially things that the computer is faster/better at computing than humans.

As for B246/S157 itself, I poked around a tiny bit but don't really have any results. I ran a 5/3 geometry for a bit (my choice was raw:5:-3:0:-1:0:1:0:0:1 for reasons of screen orientation and simplicity with W=T although I suspect your 5/3 geometry is going to be more or less equivalent for arbitrary width searches). The last partial at the time I gave up was:

Code: Select all

|                                                            ..................... |
|                                                          ......................  |
|                                                        ......................    |
|                                                       .....................      |
|                                                     ......................       |
|                                                   ......................         |
|                                                  ..............*......           |
|                                                ..............*....*..            |
|                                              ...............*.*.***              |
|                                             ............*..*.*...                |
|                                           ............*....*...*                 |
|                                         .............*.*.**...                   |
|                                        ..........*..*.*.....                     |
|                                      ..........*....*...*..                      |
|                                    ...........*.*.**.....                        |
|                                   ........*..*.*....*.*                          |
|                                 ........*....*...*..*.                           |
|                               .........*.*.**.......                             |
|                              ......*..*.*....*.*.*                               |
|                            ......*....*...*..*.**                                |
|                          .......*.*.**........*                                  |
|                         .......*.*....*.*.**.                                    |
|                       ........*.*.*..*......                                     |
|                     .........*.*..*.*..*.*                                       |
|                    .........*.*..*..*...                                         |
|                  ..........*..*...*..*.                                          |
|                ............*..*....*.                                            |
|               ..............*.*....                                              |
|             .................*..*.                                               |
|           .....................*                                                 |
|          .....................                                                   |
|        ......................                                                    |
|      ......................                                                      |
|     .....................                                                        |
|   ......................                                                         |
| ......................                                                           |

Which suggests there is also a 7/3 sloped edge in our way.

I also ran some searches at the 5/3s slope which were the equivalent of hand-unrolling what WAO does and slipping a bunch more "u"-tagged columns in there to see if anything much was forced around the first non-zero cell. Not much was.

I know the 5/3 slope shows up a lot in partials but I'm not convinced it is actually self-forcing in much of any sense, e.g. this I spotted:

Code: Select all

| .................................................................... |
| .................................................................... |
| ............................................................*....... |
| ............................................................**...*.. |
| ........................................................*..***.*.... |
| .......................................................*.*******.... |
| .......................................................****...*..*.. |
| ...................................................*..*****......... |
| ......................................*...........*.*****.*......... |
| ......................................**...*......****....*..*...... |
| ..................................*..***.*....*..*****...*.*........ |
| .................................*.*********.*.*****.*..*..*........ |
| .................................****...*.**.****....*..*..*........ |
| .............................*..*****....*..*****...*.*.*...*....... |
| ............................*.*****.*.......***.*..*.*.*..**....*... |
| ............................****....*..*.**.**.*.*..*..*....*.*..... |
| .......................*...*****...*.*.....*.**..*...*..*.*..**..... |
| ......................*.******.*..*..*...*..**..*..**.*.*.***.*..... |
| ......................*****....*..*..*..*.*.***.*....*.*.***.**..... |
| ..................*..*****.*.*..*.*...*..*.*.*..*...*.*..***.**..... |
| .................*.*****.**.**...*.*.****.*.....*..*.*..*.***.*..... |
| .................****....****..**.*.***.*...*.**..*.*.*.*.*.....*... |
| .............*..*****...*.*......*.*.*.*........*.*..*.*....*....... |
| ............*.*****.*..*...*....*..*.*.*......*..*....*.*........... |
| ............****....*..*..***..*..*.***..*...*.*.*.....*............ |
| ........*..*****...*.*.*****...*...*.****.************.*............ |
| .......*.*****.*..*..****.*.**.*......*.*****.*.*.******............ |
| .......****....*..*******..*****.....*..****.*..*..**..*............ |
| ...*..*****...*..***.*.***.*****....*..*.**.**..*.*...**............ |
| ..*.*****.*..*..****...*...**.*******...***.**...*...***............ |

I think in general whatever slopes are most space-efficient will tend to dominate partials due to how the partials are picked/constructed. The "random" partial is just a single random vertical (as in "W" vertical) slice and the shortest possible path to the left (as in minimum U coordinate) edge and the shortest possible path to the right edge. In this sense both the "shortest" and "random" partials are made mostly of shortest (as in U distance) paths which will therefore optimize for efficient slopes.

I do however agree that I somewhat doubt there is a finite ship in here anywhere.

[Sokwe]

I have never been able to get very complex slopes to go anywhere performance-wise...

As for B246/S157 itself,... I ran a 5/3 geometry for a bit. The last partial at the time I gave up... suggests there is also a 7/3 sloped edge in our way.

I know the 5/3 slope shows up a lot in partials but I'm not convinced it is actually self-forcing in much of any sense

Given all this, I think the best chance of a proof on nonexistence is a search with raw:0:1:2:1:0:1:0:0:1 or something essentially equivalent, but it will require more memory than I have available and will probably take a long time. It reminds me somewhat of the case B256/S02358, where a search with raw:1:1:2:1:0:1:0:1:0 eventually proved (after several hours) that there are no p1 photons, despite there being some long edges of alternate slopes that occurred frequently in the partial results.

Also, I've added "grid-tool geom-info" so you can run this...

Code: Select all

$ rlife grid-tool geom-info raw:-3:5:0:0:-1:1:1:0:-1
20241024 11:20:13 [src/utils/grid_tool.rs:249] geom.nh_u_size = 3
20241024 11:20:13 [src/utils/grid_tool.rs:250] geom.nh_w_size = 9
20241024 11:20:13 [src/utils/grid_tool.rs:251] geom.spots = [(Vec3(0, 0, 0), Vec3Uvw(0, 0, 0)), (Vec3(-1, 2, 0), Vec3Uvw(1, 1, 1))]

...and quickly see the U and W neighborhood sizes. I just dumped out the stats about the geometry it had already computed, and just in the most slipshod "debug" format. We could of course add more data here, especially things that the computer is faster/better at computing than humans.

Is there also a way to tell how many I-blocks (?) I need in my UWI input file for from-uwi? I mean these things:

Code: Select all

| zzz |
| ... |
| ... |
| ... |

It would actually be nice if there was some mode that allowed the user to run a simple from-zeros search by inputting only the geometry and width (and optional input like --ends and --left-edge) without having to bother with the geometry input file and other things like --wao-left-pad and so on. I think most people who use these spaceship search programs are only looking for something simple like this.

Also, where can I find a list of the named geometries (c1-s2s, c2d-down, etc.)?

Edit:

It occurs to me now that reducing mid_steps dynamically during expand based on estimated memory is probably possible. There is no analog of reducing mid_steps in fixed board so I hadn't thought if it when I was writing the autochoke stuff. I will also think more on this idea specifically... The worst problem is probably that I'm not sure we'd be able to salvage anything so if we decided we had a memory problem right before reify we'd have to toss everything we had done and start the expand step over from scratch with mid_steps reduced one. Even so a slow search is better then no search. We might be cooking something here.

I sketched this and it's a mixed bag. The implementation details are also complicated...

Did this feature get added somewhere? If so, how would you set up the search? If not, that's fine. I'll let you be the judge on what things should ultimately be included. Especially, I would say don't add a feature that somehow slows down unrelated searches.

Edit 2: please let me know if my questions, suggestions, comments, etc. are excessive. I realize I'm asking things almost every day.

[amling]

I have never been able to get very complex slopes to go anywhere performance-wise...

As for B246/S157 itself,... I ran a 5/3 geometry for a bit. The last partial at the time I gave up... suggests there is also a 7/3 sloped edge in our way.

I know the 5/3 slope shows up a lot in partials but I'm not convinced it is actually self-forcing in much of any sense

Given all this, I think the best chance of a proof on nonexistence is a search with raw:0:1:2:1:0:1:0:0:1 or something essentially equivalent, but it will require more memory than I have available and will probably take a long time. It reminds me somewhat of the case B256/S02358, where a search with raw:1:1:2:1:0:1:0:1:0 eventually proved (after several hours) that there are no p1 photons, despite there being some long edges of alternate slopes that occurred frequently in the partial results.

I'll leave it run on my laptop (to 60GB) and see what happens.

EDIT: Sadly it did not terminate. Last partial output before it filled memory and died:

Code: Select all

Shortest partial:
|                                                                                                                                                                           .. |
|                                                                                                                                                                         .... |
|                                                                                                                                                                       ...... |
|                                                                                                                                                                     ........ |
|                                                                                                                                                                   .......... |
|                                                                                                                                                                 ............ |
|                                                                                                                                                               .............. |
|                                                                                                                                                             ................ |
|                                                                                                                                                           .................. |
|                                                                                                                                                         .................... |
|                                                                                                                                                       .......*.............. |
|                                                                                                                                                     .........**..*..*....... |
|                                                                                                                                                   .......*..***.*.****...... |
|                                                                                                                                                 ........*.**********.*.*.... |
|                                                                                                                                               ..........****...*.*...*...... |
|                                                                                                                                             ........*..*****.....*..*....... |
|                                                                                                                                           .........*.*****.*.....*..*....... |
|                                                                                                                                         ...........****....*..*...*.*..*.... |
|                                                                                                                                       .........*..*****...*.*......*.*...... |
|                                                                                                                                     ..........*.*****.*..*..*....**..*...... |
|                                                                                                                                   ............****....*..*..*..*....*.*..... |
|                                                                                                                                 ..........*..*****...*.*.*...*...*...*....   |
|                                                                                                                               ...........*.*****.*..*.*..*....*.**.**..*     |
|                                                                                                                             .............****....*..*...*.*....***....       |
|                                                                                                                           ...........*..*****...*.*.*.**..*.*.**....         |
|                                                                                                                         ............*.*****.*..*.*..*....*.*.*****           |
|                                                                                                                       ..............****....*..*...*...*.*...***             |
|                                                                                                                     ............*..*****...*.*.*.**.*.*.*....*               |
|                                                                                                                   .............*.*****.*..*.*..*....*.*..*.*                 |
|                                                                                                                 ...............****....*..*...*...*..***.*                   |
|                                                                                                               .............*..*****...*.*.*.**.*.*.*.**.                     |
|                                                                                                             ..............*.*****.*..*.*..*....*.*..*.                       |
|                                                                                                           ................****....*..*...*...*..**.*                         |
|                                                                                                         ..............*..*****...*.*.*.**.*.*.*.**                           |
|                                                                                                       ...............*.*****.*..*.*..*....*.*..*                             |
|                                                                                                     .................****....*..*...*...*..**.                               |
|                                                                                                   ...............*..*****...*.*.*.**.*.*.*.*                                 |
|                                                                                                 ................*.*****.*..*.*..*....*.*..                                   |
|                                                                                               ..................****....*..*...*...*..**                                     |
|                                                                                             ................*..*****...*.*.*.**.*.*.*.                                       |
|                                                                                           .................*.*****.*..*.*..*....*.*.                                         |
|                                                                                         ...................****....*..*...*...*..*                                           |
|                                                                                       .................*..*****...*.*.*.**.*.*.*                                             |
|                                                                                     ..................*.*****.*..*.*..*....*.*                                               |
|                                                                                   ....................****....*..*...*...*..                                                 |
|                                                                                 ..................*..*****...*.*.*.**.*.*.                                                   |
|                                                                               ...................*.*****.*..*.*..*....*.                                                     |
|                                                                             .....................****....*..*...*...*.                                                       |
|                                                                           ...................*..*****...*.*.*.**..**                                                         |
|                                                                         ....................*.*****.*..*.*..*...*.                                                           |
|                                                                       ......................****....*..*...*...*                                                             |
|                                                                     ....................*..*****...*.*.*.**..*                                                               |
|                                                                   .....................*.*****.*..*.*..*....                                                                 |
|                                                                 .......................****....*..*...*...                                                                   |
|                                                               .....................*..*****...*.*.*.**..                                                                     |
|                                                             ......................*.*****.*..*.*..*...                                                                       |
|                                                           ........................****....*..*...*..                                                                         |
|                                                         ......................*..*****...*.*.*.**.                                                                           |
|                                                       .......................*.*****.*..*.*..*..                                                                             |
|                                                     .........................****....*..*..*..                                                                               |
|                                                   .......................*..*****...*.*.*.**                                                                                 |
|                                                 ........................*.*****.*..*..*..*                                                                                   |
|                                               ..........................****....*..*..*.                                                                                     |
|                                             ........................*..*****...*.*.*..                                                                                       |
|                                           .........................*.*****.*...*..*.                                                                                         |
|                                         ...........................****....*....**                                                                                           |
|                                       .........................*..*****...*..*.*                                                                                             |
|                                     ..........................*.*****.*...*...                                                                                               |
|                                   ............................****....*....*                                                                                                 |
|                                 ..........................*..*****...*..*.                                                                                                   |
|                               ...........................*.*****.*...*..                                                                                                     |
|                             .............................****....*....                                                                                                       |
|                           ...........................*..*****...*..*                                                                                                         |
|                         ............................*.*****.*...*.                                                                                                           |
|                       ..............................****....*...                                                                                                             |
|                     ............................*..*****...*..                                                                                                               |
|                   .............................*.*****.*...*                                                                                                                 |
|                 ...............................****....*..                                                                                                                   |
|               .............................*..*****...*.                                                                                                                     |
|             ..............................*.*****.*...                                                                                                                       |
|           ................................****....*.                                                                                                                         |
|         ..............................*..*****...*                                                                                                                           |
|       ...............................*.*****.*..                                                                                                                             |
|     .................................****....*                                                                                                                               |
|   ...............................*..*****...                                                                                                                                 |
| ................................*.*****.*.                                                                                                                                   |
| ................................****....                                                                                                                                     |
| ............................*..*****..                                                                                                                                       |
| ...........................*.*****.*                                                                                                                                         |
| ...........................****...                                                                                                                                           |
| .......................*..*****.                                                                                                                                             |
| ......................*.*****.                                                                                                                                               |
| ......................****..                                                                                                                                                 |
| ..................*..*****                                                                                                                                                   |
| .................*.*****                                                                                                                                                     |
| .................****.                                                                                                                                                       |
| .............*..****                                                                                                                                                         |
| ............*.****                                                                                                                                                           |
| ............****                                                                                                                                                             |
| ........*..***                                                                                                                                                               |
| .......*.***                                                                                                                                                                 |
| .......***                                                                                                                                                                   |
| ......**                                                                                                                                                                     |
| .....*                                                                                                                                                                       |
| ....                                                                                                                                                                         |
| ..                                                                                                                                                                           |

Is there also a way to tell how many I-blocks (?) I need in my UWI input file for from-uwi? I mean these things:

Code: Select all

| zzz |
| ... |
| ... |
| ... |

It's the length of that "spots" array which I recognize is very painful to count. Other places in the code might call it the determinant (or absolute value of such anyway) which is a way to compute it from the U, V, and W vectors. I've changed it to output e.g.:

Code: Select all

Geometry: raw:-3:5:0:0:-1:1:1:0:-1
   U: Vec3(-3, 5, 0)
   V: Vec3(0, -1, 1)
   W: Vec3(1, 0, -1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(-1, 2, 0) => Vec3Uvw(1, 1, 1)

Input files for from-uwi should have as many big left-to-right blocks as there are "unique positions".

It would actually be nice if there was some mode that allowed the user to run a simple from-zeros search by inputting only the geometry and width (and optional input like --ends and --left-edge) without having to bother with the geometry input file and other things like --wao-left-pad and so on. I think most people who use these spaceship search programs are only looking for something simple like this.

I have debated many times trying to have other ways to specify starting states but never came up with anything I liked. The problem is it's much more than just the picture that goes into it and so it's this weird argument parsing mess of having groups of options that work together (and should be specified together) to produce the state one way or another. I had thought about splitting apart the state generation and search execution commands (so we could have multiple distinct state generators with their own collections of options), but it seems like it would be even more agonizing.

WAO left pad, right pad, and idxs are all optional although the defaults are certainly debatable. When I was first running it I generally wanted larger pads because I was using it to split up searches (and so the default pads are 1 and the default idxs are none so you can just see what idxs exist). I am not exactly married to this decision but I'm at least a little skeptical of privileging this particular use of WAO (from zeros) over others (from a wick or a wave).

Also, where can I find a list of the named geometries (c1-s2s, c2d-down, etc.)?

Nowhere, alas. "geom_by_name" is the code that parses it, but there is no list and you'll have to reverse engineering it from the pattern matching in there. The patterns (as of now) in there are:

Code: Select all

KcN-f2b - orthogonal north front-to-back
KcN-b2f - orthogonal south back-to-front
KcN-s2s - orthogonal west side-to-side
KcNd-down - diagonal northwest, XY axis-aligned, more like f2b
KcNd-up - diagonal southeast, XY axis-aligned, more like b2f
pN - oscillator
raw:... - custom
KcNk-1 - knight-wise north-northwest, XY axis-aligned, most f2b-like
KcNk-2 - knight-wise west-northwest, XY axis-aligned
KcNk-3 - knight-wise east-southeast, XY axis-aligned
KcNk-4 - knight-wise south-southeast, XY axis-aligned, most b2f-like

Where "K" and "N" are numbers (or empty K for K=1) and they generally build downward with W=Y or at least W "positive Y-like". You can of course run "geom-info" to dump out the details (although you'd have to pick numeric values for K and N).

It occurs to me now that reducing mid_steps dynamically during expand based on estimated memory is probably possible. There is no analog of reducing mid_steps in fixed board so I hadn't thought if it when I was writing the autochoke stuff. I will also think more on this idea specifically... The worst problem is probably that I'm not sure we'd be able to salvage anything so if we decided we had a memory problem right before reify we'd have to toss everything we had done and start the expand step over from scratch with mid_steps reduced one. Even so a slow search is better then no search. We might be cooking something here.

I sketched this and it's a mixed bag. The implementation details are also complicated...

Did this feature get added somewhere? If so, how would you set up the search? If not, that's fine. I'll let you be the judge on what things should ultimately be included. Especially, I would say don't add a feature that somehow slows down unrelated searches.

It got added on a private branch which I never published since I was still debating it with myself. In terms of cost it's minor for the code (another flag, a few more control statements), and should be no meaningful runtime cost for other searches.

I was also (as I was debating) thinking about writing the autochoke by "u" column cells as well or instead. If I changed WAO to be able to mark "u" columns when there is only one WAO idx (as there will be for asymmetric from-zeros searches) then you'd even be able to use it there (and with WAO's pad arguments have it add the padding distinguishing "u" columns for you). Perhaps more on all these ideas later...

I've pushed it to codeberg as 20241024-rc-pre-reify-autochoke-03 so you can take it for a spin if you want. If you do run it please do let me know how it goes. I had given it the limit of 10MB with "--pre-reify-autochoke 10485760" (should work for both normal recentering and for recentering WAO). If it actually ships we can worry about making that "--pre-reify-autochoke 10MB" instead but for now you'll have to do some math.