amling search program principles discussion / brain dump

MDA · Post by **MDA** » August 20th, 2026, 9:06 am

What does the frequently mentioned “pre-reify-autochoke” option do?

amling · Post by **amling** » August 20th, 2026, 10:40 am

MDA wrote: August 20th, 2026, 9:06 am What does the frequently mentioned “pre-reify-autochoke” option do?

The shortest version is it truncates the search to try to keep it from using too much memory. There are a lot more details up thread about how the internals work, but from a user perspective pick a memory amount and you're off to the races, except...

(*) Your search is now approximate and will not necessarily find what it would have without the option.

(*) Its estimate of memory sizes is not so great for complex reasons. Best to consider the amount you specify a fuzzy sliding bigness scale and figure out what you can afford empirically. I think I have usually run it with a limit of 24 GB on a box with 64 GB e.g.

(*) Depending on the rest of your arguments it can get stuck in a weird sort of "pyramidal" failure mode where partials keep getting wider and wider but are clearly too big to ever work out. This is especially a problem with unlimited width searches (mid_steps=XX). You might want to keep an eye on partials as it goes and give up on the search if they're looking sufficiently bad.

amling · Post by **amling** » August 20th, 2026, 11:03 am

amling wrote: August 12th, 2026, 1:09 pm
amling wrote: August 11th, 2026, 7:30 pm (recentering MDSE V2 MVP)
There are definitely still big perf issues left before I move on to the real benchmarking, but I think I have ideas about how to address most of them.

I have moved on to the first couple rounds of serious benchmarking and it's maybe in the range of what was expected.

Originally MDSE V1 searches had been hurt pretty badly by the abstraction and the required changes in some algorithms, but as I was playing with it I worked out a different way to do the MDSE V2 BitTree parallelization that is both quite a bit faster for itself and also might recover a bunch of that abstraction cost for MDSE V1.

On my current branch I've applied the trick in only a few select places and already the improvements from it are huge. For the last, biggest recentering search this round ran...

MDSE V1 was very slightly faster than on master: 425s -> 414s, although it's not super clear if this is variance. It is believable that it is improvement, as on master there were definitely some abstraction costs already paid (as part of shared code with fixed board that was migrated to MDSE stuff earlier).

MDSE V2 is not great, but not as bad as I had worried it would be and much better than earlier (unposted) rounds of benchmarking: 414s -> 2924s (~7.06x). Improvement in maximum memory observed at any point is similar to fixed board work: 6.33 GB -> 1.73 GB (~3.66x better).

I think it is likely that both of these will get even better once I apply the new BitTree parallelization everywhere as this round of benchmarking was just testing individually migrating the two most expensive users of BitTree parallelization.

I am undecided if I will pause this to go do these BitTree improvements directly on master first, while carefully benchmarking fixed board MDSE V2 or if I will just blaze on and include all those improvements in this recentering MDSE V2 work. The former is definitely the right and paranoid thing to do, but I am pretty excited about recentering MDSE V2.

LaundryPizza03 · Post by **LaundryPizza03** » August 21st, 2026, 2:42 am

amling wrote: August 17th, 2026, 1:56 pm
LaundryPizza03 wrote: August 16th, 2026, 4:49 pm
amling wrote: August 14th, 2026, 10:56 am I'm not sure exactly why you want to search this way, but if you expand your motivations we might have other ideas that could help. I assume you think there are interesting partials that "tilt" (viewed from the W=Y angle of c5k-1) this way and you're running "fixed board" searches (i.e. "llsss" subcommand) which are obligated to follow W strictly. Recentering searches would cover patterns that tilt, although it widens the search space to any kind of tilting, and might take slightly wider mid_steps than you might think, due to all that tilting.
Two ships found by Josh Ball in 2011 in closely related rules have this orientation, as do the known (2,1)c/5 ships in B35/S34. It is likely that some rules favor knightships whose long axis is closer to orthogonal than the direction of propagation, while others favor knightships whose long axis is closer to diagonal.
That's sort of what I suggested, and an overwhelming reason to do something other than search with fixed board c5k-1. From my experience with LLSSS I really think c5k-1 recentering is the best choice, but you are of course free to chase (and advocate for) others...

LaundryPizza03 wrote: August 16th, 2026, 4:49 pm Is AF2 a variable in the build file or an environment variable?
(2) c5k-1/W=X+Y/U=X-Y fixed board last completed board width 12 (so pattern width 8, although these are essentially twice as big as the above with U=X) in 3.88 GB:
Code: Select all
x = 311, y = 60, rule = B36/S3458History
F61.F61.F61.F61.F12.B48.F$F61.F13.B47.F12.2B47.F12.2B47.F11.3B47.F$F
12.2B47.F12.3B46.F11.4B46.F11.4B46.F10.5B46.F$F11.4B46.F11.5B45.F10.
6B45.F10.6B45.F9.7B45.F$F10.6B45.F10.7B44.F9.8B44.F9.8B44.F8.9B44.F$F
9.8B44.F9.9B43.F8.10B43.F8.10B43.F7.11B43.F$F8.10B43.F8.11B42.F7.12B
42.F7.12B42.F6.13B42.F$F7.12B42.F7.13B41.F6.14B41.F6.14B41.F5.7BA7B
41.F$F6.14B41.F6.15B40.F5.7BA8B40.F5.6B3A2BA4B40.F4.6B3AB2A5B40.F$F5.
9BA6B40.F5.6B3AB2A5B39.F4.7B3AB3A4B39.F4.6B2ABAB2A5B39.F3.6B2A2BAB2A
5B39.F$F4.6B4AB3A4B39.F4.5B5AB3A5B38.F3.7B4AB2A6B38.F3.6B5ABA7B38.F2.
6B2AB5A7B38.F$F3.6B6AB2A5B38.F3.6BA14B37.F2.7B2A5B2A6B37.F2.6B3A2BAB
2A7B37.F.7BABA4B3A6B37.F$F2.7B2AB7A5B37.F2.6B2ABA6BA6B36.F.7B2A2BA12B
36.F.7B2A6BABA6B36.F.6B2A2B3AB2A8B36.F$F.8BABABAB3A7B36.F2.7BAB2A13B
35.F2.7BAB2A4B2A7B35.F2.6B2AB2AB3A9B35.F2.5B3AB2ABABA9B35.F$F2.6B2A2B
3AB2A8B35.F3.5B2A2B3A2B2A8B34.F3.7B7A10B34.F3.5BABAB5ABA8B34.F3.5B5AB
AB2A9B34.F$F3.5BAB2A2B4A9B34.F4.10B2ABA10B33.F4.4B3ABAB2ABA10B33.F4.
5B2AB2A2B3A9B33.F4.4B3AB5ABA9B33.F$F4.9BABAB2A9B33.F5.4BABA2B2AB2A10B
32.F5.9B2AB2A10B32.F5.4BA4B2AB3A9B32.F5.5BABAB2A3B2A8B32.F$F5.4BABABA
BABA2BA8B32.F6.11BA12B31.F6.8BA2B2ABA9B31.F6.7B2A2B4A9B31.F6.7B3ABA2B
A9B31.F$F6.7BA4B3A9B31.F7.6BA3B5A9B30.F7.7BABAB5A8B30.F7.6BA3B2AB3ABA
6B30.F7.5B2A2B2A2B3AB2A5B30.F$F7.5BAB3A2BABA9B30.F8.6B2A3BAB2A2BA6B
29.F8.6BABAB2A2B4A6B29.F8.5BA3B2ABAB4A6B29.F8.4BABAB5A3B2A6B29.F$F8.
5B2A2B2A2B2AB3A5B29.F9.4B2A2B2AB3AB4A5B28.F9.5BA2B2AB3ABABA6B28.F9.4B
A3B2AB5A8B28.F9.8B2AB2A4BA6B28.F$F9.7B2AB9A5B28.F10.5B3ABA3B4A7B27.F
10.4BAB2ABABABABA8B27.F10.6B2A3BABAB2A7B27.F10.6B2A2B6A8B27.F$F10.6BA
2B4A11B27.F11.8BA3B4A8B26.F11.5BA6B2ABA8B26.F11.4BABA5B2A10B26.F11.9B
2ABA2BA8B26.F$F11.7B2ABAB5A7B26.F12.7BABAB3A10B25.F12.11BABA10B25.F
12.8B2AB3A10B25.F12.8B2AB3A10B25.F$F12.8B2A2BA11B25.F13.7B2A3BA11B24.
F13.6B4AB3A10B24.F13.7B3A3BA10B24.F13.7B3A14B24.F$F13.7B2AB3A11B24.F
14.6B4ABA12B23.F14.6BA2B4A11B23.F14.5B2A2BA2BA11B23.F14.5B2A6BA10B23.
F$F14.7B5A12B23.F15.6B5A13B22.F15.6BAB3A13B22.F15.5BA2BA3BA11B22.F15.
4BABABAB4A10B22.F$F15.5B2A6B2A9B22.F16.5BA3B2AB2A10B21.F16.5BA3B2AB2A
10B21.F16.6B3ABAB2A10B21.F16.7B3A2B3A9B21.F$F16.7BA2B4A10B21.F17.5BA
3B4A11B20.F17.7B6A11B20.F17.7BA3B3A10B20.F17.7BA3B2A11B20.F$F17.6B4A
2B2A10B20.F18.6B3A2B3A10B19.F18.7B2ABABA11B19.F18.7BA2BA13B19.F18.6BA
BABA13B19.F$F18.7BA3B3A10B19.F19.6BA2B3A12B18.F19.6BAB2A14B18.F19.6BA
B2A14B18.F19.8B3A13B18.F$F19.7BA2BA13B18.F20.5B2A2B3A12B17.F20.6BABA
2BA12B17.F20.6B3A15B17.F20.6BAB2A2BA11B17.F$F20.6B5A13B17.F21.6B5A13B
16.F21.6B2ABA14B16.F21.6B2A2B3A11B16.F21.7B2A2BABA10B16.F$F21.9B2A2BA
10B16.F22.5BAB5A12B15.F22.6BA3B3A11B15.F22.5B2A4BABABA8B15.F22.5B2A3B
2A3BA8B15.F$F22.7B2AB2A12B15.F23.6B2AB3A2BA9B14.F23.6B3A2BAB3A8B14.F
23.6B3AB2AB4A7B14.F23.6B6AB5A6B14.F$F23.6BA3BA2B3ABA6B14.F24.5BA2B2A
2B3ABA7B13.F24.6BABABAB3AB2A6B13.F24.5B6ABAB3A7B13.F24.5BA4BA2BA2B2A
6B13.F$F24.6B13A5B13.F25.7B5AB4A7B12.F25.6B4A3B3A8B12.F25.6B4A3B4A7B
12.F25.6BA2B2AB5A7B12.F$F25.10BA2BA3BA6B12.F26.4BA3B5A11B11.F26.8BA4B
A10B11.F26.6BA8BA8B11.F26.5B2AB3A2B4A7B11.F$F26.5BABAB2AB3A9B11.F27.
8B5A3BA7B10.F27.11B3ABA8B10.F27.8B6ABA8B10.F27.9B5AB2A7B10.F$F27.7B5A
4B2A6B10.F28.6B3A2B2AB2A8B9.F28.7B3ABAB4A7B9.F28.8B2ABAB2ABA7B9.F28.
8BAB2ABA10B9.F$F28.9B3A2B2A8B9.F29.7BABA3B2A9B8.F29.7BABABAB3A8B8.F
29.7BABA5BA8B8.F29.7B3ABA12B8.F$F29.7B2A4B2A9B8.F30.7B2ABAB2A10B7.F
30.6B3A3B2A10B7.F30.7B2ABAB2A10B7.F30.8BA2BA5B2A5B7.F$F30.8B2AB2A11B
7.F31.5BAB2ABA7BA5B6.F31.7BAB2A3BA2BA6B6.F31.5B3A2BA4B4A5B6.F31.6B2A
2B2AB6A5B6.F$F31.6B3AB3A2BAB3A4B6.F32.6B4AB4AB2A6B5.F32.5B2A2B2AB2AB
3A6B5.F32.7B6AB4A6B5.F32.7BAB4ABA4BA4B5.F$F32.7B2AB2AB5A6B5.F33.6B2A
3B2A2B3A6B4.F33.10BA4B4A5B4.F33.5B4AB2A3B5A4B4.F33.6BABA2BA3B4A5B4.F$
F33.9B6A9B4.F34.5B2AB4AB2A2B2A5B3.F34.5B2A2B3ABA2B3A5B3.F34.7BAB2A4BA
2BA5B3.F34.4BA2B4A2BABA2BA5B3.F$F34.5BA2BA2BA2B6A4B3.F35.7BA4B6A6B2.F
35.5BAB2A5B4A6B2.F35.4BA2B2AB2AB2A2B2A5B2.F35.5BA4BAB3AB2A6B2.F$F35.
5BAB7AB2ABA5B2.F36.5BAB2AB3A4B2A5B.F36.6B2A2BA2BABABA6B.F36.5B5A2B2AB
A7B2.F36.6B4A2B4A7B2.F$F36.8B3ABAB4A6B.F37.7BAB4A3BA6B.F37.7BABA2B2A
3BA4B2.F37.6BA2BA2B3A6B3.F37.6B4A4BA6B3.F$F37.7BABA2B4A6B2.F38.6B3AB
3A8B2.F38.7B2AB2A2B2A4B3.F38.6B3AB6ABAB4.F38.6B5ABA2BA3B4.F$F38.5B2A
2BA4B2A4B3.F39.7BABA3B2A4B3.F39.6B2ABA3B2AB2A4.F39.6B9ABA5.F39.5B5A4B
3A5.F$F39.7BA2B2A2BA2BA4.F40.4B2A2B9A4.F40.6BAB3A2B2AB5.F40.6BA2B2A2B
2A6.F40.6B2A4B3A6.F$F40.5BA3B2A3BAB5.F41.6BAB4A3B5.F41.4B2A3B2A3B6.F
41.5BABAB3AB7.F41.4BA3BAB2AB7.F$F41.4BAB2A3B2AB6.F42.4BA2B6A6.F42.5BA
2BA2BA7.F42.4BA2B3AB8.F42.5B3A3B8.F$F42.9BABA7.F43.5B4ABA7.F43.6BA3B
8.F43.6BABA9.F43.5B3AB9.F$F43.6B2ABA8.F44.6BABA8.F44.4B3AB9.F44.5BAB
10.F44.4BABA10.F$F44.5BABA9.F45.4B2AB9.F45.6B10.F45.4BA11.F45.5B11.F$
F45.5BA10.F46.5B10.F46.4B11.F46.3B12.F46.3B12.F$F46.4B11.F47.3B11.F
47.2B12.F47.B13.F47.B13.F$F47.2B12.F48.B12.F61.F61.F61.F!
One iffy idea is we could only offer specific choices of U and W that enforce the sufficiency and appropriateness of AF2=3. Maybe something like "vv_orth:K:N:M" -> V=(K, N, M), U=X, W=Y and "vv_diag:K:N:M" -> V=(K, N, M), U=X-Y, W=X+Y? Exact syntax probably TBD. With these choices of UW, the CA neighborhood current generation always fits w/in a U neighborhood of 3 and I believe the future cell should as well so long as we require max(|K|, |N|) <= |M| and thus the generational staggering is by at most 1 X and 1 Y. With this, something like "vv_orth-2:5" might be more intuitive than "c5k-1" and you'd be able to use "vv_diag-2:5" instead of "c5k-1/W=X+Y/U=X-Y".

I couldn't reproduce this. I got: