amling search program principles discussion / brain dump

For scripts to aid with computation or simulation in cellular automata.
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

amling wrote: September 14th, 2025, 4:02 pm I also sketched real quick some hacky variations on the max-pop code that would let it contribute here. Specifically adding it for non-WAO rc searches and fixing all spine weights to one (so I can use root labels for constraints instead). With these, and scrolling five rows of still life initialization to be in bounds (and thus counted by max-pop), this can show there are no pop 17 p3 "1,2" oscillators (all three searches complete with no "End"s)...
Interesting. Since these searches didn't run when I tried them in the osc_freq_hack branch, I take it you didn't push this particular change. I was simply wondering about the feasibility of proving that pseudo-barberpole is the smallest possible p5 oscillator. I thought that you couldn't approach this question previously due to the double-block problem, but being able to force a p5 cell should avoid that.

Edit: looking back at an earlier post of yours, it seems you may have already tried this. If so, feel free to ignore this post.

Edit 2: I was able to use the osc_freq_hack to disprove the existence of p5 oscillators with exactly two cell frequencies, except the pairs (2,5) and (3,5). I was unable to disprove any other types, but I only have about 5 GB of RAM free to work with.
-Matthias Merzenich
wildmyron
Posts: 1571
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: amling search program principles discussion / brain dump

Post by wildmyron »

amling wrote: September 13th, 2025, 11:51 pm
Sokwe wrote: September 13th, 2025, 7:27 pm
amling wrote: July 19th, 2024, 3:27 pm I've just pushed `2345a0101a81` which includes:

(*) `--constraint statorless`....
Is there any way to prevent other cell frequencies? That is, could LLSSS be set up to search for a p3 oscillator where all cells are on for exactly two out of three generations?
That is well within the range of what a constraint can know when it must make its decision. Unfortunately deciding exactly what form of user input to take is a somewhat harder problem.

I've pushed a quick and dirty demo to codeberg as 20250913-p3-hack-01 to implement exactly this (require each cell to be on in zero or two generations). Even a debug build of this is quickly able to rule out such p3 oscillators almost instantly, at least assuming no bugs:

<snip code block with partial output>

The partial looks like the right sort of thing to me (all completed cohorts are zero or two gens on), but it would be nice to have a rule with an example oscillator to try to find.

<snip>
Here's an example I found with a quick and dirty hack of logic-life-search

Code: Select all

x = 5, y = 5, rule = B2k3ejnr4akr5r6ace/S12ck3ceir4ijz5r
b3o$o$5o$o2bo$bobo!
There are smaller examples in other rules, but this one seemed a reasonable size at width 5. I'm confident there's no width 4 example in this rule, but haven't ruled it out - checked up to 4x100 search area.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: September 14th, 2025, 6:45 pm I was able to use the osc_freq_hack to disprove the existence of p5 oscillators with exactly two cell frequencies, except the pairs (2,5) and (3,5). I was unable to disprove any other types, but I only have about 5 GB of RAM free to work with.
I'm just collecting my own p5 searches (to 60GB) with almost the same results (had to use a similar still-life start plus forced change cell in first row for searches including 5). All pairs except for "2,5" completed ("3,5" reached VmPeak 25.28 GB) and none of the eight remaining triples completed.

Do we think any oscillators exist with any of those remaining triples might exist? I guess I'm gonna start looking into some positive limited searches for them and see if any healthy-looking partials show up.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

wildmyron wrote: September 15th, 2025, 2:23 am
amling wrote: September 13th, 2025, 11:51 pm The partial looks like the right sort of thing to me (all completed cohorts are zero or two gens on), but it would be nice to have a rule with an example oscillator to try to find.
Here's an example I found with a quick and dirty hack of logic-life-search

Code: Select all

x = 5, y = 5, rule = B2k3ejnr4akr5r6ace/S12ck3ceir4ijz5r
b3o$o$5o$o2bo$bobo!
There are smaller examples in other rules, but this one seemed a reasonable size at width 5. I'm confident there's no width 4 example in this rule, but haven't ruled it out - checked up to 4x100 search area.
Yes, exactly! This is found successfully by:

Code: Select all

rlife llsss-recentering-wao p3 '@bg' --rule 'B2k3ejnr4akr5r6ace/S12ck3ceir4ijz5r' --llsss-env LLSSS_HALT_ON_ENDS=true --constraint osc_freq_hack:5 XX
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I've reworked this code to be a more general "spine_nfa" constraint. I left "osc_freq_hack" as a short-hand way of configuring it, whose behaviour hasn't changed from the above. The full version is kind of a pain as the format is very raw, but it would allow e.g. to search for strict volatility p4 oscillators with this config file:

Code: Select all

$ cat p4sv.cfg
{
    "steps": [
        ["ZERO", false, "s0"],
        ["ZERO", true, "s1"],
        ["s0", false, "s00"],
        ["s0", true, "s01"],
        ["s1", false, "s10"],
        ["s1", true, "s11"],
        ["s00", false, "s000"],
        ["s00", true, "s001"],
        ["s01", false, "s010"],
        ["s01", true, "s011"],
        ["s10", false, "s100"],
        ["s10", true, "s101"],
        ["s11", false, "s110"],
        ["s11", true, "s111"],
        ["s000", false, "ZERO"],
        ["s000", true, "ZERO"],
        ["s001", false, "ZERO"],
        ["s001", true, "ZERO"],
        ["s010", false, "ZERO"],
        ["s011", false, "ZERO"],
        ["s011", true, "ZERO"],
        ["s100", false, "ZERO"],
        ["s100", true, "ZERO"],
        ["s101", true, "ZERO"],
        ["s110", false, "ZERO"],
        ["s110", true, "ZERO"],
        ["s111", false, "ZERO"],
    ],
    "esteps": [
    ],
}
$
And then e.g.:

Code: Select all

$ rlife llsss-recentering-wao p4 '@bg' --constraint spine_nfa:p4sv.cfg 06
20250916 00:07:40 [INFO] LlsssConstraintSpineNfa: 15 NFA states
20250916 00:07:40 [INFO] LlsssConstraintSpineNfa: 15 DFA states
...
20250916 00:07:50 [INFO] Shortest partial:
20250916 00:07:50 [INFO] | ZZZZZZZZZZ | ZZZZZZZZZZ | ZZZZZZZZZZ | ZZZZZZZZZZ |
20250916 00:07:50 [INFO] | .......... | .......... | .......... | .......... |
20250916 00:07:50 [INFO] | .......... | .......... | .......... | .......... |
20250916 00:07:50 [INFO] | .......... | ....*..... | .......... | .......... |
20250916 00:07:50 [INFO] | ...***.... | ....*..... | .......... | ....*..... |
20250916 00:07:50 [INFO] | .......... | ...***.... | ...***.... | ...***.... |
20250916 00:07:50 [INFO] | ..*...*... | .......... | ....*..... | ...***.... |
20250916 00:07:50 [INFO] | ...*...... | .......... | .......... | ...***.... |
20250916 00:07:50 [INFO] | .......*.. | ....*.*... | ...**.*... | .....***.. |
20250916 00:07:50 [INFO] | ....**.*.. | ...****... | ......**.. | .....***.. |
20250916 00:07:50 [INFO] | ...**..... | ...**..*.. | .......*.. | ...*...... |
20250916 00:07:50 [INFO] | ......**.. | ....*..*.. |            |            |
...
20250916 00:07:50 [DEBUG] Completed w_pos 10[2]: 0 B [-200.00%], 79.283427ms [-1.97%]
20250916 00:07:50 [INFO] VmPeak: 658.24 MB
...
20250916 00:07:50 [INFO] Finish: search proper -> took 9.955958425s (29.429975s user, 1.107273s sys)
...
20250916 00:07:50 [INFO] Total: 10.370349802s (30.615285s user, 1.138997s sys)
20250916 00:07:50 [INFO] Done
Given that all the code amounts to only about 100 lines, completely separated from any of the main engine code, I'm likely to just merge it into master and forget about it. Maybe I'll give it a day or two to see if we can think of any other changes to go with it. In the mean time it is pushed to codeberg as 20250915-spine-nfa-constraint-04.
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

amling wrote: September 16th, 2025, 3:13 am I've reworked this code to be a more general "spine_nfa" constraint. I left "osc_freq_hack" as a short-hand way of configuring it, whose behaviour hasn't changed from the above. The full version is kind of a pain as the format is very raw, but it would allow e.g. to search for strict volatility p4 oscillators with this config file:

Code: Select all

$ cat p4sv.cfg
{
    "steps": [
        ["ZERO", false, "s0"],
        ["ZERO", true, "s1"],
        ["s0", false, "s00"],
        ["s0", true, "s01"],
        ["s1", false, "s10"],
        ["s1", true, "s11"],
        ["s00", false, "s000"],
        ["s00", true, "s001"],
        ["s01", false, "s010"],
        ["s01", true, "s011"],
        ["s10", false, "s100"],
        ["s10", true, "s101"],
        ["s11", false, "s110"],
        ["s11", true, "s111"],
        ["s000", false, "ZERO"],
        ["s000", true, "ZERO"],
        ["s001", false, "ZERO"],
        ["s001", true, "ZERO"],
        ["s010", false, "ZERO"],
        ["s011", false, "ZERO"],
        ["s011", true, "ZERO"],
        ["s100", false, "ZERO"],
        ["s100", true, "ZERO"],
        ["s101", true, "ZERO"],
        ["s110", false, "ZERO"],
        ["s110", true, "ZERO"],
        ["s111", false, "ZERO"],
    ],
    "esteps": [
    ],
}
$
Sorry for my potential naivete, but I'm just trying to parse the NFA definition above. It appears to me that the states represent a single cell's history, such that "s101" represents a cell that was on, then off, then on again. I assume the lack of a ["s101", false, "ZERO"] transition indicates that true-false-true-false (i.e., on-off-on-off) is not an accepted word of the NFA. Is "ZERO" defined to be both the starting state and the only possible final state? I assume "esteps" would just be a set of ordered state pairs, although I'm not sure in what circumstances they would be useful.
-Matthias Merzenich
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sokwe wrote: September 16th, 2025, 4:10 am
amling wrote: September 16th, 2025, 3:13 am I've reworked this code to be a more general "spine_nfa" constraint. I left "osc_freq_hack" as a short-hand way of configuring it, whose behaviour hasn't changed from the above. The full version is kind of a pain as the format is very raw, but it would allow e.g. to search for strict volatility p4 oscillators with this config file:

Code: Select all

(snip)
Sorry for my potential naivete, but I'm just trying to parse the NFA definition above. It appears to me that the states represent a single cell's history, such that "s101" represents a cell that was on, then off, then on again. I assume the lack of a ["s101", false, "ZERO"] transition indicates that true-false-true-false (i.e., on-off-on-off) is not an accepted word of the NFA. Is "ZERO" defined to be both the starting state and the only possible final state? I assume "esteps" would just be a set of ordered state pairs, although I'm not sure in what circumstances they would be useful.
This was just the quickest raw format I could whip up. "ZERO" is the implicit start state. I chose to name states with their history of bits to try to keep track of them (any string is fine). "steps" are transitions, "esteps" are epsilon transitions (i.e. can be followed without consuming any input bits). Any NFA with epsilon transitions can be converted to one without so in a sense they are useless, but that is also true of using an NFA over a DFA and in both cases it is sometimes more convenient to have the extra options (even if I used neither here).

In terms of how this is matched against the spine to decide what bits to extend with, we concatenate the potential one bit extension onto the bits already there and match the entire thing. All states are considered accepting as I had believed non-accepting states were going to be irrelevant, but now I struggle to work through the cases to convince myself any NFA with non-accepting states must be immediately convertible to one that has none (of course you can go the long route converting to a DFA and there non-accepting states are definitely useless, but I had thought I had convinced myself there was an easy and direct edit). Perhaps in the future I will be adding a list of accepting states to the format or patching an edit in here to explain why they aren't needed. In the meantime I certainly don't have any applications that need non-accepting states.

This NFA is intended to match any number of legal (strictly volatile) tiles followed by one final any prefix of a legal tile. The missing s101 + false -> ZERO, s010 + true -> ZERO, and s111 + true -> ZERO transitions mean if it would place a fourth (mod four) bit that made the just-completed tile 1010, 0101, or 1111, there will be nowhere to go in the NFA and thus that string will not be accepted.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

amling wrote: September 16th, 2025, 3:13 am Maybe I'll give it a day or two to see if we can think of any other changes to go with it.
amling wrote: September 16th, 2025, 4:30 am Perhaps in the future I will be adding a list of accepting states to the format...
I've convinced myself that what I was thinking about easily eliminating non-accepting states was incorrect. I had thought that non-accepting states were pointless because if you had one on a would-be accepting path it wouldn't be reachable as the prefix that ended in the non-accepting state wouldn't have been accepted earlier (something something dealing with epsilon transitions, but I don't think they're the problem with this line of thought). This however isn't right for NFAs as that prefix could still have been accepted via a completely different path that diverged earlier. For DFAs I believe the argument still works, but of course converting NFAs to DFAs is a big mess and is neither what I was thinking nor something I would want to require of users of this feature.

Ultimately I added an optional "ends" key to the config, which expects a list of state strings (defaults to all states referenced in "steps" and "esteps"). The previous p4sv.cfg works but it could also be made explicit:

Code: Select all

{
    "steps": [
        ["ZERO", false, "s0"],
        ["ZERO", true, "s1"],
        ["s0", false, "s00"],
        ["s0", true, "s01"],
        ["s1", false, "s10"],
        ["s1", true, "s11"],
        ["s00", false, "s000"],
        ["s00", true, "s001"],
        ["s01", false, "s010"],
        ["s01", true, "s011"],
        ["s10", false, "s100"],
        ["s10", true, "s101"],
        ["s11", false, "s110"],
        ["s11", true, "s111"],
        ["s000", false, "ZERO"],
        ["s000", true, "ZERO"],
        ["s001", false, "ZERO"],
        ["s001", true, "ZERO"],
        ["s010", false, "ZERO"],
        ["s011", false, "ZERO"],
        ["s011", true, "ZERO"],
        ["s100", false, "ZERO"],
        ["s100", true, "ZERO"],
        ["s101", true, "ZERO"],
        ["s110", false, "ZERO"],
        ["s110", true, "ZERO"],
        ["s111", false, "ZERO"],
    ],
    "esteps": [
    ],
    "ends": [
        "ZERO",
        "s0",
        "s1",
        "s00",
        "s01",
        "s10",
        "s11",
        "s000",
        "s001",
        "s010",
        "s011",
        "s100",
        "s101",
        "s110",
        "s111",
    ],
}
I've pushed the changes to codeberg just now. I would consider both spine_nfa and osc_freq_hack somewhat provisional and subject to change (or removal). As always, if you make any use of them (or have any ideas to use something like this) I would love to know (and/or consult).
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

amling wrote: September 15th, 2025, 12:33 pm I'm just collecting my own p5 searches (to 60GB) with almost the same results (had to use a similar still-life start plus forced change cell in first row for searches including 5). All pairs except for "2,5" completed ("3,5" reached VmPeak 25.28 GB) and none of the eight remaining triples completed.

Do we think any oscillators exist with any of those remaining triples might exist? I guess I'm gonna start looking into some positive limited searches for them and see if any healthy-looking partials show up.
My various quick attempts at limited width searches didn't really come up with much. p5 "2,4,5" ran into an interesting partial which is essentially the north end of this, from jslife:

Code: Select all

x = 30, y = 38, rule = B3/S23
26b2o$26bo2bo$20b2ob2obob2o$21bobo2bobo$21bobo4bo$18b2obobob3o$19bobob
o$19bo2bob4o$16b2obobo5bo$15bobobo2b3o$15bobobo4bo$12b2obob7o$13bobobo
$13bobo2b4o$10b2obo7bo$9bobobob4o$9bobobo4bo$6b2obo2bob4o$7bobobo$7bob
o2b4o$4b2obobo5bo$2bo2bob6o$2b2obobo4bo$3bobo2b4o$3bo$2b2ob5o$bo3bo2bo
bo$o2b2o3bobo$3o2b2obob2o$3b4obobo2bo$2bo2bob2o3b2o$2b2ob2ob2o$6bo3bo$
2b3o4bo2bo$bo2bobo2bob2o$2bo4bobo$3b3obobo$5bob2o!
This means if there are no "2,4,5" oscillators it's certainly going to be tricky to prove it.

Skimming the other longest partials, two stand out as sort of healthy-adjacent. "1,2,3":

Code: Select all

x = 96, y = 15, rule = LifeHistory
F.16B.F.16B.F.16B.F.16B.F.16B.F$F.16B.F.16B.F.16B.F.16B.F.16B.F$F.16B
.F.16B.F.16B.F.6B2A8B.F.6B2A8B.F$F.5BABA8B.F.16B.F.5B4A7B.F.5BAB3A6B.
F.9BA6B.F$F.8BABA5B.F.4B6A6B.F.5B2A2B2A5B.F.8B2A6B.F.5B2A9B.F$F.4B2A
2BA2BA4B.F.7B2AB2A4B.F.4B2A6BA3B.F.4BABA2B2A5B.F.8B3A5B.F$F.8BA2BA4B.
F.3BA6B3A3B.F.4BA4BA6B.F.3BA12B.F.3B2A4B3A4B.F$F.3B3A5BA4B.F.4B2A5B2A
3B.F.4B2A4BA2BA2B.F.3BA6BABA3B.F.11BA4B.F$F.5BA6BA3B.F.5BA7BA2B.F.4B
2A5BABA2B.F.6BA5BA3B.F.4BABA5B2A2B.F$F.11B3A2B.F.11BABA2B.F.5BA10B.F.
4B3A5BA3B.F.6BA9B.F$F.5BA5BA4B.F.4BABABA2BA4B.F.6BABA2BA4B.F.6BABA7B.
F.4BA4B2ABA3B.F$F.3BABAB3ABA4B.F.5B3ABAB2A3B.F.4BAB3A7B.F.5B2A2B4A3B.
F.4BA7BA3B.F$F.4BA3B2A2BA3B.F.4BA6B2A3B.F.3BA3BABAB2A3B.F.3B2AB2AB3A
4B.F.2BA3B3A7B.F$F.8BA2BA4B.F.3B3A2B2A6B.F.3BA6BA5B.F.2B3A5BA2BA2B.F.
2BAB5AB3A3B.F$F.3B2AB2A8B.F.4BABA4B2A3B.F.3BA8B2A2B.F18.F18.F!
And maybe "1,2,4":

Code: Select all

x = 111, y = 15, rule = LifeHistory
F.19B.F.19B.F.19B.F.19B.F.19B.F$F.19B.F.19B.F.19B.F.19B.F.19B.F$F.7BA
11B.F.7BA11B.F.7BA11B.F.7BA11B.F.19B.F$F.6BABA10B.F.6BABA10B.F.6BABA
10B.F.7BA11B.F.6B3A10B.F$F.6BA2BA9B.F.6BABA10B.F.19B.F.7BA11B.F.7B2A
10B.F$F.7BA11B.F.19B.F.8BA10B.F.8BA10B.F.9BA9B.F$F.19B.F.7B2A10B.F.7B
ABA9B.F.7B3A9B.F.7BA11B.F$F.7B2A2BA7B.F.7B3ABA7B.F.6BA3BA8B.F.9B3A7B.
F.11BA7B.F$F.7B2ABABA6B.F.7B3A2BA6B.F.10BABA6B.F.7B2ABA8B.F.7B2ABABA
6B.F$F.4BA7BA6B.F.8BA4BA5B.F.4BA2B3A2BA6B.F.4B2A2BA3B2A5B.F.4B2A2BABA
BA6B.F$F.3BA2BABABA3BA4B.F.3B3A5BA7B.F.4B2A3B3ABA5B.F.4B2ABA2B2A7B.F.
4B3AB4AB2A4B.F$F.4BA7BABA4B.F.5BA2BAB3ABA4B.F.8BA3B4A3B.F.9BA3BABA3B.
F.4BA2BA4BABA4B.F$F.6BAB2ABAB2ABA2B.F.5B5ABA2B2A3B.F.4B2A5BA3BA3B.F.
5B2AB4A3BA3B.F.5B2AB3A4B2A2B.F$F.2BA2BABA2B2ABA5B.F.2BA2BABABA3B2A4B.
F.2B4ABAB2ABA6B.F.6B2A7BA3B.F.2B4A2BA3BA2B2A2B.F$F.2B4ABA3B2A6B.F.2B
2A9B2A4B.F21.F21.F21.F!
Neither looks exactly completable with current computing resources, but they do not look nearly sick enough for me to hope for a proof of no oscillator. My money might even be on one or both of these existing.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

amling wrote: September 1st, 2025, 2:02 am
amling wrote: August 31st, 2025, 9:54 pm Try to do some heuristic to understand when the "only cycles" are the two edge agars and show some sense of all recombinations of the other parts?
One possible idea for this is to identify the nontrivial strongly connected components (i.e. those that are not just a single vertex without even a self-loop edge) of the graph of left-to-right traversals and output their contents how we do now (merging only unique neighbors), but then multiply out completely all paths between these nontrivial strongly connected components.

In typical results in typical searches you'd get one SCC of the left agar, one SCC of the right agar, and whatever finite and fully-expanded collection of paths between then. In searches that hit a cycle in the middle you'd get, well, something.
I've reworked LLSSS_RC_ENDS_FULL into LLSSS_RC_ENDS_FULL_TYPES. "NONE" does nothing (analogous to old LLSSS_RC_ENDS_FULL=false), "V1" (the default) does current behavior of showing each step exactly once but combining unique neighbors. I've also sketched a "V2" to do what I suggested above about showing intra-SCC paths for "nontrivial" SCCs as we do now, but fully multiplying out paths between them that pass through only "trivial" SCCs (i.e. SCCs that are a single vertex with no self-step loop and have have no label like "start" or "keep"). You can also separate multiple options with commas (e.g. "V1,V2").

Compare finding the LWSS s2s before:

Code: Select all

$ rlife llsss-recentering-wao 2c4-s2s '@bg' --llsss-env LLSSS_HALT_ON_ENDS=true 06
...
20250919 11:53:43 [INFO] End [piece] #0 "start" -> #0 "start":
20250919 11:53:43 [INFO] |  ZZZ |  ZZZ | ZZZ  | ZZZ  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] End [piece] #0 "start" -> #1:
20250919 11:53:43 [INFO] |  ZZZ |  ZZZ | ZZZ  | ZZZ  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ..* | ...  | ..*  |
20250919 11:53:43 [INFO] |  ..* |  ..* | ..*  | ..*  |
20250919 11:53:43 [INFO] |  ... |  ..* | ...  | ..*  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] End [piece] #1 -> #2 ("keep", ("LlsssEndsAgar", "zero")):
20250919 11:53:43 [INFO] |  ZZZZZZZZ |  ZZZZZZZZ | ZZZZZZZZ  | ZZZZZZZZ  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ...**...  | ..*..*..  |
20250919 11:53:43 [INFO] |  ..**.... |  .****... | ..****..  | .*......  |
20250919 11:53:43 [INFO] |  .**.**.. |  .*...*.. | .**.**..  | .*...*..  |
20250919 11:53:43 [INFO] |  ..****.. |  .*...... | ..**....  | .****...  |
20250919 11:53:43 [INFO] |  ...**... |  ..*..*.. | ........  | ........  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] End [piece] #1 -> #2 ("keep", ("LlsssEndsAgar", "zero")):
20250919 11:53:43 [INFO] |  ZZZZZZZZ |  ZZZZZZZZ | ZZZZZZZZ  | ZZZZZZZZ  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] |  ...**... |  ..*..*.. | ........  | ........  |
20250919 11:53:43 [INFO] |  ..****.. |  .*...... | ..**....  | .****...  |
20250919 11:53:43 [INFO] |  .**.**.. |  .*...*.. | .**.**..  | .*...*..  |
20250919 11:53:43 [INFO] |  ..**.... |  .****... | ..****..  | .*......  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ...**...  | ..*..*..  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] |  ........ |  ........ | ........  | ........  |
20250919 11:53:43 [INFO] End [piece] #2 ("keep", ("LlsssEndsAgar", "zero")) -> #2 ("keep", ("LlsssEndsAgar", "zero")):
20250919 11:53:43 [INFO] |  ZZZ |  ZZZ | ZZZ  | ZZZ  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:43 [INFO] |  ... |  ... | ...  | ...  |
...
With after:

Code: Select all

$ rlife llsss-recentering-wao 2c4-s2s '@bg' --llsss-env LLSSS_HALT_ON_ENDS=true --llsss-env LLSSS_RC_ENDS_FULL_TYPES=V2 06
...
20250919 11:53:56 [INFO] [V2] End [SCC piece] #0 "start" -> #0 "start":
20250919 11:53:56 [INFO] |  ZZZ |  ZZZ | ZZZ  | ZZZ  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] [V2] End [piece] #0 "start" -> #1 ("keep", ("LlsssEndsAgar", "zero")):
20250919 11:53:56 [INFO] |  ZZZZZZZZZ |  ZZZZZZZZZ | ZZZZZZZZZ  | ZZZZZZZZZ  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] |  ......... |  ......... | ....**...  | ...*..*..  |
20250919 11:53:56 [INFO] |  ...**.... |  ..****... | ...****..  | ..*......  |
20250919 11:53:56 [INFO] |  ..**.**.. |  ..*...*.. | ..**.**..  | ..*...*..  |
20250919 11:53:56 [INFO] |  ...****.. |  ..*...... | ...**....  | ..****...  |
20250919 11:53:56 [INFO] |  ....**... |  ...*..*.. | .........  | .........  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] [V2] End [piece] #0 "start" -> #1 ("keep", ("LlsssEndsAgar", "zero")):
20250919 11:53:56 [INFO] |  ZZZZZZZZZ |  ZZZZZZZZZ | ZZZZZZZZZ  | ZZZZZZZZZ  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] |  ....**... |  ...*..*.. | .........  | .........  |
20250919 11:53:56 [INFO] |  ...****.. |  ..*...... | ...**....  | ..****...  |
20250919 11:53:56 [INFO] |  ..**.**.. |  ..*...*.. | ..**.**..  | ..*...*..  |
20250919 11:53:56 [INFO] |  ...**.... |  ..****... | ...****..  | ..*......  |
20250919 11:53:56 [INFO] |  ......... |  ......... | ....**...  | ...*..*..  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] |  ......... |  ......... | .........  | .........  |
20250919 11:53:56 [INFO] [V2] End [SCC piece] #1 ("keep", ("LlsssEndsAgar", "zero")) -> #1 ("keep", ("LlsssEndsAgar", "zero")):
20250919 11:53:56 [INFO] |  ZZZ |  ZZZ | ZZZ  | ZZZ  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
20250919 11:53:56 [INFO] |  ... |  ... | ...  | ...  |
...
In the V1 display it separates out that first shared step for the nose whereas in the V2 display it has duplicated it in the paths between the left and right agar SCCs.

I was unfortunately not able to come up with a particularly concise demo, but it is definitely true that V2 can blow up the output substantially in cases where there are a lot of small variations that can (will) be recombined. As an example, running a c2-f2b parallel stripes greyship edge search from the common diagonal edge back to itself has very different results with, say, mid_steps=10 at w_pos 34. V1 outputs 106 pieces, most of which are pretty thin. V2 outputs 438 pieces, most of which are very wide (more or less entire patterns) and the rest I think are all either small looping SCCs for the edges or very thin agar-only transitions near the edges due to how the slices ends works.

I've pushed the changes to codeberg as-is for now and I'm going to try to remember to use it in projects going forward. Once it's a little more battle-tested we can try to figure out if we want to switch the default.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I've sketched (and pushed) a slighty dubious version of an unstaggered_max_height constraint. When it is invoked it analyzes the in-memory state that has reached it to decide the shape of the grid, works out the intersection of the non-edge parts of the board, and then applies that intersection to all generations.

It will happily run and execute its logic in places that make no sense, but at least when run in normal s2s from-zeros searches it should do what's expected. It will print out its analysis when first reached (and twice for complicated reasons as it is "compiled" twice separately, once for state init and then once for expansions).

The sort of way I would expect to use it is like:

Code: Select all

$ rlife llsss 2c5-s2s '@bg:8' --constraint unstaggered_max_height --filters wcaf
Which will include output like:

Code: Select all

20250921 10:47:03 [INFO] LlsssConstraintUnstaggeredMaxHeight analysis:
20250921 10:47:03 [INFO]    |  ..???... |  ..???... |  ..???... | ...???..  | ...???..  |
Here our board width of 8 has been cut down to unstaggered height 3 due to losing 2 on the left edge, 2 on the right edge, and then one more from the single staggering in 2c/5.

If you ran board width 8 with 3c/7...

Code: Select all

$ rlife llsss 3c7-s2s '@bg:8' --constraint unstaggered_max_height --filters wcaf
...you'd get only width 2 as 3c/7 staggers twice:

Code: Select all

20250921 10:48:44 [INFO] LlsssConstraintUnstaggeredMaxHeight analysis:
20250921 10:48:44 [INFO]    |   ..??.... |   ..??.... |   ..??.... |  ...??...  |  ...??...  | ....??..   | ....??..   |
Theoretically it will work in recentering as well, although it will be very picky about root labels. E.g. we could run that "@bg:8" search more or less the same as:

Code: Select all

$ cat n1.in
|  uuuuuuuu |  uuuuuuuu |  uuuuuuuu | uuuuuuuu  | uuuuuuuu  |
|  ........ |  ........ |  ........ | ........  | ........  |
|  ........ |  ........ |  ........ | ........  | ........  |
|  ........ |  ........ |  ........ | ........  | ........  |
$ rlife llsss-recentering-wao 2c5-s2s 'n1.in' --constraint unstaggered_max_height XX
...
20250921 10:50:39 [INFO] LlsssConstraintUnstaggeredMaxHeight analysis:
20250921 10:50:39 [INFO]    |  ..???... |  ..???... |  ..???... | ...???..  | ...???..  |
...
It's different in that the expansion order for mid_steps=XX is very different than fixed board (badly) and WAO is different than WCAF, but the space of patterns findable should be the same.

I'm not in love with this rendition of this, especially the weird handling of mapping root labels to X positions very late in the game and the weird disconnect between board size and effective search size. Unfortunately, I don't really have any bright ideas on fixing either and I want to get this checked in so it can stop bit rotting. As usual for this sort of thing, please conider it provisional and I would love to hear if anyone makes anything of it.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I've sketched (and pushed) a "grid_loop" constraint similar to "grid", but looping the same W rows over and over again forever instead of deferring to a second, chained constraint. This is helpful when you have an endlessly repeating constraint but you don't know how long your search will be.

As an example, let's redo that 35 half diagonal search from above. Just like last time, we're gonna run with (the equivalent of) "@zero:12" input and make a constraint grid to trim the side, but this time I'm gonna make it just 8 W rows tall:

Code: Select all

$ cat n2.cstr.pre.uwi
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
| WWWWWWWWW1.. | WWWWWWWWW2.. |
$ rlife grid-tool from-uwi c4d-f2b < n2.cstr.pre.uwi > n2.cstr.pre
$ cat n2.cstr.pre
|                |                |            .   |            .   |
|            ..  |            ..  |           ...  |           ...  |
|           .... |           .... |          2...  |          2...  |
|          12..  |          12..  |         W12.   |         W12.   |
|         WW12   |         WW12   |        WWW1    |        WWW1    |
|        WWWW    |        WWWW    |       WWWW     |       WWWW     |
|       WWWW     |       WWWW     |      WWWW      |      WWWW      |
|      WWWW      |      WWWW      |     WWWW       |     WWWW       |
|     WWWW       |     WWWW       |    WWWW        |    WWWW        |
|    WWWW        |    WWWW        |   WWWW         |   WWWW         |
|   WWWW         |   WWWW         |  WWWW          |  WWWW          |
|  WWWW          |  WWWW          | WWWW           | WWWW           |
| WWWW           | WWWW           | WWW            | WWW            |
|  WW            |  WW            |  W             |  W             |
$ sed 's/1/W/g; s/2/./g' < n2.cstr.pre > n2.cstr
$ cat n2.cstr
|                |                |            .   |            .   |
|            ..  |            ..  |           ...  |           ...  |
|           .... |           .... |          ....  |          ....  |
|          W...  |          W...  |         WW..   |         WW..   |
|         WWW.   |         WWW.   |        WWWW    |        WWWW    |
|        WWWW    |        WWWW    |       WWWW     |       WWWW     |
|       WWWW     |       WWWW     |      WWWW      |      WWWW      |
|      WWWW      |      WWWW      |     WWWW       |     WWWW       |
|     WWWW       |     WWWW       |    WWWW        |    WWWW        |
|    WWWW        |    WWWW        |   WWWW         |   WWWW         |
|   WWWW         |   WWWW         |  WWWW          |  WWWW          |
|  WWWW          |  WWWW          | WWWW           | WWWW           |
| WWWW           | WWWW           | WWW            | WWW            |
|  WW            |  WW            |  W             |  W             |
$
From n2.cstr.pre to n2.cstr I replaced "1" with "W" and "2" with "." to constrain those two half diagonals as desired.

Now this constraint can be used, looped, like:

Code: Select all

$ rlife llsss --rule 'B3/S12' c4d-f2b '@zero:12' --constraint grid_loop:n2.cstr --left-edge odd --filters wcaf
You could also make it just one W row tall but it's a little harder to read and a little scarier-looking (but should produce the same exact search):

Code: Select all

$ cat n2x.cstr
|              |              |            . |
|            . |              |           .  |
|           .  |              |          .   |
|          W   |              |         W    |
|         W    |              |        W     |
|        W     |              |       W      |
|       W      |              |      W       |
|      W       |              |     W        |
|     W        |              |    W         |
|    W         |              |   W          |
|   W          |              |  W           |
|  W           |              | W            |
| W            |              |              |
$ rlife llsss --rule 'B3/S12' c4d-f2b '@zero:12' --constraint grid_loop:n2x.cstr --left-edge odd --filters wcaf
...
Linked wildcards that persist up and down the column (like "y"/"Y" or "A" in default configuration) should correctly be allowed to be whatever in their first instance in the first repeat, but then link within repeats and even across repeats, really as if you had specified an infinitely looped copy of your grid. I struggle to imagine a real use for this behavior, but I tested it with something like...

Code: Select all

$ cat n3.in
| uuRRRRR |
| WWWWW.. |
| WWWWW.. |
$ cat n3.cstr
| uuRRRRR |
| ABWWWWW |
$ rlife llsss-recentering p1 n3.in --left-edge odd --constraint grid_loop:n3.cstr --ends none 06
...
...and partials have each of their first two columns always all on or all off.

This feature can probably be considered a little more final (as final as anything ever is for LLSSS), as I'm pretty happy with its behaviour and structure.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I've extended the geometry name parser to understand notation like "3c4-f2b/U=X+W" or "c2-s2s/W=2Y". I've been naming these sorts of geometries like this pretty consistently in discussion and hopefully those involved in those conversations have been able to make sense of it, but now it's programmatically defined and should be much less error-prone to use than mucking about with "raw:...".

As examples, some slanted geometries:

Code: Select all

$ rlife grid-tool geom-info c2-f2b/U=X-2T
Geometry: c2-f2b/U=X-2T
   U: Vec3(1, 0, -2)
   V: Vec3(0, -1, 2)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 9
   Unique positions (1):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
   WAO maximal tile masks: WaoTileMasks(1 = 0b1, 1 = 0b1)
$ rlife grid-tool geom-info 3c4-f2b/U=X+W
Geometry: 3c4-f2b/U=X+W
   U: Vec3(1, 1, -1)
   V: Vec3(0, -3, 4)
   W: Vec3(0, 1, -1)
   Neighborhood sizes:
      U: 3
      W: 11
   Unique positions (1):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
   WAO maximal tile masks: WaoTileMasks(1 = 0b1, 1 = 0b1)
$ rlife grid-tool geom-info p4/U=X+Y
Geometry: p4/U=X+Y
   U: Vec3(1, 1, 0)
   V: Vec3(0, 0, 4)
   W: Vec3(0, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 5
   Unique positions (4):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(0, 1, 0)
      #2: Vec3(0, 0, 2) => Vec3Uvw(0, 2, 0)
      #3: Vec3(0, 0, 3) => Vec3Uvw(0, 3, 0)
   WAO maximal tile masks: WaoTileMasks(15 = 0b1111, 15 = 0b1111)
$
Geometries forcing W=Y where it would otherwise be merely T-like:

Code: Select all

$ rlife grid-tool geom-info c2-f2b/W=Y
Geometry: c2-f2b/W=Y
   U: Vec3(1, 0, 0)
   V: Vec3(0, -1, 2)
   W: Vec3(0, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, 0, 1) => Vec3Uvw(0, 1, 1)
   WAO maximal tile masks: WaoTileMasks(2 = 0b10, 2 = 0b10)
$ rlife grid-tool geom-info 2c4-f2b/W=Y
Geometry: 2c4-f2b/W=Y
   U: Vec3(1, 0, 0)
   V: Vec3(0, -2, 4)
   W: Vec3(0, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (4):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 2) => Vec3Uvw(0, 2, 0)
      #2: Vec3(0, 0, 1) => Vec3Uvw(0, 1, 2)
      #3: Vec3(0, -1, 3) => Vec3Uvw(0, 3, 2)
   WAO maximal tile masks: WaoTileMasks(12 = 0b1100, 12 = 0b1100)
$ rlife grid-tool geom-info 2c5-f2b/W=Y
Geometry: 2c5-f2b/W=Y
   U: Vec3(1, 0, 0)
   V: Vec3(0, -2, 5)
   W: Vec3(0, 1, 0)
   Neighborhood sizes:
      U: 3
      W: 3
   Unique positions (5):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 3) => Vec3Uvw(0, 3, 1)
      #2: Vec3(0, 0, 1) => Vec3Uvw(0, 1, 2)
      #3: Vec3(0, -1, 4) => Vec3Uvw(0, 4, 3)
      #4: Vec3(0, 0, 2) => Vec3Uvw(0, 2, 4)
   WAO maximal tile masks: WaoTileMasks(16 = 0b10000, 16 = 0b10000)
$
And that one silly geometry with W=2Y I used to help reason about WAO tile error masks:

Code: Select all

$ rlife grid-tool geom-info c2-s2s/W=2Y
Geometry: c2-s2s/W=2Y
   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)
$
User avatar
Katrina
Posts: 161
Joined: September 26th, 2024, 3:23 am

Re: amling search program principles discussion / brain dump

Post by Katrina »

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

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

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

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

Anyway, that is all boring and especially painful but it gets rid of a lot of hideous edge cases in CA check code and bitvector management. Most searches pick V to be translation, U to be (M, 0, 0), W to be some weirdo vector to minimize lattice volume and are set.
(.,.)
Is there a better explanation for what type of lattice is being used here? Is there a name for what type of lattice is being used? Why can't I find any meaningful definition of "UVW" coordinates that match these?
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sylvani wrote: October 1st, 2025, 11:13 am
amling wrote: May 4th, 2022, 11:04 pm ...
Is there a better explanation for what type of lattice is being used here? Is there a name for what type of lattice is being used? Why can't I find any meaningful definition of "UVW" coordinates that match these?
Right, right. When I reread what I wrote above, it is definitely littered with defects somewhere on the scale from imprecision to outright mistake. When I wrote it I was in a hurry (I had a lot to write) and unsure what my readers would know, both in an absolute sense of how much, but also by what names (math versus CS background). I chose wobbly, intuitive words rather than precise math words, hoping that it would give more people a better shot at parsing it and that the serious mathematicians might be able to figure it out anyway.

As an example, where I write "lattice" above here in the thread I almost exclusively mean "finitely-generated free abelian group, possibly with a specific arrangement of intended generators and possibly with specific intended names for them". I.e. by "XYT lattice" I mean integer coordinates in 3-space (Z^3) where I'm thinking of it as generated by (1, 0, 0) which I'd call X, (0, 1, 0) which I'd call Y, and (0, 0, 1) which I'd call T. When I write "lattice volume" I'm thinking of the lattice as embedded in a bigger abelian group and carving it up, e.g. the way Z^3 carves up R^3 into 1x1x1 cubes.

So if I could redo the above, what would change? XYT and UVW coordinates still makes sense. U, V, and W are three elements of Z^3 that are linearly independent. The planes of the form U (coordinate, not vector) = N, V = N, or W = N for each integer N collectively slice R^3 (thought of as XYT coordinates) into parallelepipeds. If you think of these parallelepipeds as closed on one half of sides (the side of lower U/V/W coordinate) and open on the other, they similarly divide Z^3 into ... something. I use "lattice volume" up thread for both of these notions (the parallelepipeds in R^3 and the sets of Z^3 points that are grouped together).

After doing some googling of my own, I see that Wikipedia's "Lattice (group)" page discusses some of this and is more or less what I have meant (and "Lattice (order)" discusses a completely different, unrelated mathematical notion). It also informs me "lattice volume" I guess should be "fundamental region" which is not something I would call it if not specifically writing to a math audience.
User avatar
Katrina
Posts: 161
Joined: September 26th, 2024, 3:23 am

Re: amling search program principles discussion / brain dump

Post by Katrina »

Sylvani wrote: August 31st, 2025, 10:15 pm ...
I've been thinking about this again, and I have no idea if you'll ever implement this, but maybe there could be some way to read the dumped state file from LLSSS and get the thinnest partial (and maybe other partials along with it) up to that part of the search?
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

Sylvani wrote: October 4th, 2025, 3:20 pm
Sylvani wrote: August 31st, 2025, 10:15 pm ...
I've been thinking about this again, and I have no idea if you'll ever implement this, but maybe there could be some way to read the dumped state file from LLSSS and get the thinnest partial (and maybe other partials along with it) up to that part of the search?
You mean for recentering again? I'm a little confused as searches already show the thinnest partial as they go, although they label it "shortest" as it is the shortest path from the left edge of the state file to the right edge. I recognize that was perhaps not a great choice and I'm going to go relabel it "Thinnest partial" right now.

I am not particularly likely to write any further visualizations of search state without a fairly compelling use or a fairly new (and specific!) idea. Thinnest partial ("shortest" up until just a moment ago), random partial, and SRV2 already cover so much ground in terms of trying to find interesting partials by eye.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

I took another crack at the max pop custom weight code and I think I like this version better than the last sketch of it. This one allows configuration per combination of root label and depth, but with a built-in default of:

Code: Select all

[
    [['0', null], [0, 0]],
    [['1', null], [1, 0]],
    [['2', null], [2, 0]],
    [['G', null], [1, 1]],
]
This codes the 0/1/2/G behavior we do right now (and "@maxpop" magic grid expects). The fields are root label, depth ("null" is the default at every unconfigured depth), the own generation weight, and the GS-flipped generation weight.

With this I took a look at trying to push on the c4/d non-trivial gutter pop limits (>29, <=50 right now).

Even before these changes you could search for c4d-s2s non-trivial gutter ships with a gnarly input file like:

Code: Select all

$ cat g.pre
| LLLLLuRRRRR | LLLLLuRRRRR | LLLLLuRRRRR | LLLLLuRRRRR | LLLLLuRRRRR | LLLLLuRRRRR | LLLLLuRRRRR | LLLLLuRRRRR |
| .....*AAA.. | .....AAAA.. | .....AAAA.. | .....AAAA.. | ........... | ........... | ........... | ........... |
| .....*AAA.. | .....AAAA.. | .....AAAA.. | .....AAAA.. | ..WWWWWWW.. | ..WWWWWWW.. | ..WWWWWWW.. | ..WWWWWWW.. |
$ ./rlife grid-tool from-uwi c4d-s2s < g.pre > g.in
$ cat g.in
|     L           |     L           |    LL           |    LL           |
|    .LL          |    .LL          |   ..LL          |   ..LL          |
|   ...LL         |   ...LL         |  ....LL         |  ....LL         |
|   ....LL        |   ....LL        |   ....LL        |   ....LL        |
|    ....LL       |    ....LL       |    W...LL       |    W...LL       |
|     W...Lu      |     W...Lu      |     W...uu      |     W...uu      |
|      W..*uR     |      W..AuR     |      W..ARR     |      W..ARR     |
|       W*.ARR    |       WA.ARR    |       WA.ARR    |       WA.ARR    |
|        WA.ARR   |        WA.ARR   |        WA.ARR   |        WA.ARR   |
|         WA.ARR  |         WA.ARR  |         WA.ARR  |         WA.ARR  |
|          WA..RR |          WA..RR |          WA..RR |          WA..RR |
|           W...R |           W...R |           ....  |           ....  |
|            ...  |            ...  |            ..   |            ..   |
|             .   |             .   |                 |                 |
$
Here "non-trivial" is taken to mean "some cell is on in the half-diagonal adjacent to the gutter HD". I've marked a chosen first (in T order) such cell and built the input file around it.

As there are no even birth conditions in S23/B3 there is no concern about not completing the CA check on the gutter itself. In rules with even birth conditions you would have to scroll another HD into view and would probably die on wildcard combinatorial explosion.

Now with --max-pop added for non-WAO recentering and custom weight config we could max-pop this. But what weights where?

Depths 0-3 are I0-I3 in the first W row and are the duplicated HD on the "far" side of the gutter. Depth 4-7 are I4-I7 in the first W row and are the HD that is the gutter. Depth 8-11 are I0-I3 in the second W row and are the duplicated HD on the "near" side of the gutter ("A" wildcard is generated independently per subtile-position and persists from W row to W row). Depth 12+ are the rest of the ship somewhat more "away" from the gutter and only appear once in view.

It would be morally superior to weight depths 0-11 with 1 and everything else with 2, but it makes a bigger config file. You get the same results if you weight depths 0-3 with 0 and everything else with 2 and it's less configuration that way:

Code: Select all

$ cat g.wcfg
[
    [['L', 0], [0, 0]],
    [['L', 1], [0, 0]],
    [['L', 2], [0, 0]],
    [['L', 3], [0, 0]],
    [['L', null], [2, 0]],
    [['u', 0], [0, 0]],
    [['u', 1], [0, 0]],
    [['u', 2], [0, 0]],
    [['u', 3], [0, 0]],
    [['u', null], [2, 0]],
    [['R', 0], [0, 0]],
    [['R', 1], [0, 0]],
    [['R', 2], [0, 0]],
    [['R', 3], [0, 0]],
    [['R', null], [2, 0]],
]
$
Finally we can run with something like...

Code: Select all

$ rlife llsss-recentering c4d-s2s g.in --max-pop 00:10 --llsss-env LLSSS_MAX_POP_WEIGHT_CONFIG=g.wcfg --ends none XX
$ rlife llsss-recentering c4d-s2s g.in --max-pop 01:10 --llsss-env LLSSS_MAX_POP_WEIGHT_CONFIG=g.wcfg --ends none XX
$ rlife llsss-recentering c4d-s2s g.in --max-pop 02:10 --llsss-env LLSSS_MAX_POP_WEIGHT_CONFIG=g.wcfg --ends none XX
$ rlife llsss-recentering c4d-s2s g.in --max-pop 03:10 --llsss-env LLSSS_MAX_POP_WEIGHT_CONFIG=g.wcfg --ends none XX
I've just started running these. Pop 10 worst gen internal memory was 1.60 GB and pop 15 was 8.57 GB. I've started the line of searches from pop 16 onward, but I'm not optimistic as naive projection (admittedly from only these two very early data points) puts pop 30 at 1.28 TB.

Also unfortunately I don't think this is gonna allow anything for odd symmetry c4/d. The problem is any framing of it is going to involve 3 distinct HDs in initialization which is going to end up with 36 wildcard bits in the worst AF2 window. In the most compact form the jcol is 8 bytes per entry and you've got 2^36 of them which is 512 GB of just that, not to mention all the other various overheads and duplications on the way. Even with the 1TB computer I don't think there is any surviving that.

I've pushed both --max-pop for non-WAO recentering and LLSSS_MAX_POP_WEIGHT_CONFIG to codeberg just now. As always, maybe let me know if you get up to anything with it.

EDIT: I almost immediately thought better of the configuration. I've simplified it and also made it slightly more flexible (just pushed). Now it's specified by subtile position and W position (rather than depth) and you can specify any prefix of (root label, subtile pos, w pos) and it will default accordingly. You can also omit the GS-flipped weight. As an example:

Code: Select all

[
    [null, 1],
    ['A', 2],
    [['B', 0], 3],
    [['C', 0, 0], [4, 5]],
]
User avatar
ThePlayzr
Posts: 788
Joined: April 19th, 2025, 1:33 am
Location: Australia
Contact:

Re: amling search program principles discussion / brain dump

Post by ThePlayzr »

Does anyone know how to set up LLSSS to search for negative zebra stripe against-the-grain spaceships?
Edit: I want this for b3s23-a5.
Last edited by ThePlayzr on October 8th, 2025, 2:11 am, edited 1 time in total.
Please visit my rules (found on my wiki page) and contribute!
User:ThePlayzr
I have LLS and qfind.
My avatar is the 80th most common pattern, and I have the 80th most posts on the forums.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

ThePlayzr wrote: October 7th, 2025, 7:03 am Does anyone know how to set up LLSSS to search for negative zebra stripe against-the-grain spaceships?
I think this is answered (or at least implied) at length above. It's mostly just use "--bg-agar" with either "vertical-stripes" or "horizontal-stripes" and off you go. Most features that could make any sense should do the right thing once --bg-agar is set.

For S23/B3 I think these spaces are well searched. My understanding is that 2c/3 has a wealth of (known) complex signals, 2c/4 is almost certain to have no finite signals (of strict 2c/4 period 4), although any form of proof eludes me, and 2c/5+ all seem intractable to get much of any real searching done and all partials I've seen look unhealthily pyramidal. There is maybe a chance a finite 4c/8 signal exists but any searches in that range are gummed up horribly by the known 2c/1 x 2c/4 edge.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

amling wrote: August 29th, 2025, 3:39 pm I'm still chewing on the ideas for a potential EDBV4.
I've done a bunch of further work towards a hypothetical EDBV4:

As written, V4 databases are sort of the combination of slices-tool slice collections and V3 databases. Like in V3 databases we keep "edges" which are steps from one W overlap-sized slice to another with a known U position change and a string "provenance". Like slices-tool slice collections we have a notion of left/right agar and all slices know their positions in them. Sort of like both, there is a distinct collection of W overlap-sized slices, "ends", which are considered to be irreducible goals.

There is a tool that can read a V3 database and rewrite it in V4 format. Even on the biggest V3 databases I have (ingested from knightt-results) this only takes ~10s and adds maybe 7% file size overhead so that's looking pretty good.

There is of course an "--ends edbv4:..." that will search for slices in the database and show completions. I was able to keep much of the structure of the V3 ends (and I expect the performance), at the cost of making minor assumptions about agars. The matcher (and in fact much of the V4 altogether) requires that all slices are either (a) "background" slices, namely of zero width and with equal positions in equal left/right agars, or (b) "anchored" slices, namely slices where there is a [first] U column that mismatches the left agar. Pathological slices that do not meet either of these criteria (called "slippery" in the code) can exist in a general sense, although I hope no one will need one in practice. The simplest would be something like an all-zeros slices in a database where the left agar was zeros and the right agar was a still life of one frozen generation of horizontal venetian blinds (in a rule with S5i and without B3i).

I also wrote a bunch of tools to manage V4 databases although they are rather verbose and weird. In the long term I would probably like to write simpler ingesters for typical uses, but right now I just want to get this all baking and the tools represent a complete set of transformations of the formats involved.

Let's walk through building a f2b database for 2c/3 horizontal stripe crawlers and demo finding a result with it:

First, get a known 2c/3 signal (jslife says from HH, 2006), padded with some agar to make sure the ingest can make sense of it.

Code: Select all

x = 114, y = 123, rule = B3/S23
114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o
2$114o2$114o2$114o2$55o4b55o2$54o6b54o$54bo4bo$55o4b55o$53b8o$51o4bo2b
o4b51o$51bo3bo2bo3bo$51o12b51o$52bo8bo$53o8b53o$53bo6bo$55o4b55o2$52o
3b4o3b52o$56b2o$51o12b51o$51bo10bo$53o8b53o$53bo6bo$54o6b54o$54bo4bo$
53o3b2o3b53o$56b2o$51o12b51o$51bo10bo$52o10b52o$52bo8bo$54o6b54o$54bo
4bo$55o4b55o$53b8o$51o4bo2bo4b51o$51bo3bo2bo3bo$51o12b51o$52bo8bo$53o
8b53o$53bo6bo$55o4b55o2$52o3b4o3b52o$56b2o$51o12b51o$51bo10bo$53o8b53o
$53bo6bo$54o6b54o$48b2o4bo4bo4b2o$46o6b4o2b4o6b46o$46bo3b2o3bo2bo3b2o
3bo$46o9bo2bo9b46o$47bo5bo6bo5bo$48o6bo4bo6b48o$48bo4b2ob2ob2o4bo$50o
4bo4bo4b50o$50b2o4b2o4b2o$46o2b3obo2bo2bo2bob3o2b46o$53b3o2b3o$44o6b3o
bo4bob3o6b44o$44bo4bo14bo4bo$45o8bo6bo8b45o$45bo3b2o2bo2b2o2bo2b2o3bo$
47o5bob2o2b2obo5b47o$47bo2bob2o6b2obo2bo$48o3b2o8b2o3b48o$49bo14bo$55o
4b55o$55b4o$56o2b56o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$
114o2$114o2$114o2$114o!

Code: Select all

$ cat sg1.rle
#CXRLE Pos=54,-8
x = 114, y = 123, rule = B3/S23
114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o
2$114o2$114o2$114o2$55o4b55o2$54o6b54o$54bo4bo$55o4b55o$53b8o$51o4bo2b
o4b51o$51bo3bo2bo3bo$51o12b51o$52bo8bo$53o8b53o$53bo6bo$55o4b55o2$52o
3b4o3b52o$56b2o$51o12b51o$51bo10bo$53o8b53o$53bo6bo$54o6b54o$54bo4bo$
53o3b2o3b53o$56b2o$51o12b51o$51bo10bo$52o10b52o$52bo8bo$54o6b54o$54bo
4bo$55o4b55o$53b8o$51o4bo2bo4b51o$51bo3bo2bo3bo$51o12b51o$52bo8bo$53o
8b53o$53bo6bo$55o4b55o2$52o3b4o3b52o$56b2o$51o12b51o$51bo10bo$53o8b53o
$53bo6bo$54o6b54o$48b2o4bo4bo4b2o$46o6b4o2b4o6b46o$46bo3b2o3bo2bo3b2o
3bo$46o9bo2bo9b46o$47bo5bo6bo5bo$48o6bo4bo6b48o$48bo4b2ob2ob2o4bo$50o
4bo4bo4b50o$50b2o4b2o4b2o$46o2b3obo2bo2bo2bob3o2b46o$53b3o2b3o$44o6b3o
bo4bob3o6b44o$44bo4bo14bo4bo$45o8bo6bo8b45o$45bo3b2o2bo2b2o2bo2b2o3bo$
47o5bob2o2b2obo5b47o$47bo2bob2o6b2obo2bo$48o3b2o8b2o3b48o$49bo14bo$55o
4b55o$55b4o$56o2b56o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$114o2$
114o2$114o2$114o2$114o!
$
Now run the slices-tool one generation partial ingester to collect all the slices of W height 7 (in 2c3-f2b W overlap is 6 W rows and so for these to make the edges of an ends database they need to be one longer).

Code: Select all

$ rlife slices-tool ingest-1gp 2c3-f2b --left-agar horizontal-stripes --right-agar horizontal-stripes --w-size 7 --w-cuts ALL sg1.rle sg1.W07.slices
...
20251008 15:35:12 [INFO] Total of 117 slices.
20251008 15:35:12 [INFO] Saved to "sg1.W07.slices".
$
Ingest those slices to V4 format. By default the slices ingester does not mark them as ends, which is appropriate for a non-repeating part like this. If we were building a greyship edge database we would do an ingest like this with a known seam but include --mark-ends=true to provide a foundation to build a database on.

Code: Select all

$ rlife edb-tool v4-from-slices 2c3-f2b sg1-only.edbv4 sg1.W07.slices
20251008 15:37:20 [INFO] Geometry: Vec3(1, 0, 0), Vec3(0, -2, 3), Vec3(0, 1, -1)
20251008 15:37:20 [INFO] Wrote slices EDBV4 to "sg1-only.edbv4": 115 slices, 0 ends, 115 edges
$
Make a baseline database from the agar (these slice will be marked as ends).

Code: Select all

$ rlife edb-tool v4-from-agar 2c3-f2b bg.edbv4 horizontal-stripes
20251008 15:37:53 [INFO] Geometry: Vec3(1, 0, 0), Vec3(0, -2, 3), Vec3(0, 1, -1)
20251008 15:37:53 [INFO] Wrote initial horizontal-stripes agar-only EDBV4 to "bg.edbv4": 2 slices, 2 ends, 2 edges
$
Now merge the agar baseline with the slices from the known signal.

Code: Select all

$ rlife edb-tool v4-merge sg1.edbv4 bg.edbv4 sg1-only.edbv4
20251008 15:38:13 [INFO] Read "bg.edbv4": 2 slices, 2 ends, 2 edges
20251008 15:38:13 [INFO] Merged totals: 2 slices, 2 ends, 2 edges
20251008 15:38:13 [INFO] Read "sg1-only.edbv4": 115 slices, 0 ends, 115 edges
20251008 15:38:13 [INFO] Merged totals: 115 slices, 2 ends, 117 edges
20251008 15:38:13 [INFO] Wrote merged EDBV4 to "sg1.edbv4": 115 slices, 2 ends, 117 edges
$
It doesn't print anything about it, but by default v4-merge "link checks" the resulting database to make sure all parts have a solution path to an "end" slice. This will also be done later when loaded for use in an actual search.

Now we can run a search like...

Code: Select all

$ rlife llsss-recentering-wao 2c3-f2b --bg-agar horizontal-stripes '@bg' --ends edbv4:sg1.edbv4 10
...
It's of course a little silly since we're starting from BG and it's just gonna find the first slice immediately.

Code: Select all

...
20251008 15:39:39 [INFO] End [thinnest] "LlsssEndsEdbv4":
20251008 15:39:39 [INFO] |        | ZZZZZZ | ...... |
20251008 15:39:39 [INFO] | ****** | ****** | ****** |
20251008 15:39:39 [INFO] | ...... | ...... |        |
20251008 15:39:39 [INFO] | **..** |        |        |
...
20251008 15:39:39 [INFO] Completion [bg delta]:
20251008 15:39:39 [INFO] |                                |                                | ****************************** |
20251008 15:39:39 [INFO] | .............................. | .............................. | .............................. |
20251008 15:39:39 [INFO] | ****************************** | **************..************** | *************....************* |
20251008 15:39:39 [INFO] | ..............**.............. | .............................. | .............................. |
20251008 15:39:39 [INFO] | ************......************ | ************......************ | ************......************ |
20251008 15:39:39 [INFO] | ............*....*............ | ............*....*............ | ............*....*............ |
20251008 15:39:39 [INFO] | ************......************ | *************....************* | *************....************* |
20251008 15:39:39 [INFO] | ............*....*............ | .............................. | ...........********........... |
20251008 15:39:39 [INFO] | ***********...**...*********** | **********...****...********** | *********....*..*....********* |
20251008 15:39:39 [INFO] | ..............**.............. | ..............**.............. | .........*...*..*...*......... |
20251008 15:39:39 [INFO] | *********............********* | *********............********* | *********............********* |
20251008 15:39:39 [INFO] | .........*..........*......... | .........*..........*......... | ..........*........*.......... |
20251008 15:39:39 [INFO] | **********..........********** | ***********........*********** | ***********........*********** |
20251008 15:39:39 [INFO] | ..........*........*.......... | ...........*......*........... | ...........*......*........... |
20251008 15:39:39 [INFO] | ************......************ | ************......************ | ******..*****....*****..****** |
20251008 15:39:39 [INFO] | ............*....*............ | ......**....*....*....**...... | .............*..*............. |
20251008 15:39:39 [INFO] | *****....****....****....***** | ****......****..****......**** | ****...*****.*..*.*****...**** |
20251008 15:39:39 [INFO] | .......*.....*..*.....*....... | ....*...**...*..*...**...*.... | ....*....***.****.***....*.... |
20251008 15:39:39 [INFO] | ****....*..*.*..*.*..*....**** | ****.........*..*.........**** | *****.......*....*.......***** |
20251008 15:39:39 [INFO] | ....*........****........*.... | .....*.....*......*.....*..... | .....*......*....*......*..... |
20251008 15:39:39 [INFO] | ******....*.*.**.*.*....****** | ******......*....*......****** | *******.....**..**.....******* |
20251008 15:39:39 [INFO] | ......*....**....**....*...... | ......*....**.**.**....*...... | .......*...**....**...*....... |
20251008 15:39:39 [INFO] | *******......*..*......******* | ********....*....*....******** | *********..**....**..********* |
20251008 15:39:39 [INFO] | ........*............*........ | ........**....**....**........ | .........*...****...*......... |
20251008 15:39:39 [INFO] | *********.**..**..**.********* | ****..***.*..*..*..*.***..**** | ***....**.**.*..*.**.**....*** |
20251008 15:39:39 [INFO] | ....**...*...****...*...**.... | ...........***..***........... | .............*..*............. |
20251008 15:39:39 [INFO] | **......***..*..*..***......** | **......***.*....*.***......** | **......***.**..**.***......** |
20251008 15:39:39 [INFO] | ..*....*.....****.....*....*.. | ..*....*..............*....*.. | ..*.....****......****.....*.. |
20251008 15:39:39 [INFO] | **......*...**..**...*......** | ***........*......*........*** | ****...**............**...**** |
20251008 15:39:39 [INFO] | ...*.......**....**.......*... | ...*...**..*..**..*..**...*... | ....*.....**.****.**.....*.... |
20251008 15:39:39 [INFO] | ****...**...*.**.*...**...**** | *****.....*.**..**.*.....***** | *****..**.*.******.*.**..***** |
20251008 15:39:39 [INFO] | ....*.....**......**.....*.... | .....*..*.**......**.*..*..... | .....*......*....*......*..... |
20251008 15:39:39 [INFO] | ******...**........**...****** | ******...**........**...****** | *******.****......****.******* |
20251008 15:39:39 [INFO] | ............*.**.*............ | .......*..............*....... | .......*..............*....... |
20251008 15:39:39 [INFO] | ************......************ | *************....************* | ****************************** |
20251008 15:39:39 [INFO] | .............****............. | .............****............. | ..............**.............. |
20251008 15:39:39 [INFO] | **************..************** | **************..************** | **************..************** |
20251008 15:39:39 [INFO] | .............................. | .............................. | .............................. |
20251008 15:39:39 [INFO] | ****************************** | ****************************** | ****************************** |
20251008 15:39:39 [INFO] | .............................. |                                |                                |
20251008 15:39:39 [INFO] Provenances:
20251008 15:39:39 [INFO]    110x "sg1.W07.slices"
...
How exactly it chooses to weight completions is again complicated but I believe it should generally find smaller ones and then similar to V3 ends best left and right clearance completions if they are distinct. Similarly it makes its best guess and pads the output with a little extra agar (AF1 U columns worth) on the sides for nonzero agars.

This is pushed to codeberg as 20251008-edbv4-21, but it is still quite rough. TBD stress testing it on real searches with real databases, figuring out how much of the V3 ingester I want to rewrite, etc.
User avatar
Aleph
Posts: 2276
Joined: February 18th, 2021, 11:18 am

Re: amling search program principles discussion / brain dump

Post by Aleph »

amling wrote: October 9th, 2025, 5:46 pm
wwei47 wrote: October 9th, 2025, 12:06 pm Do you mind also attempting c/2 (almost definitely impossible), and c/4 (looking really bad in RLS right now)?
I'm curious if there is a reason you can't run these yourself instead of waiting/hoping for me to get around to it.
I fear that my 16GB of RAM won't get me anywhere.
amling
Posts: 1212
Joined: April 2nd, 2020, 9:47 pm

Re: amling search program principles discussion / brain dump

Post by amling »

wwei47 wrote: October 10th, 2025, 9:51 am
amling wrote: October 9th, 2025, 5:46 pm I'm curious if there is a reason you can't run these yourself instead of waiting/hoping for me to get around to it.
I fear that my 16GB of RAM won't get me anywhere.
All the successful searches I ran (2c4-f2b, 2c5-f2b, 3c6-f2b, 4c8-f2b, c2-f2b, c2-s2s) finished in under a gigabyte of VmPeak (memory from OS point of view). The c/4 stuff was of course a huge mess and I'd presumably be looking at that either way, but you could easily have done all the others and it would have been a kindness to me.
User avatar
Aleph
Posts: 2276
Joined: February 18th, 2021, 11:18 am

Re: amling search program principles discussion / brain dump

Post by Aleph »

amling wrote: October 10th, 2025, 2:28 pm All the successful searches I ran (2c4-f2b, 2c5-f2b, 3c6-f2b, 4c8-f2b, c2-f2b, c2-s2s) finished in under a gigabyte of VmPeak (memory from OS point of view). The c/4 stuff was of course a huge mess and I'd presumably be looking at that either way, but you could easily have done all the others and it would have been a kindness to me.
Oh wow. I apologize for the misunderstanding then: I was under the impression that LLSSS tended to require hundreds of gigabytes of RAM to do stuff, but it seems like I was wrong.
Sokwe
Moderator
Posts: 3375
Joined: July 9th, 2009, 2:44 pm

Re: amling search program principles discussion / brain dump

Post by Sokwe »

wwei47 wrote: October 10th, 2025, 3:37 pm I was under the impression that LLSSS tended to require hundreds of gigabytes of RAM to do stuff
I've made many discoveries using LLSSS with only ~5GB of free RAM on my craptop. If a problem starts using too much RAM and you want to continue the search at larger widths (and you don't care about the completeness of the search), you can use the `--pre-reify-autochoke <memory-limit>` option to limit memory usage (actual memory usage will still be somewhat higher than <memory-limit>). See prior posts in this thread for details on using this option.
-Matthias Merzenich
Post Reply