amling search program principles discussion / brain dump

[lllllllllwith10ls]

Hi, I heard that it was possible to search for "skimmers" (mobile objects on the boundary between vacuum and an agar) using Llsss, but I couldn't figure out how to do so from reading this thread or expirementing by myself.

Here's an example of a skimmer I'd like to look for.

Code: Select all

x = 92, y = 27, rule = B3/S23
59bo$57bo2bo$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o9bo4bo3b2o
3b2o$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o6bo2b2obobo2b3o3b
3o$48b3ob2obobobo3bobo2b2o3bo2bobo2b2o2b2o2b2o$b48o5bo3b2o3b2o6b3o3b2o
2b2o2b2o2bobo$o52b2o2bo3bo4bo2bo4bo16bo$b45o4b3o5bob8o3b20o$58bo11bo$b
44obobo8b7ob2ob23o$o45bo8b2o8b2o24bo$b42o5bo3b2ob2o2b3o5b24o$46bo3b2o
6bo$b44obobo2b5o3b3o3b26o$o57bo4b2o26bo$b61o2b27o2$b90o$o90bo$b90o2$b
90o$o90bo$b90o2$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o!

[confocaloid]

A related forum thread from 2020: viewtopic.php?f=2&t=4726 'Skimmers'
Here's the same skimmer shown in a bounded universe with wraparound, and surviving long enough to see what it does before two copies collide:

Code: Select all

x = 80, y = 69, rule = B3/S23:T80,80-2
55bo$53bo2bo$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o9bo4bo3b2o3b2o
$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o6bo2b2obobo2b3o3b3o$44b3ob
2obobobo3bobo2b2o3bo2bobo2b2o$45o5bo3b2o3b2o6b3o3b2o2b2o$49b2o2bo3bo4b
o2bo4bo$42o4b3o5bob8o3b13o$54bo11bo$41obobo8b7ob2ob16o$42bo8b2o8b2o$
39o5bo3b2ob2o2b3o5b17o$42bo3b2o6bo$41obobo2b5o3b3o3b19o$54bo4b2o$58o2b
20o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$80o2$
80o2$80o2$80o2$80o2$80o2$20o2b58o$19b2o4bo$19o3b3o3b5o2bobob41o$25bo6b
2o3bo$17o5b3o2b2ob2o3bo5b39o$17b2o8b2o8bo$16ob2ob7o8bobob41o$13bo11bo$
13o3b8obo5b3o4b42o$9bo4bo2bo4bo3bo2b2o$b2o2b2o3b3o6b2o3b2o3bo5b45o$b2o
2bobo2bo3b2o2bobo3bobobob2ob3o$11b3o3b3o2bobob2o2bo6b2o2b2o2b2o2b2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o$12b2o3b2o3bo4bo9b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o$23bo2bo$24bo!

Hi, I heard that it was possible to search for "skimmers" (mobile objects on the boundary between vacuum and an agar) using Llsss, but I couldn't figure out how to do so from reading this thread or expirementing by myself.

Here's an example of a skimmer I'd like to look for.

Code: Select all

x = 92, y = 27, rule = B3/S23
59bo$57bo2bo$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o9bo4bo3b2o
3b2o$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o6bo2b2obobo2b3o3b
3o$48b3ob2obobobo3bobo2b2o3bo2bobo2b2o2b2o2b2o$b48o5bo3b2o3b2o6b3o3b2o
2b2o2b2o2bobo$o52b2o2bo3bo4bo2bo4bo16bo$b45o4b3o5bob8o3b20o$58bo11bo$b
44obobo8b7ob2ob23o$o45bo8b2o8b2o24bo$b42o5bo3b2ob2o2b3o5b24o$46bo3b2o
6bo$b44obobo2b5o3b3o3b26o$o57bo4b2o26bo$b61o2b27o2$b90o$o90bo$b90o2$b
90o$o90bo$b90o2$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o!

[amling]

Hi, I heard that it was possible to search for "skimmers" (mobile objects on the boundary between vacuum and an agar) using Llsss, but I couldn't figure out how to do so from reading this thread or expirementing by myself.

Here's an example of a skimmer I'd like to look for.

Code: Select all

x = 92, y = 27, rule = B3/S23
59bo$57bo2bo$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o9bo4bo3b2o
3b2o$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o6bo2b2obobo2b3o3b
3o$48b3ob2obobobo3bobo2b2o3bo2bobo2b2o2b2o2b2o$b48o5bo3b2o3b2o6b3o3b2o
2b2o2b2o2bobo$o52b2o2bo3bo4bo2bo4bo16bo$b45o4b3o5bob8o3b20o$58bo11bo$b
44obobo8b7ob2ob23o$o45bo8b2o8b2o24bo$b42o5bo3b2ob2o2b3o5b24o$46bo3b2o
6bo$b44obobo2b5o3b3o3b26o$o57bo4b2o26bo$b61o2b27o2$b90o$o90bo$b90o2$b
90o$o90bo$b90o2$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b
2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o$b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o!

This is a much more complicated question than I can answer on a mobile phone, but I'll get the ball rolling. LLSSS can definitely find skimmers like this one although the specifics of its first divergence from the background being far away from the boundary between the two background agars might make finding this exact one rough.

When I get back to a computer I will document some searches than can find things like this but in the mean time you should think about which properties of that are relevant and which are accident. Do you want to find 4c/4 skimmers that change that exact boundary (blocks on parallel lines) into itself? Do you care if they rephase/move it? Do you care if they convert it to a different boundary or not? Do you want to find any skimmers? A grammar/collection capable of doing all possible moves/rephased of that boundary? Of a bigger set of boundaries? Depending on your exact goal there are many different search setups that might find something of interest.

If I don't hear otherwise by the time I am at back at a computer (approx Jan 1st) I will focus on finding conversions between still life boundaries and strict p1 c/1 edges under the theory that c/1 edges probably have a complex grammar and can do all moves/rephases and so it's "just" a matter of linking up to fronts and backs for that still life edge (and/or other still life edges that can separate the parallel lines agar from zeros).

[amling]

Code: Select all

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

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

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

Sort of, although I'd explain it the other way around: the question marks indicate a UVW prism of the input that is where the search happens. Question marks are not wildcards, they do not indicate values or sets of values or anything. They are an absolute hole that must be filled. It is required to have AF2-1 U columns (2 X columns in typical geometries) to the left and right of the hole to define the boundary conditions of the search. Ditto W overlap many W rows (2 Y rows typically) on the top for initial conditions.

When I am back to a computer I will update this assert to have, well, something at least a little better than the raw expression that failed.

[HartmutHolzwart]

Maybe you could give 3c/6 skimmers a try? They would nicely fit to your 3c/6 grey stretchers!

[amling]

Maybe you could give 3c/6 skimmers a try? They would nicely fit to your 3c/6 grey stretchers!

Skimmers/backs for all 3c/X stretchers (both wick stretchers and grey stretchers) at all reasonable speeds no faster than the stretcher (so e.g. 3c/7 skimmer or back can go behind a 3c/6 stretcher) is a project somewhere in my notes back home. I had put it off because I wanted to only do it once and I thought (hoped) the collection of 3c/X stretchers still had some growing to do.

[lllllllllwith10ls]

When I get back to a computer I will document some searches than can find things like this but in the mean time you should think about which properties of that are relevant and which are accident. Do you want to find 4c/4 skimmers that change that exact boundary (blocks on parallel lines) into itself? Do you care if they rephase/move it? Do you care if they convert it to a different boundary or not? Do you want to find any skimmers? A grammar/collection capable of doing all possible moves/rephased of that boundary? Of a bigger set of boundaries? Depending on your exact goal there are many different search setups that might find something of interest.

I want to be able to search for skimmers with specified ahead boundaries and behind boundaries. What I want is something like

Code: Select all

AABDD
AABDD
AABDD
AASDD
AACDD
AACDD
AACDD

where A and D repeat along both dimensions and B and D repeat along the vertical dimension, and S is the skimmer. (ABCD are all specified) Something that can also find something like

Code: Select all

AABDD
AABDD
AABDD
EESFF
GGCHH
GGCHH
GGCHH

would be nice (ABCDEFGH are all specified, and you solve for S), although not as much of a priority.

[amling]

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

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

Testing this just now `rustc` alone reached 14 GB. It's too slow for me to want to rerun and try to catch the linker process, rerun with `ulimit` just above/below that, etc. TBD whether or not I can do anything to improve that...

[amling]

I want to be able to search for skimmers with specified ahead boundaries and behind boundaries. What I want is something like

Code: Select all

AABDD
AABDD
AABDD
AASDD
AACDD
AACDD
AACDD

where A and D repeat along both dimensions and B and D repeat along the vertical dimension, and S is the skimmer. (ABCD are all specified) Something that can also find something like

Code: Select all

AABDD
AABDD
AABDD
EESFF
GGCHH
GGCHH
GGCHH

would be nice (ABCDEFGH are all specified, and you solve for S), although not as much of a priority.

LLSSS can theoretically do both of these although to do the latter is going to require either k-gram edges which will have issues not forcing their transitions, or manually choosing single edge transition positions which is very limiting.

As for the original problem of finding 4c/4 skimmers for that blocks-on-parallel-stripes edge...

Normally I would prefer to search f2b, something like...

Code: Select all

$ cat 1.in
|           |           |           | ABABuuRRR |
|           |           | ABABuuRRR | *.*...... |
|           | ABABuuRRR | *.*...... | *.*...... |
| ABABuuRRR | *.*.**... | *.*.**... | *.*.**... |
| *.*.**... | *.*.**... | *.*.**... |           |
| *.*...... | *.*...... |           |           |
| *.*...... |           |           |           |
$ rlife llsss-recentering-wao 4c4-f2b 1.in --left-edge agar:vertical-stripes --left-inertness agar:vertical-stripes --wao-idx ALL --partials ... --ends ... 17
...

...but unfortunately very quickly all WAO error windows die out except for the left-most one which can refuse to engage the prompt and produce useless stuff like:

Code: Select all

End [thinnest] "LlsssEndsSPeriodic([Vec3(0, 0, 1)])":
|                |                |                | ABABABABABuuRR |
|                |                | ABABABABABuuRR | *.*.*.*.*..... |
|                | ABABABABABuuRR | *.*.*.*.*..... | *.*.*.*.*..... |
| ABABABABABuuRR | *.*.*.*.*.**.. | *.*.*.*.*.**.. | *.*.....*.**.. |
| *.*.*.*.*.**.. | *.*.*.*.*.**.. | *.*.....*.**.. | *.*..*..*.**.. |
| *.*.*.*.*..... | *.*.....*..... | *.*..*..*..... | *.*.***.*..... |
| *.*.....*..... | *.*..*..*..... | *.*.***.*..... | *.*.*.*.*..... |
| *.*..*..*.**.. | *.*.***.*.**.. | *.*.*.*.*.**.. | *.*.*.*.*.**.. |
| *.*.***.*.**.. | *.*.*.*.*.**.. | *.*.*.*.*.**.. | *.*.*.*.*.**.. |
| *.*.*.*.*..... | *.*.*.*.*..... | *.*.*.*.*..... |                |
| *.*.*.*.*..... | *.*.*.*.*..... |                |                |
| *.*.*.*.*.**.. |                |                |                |

You could maybe still get this sort of search off the ground by taking a partial that did engage like...

Code: Select all

|              |              |              | ABABABABuuRR |
|              |              | ABABABABuuRR | *.*.*.*..... |
|              | ABABABABuuRR | *.*.*.*..... | *.*.*.*..... |
| ABABABABuuRR | *.*.*.*.**.. | *.*.*.*.**.. | *.*...*.**.. |
| *.*.*.*.**.. | *.*.*.*.**.. | *.*...*.**.. | *.*...*.**.. |
| *.*.*.*..... | *.*...*..... | *.*...*..... | *....**.*... |
| *.*...*..... | *.*...*..... | *.....**.... | *.**........ |
| *.*...*.**.. | *....**..... | *.**.***.... | *.****..*... |
| *.....*..... | *.**..*..... | *.**..**.... | *.**....*... |
| *.**.**.**.. | *.**.*..*... | *....*..*... | *....*..**.. |
| *.*...**.... | *.**.****... | *.**.**.**.. |              |
| *........... | *.......*... | *........*.. |              |
| *.*..*.**... | *......*.*.. |              |              |
|              |              |              |              |

...and stripping it back to the first row that forces engagement...

Code: Select all

|              |              |              | ABABABABuuRR |
|              |              | ABABABABuuRR | *.*.*.*..... |
|              | ABABABABuuRR | *.*.*.*..... | *.*.*.*..... |
| ABABABABuuRR | *.*.*.*.**.. | *.*.*.*.**.. | *.*...*.**.. |
| *.*.*.*.**.. | *.*.*.*.**.. | *.*...*.**.. | *.*...*.**.. |
| *.*.*.*..... | *.*...*..... | *.*...*..... | *....**.*... |
| *.*...*..... | *.*...*..... | *.....**.... |              |
| *.*...*.**.. | *....**..... |              |              |
| *.....*..... |              |              |              |

...and searching that. This sort of single-shot WAO search might also do better for other fronts. Generally you'd be using either `--ends pd_lite:K` if you're trying to reduce to lower period (ultimately wanting c/1) or `--ends s_periodic:0:0:1` if you're trying to find patterns returning to a still-life back.

For this blocks edge I instead concentrated on trying to complete the period division to a common c/1 edge. For this I included `--ends pd_lite:2` in the above search (to search for division by 2 from 4c/4 to 2c/2) and noticed:

Code: Select all

End LlsssEndsPdLite depth 4:
|                |                |                | ABABABABABuuRR |
|                |                | ABABABABABuuRR | *.*.*.*.*..... |
|                | ABABABABABuuRR | *.*.*.*.*..... | *.*.*.*.*..... |
| ABABABABABuuRR | *.*.*.*.*.**.. | *.*.*.*.*.**.. | *.*.....*.**.. |
| *.*.*.*.*.**.. | *.*.*.*.*.**.. | *.*.....*.**.. | *.*..*..*.**.. |
| *.*.*.*.*..... | *.*.....*..... | *.*..*..*..... | *.*.***.*.*... |
| *.*.....*..... | *.*..*..*..... | *.*.***.**.... | *.*........... |
| *.*..*..*.**.. | *.*.***.*..... | *.*.***.**.... | *.*........... |
| *.*.***.*..... | *.*.....*..... | *.*..**.*..... | *.*...*.**.... |
| *.*.****..**.. | *.*....*...... | *.**.......... | *.**.......... |
| *.*..*........ | *.*..*........ | *.*........... | *............. |
| *.**.......... | *.**.......... | *.**.......... | *.**.......... |
| *.*........... | *............. | *............. | *............. |
| *.**.......... | *.**.......... | *............. |                |
| *............. | *............. |                |                |
| *............. |                |                |                |

I stripped this back to the earliest 2 Y rows of 2c/2 and searched from there looking for another division in 2 (to c/1)...

Code: Select all

$ cat 2.in
|           | ABABuuRRR |
| ABABuuRRR | *.*.**... |
| *.*.*.... | *.*...... |
| *.*.**... |           |
$ rlife llsss-recentering 2c2-f2b 2.in --left-edge agar:vertical-stripes --left-inertness agar:vertical-stripes --ends pd_lite:2 20
...

This finds:

Code: Select all

End LlsssEndsPdLite depth 2:
|            | ABABABuuRR |
| ABABABuuRR | *.*.*.**.. |
| *.*.*.*... | *.*.*..... |
| *.*.*.**.. | *.....**.. |
| *......... | *..*...... |
| *..*...... | *.**...... |
| *.**...... |            |

Next, to find c/1 repositionings I chose to search s2s. This is unfortunate in some ways because then top pad (how far "inward" the pattern can deviate from agar) has to be chosen in advance but it does specify the edges more nicely than searching for this f2b would.

For example, to find a widening by one lane I used this:

Code: Select all

$ cat 3.in
| EABCDEAMMMFGHIJFG |
| ***************** |
| ................. |
| ***************** |
| ................. |
| ***************** |
| ................. |
| ***************** |
| ................. |
| ***************** |
| ................. |
| *..***.???******* |
| ..**...???....... |
| *...**.???..***.. |
| .......???.**...* |
| .......???...**.. |
| .......???....... |
| .......???....... |
| .......???....... |
$ rlife llsss-recentering 1c1-s2s 3.in --top-pad 08 --left-pad 05 --fuzzy-left-edge --right-pad 05 --fuzzy-right-edge XX
...

Which finds:

Code: Select all

End [thinnest] "LlsssEndsZero":
| ABCDEABCDEAMMMMFG |
| ***************** |
| ................. |
| *********..****** |
| ..........**..... |
| **..*****...***** |
| ...**........*... |
| **...**.......*** |
| ..............*.. |
| **......*.*...*** |
| .....**.*...*.... |
| ...**.....*..**** |
| .*.**.....*.*.... |
| .....**.*.....*.. |
| ........*.*.*...* |
| ............*.*.. |
| ................. |
| ................. |

Similarly to find a reduction by one lane:

Code: Select all

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

Finds:

Code: Select all

End [thinnest] "LlsssEndsZero":
| ABCDEAMMMMFGHIJ |
| *************** |
| ............... |
| **..***..****** |
| ...**...**..... |
| **...**...***** |
| ...........*... |
| **..........*** |
| ............*.. |
| ****.....*.*.** |
| .....*.*.*..... |
| **...*.....*.** |
| ...*...*.*..*.. |
| ...*.*...*.*.** |
| .*............. |
| ............... |
| ............... |

To find a rephasing is tricky because you have to force the phase mod 5 (so no 3x repeat of M in middle):

Code: Select all

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

Finds:

Code: Select all

End [thinnest] "LlsssEndsZero":
| ABCDEAuFGHIJF |
| ************* |
| ............. |
| **..********* |
| ...**........ |
| **...******** |
| ......*...... |
| **.....*..*** |
| ...*.*...**.. |
| **...*.*...** |
| ............. |
| ............. |

Finally to find the back conversion of the c/1 edge back into blocks I search b2f from blocks similar to how I did f2b for the front. I used different combinations of inertness (pd:4 on both sides instead of just agar on left), WAO padding, and mid_steps but the essential search setup is the same. Eventually some reduction to 2c/2 was able to reduce to c/1 and then find the common edge.

To find the common edge in the final c/1 search I used `--inertness agar:vertical-stripes` with `--partials srv2` in that search and it was output as a very thin choke:

Code: Select all

| LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL  |
| ABABABABABuuuuuuuuuuuuuuuuuuuuuuuuRRRRRRRRR |
| *.*.*.*.*.*.*....*..*.*.*..**..*.*......... |
| *.*.*.*.*...........*.***..**..**.......... |
| *.*.*.*.*.**.*..*.*.*..*........*.......... |
| *.*.*.***.......*.*.*......*............... |
| *.*.**...*..**...**.*.*.*.*....*.*.*..*.... |
| *.*.*............*..*.......*..*.*.*..*.... |
| *.**....*.*..*......*.**.**.*...**..**..... |
| *..*....*.*.....*.*.*.......*.*..*..**..... |
| *........**.*.*....**.*...*.**............. |
| *.*.*..*..*.*.*.**..*.*...*..*..*.*..*..... |
| *.*.*......**.*......**.*.*.....*.*........ |
| *.*.*.*.*..*..*.*....*..*.*.*.*.*.*.*.*.... |
| *.*.*.*.*.....*.*.......*.*.*.*.*.*.*.*.... |
| *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.. |
| *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.. |
| *..*...*...*...*...*...*...*...*...*..**... |
| *.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*..*... |

Stitching it all together:

Code: Select all

x = 66, y = 216, rule = B3/S23
2obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$2ob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$3bobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$3bobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobo$2obobobobobobo
bobobobobobobobobobobobobobobobobobobobobobobobobobo$2obobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobo$3bobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobo$3bobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobo$2obobobobobobobobobobobobobo
bobobobobobobobobobobobobobobobobobobo$2obobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobo$3bobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobo$3bobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobo$2obobobobobobobobobobobobobobobobobobobobo
bobobobobobobobobobobobo$2obobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobo$3bobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobo$3bobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobo$2obobobobobobobobobobobobobobobobobobobobobobobobobobobo
bobobobobo$2obobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobo$3bobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obo$3bo5bobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$2ob
o2bo2bobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$3bob3o
bobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$2o2b4obobob
obobobobobobobobobobobobobobobobobobobobobobobobobobo$6bo2bobobobobobo
bobobobobobobobobobobobobobobobobobobobobobobo$8b2obobobobobobobobobob
obobobobobobobobobobobobobobobobobobo$9bobobobobobobobobobobobobobobob
obobobobobobobobobobobobobo$8b2obobobobobobobobobobobobobobobobobobobo
bobobobobobobobobo$15bobobobobobobobobobobobobobobobobobobobobobobobob
obo$12bo2bobobobobobobobobobobobobobobobobobobobobobobobobobo$12b2obob
obobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobo
bobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobobob
obobobobobobobobobobobobobo$15bobobobobobobobobobobobobobobobobobobobo
bobobobobobo$12bo2bobobobobobobobobobobobobobobobobobobobobobobobobobo
$12b2obobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobob
obobobobobobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobobo
bobobobobobobobobobobobobobobobobobo$15bobobobobobobobobobobobobobobob
obobobobobobobobobobo$12bo2bobobobobobobobobobobobobobobobobobobobobob
obobobobo$12b2obobobobobobobobobobobobobobobobobobobobobobobobobobo$
11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobob
obobobobobobobobobobobobobobobobobobobobobobobo$15bobobobobobobobobobo
bobobobobobobobobobobobobobobobo$12bo2bobobobobobobobobobobobobobobobo
bobobobobobobobobobo$12b2obobobobobobobobobobobobobobobobobobobobobobo
bobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$
11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$15bobobobob
obobobobobobobobobobobobobobobobobobobobobo$12bo2bobobobobobobobobobob
obobobobobobobobobobobobobobobo$12b2obobobobobobobobobobobobobobobobob
obobobobobobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobo
bobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$
15bobobobobobobobobobobobobobobobobobobobobobobobobobo$12bo2bobobobobo
bobobobobobobobobobobobobobobobobobobobobo$21bobobobobobobobobobobobob
obobobobobobobobobobo$12b2o4bo2bobobobobobobobobobobobobobobobobobobob
obobobo$12b2o4b2obobobobobobobobobobobobobobobobobobobobobobobo$11bo2b
o2bobobobobobobobobobobobobobobobobobobobobobobobobo$11bo2bo2bobobobob
obobobobobobobobobobobobobobobobobobobobo$19bobobobobobobobobobobobobo
bobobobobobobobobobobo$10b2o2b2o3bobobobobobobobobobobobobobobobobobob
obobobobobo$23bobobobobobobobobobobobobobobobobobobobobobo$10bob2obo4b
o2bobobobobobobobobobobobobobobobobobobobobobo$20b2obobobobobobobobobo
bobobobobobobobobobobobobo$9b2obobo4bobobobobobobobobobobobobobobobobo
bobobobobobobo$13bo4b2obobobobobobobobobobobobobobobobobobobobobobobo$
9bobobob3obobobobobobobobobobobobobobobobobobobobobobobobo$13bobobobob
obobobobobobobobobobobobobobobobobobobobobobo$10bo2bobobobobobobobobob
obobobobobobobobobobobobobobobobobo$10b2obobobobobobobobobobobobobobob
obobobobobobobobobobobobo$9bobobobobobobobobobobobobobobobobobobobobob
obobobobobobobo$9bobobobobobobobobobobobobobobobobobobobobobobobobobob
obobo$13bobobobobobobobobobobobobobobobobobobobobobobobobobobo$10bo2bo
bobobobobobobobobobobobobobobobobobobobobobobobobobo$10b2obobobobobobo
bobobobobobobobobobobobobobobobobobobobobo$9bobobobobobobobobobobobobo
bobobobobobobobobobobobobobobobo$9bobobobobobobobobobobobobobobobobobo
bobobobobobobobobobobo$13bobobobobobobobobobobobobobobobobobobobobobob
obobobobo$10bo2bobobobobobobobobobobobobobobobobobobobobobobobobobobo$
10b2obobobobobobobobobobobobobobobobobobobobobobobobobobobo$9bobobobob
obobobobobobobobobobobobobobobobobobobobobobobobo$9bobobobobobobobobob
obobobobobobobobobobobobobobobobobobobo$13bobobobobobobobobobobobobobo
bobobobobobobobobobobobobo$10bo2bobobobobobobobobobobobobobobobobobobo
bobobobobobobobo$10b2obobobobobobobobobobobobobobobobobobobobobobobobo
bobobo$9bobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$9bo
bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$13bobobobobob
obobobobobobobobobobobobobobobobobobobobobo$10bo2bobobobobobobobobobob
obobobobobobobobobobobobobobobobo$10b2obobobobobobobobobobobobobobobob
obobobobobobobobobobobo$9bobobobobobobobobobobobobobobobobobobobobobob
obobobobobobo$9bobobobobobobobobobobobobobobobobobobobobobobobobobobob
obo$13bobobobobobobobobobobobobobobobobobobobobobobobobobobo$10bo2bobo
bobobobobobobobobobobobobobobobobobobobobobobobobo$15bo7bobobobobobobo
bobobobobobobobobobobobobobobo$11b2o2bo4bo2bobobobobobobobobobobobobob
obobobobobobobobo$20b2obobobobobobobobobobobobobobobobobobobobobobo$
11bob2o4bobobobobobobobobobobobobobobobobobobobobobobobo$19bobobobobob
obobobobobobobobobobobobobobobobobobo$12bobo8bobobobobobobobobobobobob
obobobobobobobobobo$20bo2bobobobobobobobobobobobobobobobobobobobobobo$
11b2ob2o4b2obobobobobobobobobobobobobobobobobobobobobobo$19bobobobobob
obobobobobobobobobobobobobobobobobobo$11bobobo2b2obobobobobobobobobobo
bobobobobobobobobobobobobo$12bo3b2obobobobobobobobobobobobobobobobobob
obobobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobo
bo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$15bobobo
bobobobobobobobobobobobobobobobobobobobobobobo$12bo2bobobobobobobobobo
bobobobobobobobobobobobobobobobobo$12b2obobobobobobobobobobobobobobobo
bobobobobobobobobobobo$11bobobobobobobobobobobobobobobobobobobobobobob
obobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo
$15bobobobobobobobobobobobobobobobobobobobobobobobobobo$12bo2bobobobob
obobobobobobobobobobobobobobobobobobobobobo$12b2obobobobobobobobobobob
obobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobobobobobobo
bobobobobobobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobob
obobobobo$15bobobobobobobobobobobobobobobobobobobobobobobobobobo$12bo
2bobobobobobobobobobobobobobobobobobobobobobobobobobo$12b2obobobobobob
obobobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobo
bobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobobobobobobob
obobobobobobobobobo$15bobobobobobobobobobobobobobobobobobobobobobobobo
bobo$12bo2bobobobobobobobobobobobobobobobobobobobobobobobobobo$12b2obo
bobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobobobobobob
obobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobobo
bobobobobobobobobobobobobobo$15bobobobobobobobobobobobobobobobobobobob
obobobobobobo$12bo2bobobobobobobobobobobobobobobobobobobobobobobobobob
o$12b2obobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobo
bobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobob
obobobobobobobobobobobobobobobobobobo$19bobobobobobobobobobobobobobobo
bobobobobobobobobo$12bo3bo2bobobobobobobobobobobobobobobobobobobobobob
obobo$16b2obobobobobobobobobobobobobobobobobobobobobobobobo$11b2o2bobo
bobobobobobobobobobobobobobobobobobobobobobobobo$14b2obobobobobobobobo
bobobobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobobobobob
obobobobobobobobobobobo$15bobobobobobobobobobobobobobobobobobobobobobo
bobobobo$12bo2bobobobobobobobobobobobobobobobobobobobobobobobobobo$12b
2obobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobobobob
obobobobobobobobobobobobobobobobobobobobobo$11bobobobobobobobobobobobo
bobobobobobobobobobobobobobobobo$15bobobobobobobobobobobobobobobobobob
obobobobobobobobo$12bo2bobobobobobobobobobobobobobobobobobobobobobobob
obobo$12b2obobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobo
bobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobobobobobob
obobobobobobobobobobobobobobobobobobobobo$15bobobobobobobobobobobobobo
bobobobobobobobobobobobobo$12bo2bobobobobobobobobobobobobobobobobobobo
bobobobobobobo$12b2obobobobobobobobobobobobobobobobobobobobobobobobobo
bo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$11bobobo
bobobobobobobobobobobobobobobobobobobobobobobobobo$15bobobobobobobobob
obobobobobobobobobobobobobobobobobo$12bo2bobobobobobobobobobobobobobob
obobobobobobobobobobobo$12b2obobobobobobobobobobobobobobobobobobobobob
obobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo
$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$15bobobobo
bobobobobobobobobobobobobobobobobobobobobobo$12bo2bobobobobobobobobobo
bobobobobobobobobobobobobobobobo$12b2obobobobobobobobobobobobobobobobo
bobobobobobobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobob
obobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobobobobobo$
15bobobobobobobobobobobobobobobobobobobobobobobobobobo$12bo2bobobobobo
bobobobobobobobobobobobobobobobobobobobobo$12b2obobobobobobobobobobobo
bobobobobobobobobobobobobobobo$11bobobobobobobobobobobobobobobobobobob
obobobobobobobobobo$11bobobobobobobobobobobobobobobobobobobobobobobobo
bobobobo$13bobobobobobobobo7bobo5bobobobobobobobobobobobo$13bobobobobo
bobobo2bo4bobo2bo2bobobobobobobobobobobobo$17bobo5bobob2o6bob2o6bobobo
bobobobobobobo$14bo2bobo2bo2bo3bobo2b2obobobo2bo2bobobobobobobobobobo$
22b2obo3bob2o4bobob2o8bobobobobobobobo$14b2o2bo2bobo7bobobo5bobo4bo2bo
bobobobobobobo$14b2o2b2o3bob2ob2obo6bo2bobo4b2obobobobobobobobo$13bo2b
obobo2bo7bo2bo12bobobobobobobobobobo$13bo2bobobo4bobobobob2o3b2o2bo3b
2obobobobobobobobobo$24bo6bobobo7b3obobobobobobobobobobo$19bo8bo2bobob
o2bob2obobobobobobobobobobobobo$19b2o2b2o2b3obo11bobobobobobobobobobob
obo$18bobo2b2o2bobobo2bo4bobobobobobobobobobobobobobo$18bobobo3b2obobo
b2o5bo2bobobobobobobobobobobobo$22bob3o6bobo3bobobobobobobobobobobobob
obo$22bob2o2bo4bobo3bobobobobobobobobobobobobobo$27b3o13bobobobobobobo
bobobobobo$24b2o6b2ob2o3bo2bobobobobobobobobobobobo$40b2obobobobobobob
obobobobobo$28b2o2bobobo2bobobobobobobobobobobobobobo$28b2o5bo2b2obobo
bobobobobobobobobobobo$29bo3bobobobobobobobobobobobobobobobobo$29b4o2b
obobobobobobobobobobobobobobobo$31bobobobobobobobobobobobobobobobobobo
$31bobobobobobobobobobobobobobobobobobo$29bobobobobobobobobobobobobobo
bobobobobo$29bobobobobobobobobobobobobobobobobobobo$30b2obobobobobobob
obobobobobobobobobobo$33bobobobobobobobobobobobobobobobobo$33bobobobob
obobobobobobobobobobobobo$30b2obobobobobobobobobobobobobobobobobo$30b
2obobobobobobobobobobobobobobobobobo$33bobobobobobobobobobobobobobobob
obo$33bobobobobobobobobobobobobobobobobo$30b2obobobobobobobobobobobobo
bobobobobo$30b2obobobobobobobobobobobobobobobobobo$33bobobobobobobobob
obobobobobobobobo$33bobobobobobobobobobobobobobobobobo$30b2obobobobobo
bobobobobobobobobobobobo$30b2obobobobobobobobobobobobobobobobobo$33bob
obobobobobobobobobobobobobobobo$33bobobobobobobobobobobobobobobobobo$
30b2obobobobobobobobobobobobobobobobobo$30b2obobobobobobobobobobobobob
obobobobo$33bobobobobobobobobobobobobobobobobo$33bobobobobobobobobobob
obobobobobobo$30b2obobobobobobobobobobobobobobobobobo$30b2obobobobobob
obobobobobobobobobobobo!

This hopefully shows some of the ways you can search for parts. Nothing I did above is some sort of One True Way (TM) to do it. There are a lot of ways you can specify boundary conditions (the top/start, the left and right edges, and the bottom/ends) and depending on what unhelpful patterns exist you may have to work around them.

[amling]

I've begun writing a tutorial for basic LLSSS spaceship searches, which can be found here.

I read over the tutorial as it exists now and it generally makes sense. The only things that caught my eye as some degree of suboptimal were:

(*) The LLSSS_INIT_CA_CHECKS explanation isn't quite right: what it specifically does is filter the state it constructs after expanding wildcards by checking the CA rule and then of course if the state is empty the program goes nowhere. If you have no wildcards this sort of simplifies to checking that you met CA constraints but that's not really what it's there for.

(*) I have mixed feelings about the symmetric ends being broken with agars. Using WAO to avoid the initial extraneous result only papers over the one problem. It could still miss a valid result (which was all zeros) or print extraneous results later in the search. Maybe I should just forget trying to prune extraneous results and if you have partials with all-agar bottoms they're just going to get duplicated in output?

[Sokwe]

(*) The LLSSS_INIT_CA_CHECKS explanation isn't quite right: what it specifically does is filter the state it constructs after expanding wildcards by checking the CA rule and then of course if the state is empty the program goes nowhere. If you have no wildcards this sort of simplifies to checking that you met CA constraints but that's not really what it's there for.

I suppose I don't fully understand this, so I'm not sure I could write a description that's both technically accurate and practical for beginners. I only ever needed to set that environment variable when running a search from a partial result that's too large, and I'm not sure whether ever experienced the benefits of the init CA checks.

Using WAO to avoid the initial extraneous result only papers over the one problem.

From a practical standpoint, using WAO seems to at least solve the problem of extraneous results in searches with no actual spaceships. If I run the same example search form the tutorial with llsss-recentering and mid_steps 8 instead of 9, I get 84 occurrences of "[INFO] End" in the output. However, it seems you would have to visually inspect them to conclude that none of them represent actual spaceships. This makes the classic technique of increasing the width 1 at a time until you find something much more difficult for the user.

It could still miss a valid result (which was all zeros) or print extraneous results later in the search.

What sort of valid results might be missed in a WAO search?

Maybe I should just forget trying to prune extraneous results and if you have partials with all-agar bottoms they're just going to get duplicated in output?

I don't think you need to bother pruning invalid results from the llsss and llsss-recentering agar searches, if that's what you're talking about, as long as WAO is allowing a similar search to be carried out. I view WAO as a satisfying workaround to the "problem" of extraneous end detection in this case.

By the way, you might consider creating a wiki account so if you see something easy to correct you can do it without needing to comment here.

[amling]

By the way, you might consider creating a wiki account so if you see something easy to correct you can do it without needing to comment here.

I'm not opposed in theory, but everything so far has been somewhat more involved than minor edits. I'll look into it when I find a typo or something.

I've just noticed while writing the rest of this post that I think the recentering B0 examples are missing configuring B0 inertness which is therefore probable not really taking advantage of recentering. Maybe don't worry too much about it since I think some of this may be about to change...

(*) The LLSSS_INIT_CA_CHECKS explanation isn't quite right: what it specifically does is filter the state it constructs after expanding wildcards by checking the CA rule and then of course if the state is empty the program goes nowhere. If you have no wildcards this sort of simplifies to checking that you met CA constraints but that's not really what it's there for.

I suppose I don't fully understand this, so I'm not sure I could write a description that's both technically accurate and practical for beginners. I only ever needed to set that environment variable when running a search from a partial result that's too large, and I'm not sure whether ever experienced the benefits of the init CA checks.

The tutorial could be changed to just suggest trimming the files shorter instead. That or maybe I can make CA checks work for long initializations. I see how I could do it, it's just a bunch of annoying code for very little benefit.

Using WAO to avoid the initial extraneous result only papers over the one problem.

From a practical standpoint, using WAO seems to at least solve the problem of extraneous results in searches with no actual spaceships. If I run the same example search form the tutorial with llsss-recentering and mid_steps 8 instead of 9, I get 84 occurrences of "[INFO] End" in the output. However, it seems you would have to visually inspect them to conclude that none of them represent actual spaceships. This makes the classic technique of increasing the width 1 at a time until you find something much more difficult for the user.

It could still miss a valid result (which was all zeros) or print extraneous results later in the search.

What sort of valid results might be missed in a WAO search?

Maybe I should just forget trying to prune extraneous results and if you have partials with all-agar bottoms they're just going to get duplicated in output?

I don't think you need to bother pruning invalid results from the llsss and llsss-recentering agar searches, if that's what you're talking about, as long as WAO is allowing a similar search to be carried out. I view WAO as a satisfying workaround to the "problem" of extraneous end detection in this case.

I agree WAO solves the extraneous results problem, but only on the top side. It is true that this is the side we care about most since it happens first (starting at the beginning of the search) rather than only after it's already found a complete pattern (and then starts to spew useless, all-agar extensions of it on every row, forever, as e.g. the first "do-what-I-say" version of the zero ends did way back when).

The sort of result that would be missed by the all-zero avoidance is complicated and strange: it would have to be all zeros in the bottom, which would have to match the agar in the edges (so the agar has to be able to have those zero corners) but then mismatch the agar in the middle. It's entirely possible that no such search can be constructed among the rules LLSSS is capable of searching, or at least that anyone is likely to search, but it's not correct by construction and that grates on me.

Locally I've sketched a "--bg-agar". This sort of global notion does not persist any lower than the argument translation in "cli.rs" but it's still I think gonna be pretty handy. Almost all "zero" things (and most defaults) have been replaced with "bg" (which itself defaults to the "zero" agar). I've left the "zero" magic grids in as a form of convenience and/or backward compatibility (when BG agar is left as default of "zero" they could also be made with just "bg"). I've added a "bcaf" filter to do acaf but with the BG agar.

For most people this means nothing as I doubt anyone other than me has ever explicitly specified a now-deleted "zero" component (that would now have to be "bg"). For those running agar searches, e.g. B0, "--bg-agar b0" should be able to fill it in in most places (still need "@bg[:NNN]" init grid and still need "--filters bcaf").

Unfortunately this isn't going to be published for some time for complicated personal reasons (I'm on the road with access only to less-trustworthy computers). Look for this and anything else I do to be published towards the end of January.

[amling]

It could still miss a valid result (which was all zeros) or print extraneous results later in the search.

What sort of valid results might be missed in a WAO search?

An obviously artificial example of a would-be missed zero end:

Code: Select all

$ cat 1.in
| ..**.. |
| ..**.. |
$ cat 1.agar
{
    "vu": [4, 0, 0],
    "vv": [0, 0, 1],
    "vw": [2, 2, 0],
    "cells": [
        [[0, 0, 0], true],
        [[0, 1, 0], true],
        [[1, 0, 0], true],
        [[1, 1, 0], true],
        [[2, 0, 0], false],
        [[2, 1, 0], false],
        [[3, 0, 0], false],
        [[3, 1, 0], false],
    ],
}
$ rlife llsss p1 --rule 'S3a4q/B' 1.in --bg-agar '@1.agar' --ends even
...

Comparable search as of master branch I believe will miss this, but with the new (unpublished) code now does find/include it:

Code: Select all

End ("LlsssEndsReflect(Even)"):
| ..**.. |
| ..**.. |
| **..** |
| **..** |
| ...... |
| ...... |

The key point is the last 2 rows are all zero (so would be excluded) but do diverge from the agar.

[Sokwe]

The LLSSS_INIT_CA_CHECKS explanation isn't quite right: what it specifically does is filter the state it constructs after expanding wildcards by checking the CA rule and then of course if the state is empty the program goes nowhere. If you have no wildcards this sort of simplifies to checking that you met CA constraints but that's not really what it's there for.

I changed the LLSSS_INIT_CA_CHECKS description to read

If set to true, LLSSS will filter the initial search state based on the cellular automaton rule give by the --rule option. This limits the size of the start_file, so if you have a very large file that you know is valid, you can set the value of this variable to false. This variable should be set to true when using wildcards, which are not covered by this tutorial.

My goal is to have a description that's technically correct while still being useful to a beginner. Since I don't intend to cover wildcards in this beginner tutorial, I think it should be enough to tell the user to set this variable to "true" when using them. Let me know if there's still a problem with this description.

I have mixed feelings about the symmetric ends being broken with agars.

I changed that section to now only say that llsss and llsss-recentering give extraneous results at the beginning of the search, rather than saying they "do not work properly". Let me know if this doesn't satisfy your concerns.

I frequently set ulimit 8 GB for provisional searches and I recall compilation crashing when I had run one under that limit. My best guess was something like 10 GB and I can check when I get back to a computer.

Testing this just now `rustc` alone reached 14 GB.

Thanks. I updated the prerequisites section with a little more detail on this and added an explanation of how to increase the swap space in Windows subsystem for Linux that I worked out while helping someone on Discord.

The sort of result that would be missed by the all-zero avoidance is complicated and strange: it would have to be all zeros in the bottom, which would have to match the agar in the edges (so the agar has to be able to have those zero corners) but then mismatch the agar in the middle. It's entirely possible that no such search can be constructed among the rules LLSSS is capable of searching, or at least that anyone is likely to search, but it's not correct by construction and that grates on me.

Is it currently possible for such a missed valid result to occur in a B0 spaceship search? I would think that the blinking nature of the background would mean that no such all-zeros row was possible. I imagine it would be possible in wave searches, but the tutorial doesn't mention those. If this doesn't occur in B0 spaceship searches, then I don't intend to clarify that in this beginner tutorial, because I'm not trying to explain how to do a generic agar-background search, only a simple B0 spaceship search.

I still need example searches for the seam ripper and partial result extension sections. For the partial result extension section, I at least want one example that is 2c4-s2s, and probably also one that is front-to-back of some other speed. If anyone can think of some potentially good example searches, please let me know.

I also added a very brief section about arbitrary-width searches.

[amling]

The LLSSS_INIT_CA_CHECKS explanation isn't quite right: what it specifically does is filter the state it constructs after expanding wildcards by checking the CA rule and then of course if the state is empty the program goes nowhere. If you have no wildcards this sort of simplifies to checking that you met CA constraints but that's not really what it's there for.

I changed the LLSSS_INIT_CA_CHECKS description to read

If set to true, LLSSS will filter the initial search state based on the cellular automaton rule give by the --rule option. This limits the size of the start_file, so if you have a very large file that you know is valid, you can set the value of this variable to false. This variable should be set to true when using wildcards, which are not covered by this tutorial.

My goal is to have a description that's technically correct while still being useful to a beginner. Since I don't intend to cover wildcards in this beginner tutorial, I think it should be enough to tell the user to set this variable to "true" when using them. Let me know if there's still a problem with this description.

I like that a lot better from an accuracy perspective and it seems to convey well the same bottom line for simple use: long file -> set to false.

The sort of result that would be missed by the all-zero avoidance is complicated and strange: it would have to be all zeros in the bottom, which would have to match the agar in the edges (so the agar has to be able to have those zero corners) but then mismatch the agar in the middle. It's entirely possible that no such search can be constructed among the rules LLSSS is capable of searching, or at least that anyone is likely to search, but it's not correct by construction and that grates on me.

Is it currently possible for such a missed valid result to occur in a B0 spaceship search? I would think that the blinking nature of the background would mean that no such all-zeros row was possible. I imagine it would be possible in wave searches, but the tutorial doesn't mention those. If this doesn't occur in B0 spaceship searches, then I don't intend to clarify that in this beginner tutorial, because I'm not trying to explain how to do a generic agar-background search, only a simple B0 spaceship search.

Not possible in B0 in normal geometries. The background agar would have to have some spot where it has a 2x2 block of all zeros aligned in every generation to match zero/agar at the bottom corners (technically the corner shape it needs for interesting geometries is much harder to describe, but the net result is the same). Not even clear it's going to be possible for moving searches at all with any agar. Maybe some sort of greyship-like negative signal where there's some way for the agar to easily decay at the front corner and rebuild at the back corner? I'm probably not going to spend any time trying to produce a moving counter-example when the fixed code is already written.

I also added a very brief section about arbitrary-width searches.

Nice! It looks good to me. That might be a good second place to encourage users to check in on this thread, especially if they have a rule+velocity they think doesn't exist but they can't figure out how to prove it. Perhaps I am biased by the temptation of more interesting cases to crack.

[amling]

I have mixed feelings about the symmetric ends being broken with agars.

I changed that section to now only say that llsss and llsss-recentering give extraneous results at the beginning of the search, rather than saying they "do not work properly". Let me know if this doesn't satisfy your concerns.

Reading this again I realize I may have miscommunicated here. I have no mixed feelings about the wiki page documenting correctly that the code was busto. What was suboptimal and what I have bad feelings about was the code being wrong in the first place and it being left like that, whether or not WAO was mostly papering over it in typical use. I wasn't so much meaning to ask for an edit to the tutorial, but more trying to start musing/brainstorming about what to do about the whole situation.

[confocaloid]

[...] which properties of that are relevant and which are accident. Do you want to find 4c/4 skimmers that change that exact boundary (blocks on parallel lines) into itself? Do you care if they rephase/move it? Do you care if they convert it to a different boundary or not? Do you want to find any skimmers? A grammar/collection capable of doing all possible moves/rephased of that boundary? Of a bigger set of boundaries? Depending on your exact goal there are many different search setups that might find something of interest. [...]

[...] That might be a good second place to encourage users to check in on this thread, especially if they have a rule+velocity they think doesn't exist but they can't figure out how to prove it. Perhaps I am biased by the temptation of more interesting cases to crack.

In Day & Night, is there an universal set of skimmers/trimmers traveling on the stable oblique boundary, to allow arbitrary moves of the boundary?

There are known small boundary-preserving "ripples" (described in the quote below; I only formatted it to use viewers instead of plaintext patterns).

An universal set of boundary-changing trimmers is one interesting problem (although there may be few immediate applications of those, unless something can move with the same or higher speed and create the boundary that could then be incrementally modified).

Code: Select all

x = 128, y = 64, rule = B3678/S34678:T128,64
7o86b35o$9o86b33o$11o86b31o$13o86b29o$15o86b27o$17o86b25o$19o86b23o$
21o86b21o$23o86b19o$25o86b17o$27o86b15o$29o86b13o$31o86b11o$33o86b9o$
35o86b7o$37o86b5o$39o86b3o$41o86bo$b42o$3b42o$5b42o$7b42o$9b42o$11b42o
$13b43o$15b42o$17b42o$19b42o$21b42o$23b42o$25b42o$27b42o$29b42o$31b42o
$33b42o$35b42o$37b42o$40b41o$41b42o$43b42o$45b42o$47b42o$49b42o$51b42o
$53b42o$55b42o$57b42o$59b42o$61b42o$63b42o$65b42o$67b42o$69b42o$71b42o
$73b42o$75b42o$77b42o$79b42o$81b42o$83b42o$85b42o$o86b41o$3o86b39o$5o
86b37o!

[...]

Dean Hickerson found that a staggered boundary with a slope of 1/2 can be perturbed by sparks to generate ripples along the boundary, which then returns to its original state. The staggered boundary is symmetrical with respect to Day and Night, and so the ripples can be created from either side of the boundary, and can travel in either direction. It is even possible for ripples to be traveling in both directions at the same time and to pass though each other. The ripples move with a period of 3 at 2/3 the speed of light.

The following figure shows multiple ripples being generated by a period 13 oscillator, and traveling to the upper right along the boundary. The ends of the object are designed to absorb the ripples without damage.

Code: Select all

#C [Figure 45.  Ripples along the boundary between Day and Night]
x = 31, y = 17, rule = B3678/S34678
23b2ob2ob2o$23b2ob2ob2o$24bo2bo$24b2obo$bo20b2ob2ob2o$obo17b4o4b2o$b3o
14b7ob2o$2bobo11b9ob2o$3b3o8b9o$4bobo5b9o$5bo4b9o$8b9o$6b9o$4b9o$2b9o$
2b7o$4bobo!

It turns out that an external oscillator is not required for creating repeated ripples along the staggered boundary. The ripples can be reflected by 180 degrees at each end of an object to create an oscillator which can have any period of the form 28+6N. The following figure shows a period 70 oscillator of this type. Unfortunately, the oscillator cannot support more than one ripple on the boundary.

Code: Select all

#C [Figure 46.  A period 70 ripple oscillator (DH)]
x = 37, y = 29, rule = B3678/S34678
29b2ob2o$29b2ob2o$27b2o2bo$27b2o2bo$26b7obo$26b2obo3b4o$32b5o$32bobo$
30b2o$28b3o$26b6o$24b8o$8b2o12b7obo$6b4o10b7o5bo$2o2b5o9b9o4b4o$9o7b
10o5b4o$6bo7b8o2b2o7bo$2b2o8b8o13bo$2b2o7b7o12b2ob2o$5o3b8o14b2ob2o$4o
2b8o$2bob8o$4b6o$3b3obo$2bo$4ob2o$4ob2o$b2o$b2o!

A slight modification of the ripple oscillator creates a double ripple injector, which produces a pair of ripples 8 generations apart every 28+6N generations. The following period 34 oscillator demonstrates this modification.

Code: Select all

#C [Figure 47.  A period 34 ripple duplicating oscillator (DH)
x = 37, y = 29, rule = B3678/S34678
29b2ob2o$29b2ob2o$27b2o2bo$27b2o2bo$26b7obo$26b2obo3b4o$20b2o10b5o$18b
4o10bobo$16b5o9b2o$16b5o7b3o$18bo6b7o$24b8o$22b7obo$20b7o5bo$18b9o4b4o
$16b10o5b4o$14b8o2b2o7bo$2b2o8b8o13bo$2b2o6b8o12b2ob2o$5o3b8o14b2ob2o$
4o2b8o$2bob8o$4b6o$3b3obo$2bo$4ob2o$4ob2o$b2o$b2o!

The ripples on the staggered boundary can affect objects adjacent to the boundary. Because of this, a signal can be sent across the boundary so that a normal area can affect an inverted area, and vice versa. The following construction shows how a rocket traveling in inverted space is destroyed by a period 8 oscillator, and in so doing causes a ripple on the boundary between Day and Night which in turn destroys a passing rocket traveling in normal space.

Code: Select all

#C [Figure 48.  A rocket from inverse space destroying a rocket in
#C normal space (DH)]
x = 78, y = 79, rule = B3678/S34678
53b2o$53b2o$54bob2o$53b2ob4o$3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b
o10b2o2b3o$b44o3b2ob2o3b2o$b44o3b4ob3o$46o8b2o$b45o4b2ob4o$b26o2bo2b
15o3b2ob4o$25o4bo4b13o7b4o$b24o3bobo3b14o6b4o$b26o2bo2b16o2bo4b4o$53o
2b4o$b59o$60o$b60o$28o4b29o$b24o2b2o4b29o$b23obo9b27o$11ob4o2bo2b4o9bo
b27o$b5ob3obo11b2o10bob26o$b6o5b2o23b27o$6ob3obo11b2o10bob27o$b10ob4o
2bo2b4o9bob27o$b23obo9b28o$25o2b2o4b31o$b27o4b31o$b62o$64o$b62o$b62o$
64o$b62o$b62o$3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b
o2bo4$71b3o$70bobobo$69bob3obo$69b7o$69b7o$68b9o$68bob5obo$69bob3obo$
71b3o$70bobobo$71b3o$70b5o$70b5o$69b7o$69b7o$69b7o$67b2ob5ob2o$69bo2bo
2bo$72bo$71b3o$71b3o$70b5o$70b5o$71b3o$72bo$69bob3obo$70b5o$70bo3bo$
71b3o$71b3o$70bobobo$70bobobo$71bobo2$69bo2bo2bo$68bob5obo$67b11o$69b
7o$71b3o$70b2ob2o!

[...]

[amling]

I still need example searches for the seam ripper and partial result extension sections. For the partial result extension section, I at least want one example that is 2c4-s2s, and probably also one that is front-to-back of some other speed. If anyone can think of some potentially good example searches, please let me know.

It's sort of hard to think of examples because where do people even get simple cross-section partials from? I mostly get them from much more intricate and difficult to explain engagement searches.

One candidate is finding 232P7H3V0 from the previously-known front in 3c7-f2b. It was first found with LGOL, but as I recall reproducing it was one of my demos for LLSSS recentering when I was writing it and it was possible even with very early versions of recentering.

For 2c4-s2s there are the two essential different quartermax setups but they all require complex configuration pictures at best.

You could just sketch from scratch a very demanding side spark like this...

Code: Select all

|  LLLuuuuuuuRRR |  LLLuuuuuuuRRR | LLLuuuuuuuRRR  | LLLuuuuuuuRRR  |
|  ............. |  ............. | .............  | .............  |
|  ............. |  ............. | .............  | ......*......  |
|  ............. |  ............. | .....***.....  | .............  |
|  ............. |  ...*****..... | ...*******...  | .............  |

...and you will get interesting-looking chokes and splits (ditto the domino version).

[amling]

I had been sketching a change to try to reduce memory in LLSSS by ceasing to keep the largest part of its data model around but in the end I'm not sure I can make it happen. Does anyone know how LSSS actually does things? I would be very curious to know. As for the details...

I'm going to simplify the discussion as if U=X, W=Y, AF2=3. I assume any answer for this case will generalize.

In LLSSS we have these "boundary columns", herein "bcols", which store all the cells, in all generations, for two columns as far down as we've built partials so far. These are stored in some predictable order. Most code does not care what the order is but we are sort of attached to it being fixed once constructed (as in we can't be reordering these things on the fly, at least not without a great deal of work). We also store the compatabilities between these, more or less as a giant list of pairs of indices. These were originally called "cols" although I've taking to trying to call them "join cols" or "jcols".

In practice jcol memory is much bigger than bcol memory (or so I thought, at least for big searches) and I think it represents the biggest difference in memory usage between LLSSS and LSSS as my understanding is LSSS keeps something analogous to bcols and that's it.

Now to a first approximation all algorithm code in LLSSS is loops over jcols, propagating data somehow across the join. When you have the jcol fully reified as a list of pairs of indices this is easy, but if you stop having it you have to somehow decide which entries in the left side bcol are compatible with which entries in the right side bcol, ideally in a way that is faster than two nested for loops.

The sketch I completed makes way in the type system for alternative jcol implementations to store no data (or less data) and generate/iterate over the valid index pairs on the fly. This, well, works, although the current implementation takes a bunch of memory building indices on the two bcol in order to be able to do the join. In particular for each side we build an array of indices into it such that each index appears exactly once and they are sorted by the values of the middle column of cells. We can then perform an interleaved iteration of the two indices to generate all index pairs that agree on the center column and then do some ugly business to perform CA checks (this, while ugly, is not the part I'm tearing my hair out over memory usage for).

Unfortunately in testing some small to medium searches here I've realized that these two extra indices are actually a fair amount of memory, especially when they have to be present during the entire program (so no matter where the memory peak is otherwise they are included in it). When I return home to my real computers and all my search project notes I will see how this all stacks up for some other searches, but I'm not optimistic.

Also unfortunately I can think of no way to meaningfully accelerate this join w/o a datastructure of at least this sort of size and without acceleration the nested for loop over the two sides is absolutely untenable.

So here it is finally: does anyone understand enough of what I have written above and know enough about LSSS to tell me how LSSS does these joins? Like if all it has is two bags of two columns worth of cell values how could it?

I've just reread the LSSS readme and I am more convinced than ever before that I am understanding correctly, but it seems to hide the answer I'm looking for in "The nodes [in a tree that corresponds to a bcol] are annotated with lookahead information that can be used to exclude whole branches of trees for adjacent slice positions from being joined to each other.".

[amling]

I've just reread the LSSS readme and I am more convinced than ever before that I am understanding correctly, but it seems to hide the answer I'm looking for in "The nodes [in a tree that corresponds to a bcol] are annotated with lookahead information that can be used to exclude whole branches of trees for adjacent slice positions from being joined to each other.".

As I turned those words over in my mind and tried to imagine what they could mean (what sort of annotations could it be? do the trees know about their neighbors somehow? etc.), I realized LLSSS's own bcol order sort of makes them tree-like in that the order they are kept in sorts by shallower bits first. Then I thought maybe I could get away with doing a joint recursive walk through these implicit trees (where each tree "node" is a range in the bcol that shares some prefix of values). Each node has four children (choice of one more bit in each of two columns), but of course only half of those sixteen products match on the center bit and some might be eliminated by CA checks. By doing these middle column cell comparisons and CA checks as early (shallow) as possible we might be able to eliminate large ranges of the product quickly enough. This also has a very pleasing tunable acceleration option of precomputing the expansion of this recursion but to limited depth (however much expansion you decide you can afford to keep the entire level of pairs of nodes). Pre-expanding to the full depth corresponds to reifying the complete would-be jcol.

Is any of this like what LSSS means/does? I have no idea, but I have done reasonably well so far implementing half-baked, half-mangled versions of what I thought LSSS might do so I see no reason to stop now. I've sketched the fully-unaccelerated version and it seems to work, but of course whether or not it can be made to perform (either by general optimization or by that cached pre-expansion I was talking about) will have to be seen.

[Sokwe]

Does anyone know how LSSS actually does things?

Is any of this like what LSSS means/does?

I asked this on Discord as well, but unfortunately I don't think anyone but Andrew himself understands any implementation details of LSSS. Andrew hasn't logged in since last July, but you might try contacting him via the email on his profile page. I assume you already looked through the LSSS discussion thread.

All I can offer is this discussion by Adam P. Goucher on Discord in April 2023:

I've had an idea for a spaceship search program that seems as though it should be really fast (i.e. faster than anything already out there) for orthogonal spaceship searching, although we won't know for sure until trying it. Essentially, it will follow the same methodology as LSSS, computing sets of partial spaceship slices at each position and depth. The key difference is to represent each of these sets as a BDD instead of storing a flat collection of partial slices. I expect that this will significantly improve both the runtime and space usage (hopefully enough that everything fits in memory).

One aspect that's very promising is that the number of partials (and therefore slices) at a fixed width grows exponentially with the length, but the size of the BDD representing those partials/slices only grows linearly with the length. And we get this advantage in conjunction with LSSS's superior performance on wide spaceships owing to only storing thin slices instead of entire partials.

[in response to "how do we match the slices from the decision diagram vertically?"]
Just take the conjunction of two adjacent slices (obtaining a BDD for a 3-column strip) and then eliminate the left column (if moving left-to-right) by existentially quantifying on each variable (there's discussion in Knuth about how to do this).
The BDDs will be ordered so that the variables near the tail of the spaceship are near the root of the BDD, and the variables near the head of the spaceship are near the leaves of the BDD.
In particular, this choice of variable ordering means that applying the rule constraints (to extend a 3-by-n strip into a 3-by-(n+1) strip) will only touch the nodes near the top of the BDD.

The other promising aspect is that it solves a problem that affects row-by-row searching in general (the main existing workaround being lookahead). The cells near the tail of a partial are underconstrained, causing a combinatorial explosion in the number of valid partials. Lookahead avoids this by (effectively) only storing truncated partials. But we don't need to worry about this combinatorial explosion too much: provided the BDD representing the set of partials is small (which it should be), the actual number of partials is irrelevant.

The fully general version of this algorithm applies to a satisfiability problem where you have both a tree decomposition and a linear ordering on the set of variables (for LSSS, I believe that this is boustrophedonic order?). Constraints should operate within nodes of the tree decomposition, and ideally be localised in the linear ordering. (it's basically https://en.wikipedia.org/wiki/Decomposi ... isfaction) plus BDDs)

Alex Greason mentioned this a month ago:

I tried apg's suggestion of "LSSS, but rather than reifying the slicesets store them as a BDD" and determined that 1. it isn't magic (but I could e.g. find the turtle via an assym search in 50 seconds) (I haven't implemented symmetry yet)

And then we had this discussion just now:

is there anyone here on Discord that has enough understanding of Andrew Wade's LSSS to help Keith? I think I recall [AGreason] having done their own basic implementation of the slice method.

I did - but I didn't solve the problem that's being run into here. I offloaded the join operation to "let the BDD handle it" (which it could do, but not well). And that's because my thing was in a totally different algorithmic territory from the getgo.
I also tried reading the LSSS code and got very little out of it (But I didn't spend much time on that)
I vaguely recall that LSSS itself doesn't do the join perfectly - wasn't that a cause of completeness worries?

I don't recall it ever being determined where the bug in LSSS was, or what generally was causing it.

[amling]

I did a tiny bit more testing of the new (still unaccelerated) tree joint recursive join. To find the turtle f2b, old code takes ~13s at which point the greatest internal measure of memory was 272.84 MB.

The new code takes about ~12m (yes, minutes, yes 55x slower). I believe its peak memory is going to be at the same spot although a certain part of the new code is not measured by it so I can't so easily say. I believe at that point it was using 162.81 MB memory. This is a real savings although not so dramatic. I suspect for bigger searches it might be a wider gap as (j)cols growth outpaces bcols growth.

Right before it finds the turtle the last biggest col join was for bcols of sizes 1,072,958 and 1,135,075. It found 2,351,653 valid pairs and completed 5,217,851 recursive steps to do so. These pair and step counts being the same order of magnitude makes me hopefuly this approach is going to scale well in terms of tree-walking time being vaguely proportional to the (unavoidable) number of pairs it's going to find.

I also ran 2c/4 f2b (board) width 15 (pattern width 11) just as a test. Old code takes about 2 minutes to fill the 8 GB to which I had limited it. New code took about 100m (so again 50x) to get that far. At that point the OS estimate of memory was only 3.06 GB so again a pretty real savings. The last longest join had been 32,650,873 x 32,650,873 -> 145,326,558 results in 316,120,653 steps which again seems to confirm "steps" is more closely related to results than to the worst-case of bcol x bcol.

The new join code is wildly, wildly unoptimized and e.g. the turtle run showed as only 107% CPU (on an eight core box) so the attempt to parallelize it is not working so well either. Surely these could both be improved, but I doubt enough to recover 50-55x. I'm also concerned that any savings in pre-expansion is going to require a proportional amount of memory in the result (under some vague assumptions about tree looking like typical exponential blowup in depth) and so it's maybe not clear how much pre-expansion can actually help either.

I guess I shall sleep on it and perhaps come back another time to optimize.

[Sokwe]

Keith, when it's convenient, it would be nice if you could update the exact-expand branch to include the built-in f2b, s2s, and b2f diagonal geometries, the updated symmetric ends checker, and the LLSSS_HALT_ON_ENDS environment variable. As usual, this is a low-priority request.

[amling]

Keith, when it's convenient, it would be nice if you could update the exact-expand branch to include the built-in f2b, s2s, and b2f diagonal geometries, the updated symmetric ends checker, and the LLSSS_HALT_ON_ENDS environment variable. As usual, this is a low-priority request.

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

[amling]

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

(*) "--bg-agar" changes, shipped exactly as originally written. Described up-thread, but mostly just means `--bg-agar b0` (or whatever) can substitute for a bunch of options.

(*) Hollow cols checked in to avoid bit-rotting. It is nowhere near ready to work with the big many-option dynamic mains yet, but the very, very adventurous could uncomment the "llsss-hollow" subcommand and run basic fixed board searches. This stuff is nowhere near production-quality yet and I'm not sure I can even get it there, but I just wanted to avoid conflicts with other work. The one possible relevance to more normal users is that to enable this I changed how most ends operate for fixed boards in a way that is definitely a performance regression. In my light testing it was not generally a big change for the search as a whole but it's something to keep an eye out for in the timing data output at the end of searches.

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