ConwayLife.com

Forums for Conway's Game of Life
https://conwaylife.com/forums/

amling search program principles discussion / brain dump

https://conwaylife.com/forums/viewtopic.php?t=5646

Page 26 of 27

Re: amling search program principles discussion / brain dump

Posted: October 9th, 2026, 2:27 pm
by amling
I think the filter and final partials stuff is looking pretty good. As I said above, simple use should be more or less unaffected but weird uses of filters or DL stuff will probably need to know some details.

The final partials stuff makes "--pre-partials none" slightly less weird. I still struggle to imagine wanting to have no idea what the search was doing until it finishes, but it works at least. If anyone is out there and does (want to) run LLSSS this way maybe drop me a line and let me know you exist?

I added LLSSS_LOG_LEVEL which can be used to restrict logs to that level and up. The order right now is DEBUG, INFO, WARNING, ERROR and the default is DEBUG (get everything). I've also banished a modest amount of spammier stuff to DEBUG.

Combining all this, search output can be pretty quiet now:

Code: Select all

$ rlife llsss-recentering-wao c2-f2b '@bg' 18 --llsss-env LLSSS_LOG_LEVEL=INFO --pre-partials none
20261009 10:51:49 [INFO] Start file magic grid generated:
20261009 10:51:49 [INFO] |     | ZZZ |
20261009 10:51:49 [INFO] | ... | ... |
20261009 10:51:49 [INFO] | ... | ... |
20261009 10:51:49 [INFO] | ... |     |
20261009 10:51:49 [INFO] WAO error window #0 (included):
20261009 10:51:49 [INFO] |       | ZZZZZ |
20261009 10:51:49 [INFO] | ..... | ..... |
20261009 10:51:49 [INFO] | ..... | ..... |
20261009 10:51:49 [INFO] | ..xWW |       |
20261009 10:51:49 [INFO] Start: precompile
20261009 10:51:49 [INFO] Finish: precompile -> took 23.941956ms (327.227ms user, 7µs sys)
20261009 10:51:49 [INFO] Start: search proper
20261009 10:51:49 [INFO] Cols sizes: 4 / 5
20261009 10:51:49 [INFO] Completed w_pos 4: 256 B, 12.989996ms
20261009 10:51:49 [INFO] Cols sizes: 8 / 14
20261009 10:51:49 [INFO] Completed w_pos 5: 416 B [+47.62%], 13.11836ms [+0.98%]
20261009 10:51:49 [INFO] Cols sizes: 14 / 24
20261009 10:51:49 [INFO] Completed w_pos 6: 1.15 KB [+95.48%], 14.313295ms [+8.71%]
...
20261009 10:51:51 [INFO] Completed w_pos 25: 12.33 KB [-17.99%], 41.396617ms [-21.39%]
20261009 10:51:51 [INFO] Cols sizes: 419 / 706
20261009 10:51:51 [INFO] Completed w_pos 26: 12.19 KB [-1.15%], 38.759995ms [-6.58%]
20261009 10:51:51 [INFO] Cols sizes: 415 / 627
20261009 10:51:51 [INFO] Completed w_pos 27: 10.17 KB [-18.03%], 37.87855ms [-2.30%]
20261009 10:51:51 [INFO] Cols sizes: 337 / 476
20261009 10:51:51 [INFO] Last thinnest partial RLE:
x = 49, y = 14, rule = LifeHistory
F.21B.F.21B.F$F.21B.F.21B.F$F.8BA3BA8B.F.7B3AB3A7B.F$F.7B3AB3A7B.F.6B
A2BABA2BA6B.F$F.6B2ABABAB2A6B.F.5BA3BABA3BA5B.F$F.5B2A7B2A5B.F.5BA9BA
5B.F$F.6BA7BA6B.F.7BA5BA7B.F$F.5B2A7B2A5B.F.4BABA7BABA4B.F$F.3B2ABABA
BABABAB2A3B.F.3B2AB2AB3AB2AB2A3B.F$F.3BA5BABA5BA3B.F.3BAB3ABABAB3ABA
3B.F$F.5BABABABABABA5B.F.2B2A5BABA5B2A2B.F$F.2B2ABABABABABABAB2A2B.F.
5BABABABABABA5B.F$F.5B2ABA3BAB2A5B.F.2B4A9B4A2B.F$F.2BA4BAB2AB2A4BA2B
.F.3B2ABAB2A3B2ABABA2B.F!
20261009 10:51:51 [INFO] Cols sizes hash: 0xA2A35BEF89A6CF63
20261009 10:51:51 [INFO] LlsssStepExpandRecentering: max pre-reify estimated mem: 196.36 KB
20261009 10:51:51 [INFO] Finish: search proper -> took 1.792972403s (22.111414s user, 651.021ms sys)
20261009 10:51:51 [INFO] Final results: 0 normal
20261009 10:51:51 [INFO] Done
$

Code: Select all

$ rlife llsss c2-f2b '@bg(22)' --filters bcaf --llsss-env LLSSS_LOG_LEVEL=INFO --pre-partials none
20261009 10:53:09 [INFO] Start file magic grid generated:
20261009 10:53:09 [INFO] | ...................... | ...................... |
20261009 10:53:09 [INFO] | ...................... | ...................... |
20261009 10:53:09 [INFO] Start: precompile
20261009 10:53:09 [INFO] Finish: precompile -> took 28.186804ms (341.657ms user, 3.441ms sys)
20261009 10:53:09 [INFO] Start: search proper
20261009 10:53:09 [INFO] Cols sizes: 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1 / 1 \ 1
20261009 10:53:09 [INFO] Completed w_pos 4: 2.17 KB, 34.960836ms
20261009 10:53:09 [INFO] Cols sizes: 1 / 2 \ 2 / 4 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 7 \ 4 / 4 \ 2 / 2 \ 1
20261009 10:53:09 [INFO] Completed w_pos 5: 3.40 KB [+44.04%], 47.736577ms [+30.90%]
20261009 10:53:09 [INFO] Cols sizes: 1 / 2 \ 2 / 5 \ 5 / 10 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 12 \ 7 / 10 \ 5 / 5 \ 2 / 2 \ 1
20261009 10:53:09 [INFO] Completed w_pos 6: 9.29 KB [+92.86%], 46.306472ms [-3.04%]
...
20261009 10:53:11 [INFO] Completed w_pos 25: 14.92 KB [-29.46%], 57.40335ms [-18.35%]
20261009 10:53:11 [INFO] Cols sizes: 1 / 12 \ 12 / 16 \ 16 / 24 \ 20 / 41 \ 24 / 31 \ 26 / 33 \ 25 / 35 \ 25 / 41 \ 31 / 51 \ 37 / 65 \ 34 / 65 \ 37 / 51 \ 31 / 41 \ 25 / 35 \ 25 / 33 \ 26 / 31 \ 24 / 41 \ 20 / 24 \ 16 / 16 \ 12 / 12 \ 1
20261009 10:53:11 [INFO] Completed w_pos 26: 13.23 KB [-11.99%], 53.821654ms [-6.44%]
20261009 10:53:11 [INFO] Cols sizes: 1 / 11 \ 11 / 15 \ 15 / 25 \ 19 / 25 \ 17 / 21 \ 15 / 19 \ 17 / 32 \ 21 / 44 \ 32 / 52 \ 37 / 63 \ 38 / 63 \ 37 / 52 \ 32 / 44 \ 21 / 32 \ 17 / 19 \ 15 / 21 \ 17 / 25 \ 19 / 25 \ 15 / 15 \ 11 / 11 \ 1
20261009 10:53:11 [INFO] Completed w_pos 27: 6.36 KB [-70.18%], 59.198252ms [+9.51%]
20261009 10:53:11 [INFO] Cols sizes: 1 / 4 \ 4 / 6 \ 6 / 8 \ 6 / 9 \ 6 / 9 \ 6 / 10 \ 7 / 13 \ 11 / 19 \ 18 / 28 \ 22 / 29 \ 22 / 29 \ 22 / 28 \ 18 / 19 \ 11 / 13 \ 7 / 10 \ 6 / 9 \ 6 / 9 \ 6 / 8 \ 6 / 6 \ 4 / 4 \ 1
20261009 10:53:11 [INFO] Last firstest partial RLE:
x = 51, y = 14, rule = LifeHistory
F.22B.F.22B.F$F.22B.F.22B.F$F.9BA3BA8B.F.8B3AB3A7B.F$F.8B3AB3A7B.F.7B
A2BABA2BA6B.F$F.7B2ABABAB2A6B.F.6BA3BABA3BA5B.F$F.6B2A7B2A5B.F.6BA9BA
5B.F$F.7BA7BA6B.F.8BA5BA7B.F$F.6B2A7B2A5B.F.5BABA7BABA4B.F$F.4B2ABABA
BABABAB2A3B.F.4B2AB2AB3AB2AB2A3B.F$F.4BA5BABA5BA3B.F.4BAB3ABABAB3ABA
3B.F$F.6BABABABABABA5B.F.3B2A5BABA5B2A2B.F$F.3B2ABABABABABABAB2A2B.F.
6BABABABABABA5B.F$F.6B2ABA3BAB2A5B.F.3B4A9B4A2B.F$F.3BA4BAB2AB2A4BA2B
.F.4B2ABAB2A3B2ABABA2B.F!
20261009 10:53:11 [INFO] Cols sizes hash: 0xBD35983F2FF3EA17
20261009 10:53:11 [INFO] Finish: search proper -> took 2.404107598s (24.427787s user, 1.452524s sys)
20261009 10:53:11 [INFO] Final results: 0 normal
20261009 10:53:11 [INFO] Done
$
I did not exactly audit carefully all log lines, rather I just zapped whatever noisy stuff came up in my brief testing of this. If you choose to run at INFO and notice any particularly spammy lines maybe chime in here and we might choose to exile them to DEBUG as well.

The DL consequences of some of this reworking are material. For, uh, "simple" uses of DL it should shake out as "replace ^e with ^^ in lambdas", but it's certainly possible to have written DL that can't be fixed by just that. The details are complicated.

Previously when you did something like...

Code: Select all

$ rlife ... --extras 'cb_step(^e $e.log("DEBUG", "yay"))
...what was happening was it was all compiled and interpreted in one shot by one DL interpreter. The "^e" constructs a lambda that cb_step's internals would later call with an object (bound to $e) that has methods like "log" on it. In this version the choice of "e" is arbitrary as the lambda's argument isn't named to its callers. This single DL interpreter's library of calls includes both "cb_step" and "log".

Now this has to be:

Code: Select all

$ rlife ... --extras 'cb_step(^^ $e.log("DEBUG", "yay"))
What is happening is "^^" is just quoting the inside (as a DL AST). When cb_step() is called with it, it does a second tier compile with a second DL interpreter and this compile provides a $e (or rather indicates it will provide one when it evaluates the results from the compile). The name "e" is part of cb_step's contract with the ASTs it is passed and it matters. Here the outer DL interpreter's library of calls includes "cb_step" and the inner's library includes "log".

Similarly there are difference in accessing $cfg, although it is provided either way. Before it was provided on the sole interpreter and the lambda could capture it from context. Now it is provided separately on each interpreter, and they both have registered the APIs for using it.

Finally, the APIs for halt have been reworked. I have replaced the convoluted dance of returning a halt indication with halt() being able to abort the DL evaluation and just stop everything immediately. E.g. this previously would fail to type check as old halt() return type and () don't match, but now, as a slight oversimplification, halt doesn't return so it's fine.

Code: Select all

$ rlife llsss c2-f2b '@bg(10)' --extras 'cb_step(^^ $e.w_pos == 10 ? $e.halt("BYE") : ())' | grep 'Completed\|BYE'
20261009 11:11:23 [INFO] Completed w_pos 4: 784 B, 24.147277ms
20261009 11:11:23 [INFO] Completed w_pos 5: 1.05 KB [+31.76%], 23.282858ms [-3.65%]
20261009 11:11:23 [INFO] Completed w_pos 6: 2.07 KB [+65.00%], 27.400144ms [+16.25%]
20261009 11:11:23 [INFO] Completed w_pos 7: 3.85 KB [+60.16%], 24.607157ms [-10.74%]
20261009 11:11:23 [INFO] Completed w_pos 8: 5.20 KB [+29.71%], 28.248522ms [+13.78%]
20261009 11:11:23 [WARNING] Halting (reason: BYE)...
Most of this rework was done to make fixing the filter DL integration much less painful. Similar to step.gate() (formerly known as "gate_step()"), there is filter.gate() which will cause the filters to only run when the gate code evaluates to true. These gate() calls both (step and filter) again take an AST and provide a $e that has the sorts of methods you might expect.

Compare ungated filter running every expansion round:

Code: Select all

$ rlife llsss p3 '@bg(10)' --constraint statorless --filters 'bcaf' | grep 'LlsssFilterAgarCycleAvoiding.*u_pos 0'
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 2[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 2[2] u_pos 0 [col]: 7 -> 7 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[0] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[0] u_pos 0 [col]: 12 -> 12 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[1] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[1] u_pos 0 [col]: 18 -> 18 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[2] u_pos 0 [col]: 16 -> 16 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[0] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[0] u_pos 0 [col]: 27 -> 27 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[1] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[1] u_pos 0 [col]: 42 -> 42 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:07:57 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[2] u_pos 0 [col]: 43 -> 43 [-]
...
Versus gated filter running only once at the end of each W row:

Code: Select all

$ rlife llsss p3 '@bg(10)' --constraint statorless --filters 'bcaf.gate(^^ $e.subtile_pos == 2)' | grep 'LlsssFilterAgarCycleAvoiding.*u_pos 0'
20261009 11:19:52 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 2[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:19:52 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 2[2] u_pos 0 [col]: 7 -> 7 [-]
20261009 11:19:53 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:19:53 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 3[2] u_pos 0 [col]: 16 -> 16 [-]
20261009 11:19:53 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:19:53 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 4[2] u_pos 0 [col]: 43 -> 43 [-]
20261009 11:19:53 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 5[2] u_pos 0 [bcol]: 1 -> 1 [-]
20261009 11:19:53 [DEBUG] Filtered [LlsssFilterAgarCycleAvoiding]: w_pos 5[2] u_pos 0 [col]: 76 -> 76 [-]
...
I've pushed (just now) all this to codeberg master as of 62cf0a520031. Please let me know here if it breaks on you.

Re: amling search program principles discussion / brain dump

Posted: October 9th, 2026, 6:24 pm
by amling
I sketched hiking the edge configuration way, way up and having it annotate a few select outputs with reflected copies (where appropriate). This works even for wacky geometries, e.g.:

Code: Select all

$ rlife llsss-recentering-wao c5-f2b/U=2X+3T '@bg' --right-edge odd --wao-right-edge-errors 01
...
20261009 14:39:54 [INFO] Thinnest partial:
20261009 14:39:54 [INFO] |          |          |          |          | Z        |
20261009 14:39:54 [INFO] | .        | .Z       | ..Z      | ...      | ...Z     |
20261009 14:39:54 [INFO] | ....Z    | .....    | .....Z   | ......Z  | .......  |
20261009 14:39:54 [INFO] | .......Z | ........ | ........ | ........ | ........ |
20261009 14:39:54 [INFO] | ........ | ........ | ........ | ........ | ........ |
20261009 14:39:54 [INFO] | ........ | ........ | ......*. | ......*. | ......*. |
20261009 14:39:54 [INFO] | ......*. | .....*** | .....*.* | .....*.* | .....*.* |
20261009 14:39:54 [INFO] | ....**.* | .....*** | .....*.* | .....*.* | ....**.* |
20261009 14:39:54 [INFO] | ........ | ........ | ......*. | .....*** | ....**.* |
20261009 14:39:54 [INFO] | ........ | ........ | ......*. | .....*.* | .....*.* |
20261009 14:39:54 [INFO] | ....**.* | .....*** | ....*... | ........ | ........ |
20261009 14:39:54 [INFO] | ......*. |  ...**** |   ...... |   ...... |    ...*. |
20261009 14:39:54 [INFO] |     .... |     *... |      ... |       ** |       .. |
20261009 14:39:54 [INFO] |        . |          |          |          |          |
...
20261009 14:39:54 [INFO] Last thinnest partial RLE:
x = 81, y = 13, rule = LifeHistory
F.B11.B.F.B11.B.F.2B9.2B.F.3B7.3B.F.3B7.3B.F$F.4B5.4B.F.5B3.5B.F.5B3.
5B.F.6B.6B.F.13B.F$F.13B.F.13B.F.13B.F.13B.F.13B.F$F.13B.F.13B.F.13B.
F.13B.F.13B.F$F.13B.F.13B.F.6BA6B.F.6BA6B.F.6BA6B.F$F.6BA6B.F.5B3A5B.
F.5BABA5B.F.5BABA5B.F.5BABA5B.F$F.4B2AB2A4B.F.5B3A5B.F.5BABA5B.F.5BAB
A5B.F.4B2AB2A4B.F$F.13B.F.13B.F.6BA6B.F.5B3A5B.F.4B2AB2A4B.F$F.13B.F.
13B.F.6BA6B.F.5BABA5B.F.5BABA5B.F$F.4B2AB2A4B.F.5B3A5B.F.4BA3BA4B.F.
13B.F.13B.F$F.6BA6B.F2.3B5A3B2.F3.9B3.F3.9B3.F4.3BA3B4.F$F5.5B5.F5.A
3BA5.F6.3B6.F6.3A6.F6.3B6.F$F6.B.B6.F15.F15.F15.F15.F!
...

Code: Select all

x = 81, y = 13, rule = LifeHistory
F.B11.B.F.B11.B.F.2B9.2B.F.3B7.3B.F.3B7.3B.F$F.4B5.4B.F.5B3.5B.F.5B3.
5B.F.6B.6B.F.13B.F$F.13B.F.13B.F.13B.F.13B.F.13B.F$F.13B.F.13B.F.13B.
F.13B.F.13B.F$F.13B.F.13B.F.6BA6B.F.6BA6B.F.6BA6B.F$F.6BA6B.F.5B3A5B.
F.5BABA5B.F.5BABA5B.F.5BABA5B.F$F.4B2AB2A4B.F.5B3A5B.F.5BABA5B.F.5BAB
A5B.F.4B2AB2A4B.F$F.13B.F.13B.F.6BA6B.F.5B3A5B.F.4B2AB2A4B.F$F.13B.F.
13B.F.6BA6B.F.5BABA5B.F.5BABA5B.F$F.4B2AB2A4B.F.5B3A5B.F.4BA3BA4B.F.
13B.F.13B.F$F.6BA6B.F2.3B5A3B2.F3.9B3.F3.9B3.F4.3BA3B4.F$F5.5B5.F5.A
3BA5.F6.3B6.F6.3A6.F6.3B6.F$F6.B.B6.F15.F15.F15.F15.F!
You can see it has faithfully reflected the parallelogram of the board and unioned with itself.

It of course works for diagonal geometries:

Code: Select all

$ rlife llsss-recentering-wao c4d-f2b '@bg' --left-edge gse --wao-left-edge-errors --llsss-env LLSSS_RLE_ENDS=both --llsss-env LLSSS_HALT_ON_ENDS=true 01
...
20261009 15:20:03 [INFO] End [thinnest] ("LlsssEndsAgar", "zero"):
20261009 15:20:03 [INFO] |             |     Z       |     .       |    Z.       |
20261009 15:20:03 [INFO] |     ..      |    Z..      |    ...      |   Z...      |
20261009 15:20:03 [INFO] |    ....     |   Z....     |   .....     |  Z.....     |
20261009 15:20:03 [INFO] |   ......    |  Z......    |  .......    | Z.......    |
20261009 15:20:03 [INFO] |  ........   |  ........   |  ........   |  ...*....   |
20261009 15:20:03 [INFO] |   ..**....  |   ..**....  |   .***....  |   .**.....  |
20261009 15:20:03 [INFO] |    .*.*.... |    **...... |    *......  |    *.*....  |
20261009 15:20:03 [INFO] |     *.....  |     .*....  |     *....   |     .....   |
20261009 15:20:03 [INFO] |      ....   |      ....   |      ...    |      ...    |
20261009 15:20:03 [INFO] |       ..    |       ..    |       .     |       .     |
x = 61, y = 12, rule = LifeHistory
F14.F14.F6.B7.F6.B7.F$F6.2B6.F6.2B6.F5.3B6.F5.3B6.F$F5.4B5.F5.4B5.F4.
5B5.F4.5B5.F$F4.6B4.F4.6B4.F3.7B4.F3.7B4.F$F3.8B3.F3.8B3.F2.9B3.F2.4B
A4B3.F$F2.4B2A4B2.F2.4B2A4B2.F.4B3A4B2.F.4B2A5B2.F$F.5BABA4B.F.4B2A6B
.F.4BA6B2.F.4BABA4B2.F$F2.4BA5B2.F2.5BA4B2.F2.4BA4B3.F2.9B3.F$F3.8B3.
F3.8B3.F3.7B4.F3.7B4.F$F4.6B4.F4.6B4.F4.5B5.F4.5B5.F$F5.4B5.F5.4B5.F
5.3B6.F5.3B6.F$F6.2B6.F6.2B6.F6.B7.F6.B7.F!
...

Code: Select all

x = 61, y = 12, rule = LifeHistory
F14.F14.F6.B7.F6.B7.F$F6.2B6.F6.2B6.F5.3B6.F5.3B6.F$F5.4B5.F5.4B5.F4.
5B5.F4.5B5.F$F4.6B4.F4.6B4.F3.7B4.F3.7B4.F$F3.8B3.F3.8B3.F2.9B3.F2.4B
A4B3.F$F2.4B2A4B2.F2.4B2A4B2.F.4B3A4B2.F.4B2A5B2.F$F.5BABA4B.F.4B2A6B
.F.4BA6B2.F.4BABA4B2.F$F2.4BA5B2.F2.5BA4B2.F2.4BA4B3.F2.9B3.F$F3.8B3.
F3.8B3.F3.7B4.F3.7B4.F$F4.6B4.F4.6B4.F4.5B5.F4.5B5.F$F5.4B5.F5.4B5.F
5.3B6.F5.3B6.F$F6.2B6.F6.2B6.F6.B7.F6.B7.F!
It also correctly rotates V/2 for GS symmetries:

Code: Select all

$ rlife llsss-recentering-wao 2c4-f2b '@bg' --left-edge gso --wao-left-edge-errors --llsss-env LLSSS_RLE_ENDS=both --llsss-env LLSSS_HALT_ON_ENDS=true 02
...
20261009 14:42:26 [INFO] End [thinnest] ("LlsssEndsAgar", "zero"):
20261009 14:42:26 [INFO] |       |       |       | ZZZZZ |
20261009 14:42:26 [INFO] |       | ZZZZZ | ..... | ..... |
20261009 14:42:26 [INFO] | ..... | ..... | ..... | ..... |
20261009 14:42:26 [INFO] | ..... | ..... | *.... | **... |
20261009 14:42:26 [INFO] | *.... | **... | **... | .*... |
20261009 14:42:26 [INFO] | **... | ..*.. | .*... | .*... |
20261009 14:42:26 [INFO] | .**.. | ..... | *.... | .*... |
20261009 14:42:26 [INFO] | ***.. | ..... | *.... | *.... |
20261009 14:42:26 [INFO] | **... | *.*.. | ..... | ..... |
20261009 14:42:26 [INFO] | ..... | ..... | ..... | ..... |
20261009 14:42:26 [INFO] | ..... | ..... |       |       |
x = 49, y = 10, rule = LifeHistory
F11.F11.F.9B.F.9B.F$F.9B.F.9B.F.9B.F.9B.F$F.9B.F.9B.F.4BA4B.F.3B3A3B.
F$F.4BA4B.F.3B3A3B.F.3B3A3B.F.2BA2BA3B.F$F.3B3A3B.F.3BA2BA2B.F.2B2ABA
3B.F.5BA3B.F$F.3BAB2A2B.F.3BA5B.F.2B3A4B.F.5BA3B.F$F.4B3A2B.F.3BA5B.F
.3B2A4B.F.2BABA4B.F$F.4B2A3B.F.4BABA2B.F.9B.F.9B.F$F.9B.F.9B.F.9B.F.
9B.F$F.9B.F.9B.F11.F11.F!
...

Code: Select all

x = 49, y = 10, rule = LifeHistory
F11.F11.F.9B.F.9B.F$F.9B.F.9B.F.9B.F.9B.F$F.9B.F.9B.F.4BA4B.F.3B3A3B.
F$F.4BA4B.F.3B3A3B.F.3B3A3B.F.2BA2BA3B.F$F.3B3A3B.F.3BA2BA2B.F.2B2ABA
3B.F.5BA3B.F$F.3BAB2A2B.F.3BA5B.F.2B3A4B.F.5BA3B.F$F.4B3A2B.F.3BA5B.F
.3B2A4B.F.2BABA4B.F$F.4B2A3B.F.4BABA2B.F.9B.F.9B.F$F.9B.F.9B.F.9B.F.
9B.F$F.9B.F.9B.F11.F11.F!
And correctly toggles cells for toggle symmetries:

Code: Select all

$ rlife llsss-recentering-wao --rule 'B3678/S34678' 2c4-f2b '1.in' --left-edge gso_toggle --wao-left-edge-errors 02
...
20261009 15:11:05 [INFO] Thinnest partial:
20261009 15:11:05 [INFO] |       |       |       | uuRRR |
20261009 15:11:05 [INFO] |       | uuRRR | ..... | ..... |
20261009 15:11:05 [INFO] | *.... | *.... | *.... | *.... |
20261009 15:11:05 [INFO] | ..... | ..... | *.... | **... |
20261009 15:11:05 [INFO] | .*... | ..... | *.... | ..... |
20261009 15:11:05 [INFO] | ..... | *.... | **... | .**.. |
20261009 15:11:05 [INFO] | ..*.. | **... | .**.. | *.*.. |
20261009 15:11:05 [INFO] | **... | .**.. | *.*.. | .*... |
20261009 15:11:05 [INFO] | ..*.. | **... |       |       |
...
20261009 15:11:05 [INFO] Last thinnest partial RLE:
x = 49, y = 8, rule = B3678/S34678History
F11.F11.F.4A5B.F.4A5B.F$F.5A4B.F.5A4B.F.5A4B.F.5A4B.F$F.4A5B.F.4A5B.F
.3ABA4B.F.6A3B.F$F.4ABA3B.F.3A6B.F.5A4B.F.4A5B.F$F.4A5B.F.5A4B.F.2AB
3A3B.F.3A2B2A2B.F$F.3A3BA2B.F.2A2B2A3B.F.3A2B2A2B.F.2A2BABA2B.F$F.2A
2B2A3B.F.2ABAB2A2B.F.2AB2ABA2B.F.3A2BA3B.F$F.2ABA2BA2B.F.3AB2A3B.F11.
F11.F!
...

Code: Select all

x = 49, y = 8, rule = B3678/S34678History
F11.F11.F.4A5B.F.4A5B.F$F.5A4B.F.5A4B.F.5A4B.F.5A4B.F$F.4A5B.F.4A5B.F
.3ABA4B.F.6A3B.F$F.4ABA3B.F.3A6B.F.5A4B.F.4A5B.F$F.4A5B.F.5A4B.F.2AB
3A3B.F.3A2B2A2B.F$F.3A3BA2B.F.2A2B2A3B.F.3A2B2A2B.F.2A2BABA2B.F$F.2A
2B2A3B.F.2ABAB2A2B.F.2AB2ABA2B.F.3A2BA3B.F$F.2ABA2BA2B.F.3AB2A3B.F11.
F11.F!
Really, it should work for any choice of geometry and reflect edge that can run a search.

I'm reasonably happy with most of the restructuring necessary to get this done. Doing the actual geometry in reflect edges still sucks, but it's mostly shared between the two places (extension and output). The remaining questions I think are...

(*) Which outputs to do it for? It really, really doesn't work with roots and I am very attached to including roots in almost anything I read. So far I've put it just on the two last partials (already RLE) and ends RLE output. Maybe that's it?

(*) Testing testing testing. That reflect edge is some of the scariest code in the codebase and this rearranges it a bit. I have been building some infra for doing big, slow runs to compare multiple versions of the codebase so I think I know what I want to do, I just have to pick a bunch of searches.

(*) skew_gutter. This turd is its own completely separate implementation which I did not yet do anything about. We'll see if I run out of steam before I get to it...

Probably I will get my testing done and then let it fly more or less as-is. In the fullness of time we can worry about tweaking the outputs and/or fixing skew_gutter.

Re: amling search program principles discussion / brain dump

Posted: October 10th, 2026, 1:38 am
by amling
I did a little more work on symmetric handling in mgp-tool today. It's slow going because it's a lot of icky geometry and grid management and the edge cases are just vile.

On branch (unpublished), --pic-mode will add question marks for asymmetric recentering:

Code: Select all

$ cat p1.l
...***
..*..*
.....*
.*...*
.*...*
.....*
..*.*.
......
**....
$ rlife mgp-tool ingest-1gp 2c4-f2b p1.l p1.mgp
20261009 22:12:21 [INFO] Saved to "p1.mgp".
$ cat p1.mgp
|              |              |              |              |
|              |              | ............ | ............ |
| ............ | ............ | ............ | ............ |
| ............ | ............ | ......*..... | .....***.... |
| ......*..... | .....***.... | .....***.... | .....*..*... |
| .....***.... | ....*..*.... | .....*.**... | .....*...... |
| ....**.*.... | .......*.... | ......***... | .....*...*.. |
| ....***..... | ...*...*.... | ......***... | .....*...*.. |
| ....***..... | ...*...*.... | ......***... | .....*...... |
| ....***..... | .......*.... | ......**.... | ......*.*... |
| .....**..... | ....*.*..... | ............ | ............ |
| ............ | ............ | ...*........ | ............ |
| ............ | ..**........ |              |              |
$ rlife mgp-tool to-rc-input 2c4-f2b p1.mgp
20261009 22:12:44 [INFO] Final grid:
20261009 22:12:44 [INFO]    |                |                |                | AAAuuuuuuuuBBB |
20261009 22:12:44 [INFO]    |                | AAAuuuuuuuuBBB | .............. | .............. |
20261009 22:12:44 [INFO]    | .............. | .............. | .............. | .............. |
20261009 22:12:44 [INFO]    | .............. | .............. | .......*...... | ......***..... |
20261009 22:12:44 [INFO]    | .......*...... | ......***..... | ......***..... | ......*..*.... |
20261009 22:12:44 [INFO]    | ......***..... | .....*..*..... | ......*.**.... | ......*....... |
20261009 22:12:44 [INFO]    | .....**.*..... | ........*..... | .......***.... | ......*...*... |
20261009 22:12:44 [INFO]    | .....***...... | ....*...*..... | .......***.... | ......*...*... |
20261009 22:12:44 [INFO]    | .....***...... | ....*...*..... | .......***.... | ......*....... |
20261009 22:12:44 [INFO]    | .....***...... | ........*..... | .......**..... | .......*.*.... |
20261009 22:12:44 [INFO]    | ......**...... | .....*.*...... | .............. | .............. |
20261009 22:12:44 [INFO]    | .............. | .............. | ....*......... | .............. |
20261009 22:12:44 [INFO]    | .............. | ...**......... |                |                |
$ rlife mgp-tool to-rc-input --pic-mode 2c4-f2b p1.mgp
20261009 22:12:50 [INFO] Final grid:
20261009 22:12:50 [INFO]    |                |                |                | AAAuuuuuuuuBBB |
20261009 22:12:50 [INFO]    |                | AAAuuuuuuuuBBB | .............. | .............. |
20261009 22:12:50 [INFO]    | .............. | .............. | .............. | .............. |
20261009 22:12:50 [INFO]    | .............. | .............. | .......*...... | ......***..... |
20261009 22:12:50 [INFO]    | .......*...... | ......***..... | ......***..... | ......*..*.... |
20261009 22:12:50 [INFO]    | ......***..... | .....*..*..... | ......*.**.... | ......*....... |
20261009 22:12:50 [INFO]    | .....**.*..... | ........*..... | .......***.... | ......*...*... |
20261009 22:12:50 [INFO]    | .....***...... | ....*...*..... | .......***.... | ......*...*... |
20261009 22:12:50 [INFO]    | .....***...... | ....*...*..... | .......***.... | ......*....... |
20261009 22:12:50 [INFO]    | .....***...... | ........*..... | .......**..... | .......*.*.... |
20261009 22:12:50 [INFO]    | ......**...... | .....*.*...... | .............. | .............. |
20261009 22:12:50 [INFO]    | .............. | .............. | ....*......... | .............. |
20261009 22:12:50 [INFO]    | .............. | ...**......... | ...??......... | ...??......... |
20261009 22:12:50 [INFO]    | ...??......... | ...??......... | ...??......... | ...??......... |
20261009 22:12:50 [INFO]    | ...??......... | ...??......... |                |                |
$
to-rc-input can now also do symmetric mode which can also be with or without --pic-mode:

Code: Select all

$ cat p2.l
..***
.*..*
....*
*...*
*...*
*...*
....*
.*.*.
$ rlife mgp-tool ingest-1gp 2c4-f2b --sym gso p2.l p2.mgp
20261009 22:13:47 [INFO] Saved to "p2.mgp".
$ cat p2.mgp
|        |        |        |        |
|        |        | ...... | ...... |
| ...... | ...... | ...... | ...... |
| ...... | ...... | *..... | **.... |
| *..... | **.... | **.... | ..*... |
| **.... | .*.... | .**... | ...... |
| .*.... | .*.... | ***... | ...*.. |
| *..... | .*.... |        |        |
$ rlife mgp-tool to-rc-input 2c4-f2b --sym gso p2.mgp
20261009 22:15:14 [INFO] Final grid:
20261009 22:15:14 [INFO]    |         |         |         | uuuuAAA |
20261009 22:15:14 [INFO]    |         | uuuuAAA | ....... | ....... |
20261009 22:15:14 [INFO]    | ....... | ....... | ....... | ....... |
20261009 22:15:14 [INFO]    | ....... | ....... | *...... | **..... |
20261009 22:15:14 [INFO]    | *...... | **..... | **..... | ..*.... |
20261009 22:15:14 [INFO]    | **..... | .*..... | .**.... | ....... |
20261009 22:15:14 [INFO]    | .*..... | .*..... | ***.... | ...*... |
20261009 22:15:14 [INFO]    | *...... | .*..... |         |         |
$ rlife mgp-tool to-rc-input 2c4-f2b --sym gso --pic-mode p2.mgp
20261009 22:15:22 [INFO] Final grid:
20261009 22:15:22 [INFO]    |         |         |         | uuuuAAA |
20261009 22:15:22 [INFO]    |         | uuuuAAA | ....... | ....... |
20261009 22:15:22 [INFO]    | ....... | ....... | ....... | ....... |
20261009 22:15:22 [INFO]    | ....... | ....... | *...... | **..... |
20261009 22:15:22 [INFO]    | *...... | **..... | **..... | ..*.... |
20261009 22:15:22 [INFO]    | **..... | .*..... | .**.... | ....... |
20261009 22:15:22 [INFO]    | .*..... | .*..... | ***.... | ...*... |
20261009 22:15:22 [INFO]    | *...... | .*..... | !!??... | !!??... |
20261009 22:15:22 [INFO]    | !!??... | !!??... | !!??... | !!??... |
20261009 22:15:22 [INFO]    | !!??... | !!??... |         |         |
$
Something even more horrible than I foresaw can happen, where an insanely thin symmetric partial can not even fill the edge 2 columns. This would be bad for picture mode, leaving us without enough columns to put in question marks so when we load symmetric partials we pad them to 2 columns (actually one U overlap).

Code: Select all

$ cat p3.l
.*.
***
$ rlife mgp-tool ingest-1gp 2c4-f2b --sym gso p3.l p3.mgp
20261009 22:17:11 [INFO] Saved to "p3.mgp".
$ cat p3.mgp
|     |     |     |     |
|     |     | ... | ... |
| ... | ... | ... | ... |
| ... | ... | *.. |     |
| *.. |     |     |     |
$ rlife mgp-tool to-rc-input 2c4-f2b --sym gso p3.mgp
20261009 22:17:24 [INFO] Final grid:
20261009 22:17:24 [INFO]    |       |       |       | uuAAA |
20261009 22:17:24 [INFO]    |       | uuAAA | ..... | ..... |
20261009 22:17:24 [INFO]    | ..... | ..... | ..... | ..... |
20261009 22:17:24 [INFO]    | ..... | ..... | *.... |       |
20261009 22:17:24 [INFO]    | *.... |       |       |       |
$ rlife mgp-tool to-rc-input 2c4-f2b --sym gso --pic-mode p3.mgp
20261009 22:17:30 [INFO] Final grid:
20261009 22:17:30 [INFO]    |       |       |       | uuAAA |
20261009 22:17:30 [INFO]    |       | uuAAA | ..... | ..... |
20261009 22:17:30 [INFO]    | ..... | ..... | ..... | ..... |
20261009 22:17:30 [INFO]    | ..... | ..... | *.... | !!?.. |
20261009 22:17:30 [INFO]    | *.... | !!?.. | !!?.. | !!?.. |
20261009 22:17:30 [INFO]    | !!?.. | !!?.. | !!?.. |       |
20261009 22:17:30 [INFO]    | !!?.. |       |       |       |
$
Arguably for the non-pic-mode case you could skip the padding (and just have "uAAA" columns), but I don't think it's worth adding yet another epicycle on an already complex mess.

This was all sketched with the plan of generating the question mark range just on the last W overlap of difference from the agar, but now I'm wondering if recentering doesn't need to distinguish "full" from "split" as well? Like consider this silly input:

Code: Select all

$ cat p4.l
***.......***.
*..*......*..*
*.........*...
*.........*...
.*.*.......*.*
..............
..*.........*.
$ rlife mgp-tool ingest-1gp 2c4-f2b --sym gso p4.l p4.mgp
20261009 22:27:04 [INFO] Saved to "p4.mgp".
$ cat p4.mgp
|            |            |            |            |
|            |            | .......... | .......... |
| .......... | .......... | .......... | .......... |
| .......... | .......... | .....*.... | ....***... |
| .....*.... | ....***... | ....***... | ...*..*... |
| ....***... | ....*..*.. | ...**.*... | ......*... |
| ....*.**.. | ....*..... | ...***.... | ......*... |
| .....***.. | ....*..... | ....**.... | ...*.*.... |
| .....**... | .....*.*.. |            |            |
$
As just sketched, --pic-mode generates this:

Code: Select all

$ rlife mgp-tool to-rc-input 2c4-f2b --sym gso --pic-mode p4.mgp
20261009 22:27:40 [INFO] Final grid:
20261009 22:27:40 [INFO]    |             |             |             | uuuuuuuuAAA |
20261009 22:27:40 [INFO]    |             | uuuuuuuuAAA | ........... | ........... |
20261009 22:27:40 [INFO]    | ........... | ........... | ........... | ........... |
20261009 22:27:40 [INFO]    | ........... | ........... | .....*..... | ....***.... |
20261009 22:27:40 [INFO]    | .....*..... | ....***.... | ....***.... | ...*..*.... |
20261009 22:27:40 [INFO]    | ....***.... | ....*..*... | ...**.*.... | ......*.... |
20261009 22:27:40 [INFO]    | ....*.**... | ....*...... | ...***..... | ......*.... |
20261009 22:27:40 [INFO]    | .....***... | ....*...... | ....**..... | ...*.*..... |
20261009 22:27:40 [INFO]    | .....**.... | .....*.*... | !!.?????... | !!.?????... |
20261009 22:27:40 [INFO]    | !!.?????... | !!.?????... | !!.?????... | !!.?????... |
20261009 22:27:40 [INFO]    | !!.?????... | !!.?????... |             |             |
$
But it's sort of an unholy fusion of split and full...

If you were really trying to solve it as a separated single branch the exclamation points are in your way and you want the left agar there instead. If you were going to solve it as a full pattern you want the question marks spread up to the left edge and then you want the exclamation point placeholders to force you to specify symmetric edge.

Like I guess both behaviours make sense, maybe, but added to the pile it's a lot of weird not-quite-independent choices where the following 5 combinations are what we think we should allow:

(*) asym non-pic
(*) asym pic
(*) sym non-pic
(*) sym split pic
(*) sym full pic

I will have to think on it some more.

Re: amling search program principles discussion / brain dump

Posted: October 16th, 2026, 7:20 pm
by amling
I was trying to find a seeds c/4 moon rake yesterday f2b using regex edges and was having the usual issues, namely nothing forces engagement with the prompt and the edge can just stay zero forever.

I sometimes have related problems with "pic(bg)" edges where ends can match even before the search has finished solving the nonzero part of the picture edge. Long ago I had thought about trying to allow edges to distinguish part of the state as "ready" and somehow limit ends that way. Back then edges were buried inside the expand step and so trying to route their knowledge around to ends seemed hopeless. Now that recent work has hiked the edges way out, they're visible to all steps and we could maybe hack something up here.

As a quick sketch I have added a separate notion of "readiness" for edges, implemented it for real for regex edges only, and added a second pre-partial "default_ready" for recentering only. Obviously I will fill out more implementations if this ships, but I just want to get the ideas baking on this branch.

Solving the moon rake is too hard and too complex for a demo, but consider trying to find a moon rake output cap. This regex edge matches the moon rake output coming in on the left side and requires at least 8 W rows of zeros after it:

Code: Select all

$ cat test.edge
| (__ | Z.. | )__ | *__ |
| u*. | u.* | u.. | u*. |
| u.* | u.. | u.. | u*. |
| u.* | u.. | u.. | u.. |
| u*. | u.* | Z.. | Z.. |
| Z.. | Z.. | Z.. | Z.. |
| Z.. | Z.. | (__ | Z.. |
| )__ | *__ |     |     |
$ rlife grid-tool to-uwi c4-f2b < test.edge
| (__ |
| Z.. |
| )__ |
| *__ |
| u*. |
| u.* |
| u.. |
| u*. |
| u.* |
| u.. |
| u.. |
| u*. |
| u.* |
| u.. |
| u.. |
| u.. |
| u*. |
| u.* |
| Z.. |
| Z.. |
| Z.. |
| Z.. |
| Z.. |
| Z.. |
| Z.. |
| Z.. |
| (__ |
| Z.. |
| )__ |
| *__ |
$
Now if you run a thin search with just default_ready pre-partials, something interesting happens, namely you never get any output as it can't solve the edge:

Code: Select all

$ rlife llsss-recentering-wao --rule 'B2/S' c4-f2b '@bg' --left-edge 'regex("test.edge")' --pre-partials 'default_ready' --llsss-env LLSSS_LOG_LEVEL=INFO 06
20261016 15:56:53 [INFO] Start file magic grid generated:
20261016 15:56:53 [INFO] |     |     |     | ZZZ |
20261016 15:56:53 [INFO] | ... | ... | ... | ... |
20261016 15:56:53 [INFO] | ... | ... | ... | ... |
20261016 15:56:53 [INFO] | ... |     |     |     |
20261016 15:56:53 [INFO] WAO error window #0 (included):
20261016 15:56:53 [INFO] |       |       |       | ZZZZZ |
20261016 15:56:53 [INFO] | ..... | ..... | ..... | ..... |
20261016 15:56:53 [INFO] | ..... | ..... | ..... | ..... |
20261016 15:56:53 [INFO] | ..xWW |       |       |       |
20261016 15:56:53 [INFO] Start: precompile
20261016 15:56:53 [INFO] LlsssEdgeRegex: 80 NFA states
20261016 15:56:53 [INFO] LlsssEdgeRegex: 49 DFA states
20261016 15:56:53 [INFO] Finish: precompile -> took 6.332771ms (42.189ms user, 148µs sys)
20261016 15:56:53 [INFO] Start: search proper
20261016 15:56:53 [INFO] Cols sizes: 4 / 5
20261016 15:56:53 [INFO] Completed w_pos 8: 216 B, 15.433361ms
20261016 15:56:53 [INFO] Cols sizes: 6 / 8
20261016 15:56:53 [INFO] Completed w_pos 9: 456 B [+71.43%], 13.485238ms [-13.47%]
20261016 15:56:53 [INFO] Cols sizes: 14 / 25
20261016 15:56:53 [INFO] Completed w_pos 10: 1.11 KB [+85.43%], 18.416457ms [+30.92%]
20261016 15:56:53 [INFO] Cols sizes: 34 / 81
20261016 15:56:53 [INFO] Completed w_pos 11: 1.75 KB [+44.81%], 19.07063ms [+3.49%]
20261016 15:56:53 [INFO] Cols sizes: 55 / 133
20261016 15:56:53 [INFO] Completed w_pos 12: 2.62 KB [+40.00%], 20.539056ms [+7.41%]
20261016 15:56:53 [INFO] Cols sizes: 86 / 199
20261016 15:56:53 [INFO] Completed w_pos 13: 3.91 KB [+39.43%], 22.690603ms [+9.95%]
20261016 15:56:53 [INFO] Cols sizes: 137 / 288
20261016 15:56:53 [INFO] Completed w_pos 14: 5.16 KB [+27.54%], 24.106566ms [+6.05%]
20261016 15:56:53 [INFO] Cols sizes: 178 / 380
20261016 15:56:53 [INFO] Completed w_pos 15: 7.37 KB [+35.16%], 24.343716ms [+0.98%]
20261016 15:56:53 [INFO] Cols sizes: 238 / 507
20261016 15:56:53 [INFO] Completed w_pos 16: 6.70 KB [-9.44%], 27.708048ms [+12.93%]
20261016 15:56:53 [INFO] Cols sizes: 205 / 454
20261016 15:56:53 [INFO] Completed w_pos 17: 6.72 KB [+0.23%], 31.40918ms [+12.52%]
20261016 15:56:53 [INFO] Cols sizes: 210 / 432
20261016 15:56:53 [INFO] Completed w_pos 18: 5.74 KB [-15.67%], 25.58459ms [-20.44%]
20261016 15:56:53 [INFO] Cols sizes: 176 / 358
20261016 15:56:53 [INFO] Completed w_pos 19: 2.96 KB [-63.91%], 23.044626ms [-10.45%]
20261016 15:56:53 [INFO] Cols sizes: 92 / 134
20261016 15:56:54 [INFO] Completed w_pos 20: 2.33 KB [-23.93%], 24.331925ms [+5.43%]
20261016 15:56:54 [INFO] Cols sizes: 69 / 94
20261016 15:56:54 [INFO] Completed w_pos 21: 2.66 KB [+13.46%], 22.813611ms [-6.44%]
20261016 15:56:54 [INFO] Cols sizes: 78 / 130
20261016 15:56:54 [INFO] Completed w_pos 22: 896 B [-101.10%], 22.60528ms [-0.92%]
20261016 15:56:54 [INFO] Cols sizes: 24 / 32
20261016 15:56:54 [INFO] Last thinnest partial RLE:
x = 49, y = 6, rule = B2/SHistory
F.9B.F.9B.F.9B.F.9B.F$F.9B.F.9B.F.9B.F.9B.F$F.5BA3B.F.4BA4B.F.5BA3B.F
.4BABA2B.F$F.3BA5B.F.2BABA4B.F.5BA3B.F.4BA4B.F$F.2BA6B.F.3BA5B.F.6BA
2B.F.2B2A5B.F$F.9B.F.ABA2B2A2B.F.BAB2A4B.F11.F!
20261016 15:56:54 [INFO] Cols sizes hash: 0x4975BEE038851761
20261016 15:56:54 [INFO] LlsssStepExpandRecentering: max pre-reify estimated mem: 5.82 KB
20261016 15:56:54 [INFO] Finish: search proper -> took 369.770026ms (3.47578s user, 270.342ms sys)
20261016 15:56:54 [INFO] Final results: 0 normal
20261016 15:56:54 [INFO] Done
$
One mid_steps up though, the results start coming in, at least once it has gotten far enough to have solved the edge (i.e. the moons and at least 8 W rows of zeros on the edges)...

Code: Select all

$ rlife llsss-recentering-wao --rule 'B2/S' c4-f2b '@bg' --left-edge 'regex("test.edge")' --pre-partials 'default_ready' --llsss-env LLSSS_LOG_LEVEL=INFO 07
20261016 15:57:42 [INFO] Start file magic grid generated:
20261016 15:57:42 [INFO] |     |     |     | ZZZ |
20261016 15:57:42 [INFO] | ... | ... | ... | ... |
20261016 15:57:42 [INFO] | ... | ... | ... | ... |
20261016 15:57:42 [INFO] | ... |     |     |     |
20261016 15:57:42 [INFO] WAO error window #0 (included):
20261016 15:57:42 [INFO] |       |       |       | ZZZZZ |
20261016 15:57:42 [INFO] | ..... | ..... | ..... | ..... |
20261016 15:57:42 [INFO] | ..... | ..... | ..... | ..... |
20261016 15:57:42 [INFO] | ..xWW |       |       |       |
20261016 15:57:42 [INFO] Start: precompile
20261016 15:57:42 [INFO] LlsssEdgeRegex: 80 NFA states
20261016 15:57:42 [INFO] LlsssEdgeRegex: 49 DFA states
20261016 15:57:42 [INFO] Finish: precompile -> took 7.173443ms (43.434ms user, 1.681ms sys)
20261016 15:57:42 [INFO] Start: search proper
20261016 15:57:42 [INFO] Cols sizes: 4 / 5
20261016 15:57:42 [INFO] Completed w_pos 8: 216 B, 17.984912ms
20261016 15:57:42 [INFO] Cols sizes: 6 / 8
20261016 15:57:42 [INFO] Completed w_pos 9: 464 B [+72.94%], 16.853738ms [-6.49%]
20261016 15:57:42 [INFO] Cols sizes: 14 / 26
20261016 15:57:42 [INFO] Completed w_pos 10: 1.15 KB [+86.83%], 14.741587ms [-13.37%]
...
20261016 15:57:42 [INFO] Cols sizes: 206 / 455
20261016 15:57:42 [INFO] Completed w_pos 28: 5.80 KB [-14.60%], 29.102292ms [+6.41%]
20261016 15:57:42 [INFO] Cols sizes: 179 / 388
20261016 15:57:42 [INFO] Completed w_pos 29: 8.16 KB [+33.69%], 28.367447ms [-2.56%]
20261016 15:57:42 [INFO] Cols sizes: 246 / 592
20261016 15:57:42 [INFO] Completed w_pos 30: 8.95 KB [+9.32%], 31.417331ms [+10.20%]
20261016 15:57:42 [INFO] Cols sizes: 291 / 591
20261016 15:57:42 [INFO] Thinnest ready partial:
20261016 15:57:42 [INFO] |              |              |              | ZZZZZZZZZZZZ |
20261016 15:57:42 [INFO] | ............ | ............ | ............ | ............ |
20261016 15:57:42 [INFO] | ............ | ............ | ............ | ............ |
20261016 15:57:42 [INFO] | ......*..... | *......*.... | .*....*..... | ..*..*.*.... |
20261016 15:57:42 [INFO] | *..*....*... | .*.....*.*.. | ..*...*..... | ...*.*..*... |
20261016 15:57:42 [INFO] | *........*.. | .*......*... | ..*....*.*.. | ...*..*.*... |
20261016 15:57:42 [INFO] | ............ | *........... | .*.......... | ..*...*.*... |
20261016 15:57:42 [INFO] | ...*........ | ............ | .....*...... | ......*.*... |
20261016 15:57:42 [INFO] | ............ | ....*.*..... | .......*.*.. |              |
20261016 15:57:42 [INFO] Completed w_pos 31: 12.93 KB [+36.34%], 30.054074ms [-4.44%]
20261016 15:57:42 [INFO] Cols sizes: 373 / 859
20261016 15:57:42 [INFO] Thinnest ready partial:
20261016 15:57:42 [INFO] |             |             |             | ZZZZZZZZZZZ |
20261016 15:57:42 [INFO] | ........... | ........... | ........... | ........... |
20261016 15:57:42 [INFO] | ........... | ........... | ........... | ........... |
20261016 15:57:42 [INFO] | .....*..... | ......*.... | *....*..... | .*..*.*.... |
20261016 15:57:42 [INFO] | ..*....*... | *.....*.*.. | .*...*..... | ..*.*..*... |
20261016 15:57:42 [INFO] | ........*.. | *......*... | .*....*.*.. | ..*..*.*... |
20261016 15:57:42 [INFO] | ........... | ........... | *.......... | .*...*.*... |
20261016 15:57:42 [INFO] | ..*........ | ........... | ....*...... | .....*.*... |
20261016 15:57:42 [INFO] | ........*.. | ...*.*..... | ......*.*.. | .....*..... |
20261016 15:57:42 [INFO] Completed w_pos 32: 11.08 KB [-15.42%], 31.888694ms [+5.92%]
20261016 15:57:42 [INFO] Cols sizes: 350 / 662
20261016 15:57:42 [INFO] Thinnest ready partial:
20261016 15:57:42 [INFO] |            |            |            | ZZZZZZZZZZ |
20261016 15:57:42 [INFO] | .......... | .......... | .......... | .......... |
20261016 15:57:42 [INFO] | .......... | .......... | .......... | .......... |
20261016 15:57:42 [INFO] | ....*..... | .....*.... | ....*..... | *..*.*.... |
20261016 15:57:42 [INFO] | .*....*... | .....*.*.. | *...*..... | .*.*..*... |
20261016 15:57:42 [INFO] | .......*.. | ......*... | *....*.*.. | .*..*.*... |
20261016 15:57:42 [INFO] | .......... | .......... | .......... | *...*.*... |
20261016 15:57:42 [INFO] | .*........ | ..*....... | ...*...... | ....*.*... |
20261016 15:57:42 [INFO] | ...*...*.. | ....*..... | .....*.*.. | .......... |
20261016 15:57:42 [INFO] | ...*...... |            |            |            |
20261016 15:57:42 [INFO] Completed w_pos 33: 9.87 KB [-11.56%], 31.535159ms [-1.11%]
20261016 15:57:42 [INFO] Cols sizes: 311 / 591
20261016 15:57:42 [INFO] Thinnest ready partial:
20261016 15:57:42 [INFO] |            |            |            | ZZZZZZZZZZ |
20261016 15:57:42 [INFO] | .......... | .......... | .......... | .......... |
20261016 15:57:42 [INFO] | .......... | .......... | .......... | .......... |
20261016 15:57:42 [INFO] | ....*..... | .....*.... | ....*..... | *..*.*.... |
20261016 15:57:42 [INFO] | .*....*... | .....*.*.. | *...*..... | .*.*..*... |
20261016 15:57:42 [INFO] | .......*.. | ..*...*... | *....*.*.. | .*..*.*... |
20261016 15:57:42 [INFO] | ...*...... | .......... | .......... | *.....*... |
20261016 15:57:42 [INFO] | .*.**..... | .......... | .......... | ....*.*... |
20261016 15:57:42 [INFO] | .......... | .......... | ....***... | .......*.. |
20261016 15:57:42 [INFO] | ...*...... | ....**.*.. |            |            |
20261016 15:57:42 [INFO] Completed w_pos 34: 5.51 KB [-56.71%], 33.569849ms [+6.25%]
...
Still TBD implementing this for all the various partials/ends that inspect state. Also TBD deciding "pic(bg)" semantics. I have already sketched replacing "pic(bg)" with a special "default" edge that does what you think but can also make it a strict error if your picture fails to end with a W overlap of agar. The problem is, when is such a picture edge "ready"?

(*) The "smallest" semantics of "ready once it has passed the grid" is almost certainly too little. Pictures often have a bunch of trailing agar and you don't want to have to wait to walk off the end of it to get results.

(*) The "small" semantics of "ready once it has reached the agar-matching tail of the grid" are certainly right for some searches, and maybe even most.

(*) The "big" semantics of "ready as long as the last W overlap matches the agar" might be relevant for searches that have a bit of a sibling branch visible late in the picture but want to accept matches that happen before that as they're likely enough to be solvable clearance-wise.

(*) The "biggest" semantics of "always ready" (matches current non-existence of readiness feature) is almost certainly too much. I've had matches in DB ends that made no sense and were just some broken part of pattern happening to match some ship.

I guess I would probably lean towards making the default (the edge named "default") be the "big" semantics. It's much easier to notice "big" semantics having extraneous ends that have not passed the last bit of non-agar picture and downgrade to "small" semantics than it is to realize your search is missing results with "small" semantics to know to upgrade to "big". Either way presumably the other will stick around as a separate named edge implementation.

Even if this ships it doesn't really solve all "not engaging the prompt" issues. In particular, this doesn't change the search state you get, just what partials/ends output and so if your search is able to bumble on forever without solving the edge(s) it will still do that. What I'm hoping is that the usual tricks of skimming partials to pick a nontrivial engage and copying that to a second search will be much improved.

Re: amling search program principles discussion / brain dump

Posted: October 16th, 2026, 8:54 pm
by LuveelVoom
Here's another partial cutter result. This sort of stuff seems to be the ideal use case, I will have to add my methodology to the guide (a lot of it is just spotting "thin bits" though. I guess SRV2 could help? I don't quite understand what it does)
LuveelVoom wrote: October 16th, 2026, 8:34 pm I believe this 2c/5o is smaller than the current largest (at least population wise)? Found with LLSSS, partial cut used, cut line indicated.

Code: Select all

x = 21, y = 80, rule = B3/S135History
9.3A$8.5A$9.A.A$6.A3.A3.A$5.2A.A.A.A.2A$5.3A.3A.3A$4.2A2.2A.2A2.2A$5.
2A.2A.2A.2A$6.A.2A.2A.A$3.A13.A$3.2A11.2A$3.A3.A5.A3.A$.A6.A3.A6.A$2.
4A9.4A$.A2.2A9.2A2.A$2.2A.A9.A.2A$.19D$4.A.A7.A.A$5.3A5.3A$4.A2.A5.A2.
A$5.A.A5.A.A$4.2A.A5.A.2A$4.A11.A$5.2A7.2A$3.3A.A5.A.3A$.2A4.A5.A4.2A
$4.A.A7.A.A$3.A2.A7.A2.A$3.A.A9.A.A$3.A2.A7.A2.A$6.A7.A$2.2A.A.A5.A.A
.2A$4.A11.A$5.A9.A$6.A7.A2$5.2A7.2A$6.A7.A$6.A7.A$4.A11.A$3.3A9.3A$2.
2A13.2A$.A17.A$4.A11.A$3.A13.A$4.A11.A$4.A11.A$.3A13.3A$2.2A13.2A$A2.
A13.A2.A$A2.2A11.2A2.A$3A15.3A2$2.2A13.2A$.A2.A11.A2.A2$A.A.A11.A.A.A
$2.3A11.3A$2.2A13.2A$.A17.A$A.A.2A9.2A.A.A$A19.A$.A17.A$2.3A11.3A$3.2A
11.2A$2.A15.A$3.2A11.2A2$3.A13.A$3.A.A9.A.A$3.3A9.3A$2.A.A.A7.A.A.A$2.
A15.A$3.A13.A$2.A2.A9.A2.A$2.3A11.3A$5.A9.A$3.A2.2A5.2A2.A$5.A.A5.A.A
$6.A2.A.A2.A!

Re: amling search program principles discussion / brain dump

Posted: October 16th, 2026, 10:13 pm
by amling
LuveelVoom wrote: October 16th, 2026, 8:54 pm I guess SRV2 could help? I don't quite understand what it does
The short version is "add '--partials srv2' and read the logs". More details about its exact behaviour and how it can be configured if you want to change its parameters from the default were I believe last given here.

Re: amling search program principles discussion / brain dump

Posted: October 17th, 2026, 11:55 am
by amling
The other day I was thinking about some of the details of MDSE V3, and in particular the semantics of recentering's mid_steps and how they're gonna be tricky to extend when we remove jcols. I will likely go into more of those details in another post before I actually start writing code for MDSE V3, but right now I want to focus on what I realized about the mid_steps=XX (unlimited) case as I was staring at the code.

Originally when I wrote recentering it was a silly experiment and mid_steps=XX in particular was a curious edge case I included on a whim when I realized there were sensible semantics and it would cost very little code to include it. I had no particular plans for using it and so I didn't really think much about it. Some time later we started doing negative results and censuses (like max pop) where mid_steps=XX is critical, but I never went back and reconsidered the implementation. These days I even run a fair amount of mid_steps=XX searches with pre-reify-autochoke to explore a space or just as a quick, low effort long shot.

As it is, there's a tiny if/else guarding the central loop where if mid_steps is finite we do one thing and if it's XX we do another slightly-different thing. By hiking a bunch of the trailing code into the if/else the mid_steps=XX side can be simplified materially. It is more code overall, but not by a lot, and I believe the savings are going to be serious.

So far for benchmarking I've run p3 statorless maxpop searches. Here "pop" is the population, "t0" is the time in seconds for the current code (N=1 but I believe it's reasonably stable), "t2" is the treatment I'm planning on accepting, and "pct" is the percent savings.

Code: Select all

pop   t0                t2                pct
---   ---------------   ---------------   ------------------
100   2574.750522751    2083.444747231    19.081684659493263
110   5471.289670735    4321.593526129    21.013256723648357
120   11622.964193551   8941.667554654    23.068957231965996
130   24793.472743888   18584.875076079   25.041258769768437
140   49286.508601712   36528.136796879   25.886134292721696
Pop 140 VmPeaks went from 325.50 GB to 314.11 GB. That 314.11 GB VmPeak for t2 includes 25.38 GB of stuff that isn't needed (it's constructed but never read), but it would take quite a bit more code reorganization to eliminate it and I think it likely you wouldn't save the full amount as the new VmPeak would then be elsewhere.

I will probably go on to test MDSE V2 as well before merging the changes.

Re: amling search program principles discussion / brain dump

Posted: October 18th, 2026, 12:30 pm
by NNlk05
How do I try to find camelships with LLSSS? I think it requires a custom GEOM.

Re: amling search program principles discussion / brain dump

Posted: October 18th, 2026, 12:32 pm
by LuveelVoom
Might be worth adding a generalized version of knightwise geometries at this point since people have started searching oblique photons of low enough periods to search.

Also, I'm looking at SRV2 and it's very irritating to extract the chokepoints from the logs. This seems like an ideal usecase for a quick script to extract and sort those! I'll ask an LLM to look into it tonight. In fact, there's quite a few useful things that could be extracted en masse from the logs, you could probably make a graph of memory and time per step over time. That would be cool. The logs in general are tricky to read, which makes sense, and you don't really need to fix that since the most important components are just the visual partial outputs and the ends.

Re: amling search program principles discussion / brain dump

Posted: October 18th, 2026, 1:16 pm
by amling
NNlk05 wrote: October 18th, 2026, 12:30 pm How do I try to find camelships with LLSSS? I think it requires a custom GEOM.
If you want orthogonal axes then "simple_vv" is the current best answer to this. It's sort of like "raw" only it fills in U=X and W=Y.
LuveelVoom wrote: October 18th, 2026, 12:32 pm Might be worth adding a generalized version of knightwise geometries at this point since people have started searching oblique photons of low enough periods to search.
Mmm, I am really not excited about playing zoo whack-a-mole regarding velocity choices.

I've added "simple_vv" and "simple_vv_diag" geometries to the tutorial, including a comment about preferring named geometries and linking back to the original announcement post about them.

Re: amling search program principles discussion / brain dump

Posted: October 18th, 2026, 1:32 pm
by amling
LuveelVoom wrote: October 18th, 2026, 12:32 pm Also, I'm looking at SRV2 and it's very irritating to extract the chokepoints from the logs. ... The logs in general are tricky to read, which makes sense, and you don't really need to fix that since the most important components are just the visual partial outputs and the ends.
The output of LLSSS has no doubt reached the distinct ontological category of "logs" (no longer mere "prints") and my years of enterprise software development-induced perspective damage is no doubt not helping me keep them sensible for those without as much experience navigating enormous, messy firehoses of text. That said, I'm not really sure what to do about it. I am absolutely insistent on me getting my data and offering log level is my best idea for helping reduce the clutter for others.

As for SRV2 partials specifically, when I read an LLSSS log for them, I'm either scanning it live because it's a search I'm paying close attention to, or I search (in one way or another) for all chokes below some width limit and read them all. The LLSSS env system means it would be easy to offer other formats for SRV2 output, but I just can't imagine what they would be.

Re: amling search program principles discussion / brain dump

Posted: October 18th, 2026, 1:38 pm
by LuveelVoom
amling wrote: October 18th, 2026, 1:32 pm The output of LLSSS has no doubt reached the distinct ontological category of "logs" (no longer mere "prints") and my years of enterprise software development-induced perspective damage is no doubt not helping me keep them sensible for those without as much experience navigating enormous, messy firehoses of text. That said, I'm not really sure what to do about it. I am absolutely insistent on me getting my data and offering log level is my best idea for helping reduce the clutter for others.
I think a useful simplified log would:
-Drop the "unique" partial outputs, which aren't very informative
-Drop the massive set of [DEBUG] expand and shrink messages, and only leave a message about current w-pos, maximum memory used, PRAC (if it kicks in), and time the step took.
This would remove a ton of the clutter that most people don't really care about.
amling wrote: October 18th, 2026, 1:32 pm As for SRV2 partials specifically, when I read an LLSSS log for them, I'm either scanning it live because it's a search I'm paying close attention to, or I search (in one way or another) for all chokes below some width limit and read them all. The LLSSS env system means it would be easy to offer other formats for SRV2 output, but I just can't imagine what they would be.
Outputting a file with a list of SRV2 chokes in lowest to highest width order would be nice :)

Re: amling search program principles discussion / brain dump

Posted: October 23rd, 2026, 2:23 pm
by amling
Some time back I had carefully reworked pd_rotor_tree to catch some results intratile. Since then I have made a lot of time to think about geometry and generalize that work and I have realized that my conception of W rows (and analogously, U columns) is unnecessarily coarse. In certain geometries there is a natural division of each W row into what I've taken to calling "fractional W rows", i.e. the collection of positions that have the exact same W coordinate (really, in all geometries, but in some it's "divided into" just one fractional W row). In LLSSS, searches are always ordered accordingly (by W) and so really a lot of features could be operating on fractional W rows instead. Armed with this understanding I have (so far) improved pd, pd_lite, and pd_rotor_tree (as of 249b6d9e3b4c, just pushed).

As an example, consider search in p2/W=4Y, a silly geometry invented to showcase the problem. Each W row is 4 Y high while each fractional W row is 1 Y high. Previously the pd_rotor_tree stuff was able to catch results at the end of fractional W rows, i.e. at the end of every Y row, but it still required they be the entire W overlap long. Here W overlap is 1 which is 4 Y which is much longer than necessary. If you perform the same sort of CA check analysis on fractional W rows you get that the fractional W check size is 3 and the fractional W overlap size is 2. This matches our intuition that 2 Y rows (i.e. 2 fractional W rows) is enough to stitch patterns together. The new pd_rotor_tree code (and new pd_lite) understand this and are able to detect and record PD hits as early as is sensible.

Consider this search, completing a specifically-aligned blinker:

Code: Select all

$ cat n1.in
| ....... | ....... |
| ....... | ....... |
| ...*... | ....... |
| ...*... | ..***.. |
$ cat n1.cstr
| ....... | ....... |
| ....... | ....... |
| ...*... | ....... |
| ...*... | ..***.. |
| ...*... | ....... |
| ....... | ....... |
| ....... | ....... |
| ....... | ....... |
| !!!!!!! | !!!!!!! |
| !!!!!!! | !!!!!!! |
| !!!!!!! | !!!!!!! |
| !!!!!!! | !!!!!!! |
$ rlife llsss p2/W=4Y n1.in --constraint 'grid("n1.cstr", none)' --ends '[pd_lite(2), pd_rotor_tree(2)]'
...
20261023 11:04:11 [INFO] End LlsssEndsPdLite depth 2[/4]:
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ...*... | ....... |
20261023 11:04:11 [INFO] | ...*... | ..***.. |
20261023 11:04:11 [INFO] | ...*... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] |         |         |
20261023 11:04:11 [INFO] LlsssEndsPdRotorTree inserted: LabelTreeId(0) + 0b10000000 -> LabelTreeId(1)
20261023 11:04:11 [INFO] LlsssEndsPdRotorTree inserted: LabelTreeId(0) + 0b10000 -> LabelTreeId(2)
20261023 11:04:11 [INFO] LlsssEndsPdRotorTree inserted: LabelTreeId(2) + 0b1 -> LabelTreeId(3)
20261023 11:04:11 [INFO] End LlsssEndsPdRotorTree tree +3: {"steps":[[0,128],[0,16],[2,1]]}
...
20261023 11:04:11 [INFO] End LlsssEndsPdLite depth 3[/4]:
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ...*... | ....... |
20261023 11:04:11 [INFO] | ...*... | ..***.. |
20261023 11:04:11 [INFO] | ...*... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
20261023 11:04:11 [INFO] | ....... | ....... |
...
20261023 11:04:11 [INFO] Done
Even 7 Y rows in, which is 1 and 3/4 W rows in, it fires and detects the 2 fractional W rows of PD. Depth outputs are now marked with the fraction so here "/4" to indicate depth is measured in fractional rows which are 1/4 of a W row.

I think in common geometries there is no difference between W overlap and fractional W overlap so maybe that part isn't a big deal. I do think features understanding fractional W rows and U cols in general is going to improve oblique and diagonal geometry handling quite a bit though. E.g. if you're running c4d-down you really want ends checked every 1T (which is what a fractional W row corresponds to here), not every 1Y (which is what a full W row corresponds to, and what a lot of the features right now are limited to).

TBD percolating this new understanding down to various features. My attention was on the PD stuff because I'm trying to take another swing at the 2c/10d stuff and decided to start fresh, redoing the original pd_rotor_tree pipeline to 2 TB. I assume I will get around to updating other features as they come up for me, although perhaps I will expedite agar ends...

Re: amling search program principles discussion / brain dump

Posted: October 23rd, 2026, 8:22 pm
by Katrina
What exactly is this pd stuff for? I've tried messing around a bit and trying geometries like "2c6-f2b-pd2" but it hasn't made a difference in the way it searches from what I could tell.

Re: amling search program principles discussion / brain dump

Posted: October 23rd, 2026, 10:48 pm
by amling
Katrina wrote: October 23rd, 2026, 8:22 pm What exactly is this pd stuff for? I've tried messing around a bit and trying geometries like "2c6-f2b-pd2" but it hasn't made a difference in the way it searches from what I could tell.
The high-level overview for PD tools has not changed since the beginning:
amling wrote: May 5th, 2022, 2:43 am ...I configure ends to output partials whose tips are compatible with some division of V...
I reiterated some of that and discussed the early work on the rotor tree stuff here.

The PD geometries are sort of a weird hack to change intratile search order. Originally discussed here. Some searches may go faster, some may go slower, some may have different lucky chimerism (recentering). But 2c6-f2b and 2c6-f2b-pd2 are identical:

Code: Select all

$ rlife grid-tool geom-info 2c6-f2b
Geometry: 2c6-f2b
   U: Vec3(1, 0, 0)
   V: Vec3(0, -2, 6)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 7
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 3) => Vec3Uvw(0, 1, 0)
   WAO maximal tile masks: WaoTileMasks(3 = 0b11, 3 = 0b11)
$ rlife grid-tool geom-info 2c6-f2b-pd2
Geometry: 2c6-f2b-pd2
   U: Vec3(1, 0, 0)
   V: Vec3(0, -2, 6)
   W: Vec3(0, 0, 1)
   Neighborhood sizes:
      U: 3
      W: 7
   Unique positions (2):
      #0: Vec3(0, 0, 0) => Vec3Uvw(0, 0, 0)
      #1: Vec3(0, -1, 3) => Vec3Uvw(0, 1, 0)
   WAO maximal tile masks: WaoTileMasks(3 = 0b11, 3 = 0b11)
$
None of these are simple tools. If you have a problem at a divisible speed and you want to try, the simplest version is to add 'pd_lite(K)' to ends and see if it finds anything. If it does and you can solve it in whatever way you solve partials (at the reduced speed), great. If it does and you can't solve it, feel free to come back to this thread with the problem and we can try to talk through pd_rotor_tree.

Re: amling search program principles discussion / brain dump

Posted: October 25th, 2026, 11:56 am
by amling
amling wrote: October 17th, 2026, 11:55 am I will probably go on to test MDSE V2 as well before merging the changes.
I have finished benchmarking the new mid_steps=XX code with MDSE V2. This was p3 statorless maxpop up to 140. Times in seconds (N=1) with "pct" being the percent savings for the treatment:

Code: Select all

pop   baseline           treatment         pct                
---   ----------------   ---------------   -------------------
10    5.604885291        5.680295394       -1.3454352602200186
20    16.925585138       16.770667975      0.9152839428410215 
30    43.408398571       42.805002821      1.3900437930532406 
40    96.152888802       93.255317925      3.013503715906803  
50    204.254889099      201.54891567      1.324802280589929  
60    422.510040383      411.072786827     2.706977932555697  
70    839.213441001      822.944095193     1.938642187212137  
80    1743.798782044     1688.845377805    3.1513615449705865 
90    3724.932288123     3655.830150806    1.855124656556397  
100   8168.618403164     7839.083674809    4.0341550075023624 
110   17497.143088011    17014.682306445   2.7573688981064532 
120   37514.057217469    36407.876500108   2.9487098954625717 
130   80919.903834619    79239.209062396   2.0769856272419083 
140   164476.050509813   159337.47115139   3.1242113015818274
Memory is still in the range of what it was previously (87.76 GB here), although for different reasons. Previously the peak had been during the worst moment in expansion, which is no longer used for mid_steps=XXX. The new peak is during pre-reify filtering and it's sort of rough. Expansion's view of its state is only ~39 GB, but the bcol sizes is 2844164507 and so the maxpop filter has to allocate 2x 2844164507x 4x 2B = 42.38 GB to store l2r and r2l weights for each extended bcol position. 2x for l2r/r2l. 4x for it being each extended bcol position. 2B for the u16 we store maxpop weights in. This sort of suggests that my prior rule of thumb that any bcol position-indexed data was meaningless(ly small) is maybe less true with MDSE V2, although I'm not sure even knowing this I could do much better. I suppose we could try to move down to u8s for population where sufficient (saving ~21GB here), although it either means some weird code to manage that dynamically or requiring a recompile if we need to go over.

Anyway, I'm reasonably happy with the changes as-is and have merged them into master.

Re: amling search program principles discussion / brain dump

Posted: October 25th, 2026, 3:51 pm
by LuveelVoom
I don't know enough about LLSSS to be able to answer this question. Is it possible that an LLSSS search can be partitioned into multiple parts, like a qfind search, and then distributed across multiple machines (or runs) to use less memory and be faster? Ideally, if possible, a recentering (or recentering-wao) search?

Re: amling search program principles discussion / brain dump

Posted: October 25th, 2026, 4:59 pm
by amling
LuveelVoom wrote: October 25th, 2026, 3:51 pm I don't know enough about LLSSS to be able to answer this question. Is it possible that an LLSSS search can be partitioned into multiple parts, like a qfind search, and then distributed across multiple machines (or runs) to use less memory and be faster? Ideally, if possible, a recentering (or recentering-wao) search?
Sort of, although I don't think any of this is going to make anything faster. The only game in town is grid constraints (EDIT: well, I guess you could also roll some of this into input grids, but the principles and restrictions are the same), which can address (and can only address) cells by root label and spine position. It is not enough just that the targetted root labels be unique, but they moreover need to be "unloopable", i.e. each can show up at most once per partial, so when you fix a cell in its column, each partial can necessarily match at least one of the two choices.

In fixed board searches this all shakes out very nicely. Each column has a distinct root label, in a given partial they're all unique, and so grid constraints can address any location exactly. Partials very clearly fall into one side or the other, although some strips may be present in both searches. Any search that is too big can have its constraint forked on another location.

In recentering this is not so easy. For starters, for a typical WAO search the root labels are all the same. You could "unroll" a WAO search, filling in what it effectively does with labelled roots, and optionally unroll some left/right columns with unique labels to be able to address them.

Recentering has the additional problem that mid_steps is not exact. Any partial contained in what I think of as the intentional part of the search (i.e. whose apparent width is contained within mid_steps) will necessary be found in exactly one of the partitions. Over-wide partials that were only found due to chimerism may not be found in any partition. Extra over-wide partials may show up in a partition due to its statistics changing chimerism for itself.

As a quick example, let's sketch some splitting of a c3-f2b search. Instead of this WAO search:

Code: Select all

$ rlife llsss-recentering-wao c3-f2b '@bg' 06
...
I would unwind it to (a version of) how I would have to have run it before I invented WAO, with one marked column, and a constraint forcing it (the column) to have the first on cell (herein the "critical cell") in its row:

Code: Select all

$ cat n1.in
|         |         | LLLuRRR |
| ....... | ....... | ....... |
| ....... | ....... | ....... |
$ cat n1.cstr
|         |         | LLLuRRR |
| ....... | ....... | ....... |
| ....... | ....... | ....... |
| ...*WWW |
$ rlife llsss-recentering c3-f2b 'n1.in' --constraint 'grid("n1.cstr", none)' 06
...
I could now split it by any cell in that one "u" column. Instead let's unroll a few columns left/right:

Code: Select all

$ cat n2.in
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
$ cat n2.cstr
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
| ......*WWWWWW |               |               |
$ rlife llsss-recentering c3-f2b 'n2.in' --constraint 'grid("n2.cstr", none)' 06
...
So far these have all run similar searches (not identical due to root label changes possibly changing stats, possibly changing chimerism).

Now that I've unrolled those roots I can split on, say, the cell right of the critical cell. I've made two copies of n2.cstr and change the first W in each:

Code: Select all

$ cat n2-0.cstr
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
| ......*.WWWWW |               |               |
$ cat n2-1.cstr
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
| ......**WWWWW |               |               |
If I didn't like n2-0.cstr (too big e.g.), I could add more rows of Ws and split again, this time on, say, the cell below the critical cell:

Code: Select all

$ cat n2-00.cstr
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
| ......*.WWWWW | WWWWWWWWWWWWW | WWWWWWWWWWWWW |
| WWWWWW.WWWWWW |               |               |
$ cat n2-01.cstr
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
| ......*.WWWWW | WWWWWWWWWWWWW | WWWWWWWWWWWWW |
| WWWWWW*WWWWWW |               |               |
$ cat n2-1.cstr
|               |               | LLLuuuuuuuRRR |
| ............. | ............. | ............. |
| ............. | ............. | ............. |
| ......**WWWWW |               |               |
$
Etc.

I recognize this is all quite painful, but between how rarely I've used it and how poorly it interacts with recentering (which is nearly all my searches these days), I just haven't put much thought into imagining alternatives, either in mechanism or in interface.

Re: amling search program principles discussion / brain dump

Posted: October 25th, 2026, 5:06 pm
by LuveelVoom
amling wrote: October 25th, 2026, 4:59 pm Sort of, although I don't think any of this is going to make anything faster.
The most important part is reducing memory usage; plus, if it only searches a component of the space, it should be faster when being run on multiple people's computers simply because each section of the space has a smaller number of possibilities, no?

Anyway, I would be interested to see if a viable method for doing this can be figured out at some point. My machine has juuust a bit too little memory to do mid-steps 12 c6k-1 searches.

Re: amling search program principles discussion / brain dump

Posted: October 25th, 2026, 5:17 pm
by amling
LuveelVoom wrote: October 25th, 2026, 5:06 pm The most important part is reducing memory usage.
No doubt.
LuveelVoom wrote: October 25th, 2026, 5:06 pm ...if it only searches a component of the space, it should be faster when being run on multiple people's computers simply because each section of the space has a smaller number of possibilities, no?
I'm not sure. I do agree that the same data covered in a smaller search is probably faster, all else equal (something something memory cache hierarchy). Unfortunately, in nearly all cases some data is going to be kept on both sides of a partition and so the combined size will be strictly larger than the original. Which will win out (improvements or losses) for real world use I cannot say.
LuveelVoom wrote: October 25th, 2026, 5:06 pm Anyway, I would be interested to see if a viable method for doing this can be figured out at some point. My machine has juuust a bit too little memory to do mid-steps 12 c6k-1 searches.
It can be done right now ("viable"), it's just miserable. If you're trying to eke out more search from the same memory, at the cost of performance, you might also consider MDSE V2. Generally inputs/setups will all look the same and most features are available, it's just going to use a lot less memory and be a lot slower to run. To go down this road, you'd find the commented out lines in src/entry.rs and enable them (in corresponding pairs, for whichever subcommands you want to include), then add "-mdse-v2" to the end of your subcommand to run the MDSE V2 one instead. If you do this, I would love to hear any data you have about search performance, as so far I think it's just been me.

Re: amling search program principles discussion / brain dump

Posted: October 25th, 2026, 5:25 pm
by LuveelVoom
amling wrote: October 25th, 2026, 5:17 pm It can be done right now ("viable"), it's just miserable. If you're trying to eke out more search from the same memory, at the cost of performance, you might also consider MDSE V2. Generally inputs/setups will all look the same and most features are available, it's just going to use a lot less memory and be a lot slower to run. To go down this road, you'd find the commented out lines in src/entry.rs and enable them (in corresponding pairs, for whichever subcommands you want to include), then add "-mdse-v2" to the end of your subcommand to run the MDSE V2 one instead. If you do this, I would love to hear any data you have about search performance, as so far I think it's just been me.
I may test this on smaller searches (1-2 kiloseconds) with fairly high (10-20gb) mem requirements to see how it turns out.

Ideally there would be a way to do distributed searches, though... As I've mentioned, I feel like a lot of the abilities of LLSSS are being underused due to a lack of a good user-facing method of doing things/a lack of simple QOL features. This one (partitioning, at least) cannot be solved from my side, though, and I will not pester you about adding it (though I would be very happy if you did!)

Why is MDSE commented out if it's an optional setting, by the way?

Re: amling search program principles discussion / brain dump

Posted: October 26th, 2026, 5:43 pm
by amling
LuveelVoom wrote: October 25th, 2026, 5:25 pm Why is MDSE commented out if it's an optional setting, by the way?
It is my belief (assumption?) that including the MDSE V2 subcommands hurts compile time, compile memory, and binary size materially.
LuveelVoom wrote: October 25th, 2026, 5:25 pm Ideally there would be a way to do distributed searches, though...
It's sort of the same meta-problem all over again. How do we translate the simple-seeming user problem of "I want to partition searches" into well-defined semantics and interface we can actually implement using programming? I unfortunately just don't see it. I took some time to collect my thoughts and some previous projects and prototypes and I'll try to summarize here. Mostly the short version is I cannot imagine any version of this that is anything resembling usable by others and I run this type of search so rarely and with such weird projects that I cannot imagine it helping me. Some details below...

The first ugly detail is the notion of addressable roots. As I said earlier, grid constraints, or code that acts in that sort of way, are essentially the only option. I also said above that to have any hope of functioning at all your targetted roots must be "unloopable", which is true, but additionally if they're "optional" (i.e. can appear zero times in a partial) you probably want to first partition into state with the root and state without it, which is a bunch more icky edge cases and code. Maybe simple enough searches only have this stronger type of addressable root (always used exactly once in each partial), but e.g. multiple-index WAO searches do not (e.g. any WAO search with symmetry or an interesting background agar). We would presumably paper over this somehow if it were the only problem.

The second ugly detail is lifecycle.

I had made a prototype some time back where I had a component that was able to halt a search and start it over, passing data to its own analog in the restarted search. It then used this power to manage a queue of fragmented search spaces with more or less the same sort of goal: partition the search into small enough chunks to complete them all eventually. This sort of thing (halt search and restart in-process) was really ugly and interacts very poorly with the initialization code.

There are other options like state files/directories, separate orchestration processes, etc., but they're all so many moving parts and weird interfaces and I cannot imagine making any variant of any of them sensible for users.

Probably the cleanest-feeling is you could have some sort of "shard shedder" that would run pre-reify and split off part of the search space if it looked like the search was getting too big. Operators would then have to do follow up searches on each split shard, then on each shard split from those searches, etc. The main benefit of this approach, in my mind, is that searches never fail, instead they just cover a smaller space and leak some shards.

You could view it in a more tree-like fashion and have saved (meta)state data like a tree of shards. Every time the search starts it picks up the next node. If the search gets too big it records what happened in the tree, splitting that node, and halting the search (and operator has to restart it). If there are no nodes left it "fails" initialization to indicate success.

There are endless recombinations of these sorts of things, but they all suck.

Finally, my thoughts about splitting choices... I think generally here you want to split as evenly as possible (distinct from PRAC where you want to split as unevenly as possible). To have any chance of this I feel splits have to be chosen mid-search, rather than before any searches start. Like what are you gonna do if there is one really good start/head that 100 rows later has a huge search space behind it? No preemptive split is going to be able to break that up (keeping in mind the entire search space "beneath" that good start has identical first 100 rows). This sort of puts a damper on distributing things, although I guess you could always start distributing once your search starts leaking shards?

Re: amling search program principles discussion / brain dump

Posted: October 31st, 2026, 3:36 pm
by LuveelVoom
There seems to be severe slowdown when outputting partials. Run these two searches:

Code: Select all

./rlife llsss --rule B3/S23 --left-edge even --filters bcaf --halts 'w_pos(220)' c4-f2b '@bg(11)' 2>&1 | grep -E 'Run step LlsssMonitorUniquePartial:| Total: |Final results'

Code: Select all

./rlife llsss --rule B3/S23 --left-edge even --filters bcaf --halts 'w_pos(220)' --pre-partials none c4-f2b '@bg(11)' 2>&1 | grep -E ' Total: |Final results'
On my machine, the first one took 33 seconds and the second one took 25 seconds

Re: amling search program principles discussion / brain dump

Posted: October 31st, 2026, 9:38 pm
by amling
LuveelVoom wrote: October 31st, 2026, 3:36 pm There seems to be severe slowdown when outputting partials. Run these two searches...
Even just running the first knows the difference. Locally I rolled 34s and timing stats at the bottom tells me unique partial was 7.13s of that. There's not much I can add to it, really, other than to underscore partials do not exist and must be cooked out of the state in memory and this cooking has a cost. At this point they can be disabled if you (understandably) don't want to pay whichever cost. It's not inconceivable it could be improved, but I think it costs proportionally much, much less on larger searches so it's not really on my radar to even try.

Re: amling search program principles discussion / brain dump

Posted: October 31st, 2026, 9:41 pm
by LuveelVoom
amling wrote: October 31st, 2026, 9:38 pm Even just running the first knows the difference. Locally I rolled 34s and timing stats at the bottom tells me unique partial was 7.13s of that. There's not much I can add to it, really, other than to underscore partials do not exist and must be cooked out of the state in memory and this cooking has a cost. At this point they can be disabled if you (understandably) don't want to pay whichever cost. It's not inconceivable it could be improved, but I think it costs proportionally much, much less on larger searches so it's not really on my radar to even try.
Is generating a partial only every N w-pos a viable option?
All times are UTC-04:00
Page 26 of 27

Powered by phpBB® Forum Software © phpBB Limited