amling search program principles discussion / brain dump

[amling]

I guess I've talked myself into it and added diagonal f2b/b2f/s2s geometries. They're not as pleasingly clear choices as all the other geometries already added, but they're about as good as it's gonna get for simple AF2=3 searches.

Specifically...

KcNd-f2b is U=X-Y, V Kc/Nd northwest, W~T. This should always produce 2*gcd(K, N) bit tiles. Example geom-info output:

Code: Select all

Geometry: c3d-f2b
   U: Vec3(1, -1, 0)
   V: Vec3(-1, -1, 3)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 7
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 2) => Vec3Uvw(1, 1, 1)
Geometry: c4d-f2b
   U: Vec3(1, -1, 0)
   V: Vec3(-1, -1, 4)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 2) => Vec3Uvw(1, 1, 0)
Geometry: 2c8d-f2b
   U: Vec3(1, -1, 0)
   V: Vec3(-2, -2, 8)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (4):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 2) => Vec3Uvw(2, 1, 0)
      #2: Vec3(-1, -1, 4) => Vec3Uvw(0, 2, 0)
      #3: Vec3(-1, -2, 6) => Vec3Uvw(2, 3, 0)
Geometry: 2c5d-f2b
   U: Vec3(1, -1, 0)
   V: Vec3(-2, -2, 5)
   W: Vec3(1, 1, -2)
   Neighborhood sizes:
      U: 3
      W: 11
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(1, 0, -1) => Vec3Uvw(1, 0, 1)

KcNd-b2f is U=X-Y, V Kc/Nd southeast, W~-T. Ditto 2*gcd(K, N) bit tiles.

Code: Select all

Geometry: c3d-b2f
   U: Vec3(1, -1, 0)
   V: Vec3(1, 1, 3)
   W: Vec3(0, 0, -1)
   Neighborhood sizes:
      U: 3
      W: 7
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(1, 0, 1) => Vec3Uvw(1, 1, 1)
Geometry: c4d-b2f
   U: Vec3(1, -1, 0)
   V: Vec3(1, 1, 4)
   W: Vec3(0, 0, -1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(1, 0, 2) => Vec3Uvw(1, 1, 0)
Geometry: 2c8d-b2f
   U: Vec3(1, -1, 0)
   V: Vec3(2, 2, 8)
   W: Vec3(0, 0, -1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (4):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(1, 0, 2) => Vec3Uvw(2, 1, 0)
      #2: Vec3(1, 1, 4) => Vec3Uvw(0, 2, 0)
      #3: Vec3(2, 1, 6) => Vec3Uvw(2, 3, 0)
Geometry: 2c5d-b2f
   U: Vec3(1, -1, 0)
   V: Vec3(2, 2, 5)
   W: Vec3(1, 1, 2)
   Neighborhood sizes:
      U: 3
      W: 11
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(1, 0, 1) => Vec3Uvw(1, 0, 1)

KcNd-s2s is U=X+Y, V Kc/Nd northwest, W=-X+Y. This always produces tiles with 2N bit tiles.

Code: Select all

Geometry: c3d-s2s
   U: Vec3(1, 1, 0)
   V: Vec3(-1, -1, 3)
   W: Vec3(-1, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (6):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(2, 2, 0)
      #2: Vec3(0, 0, 2) => Vec3Uvw(4, 4, 0)
      #3: Vec3(0, 1, 0) => Vec3Uvw(3, 0, 3)
      #4: Vec3(0, 1, 1) => Vec3Uvw(5, 2, 3)
      #5: Vec3(-1, 0, 2) => Vec3Uvw(1, 4, 3)
Geometry: c4d-s2s
   U: Vec3(1, 1, 0)
   V: Vec3(-1, -1, 4)
   W: Vec3(-1, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (8):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(2, 2, 0)
      #2: Vec3(0, 0, 2) => Vec3Uvw(4, 4, 0)
      #3: Vec3(0, 0, 3) => Vec3Uvw(6, 6, 0)
      #4: Vec3(0, 1, 0) => Vec3Uvw(4, 0, 4)
      #5: Vec3(0, 1, 1) => Vec3Uvw(6, 2, 4)
      #6: Vec3(-1, 0, 2) => Vec3Uvw(0, 4, 4)
      #7: Vec3(-1, 0, 3) => Vec3Uvw(2, 6, 4)
Geometry: 2c8d-s2s
   U: Vec3(1, 1, 0)
   V: Vec3(-2, -2, 8)
   W: Vec3(-1, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (16):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(4, 2, 0)
      #2: Vec3(0, 0, 2) => Vec3Uvw(8, 4, 0)
      #3: Vec3(0, 0, 3) => Vec3Uvw(12, 6, 0)
      #4: Vec3(-1, -1, 4) => Vec3Uvw(0, 8, 0)
      #5: Vec3(-1, -1, 5) => Vec3Uvw(4, 10, 0)
      #6: Vec3(-1, -1, 6) => Vec3Uvw(8, 12, 0)
      #7: Vec3(-1, -1, 7) => Vec3Uvw(12, 14, 0)
      #8: Vec3(0, 1, 0) => Vec3Uvw(8, 0, 8)
      #9: Vec3(0, 1, 1) => Vec3Uvw(12, 2, 8)
      #10: Vec3(-1, 0, 2) => Vec3Uvw(0, 4, 8)
      #11: Vec3(-1, 0, 3) => Vec3Uvw(4, 6, 8)
      #12: Vec3(-1, 0, 4) => Vec3Uvw(8, 8, 8)
      #13: Vec3(-1, 0, 5) => Vec3Uvw(12, 10, 8)
      #14: Vec3(-2, -1, 6) => Vec3Uvw(0, 12, 8)
      #15: Vec3(-2, -1, 7) => Vec3Uvw(4, 14, 8)
Geometry: 2c5d-s2s
   U: Vec3(1, 1, 0)
   V: Vec3(-2, -2, 5)
   W: Vec3(-1, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (10):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(4, 2, 0)
      #2: Vec3(0, 0, 2) => Vec3Uvw(8, 4, 0)
      #3: Vec3(-1, -1, 3) => Vec3Uvw(2, 6, 0)
      #4: Vec3(-1, -1, 4) => Vec3Uvw(6, 8, 0)
      #5: Vec3(0, 1, 0) => Vec3Uvw(5, 0, 5)
      #6: Vec3(0, 1, 1) => Vec3Uvw(9, 2, 5)
      #7: Vec3(-1, 0, 2) => Vec3Uvw(3, 4, 5)
      #8: Vec3(-1, 0, 3) => Vec3Uvw(7, 6, 5)
      #9: Vec3(-2, -1, 4) => Vec3Uvw(1, 8, 5)

[Sokwe]

The environment variables are environment variables rather than command line arguments not so much for any strong philosophical reason, but rather the unfortunate implementation detail that they cut through code weirdly and are hard/annoying to plumb all the way to the top argument parsing. Perhaps at some point I'll see if I can plumb them to the top all together and allow them all to be set in arguments. I guess TBD but I'm not optimistic.

It's fine as an environment variable. I think I can reasonably explain it in the tutorial, and it may be helpful to immediately see an example of setting an environment variable, so that it isn't such a mystery when exploring more advanced options. What you've done accomplishes what I want fairly easily, and I certainly don't want you to do extra work for essentially no gain, so keep it as-is.

I'm also unsure whether halt on ends should be the default or not.

I pretty clearly do not want it enabled in my typical search projects and I would really rather not have to turn it off every time I run a search and/or in an RC file on every machine I run searches on.

I only mentioned this because you had made it the default, but now I see it was an accident that has been corrected. I also prefer it to be disabled by default.

It would also be nice if the search could stop after a specified number of ends are found

That might be harder than you think. Try this:

Code: Select all

rlife llsss-recentering-wao c2-f2b '@zero' --wao-left-pad 00 --wao-right-pad 00 --wao-idx ALL XX

...and tell me how many ships it found (for counting purposes) when it finds the first bunch

Do people really want to find "7 ships, but no more"?

That's a fair point. I'm so used to the idea that ships are found sequentially, rather than simultaneously, that it just "made sense" to me to think of counting the number of ships found so far. On further reflection, "LLSSS_HALT_ON_ENDS", "--halts w_pos:NN", and various ulimit options encompass all of the halting behavior I have ever wanted in a search so far.

I guess I've talked myself into it and added diagonal f2b/b2f/s2s geometries. They're not as pleasingly clear choices as all the other geometries already added, but they're about as good as it's gonna get for simple AF2=3 searches.

Thanks! I know they aren't ideal, but it felt like such geometries should still be included to allow easy setup of symmetric diagonal searches, or side-to-side searches with symmetric ends. In a sense, the predefined geometries are just suggestions for inexperienced users. If a user can get more out of a raw geometry, then they're already probably knowledgeable enough to know the limitations of the predefined geometries.

Do you think c4d-f2b is "raw:1:0:0:-1:-1:4:0:0:1"? "raw:1:-1:0:-1:-1:4:0:0:1"? Something else?

I definitely imagined it being the latter. That's how I would set up such a search in JLS, and it's the geometry I used to find a glide-symmetric ship in B026/S2 when first testing the new agar options. The former is essentially what gfind does.

By the way, when I'm explaining the input in the tutorial, what should I call the positional parameter after the geometry. That is, what should I call the parameter represented by '@zero', or '@agar', or '1.in'?

[amling]

...(diagonal) side-to-side searches with symmetric ends...

That, uh, might not be a thing. It's the same problem as edges all over again: namely these first implementations of symmetric ends are sort of hacks and specific to XY-aligned s2s geometries. I'll have to think it over and see if I can manage to cook up more geometry-generic versions...

By the way, when I'm explaining the input in the tutorial, what should I call the positional parameter after the geometry. That is, what should I call the parameter represented by '@zero', or '@agar', or '1.in'?

Ah, one of the greatest problems of computer science: naming. At various points in various places they have been called (at least) all of "inputs", "pictures", or "starts". The current argument names for clap (the argument parser library) I believe are all "start_files" so maybe I should try to start sticking to that...

[Sokwe]

That, uh, might not be a thing. It's the same problem as edges all over again: namely these first implementations of symmetric ends are sort of hacks and specific to XY-aligned s2s geometries. I'll have to think it over and see if I can manage to cook up more geometry-generic versions...

Sorry, I suppose it was a bit presumptuous to assume they worked for diagonally oriented geometries without ever trying them. I didn't mean to create another silly problem to solve. I guess I'll throw out my standard "let me know if I'm getting annoying" statement here.

By the way, when I'm explaining the input in the tutorial, what should I call the positional parameter after the geometry. That is, what should I call the parameter represented by '@zero', or '@agar', or '1.in'?

Ah, one of the greatest problems of computer science: naming. At various points in various places they have been called (at least) all of "inputs", "pictures", or "starts". The current argument names for clap (the argument parser library) I believe are all "start_files" so maybe I should try to start sticking to that...

I should have mentioned this, but I think lately I've privately been calling them "input grids", with '@zero' and '@agar' being "magic grids", but perhaps this might somehow give the wrong impression. (?) I personally prefer something like "[input] pictures/grids" over "start files", as '@zero' and '@agar' aren't really files. I would then call '@zero' and '@agar' "magic pictures" or "automatic pictures". Of course none of this is really that important. I just didn't want to call it something that was incorrect in some way.

Edit: I see that the --help option calls the second positional argument "<START_FILES>", so I will stick with that in the tutorial for consistency. I will call '@zero' and '@agar' "magic grids" that can replace the start_file, since that seems to be what you call them.

Unrelated question: are there any valid values for --pre-reify-autochoke-type besides "top", "left", and "right"?

[amling]

That, uh, might not be a thing. It's the same problem as edges all over again: namely these first implementations of symmetric ends are sort of hacks and specific to XY-aligned s2s geometries. I'll have to think it over and see if I can manage to cook up more geometry-generic versions...

I have thought more about it and I think it can be made to work. The reflect edge works I think for any geometry where T is in the VW plane and the mirrored cells end up back on valid integer XYT lattice points. Reflect ends will require similarly that T be in the VU plane, but I think might also require W not to "twist" (be non-perpendicular to VU plane) too much (although this is maybe already forced by normal CA checks fitting w/in an AF2 window?). I would have to think very hard to decide analytically now for all possibilities, but it will be easy enough for the code to decide for a single geometry/AF2 if it's okay. All named "s2s" geometries have a W with exactly zero such twist, and will thus be fine. TBD actually implementing and testing.

At various points in various places they have been called (at least) all of "inputs", "pictures", or "starts". The current argument names for clap (the argument parser library) I believe are all "start_files" so maybe I should try to start sticking to that...

I should have mentioned this, but I think lately I've privately been calling them "input grids", with '@zero' and '@agar' being "magic grids", but perhaps this might somehow give the wrong impression. (?) I personally prefer something like "[input] pictures/grids" over "start files", as '@zero' and '@agar' aren't really files. I would then call '@zero' and '@agar' "magic pictures" or "automatic pictures". Of course none of this is really that important. I just didn't want to call it something that was incorrect in some way.

Edit: I see that the --help option calls the second positional argument "<START_FILES>", so I will stick with that in the tutorial for consistency. I will call '@zero' and '@agar' "magic grids" that can replace the start_file, since that seems to be what you call them.

"Start" was chosen as the opposite of "end" which itself was chosen off the cuff 400 subjective years ago when writing the very first LGOL code. It could just as easily been "goal", "exit", "hit", "success", etc. and then who knows what "start" would have been. "Magic grid" was also improvised in a hurry when I had implemented it and wanted to explain it.

Neither represents a concerted effort to make a coherent vocabulary and I could probably be convinced to rename either of them to anything someone with more UI/documentation sense than me comes up with.

Unrelated question: are there any valid values for --pre-reify-autochoke-type besides "top", "left", and "right"?

Their parsing is buried somewhere in src/llsss/cli.rs, which is where all the CLI UI glue code lives these days. There seems to also be "left_right". These are all describing how to pick the next cell to force from among the possible cells left that have non-unique values:

(*) "top" is the most sensible I think, picking the top-most (as in lowest W value as in nearest to the beginning of the search), breaking ties by picking farthest from the U center of the board.

(*) "left"/"right" pick the U farthest in the specified direction, breaking ties towards low W (beginning of the search).

(*) "left_right" picks the U farthest from the center of the board, ditto breaking ties towards low W.

I had thought maybe some day we might also want a strategy vaguely like the mid_steps reduction for recentering on that other branch. Maybe something like pick the U farthest from the center of the board, but only in the last W overlap (2 Y rows)? This sort of simulates accepting that patterns may have been big earlier but that they now need to get small and thus hopefully more easily completable.

In the end I never got around to it since the entire autochoke feature seemed sort of hard to use and ineffective.

[amling]

Reflect ends... TBD actually implementing and testing.

I've written fancy new "reflect" ends to replace the old hacky ones. The new implementation goes to great lengths to understand geometry generically and to detect hits as early as possible (as soon as all cells are known).

This changes what results look like and makes them found earlier. Compare finding the turtle previously...

Code: Select all

End [thinnest] "LlsssEndsEven":
| ZZZZZZZZZZZZZZZZZ | ZZZZZZZZZZZZZZZZZ | ZZZZZZZZZZZZZZZZZ |
| ................. | ................. | ................. |
| ................. | ................. | ................. |
| ................. | ....*............ | ....*............ |
| ...***.......*... | ...*.*......**... | ...*.......*.*... |
| ...**..*.**.**... | ...*...**..***... | ..**..*.*..*..... |
| .....***....*.... | ...*.*...*..*.... | ......**.**...... |
| ...*..*.*...*.... | .....*..*..***... | ..**.*..***...... |
| ..*....*....*.... | ..**..***..***... | ..****...**...*.. |
| ..*....*....*.... | ..**..***..***... | ..****...**...*.. |

...with now...

Code: Select all

End [thinnest] "LlsssEndsReflect(Even)":
| ZZZZZZZZZZZZZZZZZ | ZZZZZZZZZZZZZZZZZ | ZZZZZZZZZZZZZZZZZ |
| ................. | ................. | ................. |
| ................. | ................. | ................. |
| ................. | ....*............ | ....*............ |
| ...***.......*... | ...*.*......**... | ...*.......*.*... |
| ...**..*.**.**... | ...*...**..***... | ..**..*.*..*..... |
| .....***....*.... | ...*.*...*..*.... | ......**.**...... |
| ...*..*.*...*.... | .....*..*..***... | ..**.*..***...... |
| ..*....*....*.... | ..**..***..***... | ..****...**...*.. |

Or finding the LWSS previously...

Code: Select all

End [thinnest] "LlsssEndsGSOdd":
|  ZZZZZZZZZ |  ZZZZZZZZZ | ZZZZZZZZZ  | ZZZZZZZZZ  |
|  ......... |  ......... | .........  | .........  |
|  ......... |  ......... | .........  | .........  |
|  ......... |  ......... | ....**...  | ...*..*..  |
|  ...**.... |  ..****... | ...****..  | ..*......  |
|  ..**.**.. |  ..*...*.. | ..**.**..  | ..*...*..  |
|  ...****.. |  ..*...... | ...**....  | ..****...  |

...with now...

Code: Select all

End [thinnest] "LlsssEndsReflect(GSOdd)":
|  ZZZZZZZZZ |  ZZZZZZZZZ | ZZZZZZZZZ  | ZZZZZZZZZ  |
|  ......... |  ......... | .........  | .........  |
|  ......... |  ......... | .........  | .........  |
|  ......... |  ......... | ....**...  | ...*..*..  |
|  ...**.... |  ..****... | ...****..  | ..*......  |
|  ..**.**.. |  ..*...*.. | ..**.**..  | ..*...*..  |

Theoretically I could wait until the result has scrolled farther in bounds to try to make it easier to understand for humans, but I don't think it's worth it. I believe earliest is best as searches may take long or run out of memory before they reach the later depths.

It does however mean it can be hard to see what is happening e.g. consider what it looks like finding the glider in c4d-s2s geometry:

Code: Select all

End [thinnest] "LlsssEndsReflect(GSEven)":
|     Z      |     Z      |    ZZ      |    ZZ      |
|    .ZZ     |    .ZZ     |   ..ZZ     |   ..ZZ     |
|   ...ZZ    |   ...ZZ    |  ....ZZ    |  ....ZZ    |
|  .....ZZ   |  .....ZZ   | ......ZZ   | ......ZZ   |
|  ......ZZ  |  ......ZZ  |  ......ZZ  |  ......ZZ  |
|   ......ZZ |   .*....ZZ |   **....ZZ |   **....ZZ |
|    **....Z |    *.....Z |    .*....  |    ......  |
|     .....  |     *....  |     ....   |     ....   |
|      ...   |      ...   |      ..    |      ..    |
|       .    |       .    |            |            |

I've promoted the new implementation to take over "--ends even", "--ends odd", "--ends gse", and "--ends gso". E.g. the glider above was found with:

Code: Select all

rlife llsss-recentering-wao c4d-s2s '@zero' --ends gse --wao-left-pad 00 --wao-right-pad 00 --wao-idx ALL 03

"--ends skew_gutter:N" is still a hacky, geometry-specific mess.

"--ends gutter" still does not exist. Previously it would have been strictly subsumed by "--ends odd". A more careful implementation could detect a result a little earlier, but I'm not sure it's worth it.

[Sokwe]

I've begun writing a tutorial for basic LLSSS spaceship searches, which can be found here. Currently, it only includes sections on downloading and compiling, and a simple search done with each of llsss, llsss-recentering, and llsss-recentering-wao. I intend to add several more sections over time, especially a section documenting basic options, a section on extending partial results, and a section on running B0 searches. Please mention if there are any other sections that could or should be added. Also, feel free to edit this tutorial, and let me know if I got any details egregiously wrong.

Edit: I've finished the first three sections of the above tutorial, specifically installation, a simple example, and a detailed explanation of the basic input options. This should be enough to give most people a very good starting point for using LLSSS. I still intend to add sections for the following:

• Simple B0 searches
• Seam ripper partials
• Extending partial results
• Saving and loading the search state

I think that should be reasonable for a "basic" tutorial. I would like to know if anyone has any good example searches for extending partial results. I at least want one that is 2c4-s2s, and probably one that is front-to-back.

finding skewed MWSS on MWSS both ways with `--ends skew_gutter:2:-2`:

I'm trying to make sure I understand the input here before I include it in the tutorial. What specifically does "skew_gutter:2:-2" mean? Is "2:-2" a range, or just a list of two numbers?

I am also considering topics for a potential advanced LLSSS tutorial that I might (but probably wont) write. Here is my list so far:

• Arbitrary-width searches and disproofs
• using --max-pop to find minimal population spaceships
• Autochoke (including recentering autochoke with the exact-expand branch)
• Advanced root labels and wildcards
• constraint files
• period division
• wick eaters with wao
• raw geometries (camelship and diagonally-oriented knightship?)
• forbidden block filters (including recompiling with alternate AF2 value)
• waves
• oscillators
• grayships

Some of these aren't too difficult, such as the first two, and could potentially be included in the basic tutorial. Does anyone have any other proposals for more advanced LLSSS topics? Keith, do you think there's any particularly interesting use of LLSSS that isn't covered above?

"--ends gutter" still does not exist. Previously it would have been strictly subsumed by "--ends odd". A more careful implementation could detect a result a little earlier, but I'm not sure it's worth it.

The only reason I could see to include "--ends gutter" is if someone wanted to specifically find only gutter ships in a s2s search, while ignoring the non-gutter odd-symmetric ends. It's not something I've ever really cared about.

[amling]

finding skewed MWSS on MWSS both ways with `--ends skew_gutter:2:-2`:

I'm trying to make sure I understand the input here before I include it in the tutorial. What specifically does "skew_gutter:2:-2" mean? Is "2:-2" a range, or just a list of two numbers?

The latter: a list of two numbers.

I am also considering topics for a potential advanced LLSSS tutorial that I might (but probably wont) write. Here is my list so far:
...
Does anyone have any other proposals for more advanced LLSSS topics? Keith, do you think there's any particularly interesting use of LLSSS that isn't covered above?

This thread is a wasteland of interesting uses. So probably too is the search ideas firehouse thread and skimming all the options and parts in cli.rs. Just a few candidates of varying degress of approachability:

(*) Wildcards - used for making very special input grids but also for some straight forward things like symmetric initial boundary conditions.
(*) Unwrap V searches - used mostly with weird PD constraints to find catalysts
(*) Recentering fuzzy edges - maybe actually worth discussion for those solving branches
(*) Ends DB (V3) - ditto for branch solving
(*) The mess of options that support out of bound agars and/or mixed out of bound agars for things like greyship edges. I'm maybe biased but I think support for this sort of thing might be something of a relative advantage for LLSSS over other search programs.
(*) constraints e.g. grid constraints to force zeros and protect clearance

These of course are mostly miles out of scope for any sort of tutorial, but if you're asking for interesting things that have been done with LLSSS, they are there...


About the tutorial itself, I skimmed it and it makes sense generally. I will take a closer look eventually and try to provide more specific feedback, but for a few weeks I'm on the road with access only to my cell phone.

[confocaloid]

The current version of the tutorial says "Compilation of LLSSS may take up to 7GB of RAM". Does this depend on some details of the compilation process? Is there a way to significantly reduce the memory requirements for compilation?

[amling]

The current version of the tutorial says "Compilation of LLSSS may take up to 7GB of RAM". Does this depend on some details of the compilation process? Is there a way to significantly reduce the memory requirements for compilation?

I think it's even higher, at least for me. I frequently set ulimit 8 GB for provisional searches and I recall compilation crashing when I had run one under that limit. My best guess was something like 10 GB and I can check when I get back to a computer.

Building a binary for just one subcommand (e.g. llsss-recentering) should use less but I am not really sure how to debug and improve compiler memory use for the whole unified binary. There was some discussion up thread about making it easier to build single-subcommand binaries (like maybe with environment variable instead of code change), but we never actually did it.

[Sokwe]

While writing the tutorial section for B0 searches, I noticed that symmetric ends in B0 searches don't work correctly when using llsss or llsss-recentering. Unfortunately, they detect a small section of background agar as an "end":

Code: Select all

[INFO] End [thinnest] "LlsssEndsReflect(Even)":
[INFO] | ZZ | ZZ |
[INFO] | ** | .. |
[INFO] | ** | .. |
[INFO] | ** | .. |

Fortunately, it works properly with a wao search, presumably due to the different way in which wao searches force cells in the first row. For now, I have tried to demonstrate this behavior in a section of the tutorial. I'll of course update the tutorial if the behavior of llsss or llsss-recentering changes.

About the tutorial itself, I skimmed it and it makes sense generally. I will take a closer look eventually and try to provide more specific feedback, but for a few weeks I'm on the road with access only to my cell phone.

It might be helpful if you create a wiki account so that you can fix problems in the tutorial yourself. I don't expect you to do much, but if there's something small and easy to fix, it might be better than trying to contact me or another editor to fix it. For things in the tutorial that you don't want to write or correct yourself, feel free to post them on the forums and I will try to incorporate those ideas or fixes into the tutorial to the best of my abilities.

The current version of the tutorial says "Compilation of LLSSS may take up to 7GB of RAM". Does this depend on some details of the compilation process? Is there a way to significantly reduce the memory requirements for compilation?

I think it's even higher, at least for me. I frequently set ulimit 8 GB for provisional searches and I recall compilation crashing when I had run one under that limit. My best guess was something like 10 GB and I can check when I get back to a computer.

This was just a guess on my part when it crashed on me on (months ago on a much earlier version of rlife) with my ~5GB of RAM and 2GB of swap space. I now give it much more swap memory when compiling, with compilation taking about 30 minutes.

[LaundryPizza03]

I cannot use autochoke with llsss-recentering. I'm trying to whittle down a knightship search to reduce the memory usage on my system.

Code: Select all

% ./rlife llsss-recentering --rule 'B25678/S4578' --filters wcaf c4k-1 '@zero' 20  --ends zero_and_halt --pre-reify-autochoke 550000000 > output.txt
error: unexpected argument '--pre-reify-autochoke' found

  tip: to pass '--pre-reify-autochoke' as a value, use '-- --pre-reify-autochoke'

Usage: rlife llsss-recentering <GEOM|PICTURE_FILE|MID_STEPS|--top-pad <TOP_PAD>|--left-pad <LEFT_PAD>|--right-pad <RIGHT_PAD>|--fuzzy-left-edge|--fuzzy-right-edge|--rule <RULE>|--wildcard-config <WILDCARD_CONFIG>|--unwrap-v|--left-edge <LEFT_EDGE>|--left-closure <LEFT_CLOSURE>|--right-edge <RIGHT_EDGE>|--right-closure <RIGHT_CLOSURE>|--constraint <CONSTRAINT>|--filters <FILTERS>|--partials <PARTIALS>|--ends <ENDS>|--state-file <STATE_FILE>>

For more information, try '--help'.

% ./rlife llsss-recentering --rule 'B25678/S4578' --filters wcaf c4k-1 '@zero' 20  --ends zero_and_halt -- --pre-reify-autochoke 550000000 > output.txt
error: unexpected argument '--pre-reify-autochoke' found

Usage: rlife llsss-recentering [OPTIONS] <GEOM> <PICTURE_FILE> <MID_STEPS>

For more information, try '--help'.

Is autochoke supported by WAO?

[Sokwe]

I cannot use autochoke with llsss-recentering. I'm trying to whittle down a knightship search to reduce the memory usage on my system.
...
Is autochoke supported by WAO?

Autochoke for llsss-recentering and llsss-recentering-wao searches is only available in the "exact-expand" branch of rlife. It's gone through some iterations, but the current most up-to-date is the one called 20241209-exact-expand-24.

I recommend that you only use the exact-expand branch when using autochoke for llsss-recentering and llsss-recentering-wao, because it slows down an ordinary non-autochoked search by about 15%.

Note that autochoke for llsss-recentering and llsss-recentering-wao works differently from autochoke for llsss. Autochoke in llsss looks at the not yet uniquely determined cells ('?' cells) shown in the "unique" view and forces some of them to a unique value, ordered based on the option --pre-reify-autochoke-type. For llsss-recentering and llsss-recentering-wao in the exact-expand branch, autochoke reduces the "width" (mid_steps) at each "depth" (w_pos).

KcNd-s2s is U=X+Y, V Kc/Nd northwest, W=-X+Y. This always produces tiles with 2N bit tiles.

I was trying to test this in the latest version, and I found that using --filters wcaf in diagonal s2s seems to cause an error:

Code: Select all

thread 'main' panicked at src/llsss/filter.rs:121:13:
assertion failed: check_window_size < S::SIZE

My inputs were

Code: Select all

./rlife llsss --rule 'B3/S23' --filters wcaf c4d-s2s '@zero:6'

and

Code: Select all

./rlife llsss-recentering --rule 'B3/S23' --filters wcaf c4d-s2s '@zero' 3

Without --filters wcaf they find the glider, as desired.

Unrelated: it was asked on Discord why LLSSS can take so long between printing the shortest partial and the random partial. Also, is LLSSS doing something essential during this process, or could the random (and shortest?) partial printing be disabled to slightly increase the speed of the search?

[amling]

While writing the tutorial section for B0 searches, I noticed that symmetric ends in B0 searches don't work correctly when using llsss or llsss-recentering. Unfortunately, they detect a small section of background agar as an "end":

Code: Select all

[INFO] End [thinnest] "LlsssEndsReflect(Even)":
[INFO] | ZZ | ZZ |
[INFO] | ** | .. |
[INFO] | ** | .. |
[INFO] | ** | .. |

Right, right. You're gonna have this problem with any agar. When I implemented the symmetric ends I did try to enhance the what-I-said definition (pattern ends with this symmetry) to the what-I-meant one, but did it specifically to the zero background (pattern ends with this symmetry and is not globally zero).

Arguably this definition is even more wrong for nonzero agar in that it would ignore an all-zero bottom which is a deviation from the agar. I struggle to imagine an actual case of this given it would have to be all zero and still match the agar in the left/right edges, but it's maybe a possibility.

I am not super excited about trying to communicate some notion of background agar down to those ends to make them any better in these cases.

[amling]

KcNd-s2s is U=X+Y, V Kc/Nd northwest, W=-X+Y. This always produces tiles with 2N bit tiles.

I was trying to test this in the latest version, and I found that using --filters wcaf in diagonal s2s seems to cause an error:

Code: Select all

thread 'main' panicked at src/llsss/filter.rs:121:13:
assertion failed: check_window_size < S::SIZE

My inputs were

Code: Select all

./rlife llsss --rule 'B3/S23' --filters wcaf c4d-s2s '@zero:6'

and

Code: Select all

./rlife llsss-recentering --rule 'B3/S23' --filters wcaf c4d-s2s '@zero' 3

Without --filters wcaf they find the glider, as desired.

A corner I cut to save memory use in the execution of WCAF that will not work in sufficiently bad-for-it geometries. "Check window size" is W overlap times tiles bits which here I believe will be 8. S is u8 which is the smallest scalar and I had figured would be enough based on how simple life was at the time. It needs one extra bit for bookkeeping reasons. I will probably just change the configuration to u16 when I am back home but that is going to be quite a while.

Unrelated: it was asked on Discord why LLSSS can take so long between printing the shortest partial and the random partial. Also, is LLSSS doing something essential during this process, or could the random (and shortest?) partial printing be disabled to slightly increase the speed of the search?

Both shortest and random partials are informational only and indeed can take serious time, especially depending on search. I am probably not personally willing to give up on some idea of what is happening in the search in my own projects so I never made a way to turn such on and off in the unified binaries. Originally this was all a toolkit for building search programs and it was believed users would do their own configuration in code anyway! If they were turned off searches wouldn't be saying or showing very much when they find no results, but I guess we could make options?

[Sokwe]

I am not super excited about trying to communicate some notion of background agar down to those ends to make them any better in these cases.

That's fine, since these searches can essentially be done with llsss-recentering-wao, and I've already noted this limitation in the tutorial.

A corner I cut to save memory use in the execution of WCAF that will not work in sufficiently bad-for-it geometries.... I will probably just change the configuration to u16

Could this have any noticeable negative consequences for the speed and memory use of other searches?

If they were turned off searches wouldn't be saying or showing very much when they find no results, but I guess we could make options?

I definitely think there should be options to disable any output feature that could make the search take substantially longer. However, would there still be enough information remaining at the end of the search to at least print a longest (in terms of w_pos) partial?

It also might be nice to have an option to make output less verbose, but I'm not sure what should remain and what should be suppressed with such an option. This is a very low priority, of course.

[amling]

A corner I cut to save memory use in the execution of WCAF that will not work in sufficiently bad-for-it geometries.... I will probably just change the configuration to u16

Could this have any noticeable negative consequences for the speed and memory use of other searches?

Could? Maybe. Modern compiler and hardware are crazy. My money is definitely on not though. The choices made a kind of local sense at the time: I needed a scalar but made it generic so it could be configured if it mattered and then later when configuring I thought less memory is better and surely no one could overrun u8. But really this is all silly: u8 operations aren't really gonna be any faster and we're saving at most an amount of memory smaller than the spine store (that thing whose memory size has never been relevant or optimized even once) and even that only at the trough of memory use, between expansion steps. Now that I'm thinking about it, even having it configurable was probably premature and I'm likely to just make it the same TB::VB that most scalars containing such data are (u64 in normal build).

If they were turned off searches wouldn't be saying or showing very much when they find no results, but I guess we could make options?

I definitely think there should be options to disable any output feature that could make the search take substantially longer. However, would there still be enough information remaining at the end of the search to at least print a longest (in terms of w_pos) partial?

"No" is the short answer to that. By the time the search state is empty there is nothing left to print. If the step that emptied it was expansion it techincally does have enough data about the pre-expand state to answer such a question but it's a mess to architect and this doesn't work at all if you have any sort of filtering happening (WCAF, maxpop, etc.) since the filtering could empty the state.

It also might be nice to have an option to make output less verbose, but I'm not sure what should remain and what should be suppressed with such an option. This is a very low priority, of course.

That (show less information and have less of an idea what is happening) is rather anathema to my personal style and values. If we were gonna do anything like that we'd probably invent or depend on a real logging library and let users at that.

[LaundryPizza03]

I cannot use autochoke with llsss-recentering. I'm trying to whittle down a knightship search to reduce the memory usage on my system.
...
[/code]
Is autochoke supported by WAO?

Autochoke for llsss-recentering and llsss-recentering-wao searches is only available in the "exact-expand" branch of rlife. It's gone through some iterations, but the current most up-to-date is the one called 20241209-exact-expand-24.

I recommend that you only use the exact-expand branch when using autochoke for llsss-recentering and llsss-recentering-wao, because it slows down an ordinary non-autochoked search by about 15%.

Note that autochoke for llsss-recentering and llsss-recentering-wao works differently from autochoke for llsss. Autochoke in llsss looks at the not yet uniquely determined cells ('?' cells) shown in the "unique" view and forces some of them to a unique value, ordered based on the option --pre-reify-autochoke-type. For llsss-recentering and llsss-recentering-wao in the exact-expand branch, autochoke reduces the "width" (mid_steps) at each "depth" (w_pos).

Still doesn't work. Error message is the same.

[Sokwe]

Still doesn't work. Error message is the same.

Are you sure you're using the exact-expand branch? I just tried your first input in the latest version, and it worked fine for me.

Try installing the exact-expand branch again. Start in a new folder and use

Code: Select all

git clone -b 20241209-exact-expand-24 https://codeberg.org/amling/rlife/

After that, compile as you would normally.

[LaundryPizza03]

Still doesn't work. Error message is the same.

Are you sure you're using the exact-expand branch? I just tried your first input in the latest version, and it worked fine for me.

Try installing the exact-expand branch again. Start in a new folder and use

Code: Select all

git clone -b 20241209-exact-expand-24 https://codeberg.org/amling/rlife/

After that, compile as you would normally.

I switched to 20241209-exact-expand-24 using git checkout, and it did not recognize the command. How do I recompile?

EDIT: Got it working through rebuilding cargo. Although I'm doubtful if WCAF is working correctly.

Code: Select all

20241216 20:58:08 [DEBUG] LlsssFilterWCycleAvoiding: Filtered w_pos 20[3] bcol: 17136137 -> 17136137
20241216 20:58:08 [DEBUG] LlsssFilterWCycleAvoiding: Filtered w_pos 20[3] col: 35599320 -> 35599320
20241216 20:58:08 [DEBUG] Completed w_pos 20[2]: 472.90 MB [+10.37%], 79.301171189s [+2.96%]
20241216 20:58:08 [INFO] Memory: total 472.90 MB (ss.old_gens 8.89 MB, ss.cur_gen 61.67 MB, bcol 130.74 MB, col 271.60 MB, left_edge 8 B, right_edge 8 B)
20241216 20:58:08 [INFO] Spine store sizes: old_gens [1, 24, 173, 533, 1300, 3342, 8633, 25483, 105095, 1020527], cur_gen 4041638
20241216 20:58:08 [INFO] Cols sizes: 17136137 / 35599320
20241216 20:58:08 [INFO] Shortest partial:
20241216 20:58:08 [INFO] |    |    | ZZ | ZZ |
20241216 20:58:08 [INFO] | ZZ | ZZ | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. | .. |
20241216 20:58:08 [INFO] | .. | .. | .. |    |
20241216 20:58:08 [INFO] | .. | .. |    |    |
20241216 20:58:15 [INFO] Random[ish] partial:
20241216 20:58:15 [INFO] |                              |                              |                 SS           |                 SS           |
20241216 20:58:15 [INFO] |                 SS           |                 SS           | ZZZZZZZZZZZZZZZZZZZZZZZZZZZZ | ZZZZZZZZZZZZZZZZZZZZZZZZZZZZ |
20241216 20:58:15 [INFO] | ZZZZZZZZZZZZZZZZZZZZZZZZZZZZ | ZZZZZZZZZZZZZZZZZZZZZZZZZZZZ | ............................ | ............................ |
20241216 20:58:15 [INFO] | ............................ | ............................ | ............................ | ............................ |
20241216 20:58:15 [INFO] | ............................ | ............................ | ............................ | ............................ |
20241216 20:58:15 [INFO] | ............................ | ............................ | ............................ | ............................ |
20241216 20:58:15 [INFO] | ............................ | ............................ | ............................ | .................****..*.... |
20241216 20:58:15 [INFO] | ..................*..*...... | ............................ | ..............*..**.****.... | ........................*... |
20241216 20:58:15 [INFO] | .........................*.. | ..............****.*.**.*... | ....................*..*.... | .............**..**......... |
20241216 20:58:15 [INFO] | ..............**.*.*.*..*... | ..................*......... | .............*..........*... | ..............*....*.**..... |
20241216 20:58:15 [INFO] | ................*...*****... | .............*..*...*..*.... | ..............*...*...*..... | ............*....*.*...*.... |
20241216 20:58:15 [INFO] | .............*..**.*....*... | ..........*...*.*.*....*.*.. | .............*...*.*........ | .........**...*............. |
20241216 20:58:15 [INFO] | ..........***..**.....*..... | ................**.....*.... | .........**.......*......... | ...........*.....*..*....... |
20241216 20:58:15 [INFO] | .............**..**.**...... | .........*............*..... | ..........*.........*....... | ......*............*........ |
20241216 20:58:15 [INFO] | ..........*........**....... | ...........*...**.***.*..... | ......***...*..........*.... | .........*.*...**........... |
20241216 20:58:15 [INFO] | ............**..*.**.*...... | ......**...*..**.*.......... | ...............**........... | ......*.**.*.**............. |
20241216 20:58:15 [INFO] | ......**......*............. | ...........*...*....*....... | ...*......*...*............. | .......*...**..*.*.......... |
20241216 20:58:15 [INFO] | ...........*.*....*......... | ...****.....***............. | .......***..***.*........... | ..**...*****.***............ |
20241216 20:58:15 [INFO] | ...**...********............ | .......*.***.**.*........... | ..*...*******.**............ | ......****...*.*............ |
20241216 20:58:15 [INFO] | ........*.**.*.*............ | ..*...*******.**............ | .....***********............ | ......*********.*........... |
20241216 20:58:15 [INFO] | ...**.***********........... | .....*.*....*..*............ | .......*****................ | ....*.****.**............... |
20241216 20:58:15 [INFO] | .......***.****............. | ........***.*..*.*.......... | .....*.....*..*............. | ....*..*****................ |
20241216 20:58:15 [INFO] | ....*..*****.*.**........... | ......**...**............... | ....*.***.***.**............ |                              |
20241216 20:58:15 [INFO] | ........*.**....*.*......... | ....****.*.*.*..**.*........ |                              |                              |

[Sokwe]

I'm doubtful if WCAF is working correctly.

Why do you doubt it? If it's because of the empty partials and excess empty rows at the top of partials, this is expected behavior, and is not indicative of failure or inefficiency, as detailed here. If it's because of some other issue, please be more specific.

I personally almost always use WAO to start with, although I've never been quite clear on the performance and search space differences between llsss-recentering and llsss-recentering-wao.

[LaundryPizza03]

I'm doubtful if WCAF is working correctly.

Why do you doubt it? If it's because of the empty partials and excess empty rows at the top of partials, this is expected behavior, and is not indicative of failure or inefficiency, as detailed here. If it's because of some other issue, please be more specific.

I personally almost always use WAO to start with, although I've never been quite clear on the performance and search space differences between llsss-recentering and llsss-recentering-wao.

Oky, it seems fine in hindsight. Try comparing the following two commands with or without "--pre-reify-autochoke 550000000", which I think are equivalent except for the search method:

Code: Select all

./rlife llsss-recentering-wao --rule B25678/S4578 c4k-1 '@zero' 20 --wao-left-pad 00 --wao-right-pad 00 --wao-idx ALL --ends zero_and_halt > output1.txt

./rlife llsss-recentering --rule 'B25678/S4578' --filters wcaf c4k-1 '@zero' 20  --ends zero_and_halt > output2.txt

[LaundryPizza03]

I'm doubtful if WCAF is working correctly.

Why do you doubt it? If it's because of the empty partials and excess empty rows at the top of partials, this is expected behavior, and is not indicative of failure or inefficiency, as detailed here. If it's because of some other issue, please be more specific.

I personally almost always use WAO to start with, although I've never been quite clear on the performance and search space differences between llsss-recentering and llsss-recentering-wao.

Oky, it seems fine in hindsight. Try comparing the following two commands with or without "--pre-reify-autochoke 550000000", which I think are equivalent except for the search method:

Code: Select all

./rlife llsss-recentering-wao --rule B25678/S4578 c4k-1 '@zero' 20 --wao-left-pad 00 --wao-right-pad 00 --wao-idx ALL --ends zero_and_halt > output1.txt

./rlife llsss-recentering --rule 'B25678/S4578' --filters wcaf c4k-1 '@zero' 20  --ends zero_and_halt > output2.txt

I ran two similar tests on a (2,1)c/5 problem in B358/S034 with width 12 and autochoking, and non-WAO autochokes sooner. Both searches seem to end after iteration 52[4].

output.txt

With llsss-recentering-wao

(3.71 MiB) Downloaded 138 times

output3.txt

With llsss-recentering

(4.84 MiB) Downloaded 130 times

[Katrina]

For some reason, I can't seem to get llsss to work sometimes, because most of the times I try to run it, I get this error:

Code: Select all

thread 'main' panicked at src/lat/grid.rs:184:9:
assertion failed: u_min <= u_max

There is no mention of this error anywhere else, so might as well post here

[Sokwe]

For some reason, I can't seem to get llsss to work sometimes, because most of the times I try to run it, I get this error:

Code: Select all

thread 'main' panicked at src/lat/grid.rs:184:9:
assertion failed: u_min <= u_max

There is no mention of this error anywhere else, so might as well post here

It would generally help if you provided some example input that caused the error here. You did provide the following example input on Discord:
1.in:

Code: Select all

| ...... |
| ...... |
| ..**.. |
| .????. |

Command:

Code: Select all

./rlife llsss c1-f2b --rule B2/S 1.in 0 0 0

Since you used the positional parameters 0 0 0, this means that you're not using the latest version. Anyone not using the latest version should update, as it's much easier to use now.

The problem with the above input is that you only gave one buffer column of empty cells on either side of 1.in, when you should have given two:

Code: Select all

| ........ |
| ........ |
| ...**... |
| ..????.. |

Here's what I think the (slightly simplified) technical problem is (Keith, correct me if I'm wrong): the program stores the search state essentially as a series of 3-column-wide vertical slices that overlap each other in 2 columns. So if we look at your original input, the leftmost '?' cell would be part of a 3-column-wide slice that extends off the board to the left. The program doesn't know how to construct that slice, because it doesn't know the state of the cells off the edge of the board.

So the program has to make a slice out of the leftmost 3 columns of the board, but this slice would then contain two '?' cells, which is not something easy to handle. This might get a bit trickier with wildcard ('W') cells, but I don't know enough about those to comment.