amling search program principles discussion / brain dump

[Sokwe]

I have now reviewed and published everything I had worked on when out of town:

Thanks! I've updated the tutorial to replace "zero" with "bg" where necessary, but I'm keeping all the search setups the same for now, since they all still work. I will change them to use --bg-agar and @bg when I'm sure most people have switched to the latest version.

I have updated it (with only minor conflicts) for master as of just now and published as "20250127-exact-expand-25". I don't know how long this branch (family) is going to be manageable. I know for certain the work I did while out of town is going to conflict with it horribly. I guess we'll see how it goes and I will try to remember to include the status in the announcement when I clean up and publish all that work.

Exact expand branch family updated to include all this as "20250127-exact-expand-26".

When you say that "the work I did... is going to conflict with [exact-expand] horribly", are you referring only to the hollow cols (which, as I understand it, is disabled by default), or is there any reason to think that the "20250127-exact-expand-26" branch doesn't work as well as "20250127-exact-expand-25"? I don't particularly expect or want the exact-expand branch to be maintained. I just want it to accept the same inputs that are covered in my basic LLSSS tutorial, so that someone who has read the tutorial can simply apply --pre-reify-autochoke to their basic recentering searches.

Regarding the tutorial, I think I have a decent example for the seam ripper section, but I'm curious about something. Can you tell me what w_pos the following search needs to reach to find a ship and how much memory it takes?

Code: Select all

./rlife llsss --rule 'B2357/S3678' --filters wcaf --ends even,odd,gse,gso 2c2-s2s '@zero:31'

For me it starts to use excessive amounts of memory around w_pos 48[0]. Ideally, I want an example search that is hard to complete at the full width, but that can be completed from a SRV2 partial. In this case, I can add "--partials srv2:2:8 --halts w_pos:45" to get a good partial result that can be extended and completed at a lower width.

I suspect that the following p4 c/4 diagonal ship (found by Artem Dergachev) is the smallest possible at 28 cells, but my computer doesn't quite have enough memory to confirm this:

This is an example of a place where WAO tile error mask can save some time and memory.... With "--wao-tile-error-mask 8" pop 28 finished in 2198s and 7.91 GB, finding the ship exactly once (with one extra copy marked as duplicate).

Unfortunately I have no idea how to make [WAO tile error masks] anything resembling usable. I don't think the code working out the right value is going to be possible when I can't even personally figure out c6k-1 even with just zeros, much less arbitrary insane geometries with complicated input files.

As a first approximation, for from-zeros or from-agar searches: Named geometries that are b2f or f2b cannot benefit from tile error mask. s2s geometries that are not NcN-s2s I believe can always benefit (although I didn't demo/explain this above...). Diagonal and knightwise that are not NcNd-down or NcNd-up I believe can always benefit from it.

I fear using this because I'm worried I'll do it wrong and make my search incomplete due to me not fully understanding the geometry stuff. Although you don't have a perfect programatic solution, is it possible (and reasonably easy) to implement a sort of simplified "suggested" error mask that is maybe not ideal, but is at least guaranteed to not miss anything for the given geometry? Does the proper error mask actually depend on the start_file in addition to the geometry?

I've changed the error window displays to reflect the constraints that will actually happen. Periods and asterisks are fixed values. x/o are jointly forced to mismatch. Ws are unconstrained. For example, c4d-down:

Code: Select all

$ rlife llsss-recentering-wao c4d-down '@zero' --wao-left-pad 00 --wao-right-pad 00 00
20241210 14:45:50 [INFO] WAO error window #0 (excluded):
20241210 14:45:50 [INFO] | ZZZZZ | ZZZZZ | ZZZZZ | ZZZZZ |
20241210 14:45:50 [INFO] | ..... | ..... | ..... | ..... |
20241210 14:45:50 [INFO] | ..... | ..... | ..... | ..... |
20241210 14:45:50 [INFO] | ..xWW | ..xWW | ..xWW | ..xWW |
...

When you say "x/o are jointly forced to mismatch", do you mean that at least one must mismatch? So you could have any combination of states for those 'x' cells as long as at least one of them is alive?

Edit: Let me know if I'm getting this right. Are the 'x' cells meant to represent dead cells? So the setup shown above represents a window that has been excluded from the search, namely the one where all 'x' cells are dead (i.e., at least one of the 'x' cells must be alive in the actual search)?

Edit: what is the default value of --wao-idx?

[amling]

I have updated it (with only minor conflicts) for master as of just now and published as "20250127-exact-expand-25". I don't know how long this branch (family) is going to be manageable. I know for certain the work I did while out of town is going to conflict with it horribly. I guess we'll see how it goes and I will try to remember to include the status in the announcement when I clean up and publish all that work.

Exact expand branch family updated to include all this as "20250127-exact-expand-26".

When you say that "the work I did... is going to conflict with [exact-expand] horribly", are you referring only to the hollow cols (which, as I understand it, is disabled by default), or is there any reason to think that the "20250127-exact-expand-26" branch doesn't work as well as "20250127-exact-expand-25"? I don't particularly expect or want the exact-expand branch to be maintained. I just want it to accept the same inputs that are covered in my basic LLSSS tutorial, so that someone who has read the tutorial can simply apply --pre-reify-autochoke to their basic recentering searches.

Even though hollow cols is disabled by default (or rather the jcol store is configured to be the "old" one), there are changes to the structure of the shared code to allow switching between them. By "conflict ... horribly" I mean there are going to be a bunch of source control conflicts, or rather that there were and I have fixed them all. I am reasonably confident between the strength of merge tools and the strength of rust's type system that the new code is likely to be correct.

Unfortunately "be maintained" is about the only option. I am even less keen on trying to backport individual features to it. It's still fine for now and I guess I'm just trying to ease us all into its inevitable death at the hands of bit rot.

Regarding the tutorial, I think I have a decent example for the seam ripper section, but I'm curious about something. Can you tell me what w_pos the following search needs to reach to find a ship and how much memory it takes?

Code: Select all

./rlife llsss --rule 'B2357/S3678' --filters wcaf --ends even,odd,gse,gso 2c2-s2s '@zero:31'

For me it starts to use excessive amounts of memory around w_pos 48[0]. Ideally, I want an example search that is hard to complete at the full width, but that can be completed from a SRV2 partial. In this case, I can add "--partials srv2:2:8 --halts w_pos:45" to get a good partial result that can be extended and completed at a lower width.

I cannot, at least not without waiting for time on a bigger computer. 60GB only manages to complete w_pos 52[1] at which point it has found no results.

(scary WAO stuff)

I fear using this because I'm worried I'll do it wrong and make my search incomplete due to me not fully understanding the geometry stuff. Although you don't have a perfect programatic solution, is it possible (and reasonably easy) to implement a sort of simplified "suggested" error mask that is maybe not ideal, but is at least guaranteed to not miss anything for the given geometry? Does the proper error mask actually depend on the start_file in addition to the geometry?

Yeah, fear is an absolutely reasonable response... I will have some more thoughts/notes on this in a minute.

I've changed the error window displays to reflect the constraints that will actually happen. Periods and asterisks are fixed values. x/o are jointly forced to mismatch. Ws are unconstrained. For example, c4d-down:

Code: Select all

$ rlife llsss-recentering-wao c4d-down '@zero' --wao-left-pad 00 --wao-right-pad 00 00
20241210 14:45:50 [INFO] WAO error window #0 (excluded):
20241210 14:45:50 [INFO] | ZZZZZ | ZZZZZ | ZZZZZ | ZZZZZ |
20241210 14:45:50 [INFO] | ..... | ..... | ..... | ..... |
20241210 14:45:50 [INFO] | ..... | ..... | ..... | ..... |
20241210 14:45:50 [INFO] | ..xWW | ..xWW | ..xWW | ..xWW |
...

When you say "x/o are jointly forced to mismatch", do you mean that at least one must mismatch? So you could have any combination of states for those 'x' cells as long as at least one of them is alive?

Edit: Let me know if I'm getting this right. Are the 'x' cells meant to represent dead cells? So the setup shown above represents a window that has been excluded from the search, namely the one where all 'x' cells are dead (i.e., at least one of the 'x' cells must be alive in the actual search)?

Yes, exactly. "x" / "o" mean cells that were dead / alive in the original prompt. By "jointly mismatch" I mean at least one must mismatch and for all dead cells I mean that at least one must be on.

Edit: what is the default value of --wao-idx?

Defaults to empty list. In its original use I was always running individual indices separately and so I would run it once to dump out the range, then set up runs one per index (and in some cases remove ones I knew were uselessly doomed). "ALL" was added as an afterthought.

It could probably be changed to default to "ALL" and add a "NONE" for when I just want to dump the list. Same sort of thing is true of pads: defaulting to 1 made sense for the sort of work it was doing originally but maybe that is no longer the most common mode of operation.

Shall I change these deffaults to ALL/0/0? Nearly all of my search projects specify them all explicitly anyway...

[amling]

I thought more about this and realized we sort of need two masks here...

First, note that until just now there was a mistake in the error window display, e.g. c4d-down with mask 8 (0b1000) shows:

Code: Select all

WAO error window #0 (excluded):
| ZZZZZ | ZZZZZ | ZZZZZ | ZZZZZ |
| ..... | ..... | ..... | ..... |
| ..... | ..... | ..... | ..... |
| ...WW | ...WW | ...WW | ..xWW |

But that's neither really what you want, nor what it turns out to do. The tile error mask applies everywhere right of the critical tile as well and it's really doing this:

Code: Select all

WAO error window #0 (excluded):
| ZZZZZ | ZZZZZ | ZZZZZ | ZZZZZ |
| ..... | ..... | ..... | ..... |
| ..... | ..... | ..... | ..... |
| ..... | ..... | ..... | ..xWW |

But now think about what happens for c2-s2s: with no mask it's:

Code: Select all

| ZZZZZ | ZZZZZ |
| ..... | ..... |
| ..... | ..... |
| ..xWW | ..xWW |

But this is wasteful, finding each start in two distinct positions. I'd like to do mask 2 (0b10), but that is:

Code: Select all

| ZZZZZ | ZZZZZ |
| ..... | ..... |
| ..... | ..... |
| ..... | ..xWW |

Which of course isn't right. Really I want:

Code: Select all

| ZZZZZ | ZZZZZ |
| ..... | ..... |
| ..... | ..... |
| ...WW | ..xWW |

Where it's mask 2 in the critical tile but mask 3 (0b11, effectively unmasked) in tiles right of that. A most general case would be something silly like c2-s2s with W=2Y (raw:1:0:0:-1:0:2:0:2:0), picked only to demonstrate the theory. Unmasked it's:

Code: Select all

| ZZZZZ | ZZZZZ |
| ZZZZZ | ZZZZZ |
| ..... | ..... |
| ..... | ..... |
| ..xWW | ..xWW |
| ..xWW | ..xWW |

And what we want is:

Code: Select all

| ZZZZZ | ZZZZZ |
| ZZZZZ | ZZZZZ |
| ..... | ..... |
| ..... | ..... |
| ..... | ..... |
| ...WW | ..xWW |

The critical tile has been masked to just the one bit (8 = 0b1000) while the tiles right of it have been masked to both the W-most bits (12 = 0b1100).

The general case I believe is the critical tile should be the bits with the lexically greatest (fractional W, fractional U) value. This much I had right when I was last musing about this above. The thing I got wrong (and thankfully I believe haven't run any e.g. c6k-1 searches with the bad mask), is that in the tiles right of there it needs to be any bits with just that maximum fractional W value (even if they have lesser fractional U values).

The argument for the exhaustiveness of this depends on being able to shift a hypothetical partial by any amount (XYT) which is true for a homogenous agar like all-zeros, but the truth is maybe more complicated in other cases.

E.g. consider this single, explicit input file for a B0 search:

Code: Select all

| ZZZ | ZZZ |
| ... | *** |
| ... | *** |
| ... | *** |

Even if you did the split masks of 2 (0b10), 3 (0b11) you'd have:

Code: Select all

| ZZZZZ | ZZZZZ |
| ..... | ***** |
| ..... | ***** |
| ...WW | **oWW |

Which isn't exhaustive (the first mismatch could be in a should-have-been-zero cell).

This problem doesn't apply to "@agar" magic grids since they do include every phasing of the agar (and so any hypothetical partial and hypothetical shift will still be covered) and so for b0 and split masks of 2 (0b10), 3 (0b11) you'd have:

Code: Select all

WAO error window #0 (excluded):
| ZZZZZ | ZZZZZ |
| ***** | ..... |
| ***** | ..... |
| ***WW | ..xWW |
WAO error window #1 (excluded):
| ZZZZZ | ZZZZZ |
| ..... | ***** |
| ..... | ***** |
| ...WW | **oWW |

Given the complex correctness in the face of interesting input files I'm a little hesitant to compute the masks as above and make them default but adding an explicit --wao-tile-use-computed-error-masks-why-do-I-even-have-to-say-this seems a little silly.

Maybe I should to split out the from-agar WAO search as a separate subcommand? Many of the options and most of the code would still be shared but we'd get rid of a lot of the less sensible options and fix a lot of defaults:

(*) start_file: gone, hard-coded to "@bg"
(*) top_pad: extra gone, hard-coded to zero
(*) wao_left_pad/wao_right_pad: default 0, maybe not even an option?
(*) left_edge/right_edge: only bg or symmetries allowed
(*) wao_left_edge_errors/wao_right_edge_errors: decided from edge
(*) wao_tile_error_mask(s): computed per above, now reasonably safe
(*) wao_idx: default ALL, maybe not even an option

At a minimum I will fix the window display, change it to take two masks, and put something to compute them somewhere (either in geom-info or as a separate command).

[Sokwe]

Unfortunately "be maintained" is about the only option. I am even less keen on trying to backport individual features to it. It's still fine for now and I guess I'm just trying to ease us all into its inevitable death at the hands of bit rot.

That's fine. I only really care about it working with the features covered by the basic tutorial, which I suspect will not change too much going forward, and future differences will probably be small enough that I can reasonably easily explain them.

Can you tell me what w_pos the following search needs to reach to find a ship and how much memory it takes?

I cannot, at least not without waiting for time on a bigger computer. 60GB only manages to complete w_pos 52[1] at which point it has found no results.

That's perfect! No need to search further. It means that the initial search can't be completed by the average user, but it's relatively easy to extend a choke partial to get a complete spaceship.

Shall I change these defaults to ALL/0/0? Nearly all of my search projects specify them all explicitly anyway...

In my opinion, yes. These are the settings for basic spaceship searches, which is what I suspect the average user will run the most.

Maybe I should to split out the from-agar WAO search as a separate subcommand? Many of the options and most of the code would still be shared but we'd get rid of a lot of the less sensible options and fix a lot of defaults:

(*) start_file: gone, hard-coded to "@bg"
(*) top_pad: extra gone, hard-coded to zero
(*) wao_left_pad/wao_right_pad: default 0, maybe not even an option?
(*) left_edge/right_edge: only bg or symmetries allowed
(*) wao_left_edge_errors/wao_right_edge_errors: decided from edge
(*) wao_tile_error_mask(s): computed per above, now reasonably safe
(*) wao_idx: default ALL, maybe not even an option

Would those really not be sensible options for a from-agar WAO search? Maybe I'm just not understanding exactly what you're saying here. I certainly don't know enough to have an opinion on this matter. The main reason I'm interested in the WAO tile error masks is because it can evidently make searches run faster and take less memory, which is useful for my low-spec laptop.

[amling]

Maybe I should to split out the from-agar WAO search as a separate subcommand? Many of the options and most of the code would still be shared but we'd get rid of a lot of the less sensible options and fix a lot of defaults:

(*) start_file: gone, hard-coded to "@bg"
(*) top_pad: extra gone, hard-coded to zero
(*) wao_left_pad/wao_right_pad: default 0, maybe not even an option?
(*) left_edge/right_edge: only bg or symmetries allowed
(*) wao_left_edge_errors/wao_right_edge_errors: decided from edge
(*) wao_tile_error_mask(s): computed per above, now reasonably safe
(*) wao_idx: default ALL, maybe not even an option

Would those really not be sensible options for a from-agar WAO search? Maybe I'm just not understanding exactly what you're saying here. I certainly don't know enough to have an opinion on this matter. The main reason I'm interested in the WAO tile error masks is because it can evidently make searches run faster and take less memory, which is useful for my low-spec laptop.

Some really are not sensible like start_file and top_pad. Left/right pad and idx I guess still make sense but certainly want different defaults. Edge options other than asymmetric ("bg") or symmetries I guess could make a sense in that we could run a search but seriously what else is there? There are a few others but they are uncommon (I'm guessing I am the only one who has ever seriously used any of them) and they sort of cast uncertainty on what the values for wao_xxx_edge_errors and wao_tile_error_mask(s) should be. I'm mostly trying to chop off uncommon/unlikely options here to make a simple enough setup to be more confident guessing values for those.

[amling]

I've changed the WAO left/right pad defaults to 0. I've changed the WAO idx defaults to "ALL". "NONE" can be used to explicitly run nothing.

I've written code to compute the "maximal" masks discussed above and display them as part of "geom-info", e.g. for that silly c2-s2s/W=2Y geometry:

Code: Select all

$ rlife grid-tool geom-info 'raw:1:0:0:-1:0:2:0:2:0'
Geometry: raw:1:0:0:-1:0:2:0:2:0
   U: Vec3(1, 0, 0)
   V: Vec3(-1, 0, 2)
   W: Vec3(0, 2, 0)
   Neighborhood sizes:
      U: 3
      W: 2
   Unique positions (4):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(2, 2, 0)
      #2: Vec3(0, 1, 0) => Vec3Uvw(0, 0, 2)
      #3: Vec3(0, 1, 1) => Vec3Uvw(2, 2, 2)
   WAO maximal tile masks: WaoTileMasks(8 = 0b1000, 12 = 0b1100)
$

I've also changed the internals and CLI to use two masks. You can still provide just one mask which will then be used as both, to match the current behaviour. As an example you could use --wao-tile-error-mask 8:12 to set the above:

Code: Select all

$ rlife llsss-recentering-wao 'raw:1:0:0:-1:0:2:0:2:0' '@zero' --wao-tile-error-mask 8:12 --wao-idx NONE 00
20250129 16:56:29 [INFO] WAO error window #0 (excluded):
20250129 16:56:29 [INFO] | ZZZZZ | ZZZZZ |
20250129 16:56:29 [INFO] | ZZZZZ | ZZZZZ |
20250129 16:56:29 [INFO] | ..... | ..... |
20250129 16:56:29 [INFO] | ..... | ..... |
20250129 16:56:29 [INFO] | ..... | ..... |
20250129 16:56:29 [INFO] | ...WW | ..xWW |
...
$

Or --wao-tile-error-mask 12 to get:

Code: Select all

$ rlife llsss-recentering-wao 'raw:1:0:0:-1:0:2:0:2:0' '@zero' --wao-tile-error-mask 12 --wao-idx NONE 00
20250129 16:58:55 [INFO] WAO error window #0 (excluded):
20250129 16:58:55 [INFO] | ZZZZZ | ZZZZZ |
20250129 16:58:55 [INFO] | ZZZZZ | ZZZZZ |
20250129 16:58:55 [INFO] | ..... | ..... |
20250129 16:58:55 [INFO] | ..... | ..... |
20250129 16:58:55 [INFO] | ..... | ..... |
20250129 16:58:55 [INFO] | ..xWW | ..xWW |
...
$

You can also use "MAX" as a shorthand for the former:

Code: Select all

$ rlife llsss-recentering-wao 'raw:1:0:0:-1:0:2:0:2:0' '@zero' --wao-tile-error-mask MAX --wao-idx NONE 00
20250129 16:57:51 [INFO] WAO error window #0 (excluded):
20250129 16:57:51 [INFO] | ZZZZZ | ZZZZZ |
20250129 16:57:51 [INFO] | ZZZZZ | ZZZZZ |
20250129 16:57:51 [INFO] | ..... | ..... |
20250129 16:57:51 [INFO] | ..... | ..... |
20250129 16:57:51 [INFO] | ..... | ..... |
20250129 16:57:51 [INFO] | ...WW | ..xWW |
...
$

Contrast all of these with the unmasked:

Code: Select all

$ rlife run llsss-recentering-wao 'raw:1:0:0:-1:0:2:0:2:0' '@zero' --wao-idx NONE 00
20250129 17:06:28 [INFO] WAO error window #0 (excluded):
20250129 17:06:28 [INFO] | ZZZZZ | ZZZZZ |
20250129 17:06:28 [INFO] | ZZZZZ | ZZZZZ |
20250129 17:06:28 [INFO] | ..... | ..... |
20250129 17:06:28 [INFO] | ..... | ..... |
20250129 17:06:28 [INFO] | ..xWW | ..xWW |
20250129 17:06:28 [INFO] | ..xWW | ..xWW |
...
$

The bottom line for most people should be: no need to specify idxs or pads any more and --wao-tile-error-mask MAX if you're in a geometry where it will help. Consider checking in here (or tagging me on another thread) if you're using the latter, especially for a negative result.

I've updated the exact expand branch with this as well, as 20250129-exact-expand-27.

[Sokwe]

You can also define a custom one in a separate file and load that:

Code: Select all

$ cat checkerboard.agar
{
    vu: [2, 0, 0],
    vv: [0, 0, 1],
    vw: [1, 1, 0],
    cells: [
        [[0, 0, 0], false],
        [[1, 0, 0], true],
    ],
}

There was some discussion on Discord about custom agars that I would like to briefly cover here for visibility and to see if Amling or anyone else has any thoughts or opinions.

Consider the following agar of dots:

Code: Select all

x = 20, y = 20, rule = B1c2ce3cey4/S:T20,20
obobobobobobobobobo2$obobobobobobobobobo2$obobobobobobobobobo2$obobobo
bobobobobobo2$obobobobobobobobobo2$obobobobobobobobobo2$obobobobobobob
obobo2$obobobobobobobobobo2$obobobobobobobobobo2$obobobobobobobobobo!

If we think of this agar as p2, we can write an agar file like so (saved as p2-dots.agar):

Code: Select all

{
    vu: [2, 0, 0],
    vv: [0, 0, 2],
    vw: [0, 2, 0],
    cells: [
        [[0, 0, 0], true],
        [[1, 0, 0], false],
        [[0, 1, 0], false],
        [[1, 1, 0], false],
        [[0, 0, 1], false],
        [[1, 0, 1], false],
        [[0, 1, 1], false],
        [[1, 1, 1], true],
    ],
}

We can perhaps think of this in the following way: U = (2, 0, 0) means that the agar has width 2, W = (0, 2, 0) means the agar has height 2, and V = (0, 0, 2) means the agar has velocity (0, 0)c/2. The cell setting "[[0, 0, 0], true]" means that the cell at (0, 0) in generation 0 is on; The cell setting "[[1, 0, 1], false]" means that the cell at (1, 0) in generation 1 is off; etc.

This works fine if we want to find a 2c/6 orthogonal crawler like with the following command:

Code: Select all

./rlife llsss-recentering-wao --rule 'B1c2ce3cey4/S' --bg-agar '@dots.agar' --left-edge odd --wao-left-edge-errors 2c6-f2b '@bg' 10

giving the following output (crawler found by Sylvani):

Code: Select all

x = 36, y = 42, rule = B1c2ce3cey4/S:T36,42
obobobobobobobobobobobobobobobobobo2$obobobobobobobobobobobobobobobobo
bo2$obobobobobobobobobobobobobobobobobo2$obobobobobobobobobobobobobobo
bobobo2$obobobobo7bobo7bobobobobo$8b2obo4bobo4bob2o$obobob2o3bo11bo3b
2obobobo$9bo3bo7bo3bo$obobobobobobo9bobobobobobobo$10bobobobobobobobo$
obobobo2bo15bo2bobobobo$10bobo9bobo$obobobobobob2o2bobo2b2obobobobobob
o$10bo13bo$obobobob2o3bob5obo3b2obobobobo$8bobo13bobo$obobob2ob3obobo
3bobob3ob2obobobo$8b2o15b2o$obobobobob2obobobobobob2obobobobobo2$obobo
bobo4bobobobobo4bobobobobo2$obobobobobo2bobobobobo2bobobobobobo2$obobo
bobobo2bo7bo2bobobobobobo2$obobobobobobobobobobobobobobobobobo2$obobob
obobobo4bo4bobobobobobobo2$obobobobobobobob3obobobobobobobobo2$obobobo
bobobobobobobobobobobobobobo2$obobobobobobobobobobobobobobobobobo2$obo
bobobobobobobobobobobobobobobobo!

However, this agar file is not compatible with odd-period crawlers, even though such crawlers are potentially possible as long as they have odd displacement in both the X and Y directions. For example, if you run the following search for a c/3 diagonal crawler

Code: Select all

./rlife llsss-recentering-wao --rule 'B1c2ce3cey4/S' --bg-agar '@p2-dots.agar' c3d-f2b '@bg' 4

you get the following error:

Code: Select all

Geom V (Vec3(-1, -1, 3)) is not compatible with agar "@p2-dots.agar"

You could try searching for a 2c/6 diagonal crawler and hope to find a p3 crawler among the output, but the search will be slower, use more memory, and you might have to wade through small p6 solutions like the following:

Code: Select all

x = 20, y = 20, rule = B1c2ce3cey4/S:T20,20
obobobobobobobobobo2$obobobobobobobobobo2$obobobobobobobobobo2$obobobo
bobobobobobo$8bo$obobob2o4bobobobo2$obobobobobobobobobo2$obobobobobobo
bobobo2$obobobobobobobobobo2$obobobobobobobobobo2$obobobobobobobobobo!

We can instead view the agar as a period-1 agar the travels 1 cell diagonally each period. Here we change the velocity vector V = (X, Y, T) to (1, 1, 1), and since the agar is p1, we only need to define half as many cell states (saved as dots.agar):

Code: Select all

{
    vu: [2, 0, 0],
    vv: [1, 1, 1],
    vw: [0, 2, 0],
    cells: [
        [[0, 0, 0], true],
        [[1, 0, 0], false],
        [[0, 1, 0], false],
        [[1, 1, 0], false],
    ],
}

Now the command

Code: Select all

./rlife llsss-recentering-wao --rule 'B1c2ce3cey4/S' --bg-agar '@dots.agar' c3d-f2b '@bg' 4

quickly finds the following period-3 c/3 diagonal crawler:

Code: Select all

x = 20, y = 20, rule = B1c2ce3cey4/S:T20,20
obobobobobobobobobo2$obobobobobobobobobo2$obobobobobobobobobo2$obobobo
bobobobobobo$8bo$obobob2o2bobobobobo2$obobob2ob2obobobobo2$obobobo2b2o
bobobobo2$obobobobob2o2bobobo2$obobobobobobobobobo2$obobobobobobobobob
o!

Is this the best way to set up this custom agar? Are there any other "tricks" to creating custom agar files?

[amling]

Is this the best way to set up this custom agar? Are there any other "tricks" to creating custom agar files?

Perhaps a lot could be said about such lattices and their generators. The shortest version is that you should ideally be picking some set of generators of the lattice of shift symmetries (symmetries in the abstract algebra sense). In this case 2X, 2Y, and X+Y+T will do.

Picking a multiple like 2X, 2Y, 2T still works in general, but, as you have seen, precludes some velocities as not-seemingly-compatible. I suppose we could take the agar as presented and compute any other missed shifts ourselves but it just doesn't seem worth the code.

Notice that in the multiplied up case you have multiple representatives of the same essential cell in the agar ((0, 0, 0) and (1, 1, 1) I would say are in the same apparent position e.g.) whereas when you have the shift symmetries chosen correctly there will be no duplicates. In the case of this agar the three off cells actually are distinct positions.

If we really wanted to we could probably write tools to help figure these things out but it's just never that difficult and I assumed people would be defining agars very rarely.

EDIT: Rereading the above I realize that maybe it's not clear, but the vectors U, V, and W for agars are not distinguished in any way (unlike geometries where U/V/W have very distinct meanings like V is ship period and W is build direction). They're just three vectors that had better be linearly independent and mod which the specified cells had better cover all of XYT space uniquely.

[CARuler]

You could use such a tool to find crawlers
By using things such as

Code: Select all

x = 10, y = 10, rule = B3/S23:T10,10
3$4bo$5bo$3b3o!

Perhaps it could be implemented using just the initial pattern, hight, width and period?

[Sokwe]

You could use such a tool to find crawlers
By using things such as

Code: Select all

x = 10, y = 10, rule = B3/S23:T10,10
3$4bo$5bo$3b3o!

I don't think I follow. LLSSS can already find crawlers, as demonstrated by my post above. I'm not sure how the glider on the torus is used here.

Perhaps it could be implemented using just the initial pattern, hight, width and period?

I suppose it's up to Amling, but I think the agar file format is simple enough that extra tools aren't needed. If there's a particular agar you want to implement, you could post it in this thread (maybe along with your attempt at an agar file), and somebody could probably help construct a working agar file.

[amling]

I was thinking some more about the splitting of patterns into ships especially given the mess of *WSSes I'm now swimming in.

There's really no debate that neighboring live cells need to be connected (otherwise you get serious pathologies like deleting a negative ship from a nightship in a reversible rule is considered a valid split). And there's really no debate that surviving cells need to be connected to their futures and parents to their children. The problem is what to do on non-births where there are multiple otherwise-disconnected components in the neighborhood.

Historically, the EDBV3 ingest code has considered neighborhood cells connected in the case of an overpop birth suppression but not in an underpop birth suppression. This distinction of underpop/overpop and the monotoneness (subset of underpop is always underpop) is sort of a luxury of the specific nature of B3-only where there is no middle like say a B4 neighborhood in a rule with exactly B35. Humans seem to view overpop suppressions as not necessarily connected though so this definition (connect overpop but don't connect underpop) is somewhat a problem.

As I was thinking about this I realized that it's only neighborhoods with more than 2 otherwise-connected components that are a problem. 1 component neighborhoods behave the same taking any subset of components. In 2 components neighborhoods either both components correctly do not birth the cell when cut apart, in which case we can consider them disconnected (and any subset will work apart) or one (or both) of them would birth the cell in which case we can consider them connected and merge the components. As long as there are no 3+ component neighborhoods, merging components like this isn't a problem since at most a 2 component neighborhood can become a 1 component neighborhood.

Constructing spaceships (or quasi spaceships or pseudo spacerships or not-quite spaceships or whatever we'd call them) where there is such a 3+ component neighborhood and some subset of components does something bad may or may not even be possible in plain old B3/S23 and I guess any hypothetical classifier could ignore the case (panic) until we find one.

I implemented this sort of splitter/classifier and it somewhat reduces for example the mess of 201 patterns I posted earlier for that 2c/4 pop 32 search. TBD further uses.



I was also thinking some more about the maxpop halting condition. Right now it's that there is a state-global "chasm" of an entire W overlap somewhere. This is certainly sufficient to guarantee no more valid (connected) partials but it's far from necessary. I tried to come up with a more accurate condition but haven't had much in the way of great ideas.

The best so far is to DFS through all partials similar to how the current maxpop ends do and look to see if there are any that actually connect the top to the bottom. Similar to the DFS for maxpop ends there is no need to step through a vertical slice of all zeros. I had started implementing this but realized DFS won't work since there can be vertical slices that contribute zero population in the key generation but aren't zero in other generations (and so there are cycles in the graph the DFS would be over). This is easy enough to get around with keeping a set of visitted nodes but it gets expensive in memory. The other question is what defines "actually connect the top to the bottom". Correctly adjudicating this exactly is a nightmare and I opted instead for the same horizontal chasm trick. If there is a horizontal chasm somewhere in the partial then it definitely doesn't connect the top to the bottom. This is still enough to eventually trigger (when the search is deep enough) via a simple density argument, but of course who knows if performance will pan out.

I ran 2c/4 to pop 24 (where I believe the first interesting ships are), taking maybe ~15m total. Unfortunately I did not get the final VmPeak values for a stupid reason but I suspect they were in the 10GB-20GB range.

Feeding the logs through the newer splitter produces the following 26 results. It's a lot of useless *WSS-on-*WSS and minimal spark interactions, but I do notice both pop 24 entries from jslife-moving are there (which is good considering this is supposed to be exhaustive).

Code: Select all

#C [[ TRACK 0 -1/2 ]]
x = 11, y = 444, rule = B3/S23
3o$o2bo$o$o$bobo11$3o$o2bo$o$o3bo$o$bobo11$3o$o2bo$o$o3bo$o3bo$o$bobo
11$3o3b3o$o2bobo2bo$o7bo$o7bo$o3b2obo$bobo11$3o3b3o$o2bobo2bo$o7bo$o7b
o$o4bobo$o$bobo11$3o3b3o$o2bobo2bo$o7bo$o7bo$o7bo$bobobobo11$3o$o2bo$o
5b3o$o4bo2bo$o7bo$o7bo$bobobobo11$3o$o2bo$o5b3o$o4bo2bo$o7bo$bobo4bo$
8bo$5bobo11$3o3b3o$o2bobo2bo$o7bo$o7bo$o7bo$o3b2obo$bobo11$3o3b3o$o2bo
bo2bo$o7bo$o7bo$o7bo$o7bo$bobobobo11$3o4b3o$o2bo2bo2bo$o8bo$o3bo4bo$o
3bobobo$o$bobo11$3o$o2bo$o5b3o$o4bo2bo$o7bo$o7bo$bob2o3bo$5bobo11$3o$o
2bo$o5b3o$o4bo2bo$o7bo$o7bo$bobo4bo$8bo$5bobo11$3o$o2bo$o5b3o$o4bo2bo$
o7bo$bobo4bo$4bo3bo$8bo$5bobo11$3o$o2bo3b3o$o5bo2bo$o8bo$bobobo3bo$5bo
3bo$9bo$6bobo11$3o$o2bo$o6b3o$o5bo2bo$bobo5bo$5bo3bo$5bo3bo$9bo$6bobo
11$3o$o2bo$o$o3bo2b3o$o3bobo2bo$o8bo$bobo5bo$6bobo11$3o4bo$o2bo2b3o$o
4b2obo$o3b4o$o5b2o$bobo11$8bo$3o4b3o$o2bo2b2obo$o5b3o$o3bo2b2o$o$bobo
11$3o5b3o$o2bo3bo2bo$o9bo$o3bobo3bo$o3bo5bo$o6bobo$bobo11$3o$o2bo$o$o
5bo$o4b3o$bo3bob2o$6b3o$6b3o$6b2o11$3o$o2bo$o$o3bo2b3o$o5bo2bo$bobo5bo
$5bo3bo$5bo3bo$9bo$6bobo11$3o$o2bo4b3o$o6bo2bo$o3bo5bo$o3bobo3bo$o9bo$
bobo3bobo11$3o$o2bo4b3o$o6bo2bo$o3bo5bo$o5bo3bo$bobo2bo3bo$10bo$7bobo
11$3o$o2bo$o7b3o$o3bo2bo2bo$o3bo5bo$o5bo3bo$bobo6bo$7bobo11$6b3o$3o3bo
2bo$o2bo2bo$o5bo$o3bobo$o3bo$o5b3o$bobo!

TBD improving memory performance with careful storage, improving time performance with parallelization of the visitted nodes, if I can/should push 2c/4 higher than pop 24, if I can push c/3 to pop 50+, etc.

[confocaloid]

[...] This distinction of underpop/overpop and the monotoneness (subset of underpop is always underpop) is sort of a luxury of the specific nature of B3-only where there is no middle like say a B4 neighborhood in a rule with exactly B35. Humans seem to view overpop suppressions as not necessarily connected though so this definition (connect overpop but don't connect underpop) is somewhat a problem. [...]

There was a closely related discussion years ago, which I think it could help to link and partially crosspost as far as the definition of 'overpopulated' goes:

[...]
Let's look at this simple pattern:

Code: Select all

x = 5, y = 2, rule = B3/S23
2ob2o$2ob2o!

Two off-cells have 4 on-cell neighbours each.
If the rule is standard life, B3/S23, those two cells are "overloaded" (birth is prevented because there are too many on-cell neighbours).
Because there are two islands, each of which is stable by itself, but they are connected by at least one overloaded cell, we consider it a pseudo still life.

Suppose instead the rule is B5/S23.
Now there are no overloaded cells, and the pattern should be considered a constellation, right?

What if the rule is B35/S23?
The two cells between the blocks are now "semi-overloaded"... Is it a pseudo still life or a constellation?

What is the general rule to decide if an off-cell connects two islands that are each stable by itself, into a pseudo still life?

An off-cell is overpopulated if and only if some subset of its live neighbours can trigger a birth.

So, yes, it is a pseudo-still-life in B35/S23.

[...]

An off-cell is overpopulated if and only if some subset of its live neighbours can trigger a birth.

Yes, that is the definition I had in mind, nice to have that confirmed!
[...]

[...]

An off-cell is overpopulated if and only if some subset of its live neighbours can trigger a birth.

Exactly!
[...]

[Sokwe]

I was also thinking some more about the maxpop halting condition. Right now it's that there is a state-global "chasm" of an entire W overlap somewhere. This is certainly sufficient to guarantee no more valid (connected) partials but it's far from necessary. I tried to come up with a more accurate condition but haven't had much in the way of great ideas.

The best so far is...

I ran 2c/4 to pop 24 (where I believe the first interesting ships are), taking maybe ~15m total. Unfortunately I did not get the final VmPeak values for a stupid reason but I suspect they were in the 10GB-20GB range.

Feeding the logs through the newer splitter produces the following 26 results. It's a lot of useless *WSS-on-*WSS and minimal spark interactions, but I do notice both pop 24 entries from jslife-moving are there (which is good considering this is supposed to be exhaustive).

Do you mean that this 2c/4 pop-24 search should be exhaustive (i.e., list all possible 24-cell 2c/4 spaceships)? If so, I'm curious if you could confirm that any of the following are the smallest strict ships of their respective symmetry types (c/4d gutter, c/4d bilaterally symmetric, 2c/4 even-symmetric, 2c/4 even-glide-symmetric):

Code: Select all

x = 108, y = 18, rule = B3/S23
9b2o31b2o16b3o16b3o14b3o6b3o$8b2o32bobo15bo2bo14bo2bo13bo2bo5bo2bo$9bo
2bo29bo17bo20bo16bo8bo$9b2obo32bo14bo4b3o6b3o4bo12bo3bo4bo3bo$9b2o3bo
29bobo14bo3bo2bo4bo2bo3bo13bo3bo2bobo3bo$44bobo16bo4bo4bo4bo19bobobo4b
o$12bobob2o26bo19b2o10b2o17bobo8bo$10bobo3bo27bo20bo2bo4bo2bo23b2ob2o$
bo8b3o2bo24bo3bo22b3o2b3o$5o6b2o26b3obo23bo6bo$o2b2o2b2o29b2o28bo4bo$
8b2o27b2o$2b2o2b4o28bo$29b3o$4bobo22bo8bo$8bo21bo2b5o$6b2o24bo$6bo26b
2o!

In the 2c/4 even glide symmetric case I know that there was difficulty with the weights, due I presume to having to account for cell counts in two different phases to get the correct population.

I would also be curious if you could at least bump up the 2c/4 asymmetric search to 25 cells, to verify the claims on this page, that I've long been somewhat skeptical of. You should get an additional two strict spaceships and one pseudo spaceship:

Code: Select all

x = 58, y = 8, rule = B3/S23
3o4bo10b3o27b3o$o2bo2b3o9bo2bo26bo2bo4bo$o4b2obo9bo6bo22bo6b3o$o3b4o
10bo5b3o21bo3bob2obo$o3bob2o10bo5bob2o20bo3bob3o$o17bo6b3o20bo6b2o$bob
o15bo5b3o21bobo$25b2o!

And of course I would love to know if there are any period-4 c/4 diagonal ships with size between the glider (5 cells) and crab (25 cells).

[amling]

Do you mean that this 2c/4 pop-24 search should be exhaustive (i.e., list all possible 24-cell 2c/4 spaceships)?

Yes, if I've reasoned it out correctly then it will even find a great deal more. Namely at least any pattern which is connected in the sense that it cannot be split by "chasm"-style piecewise axis-aligned paths of U overlap wide stripes of zeros and W overlap wide horizontal stripes of zeros, joined at U overlap by W overlap all-zeros corners. Anything connected in any of the definitions previously discussed would be included.

Specifically any such pattern will keep the search from halting until it's found. A great deal more will actually get dumped out as the maxpop ends has absolutely no notion of connectedness at all and just dumps out all zero-boundary partials. As a result, these searches dump an amazing amount of crap (the pop 32 2c/4 search generated gigabytes of logs) and so require another tool to split and dedupe. The one I've just written splits into "spaceships" where connectedness is defined by neighbors, self-future, parent-child, and 2-component overpop suppressions where at least one component had 3 neighbors. If that is not the desired definition of spaceship then of course something else will have to be done to deal with the output.

If so, I'm curious if you could confirm that any of the following are the smallest strict ships of their respective symmetry types (c/4d gutter, c/4d bilaterally symmetric, 2c/4 even-symmetric, 2c/4 even-glide-symmetric):

Code: Select all

x = 108, y = 18, rule = B3/S23
9b2o31b2o16b3o16b3o14b3o6b3o$8b2o32bobo15bo2bo14bo2bo13bo2bo5bo2bo$9bo
2bo29bo17bo20bo16bo8bo$9b2obo32bo14bo4b3o6b3o4bo12bo3bo4bo3bo$9b2o3bo
29bobo14bo3bo2bo4bo2bo3bo13bo3bo2bobo3bo$44bobo16bo4bo4bo4bo19bobobo4b
o$12bobob2o26bo19b2o10b2o17bobo8bo$10bobo3bo27bo20bo2bo4bo2bo23b2ob2o$
bo8b3o2bo24bo3bo22b3o2b3o$5o6b2o26b3obo23bo6bo$o2b2o2b2o29b2o28bo4bo$
8b2o27b2o$2b2o2b4o28bo$29b3o$4bobo22bo8bo$8bo21bo2b5o$6b2o24bo$6bo26b
2o!

In the 2c/4 even glide symmetric case I know that there was difficulty with the weights, due I presume to having to account for cell counts in two different phases to get the correct population.

Unfortunately as you say GSE has that counting problem and even odd diagonal isn't going to work as the innermost U column's cells need to be counted with different weights despite having the same integral U coordinate. c/4d gutter could maybe work since the non-doubled cells on the axis are all zero and so you can just double everything.

Really I need to figure out a better way to describe the translation between position and generation weight. It might be something like a configuration file mapping root label and subtile position to a weight or two weights (one for own generation and one for GS-flipped generation). Then I think we'd be able to do any of the discussed symmetries by careful combination of labeling center-most columns and configuration.

I would also be curious if you could at least bump up the 2c/4 asymmetric search to 25 cells, to verify the claims on this page, that I've long been somewhat skeptical of. You should get an additional two strict spaceships and one pseudo spaceship:

Code: Select all

x = 58, y = 8, rule = B3/S23
3o4bo10b3o27b3o$o2bo2b3o9bo2bo26bo2bo4bo$o4b2obo9bo6bo22bo6b3o$o3b4o
10bo5b3o21bo3bob2obo$o3bob2o10bo5bob2o20bo3bob3o$o17bo6b3o20bo6b2o$bob
o15bo5b3o21bobo$25b2o!

At least 25 seems likely given that 24 was a fair deal shy of the machine's capacity. It may be a bit before I get around to it since I have some other ideas tying up the machine right now.

And of course I would love to know if there are any period-4 c/4 diagonal ships with size between the glider (5 cells) and crab (25 cells).

That I am not optimistic about. As a quick test pop 24 weight gen 00 did not complete with 32 GB and it died not in the new halt code but in the normal expansion code so it's not even a matter of improving that. I am doubtful 60 GB is going to make the difference although I'll plan to try it when the machine frees up.

EDIT: 2c/4 pop 25 finished. With the newer splitter it finds just the two proper ships for pop 25 but with an older version of the splitter that considers all overpop suppressions connected it finds that third one as well. This time I did capture VmPeak and the worst of the two key generations went from 2.43 GB before the final halt check to 34.86 GB so it's definitely a problem. Unfortunately I'm not what I can do about it. Maybe this was all not meant to be...

[Sokwe]

odd diagonal isn't going to work as the innermost U column's cells need to be counted with different weights despite having the same integral U coordinate.

Could you not simply give the innermost U column the non-doubled weight? Then the search would potentially under-count the population of some ships, but it at least won't miss any. Such incorrectly identified spaceships could then simply be removed from the final census.

2c/4 pop 25 finished.... This time I did capture VmPeak and the worst of the two key generations went from 2.43 GB before the final halt check to 34.86 GB so it's definitely a problem.

Thanks. I suspect this means that a 31-cell asymmetric search would be unlikely to work even with 1TB. Such a search would presumably be enough to show that the 2c/4 gse ship shown in my earlier post is minimal (although not necessarily unique). Of course, if you can get the weights working correctly for glide-symmetric searches, then this wouldn't matter.

I am still curious to know if the 48-cell 2c/4 even-symmetric ship is minimal. I imagine it shouldn't take much more memory than the 24-cell asymmetric search. Please post the results of any of these searches in the "LLSSS min pop search results spam" thread.

Edit: I noticed when updating the tutorial that running a side-to-side search with symmetric ends with the B0 agar, that the search no longer finds the extraneous empty ends, but running the search the old way (without setting --bg-agar) does still find the extraneous ends. Does this mean that this problem has been fixed when using --bg-agar? If so, I can significantly simplify that section, but I wanted to check first to make sure there were no issues.

Edit 2: how likely is it that you'll be able to enumerate all p5 oscillators up to 14 or 15 cells (to confirm Pseudo-barberpole is the smallest)?

[amling]

odd diagonal isn't going to work as the innermost U column's cells need to be counted with different weights despite having the same integral U coordinate.

Could you not simply give the innermost U column the non-doubled weight? Then the search would potentially under-count the population of some ships, but it at least won't miss any. Such incorrectly identified spaceships could then simply be removed from the final census.

Oh yeah, something like that will do. Turns out the new reflect edge scrolls more of the pattern in window so it's two U columns that have now-visibly-doubled cells but the principle is the same.

[amling]

I noticed when updating the tutorial that running a side-to-side search with symmetric ends with the B0 agar, that the search no longer finds the extraneous empty ends, but running the search the old way (without setting --bg-agar) does still find the extraneous ends. Does this mean that this problem has been fixed when using --bg-agar? If so, I can significantly simplify that section, but I wanted to check first to make sure there were no issues.

Yeah, all the various efforts of ends to avoid extraneous results are keyed to --bg-agar. This includes...

(*) "Bg" ends (which is the replacement for zero) avoiding outputting patterns that are just BG agar extensions of results that should have been output previously.

(*) S periodic ends efforts to avoid outputting a pattern ending in all BG agar even if it would technically meet the S periodic conditions.

(*) The various symmetric ends.

These are always keyed to --bg-agar so if you run an agar search w/o it they will all (incorrectly) avoid the default which is zeros.

[Sylvani]

Am I the only one having this issue?
Running any search with "--max-pop" gives this error:

Code: Select all

...
20250210 00:22:10 [INFO] VmPeak: 879.25 MB
20250210 00:22:10 [INFO] Memory: total 256 B (ss.cur_gen 64 B, bcol 64 B, col 112 B, left_edge 8 B, right_edge 8 B)
20250210 00:22:10 [DEBUG] LlsssFilterAgarCycleAvoiding: Filtered w_pos 7 bcol: 8 -> 8
20250210 00:22:10 [DEBUG] LlsssFilterAgarCycleAvoiding: Filtered w_pos 7 col: 14 -> 14
thread '<unnamed>' panicked at src/llsss/maxpop.rs:44:22:
explicit panic

The full command is:

Code: Select all

./rlife llsss-recentering-wao --rule 'B3/S23' c3-f2b '@zero' --wao-idx ALL --max-pop 00:30 --ends none XX

[amling]

Am I the only one having this issue?
Running any search with "--max-pop" gives this error:

Code: Select all

...
20250210 00:22:10 [INFO] VmPeak: 879.25 MB
20250210 00:22:10 [INFO] Memory: total 256 B (ss.cur_gen 64 B, bcol 64 B, col 112 B, left_edge 8 B, right_edge 8 B)
20250210 00:22:10 [DEBUG] LlsssFilterAgarCycleAvoiding: Filtered w_pos 7 bcol: 8 -> 8
20250210 00:22:10 [DEBUG] LlsssFilterAgarCycleAvoiding: Filtered w_pos 7 col: 14 -> 14
thread '<unnamed>' panicked at src/llsss/maxpop.rs:44:22:
explicit panic

The full command is:

Code: Select all

./rlife llsss-recentering-wao --rule 'B3/S23' c3-f2b '@zero' --wao-idx ALL --max-pop 00:30 --ends none XX

Max pop takes its column weights from the root labels, expecting "0", "1", or "2". These are used to e.g. weight columns differently in symmetric searches. "@zero" is short for "make me a minimal size grid of all zeros with root labels 'Z'". Then max pop doesn't know what to do with those "Z" roots.

I've just pushed a change that will at least get the error to "Unexpected root label 'Z' for max pop". To actually fix you'll need to provide you own grid with labels indicating weights, which for an asymmetric search you presumably want all 1s.

[Sokwe]

Max pop takes its column weights from the root labels, expecting "0", "1", or "2". These are used to e.g. weight columns differently in symmetric searches. "@zero" is short for "make me a minimal size grid of all zeros with root labels 'Z'". Then max pop doesn't know what to do with those "Z" roots.

I've just pushed a change that will at least get the error to "Unexpected root label 'Z' for max pop". To actually fix you'll need to provide you own grid with labels indicating weights, which for an asymmetric search you presumably want all 1s.

Is there an easy way to get a valid start_file with correctly placed root labels for an asymmetric max-pop search? Is the following procedure valid?

1. Run a basic WAO search with the desired geometry and mid_steps 0. As an example, we will use 2c5_f2b:

   Code: Select all

   ./rlife llsss-recentering-wao 2c5_f2b '@bg' 0

2. At the beginning of the program output from step 1, there should be a section that looks something like this:

   Code: Select all

   [INFO] WAO error window #0 (included):
   [INFO] |       |       | ZZZZZ | ..... | ..... |
   [INFO] | ..... | ..... | ..... | ..... | ..... |
   [INFO] | ..... | ..... | ..... |       |       |
   [INFO] | ..xWW |       |       |       |       |
   

   Take only the part bounded by vertical bars, replace 'Z' with '1' and replace 'x' and 'W' with periods:

   Code: Select all

   |       |       | 11111 | ..... | ..... |
   | ..... | ..... | ..... | ..... | ..... |
   | ..... | ..... | ..... |       |       |
   | ..... |       |       |       |       |
   

   Save this in the same directory as rlife (I called it "maxpop-2c5-f2b.in"). This will be the start file.
3. Run the max-pop search like so:

   Code: Select all

   ./rlife llsss-recentering-wao --rule <rule-string> --ends none --max-pop <phase>:<pop> 2c5_f2b maxpop-2c5-f2b.in XX

   where <pop> is the desired population limit and <phase> is the phase of the pattern in which the limit is applied.

To get all spaceships of a given type up to a particular population limit, it will often be necessary to run a separate search for each possible phase. In some cases certain phase choices are redundant. Is there an easy way for a novice (like myself) to tell when that is?

[amling]

Is there an easy way to get a valid start_file with correctly placed root labels for an asymmetric max-pop search? Is the following procedure valid?

(rip off a grid from WAO output)

Sort of, although it's going to be wider than necessary. There may also be alignment issues for particularly ugly geometries (where the grid output can be shifted by X/Y in a way that will confuse the grid parser into not reparsing the same grid the same way).

A more first principles way is to run `geom-info` to get the W neighborhood size and number of unique positions and make the all-rectangles UWI view, then feed that through from-uwi to get the XYT view.

If we're trying to promote maxpop from insane hack to something run by anyone other than me ever maybe we should come up with some way to configure root weights so we can just map Z to 1.

To get all spaceships of a given type up to a particular population limit, it will often be necessary to run a separate search for each possible phase. In some cases certain phase choices are redundant. Is there an easy way for a novice (like myself) to tell when that is?

It is always sufficient to run [0, N) (i.e. 0 inclusive, N exclusive) where N is the T component of the velocity. I hesitate to try to answer completely for the general case, but for Kc/N with gcd(K, N) = D I believe it should suffice to run [0, N/D). This is based on a shift of (0, -K, N)/D being able to rotate any other generation into that range.

So for example for p3 (0c/3), gcd(0, 3) = 3 and we need just [0, 3/3) which is just 0. For 2c/4, gcd(2, 4) = 2 and we need [0, 4/2) or just 0 and 1. For 8c/12, gcd(8, 12) = 4 and we need [0, 12/4) = [0, 3).

I suspect the axis-aligned knight and/or diagonal case of V=(+/-H, -K, N), W=(0, 1, 0) is going to shake out just like Kc/N but I would want to think very hard about that before committing to anything.

[Sokwe]

If we're trying to promote maxpop from insane hack to something run by anyone other than me ever maybe we should come up with some way to configure root weights so we can just map Z to 1.

It doesn't seem too hard to run such a search, so I was thinking of adding it to the basic LLSSS tutorial. A simple mapping of 'Z' to '1' would (presumably) only work for asymmetric searches, and I'm hoping to make the section general enough that someone could run proper symmetric max-pop searches as well. For this I want an easy enough way for a beginner to set up the search, and the above method was the easiest I could think of.

it's going to be wider than necessary.

Is there any problem with a wider-than-necessary start_file in this case or in the cases with some '0' or '2' root labels?

There may also be alignment issues for particularly ugly geometries (where the grid output can be shifted by X/Y in a way that will confuse the grid parser into not reparsing the same grid the same way).

I didn't know this, but I'll try to keep it in mind from now on. Is the procedure from my previous post at least valid for all of the named geometries?

[amling]

it's going to be wider than necessary.

Is there any problem with a wider-than-necessary start_file in this case or in the cases with some '0' or '2' root labels?

No problem. For recentering the state file is determined by the leftmost 2 columns, the rightmost 2 columns, and the set of width 3 blocks it is chopped into so ZZZZZ -> {ZZZ, ZZZ, ZZZ} = {ZZZ} which is the same as ZZZ -> {ZZZ} and you get identical state file. Similarly 12222 -> {122, 222, 222} = {122, 222} is the same as 1222 -> {122, 222}, etc.

There may also be alignment issues for particularly ugly geometries (where the grid output can be shifted by X/Y in a way that will confuse the grid parser into not reparsing the same grid the same way).

I didn't know this, but I'll try to keep it in mind from now on. Is the procedure from my previous post at least valid for all of the named geometries?

The problem is the grid output can shift coordinates by +/-X and +/-Y. For named geometries U=X so any shift of X just shifts integer U positions which keeps things in the same analogous place w/in tiles. For named geometries with W=Y similarly a shift of Y just shifts integer W positions.

For named geometries where W is only Y-like I believe the worst you'll see is rotation within the tile. For example if you feed this:

Code: Select all

| 000 | 111 |
| 000 | 111 |
| 000 | 111 |

through from-uwi 2c4-f2b you get:

Code: Select all

|     |     |     |     |
|     |     | 111 | 111 |
| 000 | 000 | 000 |     |
| 111 |     |     |     |

It's put an extra blank Y row on the top to ensure the grid parser will reconstruct things exactly. Most grid outputs (including that WAO one) are not so careful. If you trim the top row and pass back through to-uwi you get:

Code: Select all

| 111 | 000 |
| 111 | 000 |
| 111 | 000 |

The two tile positions have switched places. This sort of change is not a problem for your procedure (where each tile is character homogenous anyway), but does represent a theoretical lossiness of the grid output. For more complicated geometries I believe even worse things can happen (what was a UVW prism can be parsed as not one for example).

EDIT: BTW, if we're trying to promote maxpop to semi-usability maybe we could instead make a @maxpop magic grid? Like @maxpop:asym, @maxpop:even, or @maxpop:odd to make the grid with the 111, 11222, or 1222 labels respectively. We could also forget this ends config file branch and just make up a special character (G?) to mark the special GS column weight behavior (1 as-is plus 1 shifted by V/2) and have @maxpop:gse and @maxpop:gso generate grids with it (11GGG and 1GGG respectively). Uh, although it occurs to me these proposed simple grids and weights only work for orthogonal geometries. We would still need complicated per-tile-position behavior to make diagonal work and then it's a total mess to try to make @maxpop know about any of that. Uh, maxpop is still such a mess of hacks...

[amling]

I rigged up the G label weights and @maxpop and pushed it all. Perhaps consider it provisional while we decide if we like it.

Now the original search up-thread can be run as:

Code: Select all

$ rlife llsss-recentering-wao c3-f2b '@maxpop:asym' --max-pop 00:30 --ends none XX

And orthogonal GS searches work, e.g.:

Code: Select all

$ rlife llsss-recentering-wao 2c4-f2b '@maxpop:gso' --wao-left-edge-errors --left-edge gso --max-pop 01:09 --ends none XX
...
20250210 11:12:55 [INFO] End (pop 9):
20250210 11:12:55 [INFO] |       |       |       | 1GGGG |
20250210 11:12:55 [INFO] |       | 1GGGG | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... | *.... | **... |
20250210 11:12:55 [INFO] | *.... | **... | **... | ..*.. |
20250210 11:12:55 [INFO] | **... | .*... | .**.. | ..... |
20250210 11:12:55 [INFO] | .*... | .*... | ***.. | ..... |
20250210 11:12:55 [INFO] | *.... | .*... | **... | *.*.. |
20250210 11:12:55 [INFO] | *.... | *.... | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... |       |       |
20250210 11:12:55 [INFO] End (pop 9):
20250210 11:12:55 [INFO] |       |       |       | 1GGGG |
20250210 11:12:55 [INFO] |       | 1GGGG | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... | *.... | **... |
20250210 11:12:55 [INFO] | *.... | **... | **... | .*... |
20250210 11:12:55 [INFO] | **... | ..*.. | .*... | .*... |
20250210 11:12:55 [INFO] | .**.. | ..... | *.... | .*... |
20250210 11:12:55 [INFO] | ***.. | ..... | *.... | *.... |
20250210 11:12:55 [INFO] | **... | *.*.. | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... | ..... | ..... |
20250210 11:12:55 [INFO] | ..... | ..... |       |       |
...

Diagonal symmetric searches are still NG. Half a plan is to change the @maxpop grid to always generate labels 'ABCCC' (or equivalent for wider AF2) so the columns are all distinguishable (each in the edge is labelled uniquely and the rest are all labelled the same as each other) and make the maxpop weighting code do all the work. But then it has to know the symmetry type and redo all the geometry work the symmetry edge is already doing (as well as make assumptions about where it aligned the flip) in order to figure out what should happen for each cell in the edge.

[amling]

I was thinking about recentering autochoke some more. The killer constraint that is preventing acceptance of any previous sketches is that we don't want to alter materially the performance of existing searches and so I was wondering: what could we do with exactly what we have right now? Like we hit pre-reify time, we realize it's going to be too much memory, what do we know and what could we possibly do to reduce the state file? The key problem is that we've lost the definition of background/inertness/closure and so we don't have a great way to distinguish "this is a wide partial" from "this is a partial with a wide non-zero bottom". Well, I guess we could hard-code the notion of zero and accept that it's a hack? Anyway, I realized it wouldn't cost us much to keep around until pre-reify the bcol-only results of having run the closures. They're bcol extension bit vectors only and so for AF2=3 they're each 1/16th the size of the bcol in the first place (and we'd keep two).

Given access to this it's not quite possible to capture the original closure exactly as you can't tell which adjacencies between pairs of marked points were actually considered closure neighbors or just normal CA-checks-are-legal neighbors. However, this is a small distinction in any case and isn't actually one at all for e.g. zero or B0 backgrounds. We're also not going to try to accurately capture all the weird chimerism in mid steps that would have happened in a true expand and instead going to count mid_steps exactly. Closure distances will still be inexact although I doubt anyone has ever even run a fixed steps closure before but me (and with unlimited steps closures this inexact behaviour is the same as exact).

So! We compute l2r and r2l distances for each point to the results of the closures. In the sketch these are kept as u8s and saturate at 254 which is probably fine for most searches (and can easily be changed to u16s at compile time if we want). We do some extra jiggerpokery to smear a second set of distances into the closures to retain their paths out to the edges when appropriate. Then we collect the counts of bcol points and col points by final valuation, then counts at or below each valuation, and then finally we use those counts to instantly estimate memory for truncating at a given valuation and chase down whatever threshold of memory the user has configured.

This is all to say the semantics of what is found in a search at a given size are a little different, even from every other already weirdly and slightly different versions of this feature, but I think for the purposes of desperate searches running out of memory and just wishing they could squeeze a little more out it's probably fine.

I ran the B26/S02567 c1-s2s searches again to see how it did. All with unlimited mid_steps but then very tiny memory limits. 1KB, 10KB, 100KB, and 1MB terminated similarly to previous versions, and then 10MB finds a first hit in 27s. It spent something like half that time propagating valuations around in autochoke which is not great, but probably not really avoidable. At least this is way, way less than the "just a few minutes" of the original reduce-by-one-only version of this.

This version runs similarly to the previous, e.g. I had run:

Code: Select all

env LLSSS_HALT_ON_ENDS=true rlife llsss-recentering-wao c1-s2s '@zero' --rule 'B26/S02567' --ends skew_gutter:1,skew_gutter:-1 --pre-reify-autochoke 10485760 XX

And then you get output like...

Code: Select all

20250214 21:40:01 [INFO] Autochoke SEMSV1 estimated reify memory: 16.91 MB > limit 10.00 MB, running...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 53 -> 3.93 MB <= limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 80 -> 16.06 MB > limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 67 -> 11.09 MB > limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 60 -> 6.96 MB <= limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 64 -> 9.28 MB <= limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 66 -> 10.50 MB > limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 testing valuation 65 -> 9.89 MB <= limit 10.00 MB...
20250214 21:40:01 [INFO] Autochoke SEMSV1 keeping 65 -> 9.89 MB

Similarly to previous cuts the limit is very much an approximation. Limiting the estimated in-between-expansions state to 10 MB was still able to reach 22.05 MB (per the program's reckoning of its own data structures which is also of course less than the OS's view) in the middle of some expansion.

So where do we go from here? I've pushed it to codeberg as 20250214-autochoke-semsv1-04. Ideally, Sokwe, I'd hope to talk you into trying this cut of it and if we like it, ultimately merge this to master after maybe cleaning up a few things:

(*) Argument specification should leave room for alternative strategies so this will probably be `--pre-reify-autochoke semsv1:10485760`.

(*) Sane memory quantity parsing like "10MB" or "4.5GB".

(*) Clean up output. Probably don't need to see the now-instantaneous bisection step by step. Probably still want the chosen size stats and the smallest rejected stats.