amling wrote: ↑February 21st, 2024, 6:22 am
...for LLSSS the entire pattern must meet CA checks globally...
...the implicit limitations on LLSSS's model of searches...
I think this assumption, namely that the pattern must meet CA checks globally, is likely the key point here.
But wait! Why does that have to be true? Originally it was just that, an assumption: I was searching for spaceships, I was gonna specify a velocity, and of course spaceship cells must satisfy CA checks. After writing this last post I was thinking that it's very difficult to weaken this assumption because the table precompilation is very sophisticated and in the hot, hot inner loop where it is run it doesn't have easy access to much of any notion of its position in the wider pattern. If we could weaken this assumption in a very strong sense, say by specifying a mask of what parts of the pattern meet CA checks we could just forget the perturbed part of the pattern in the last generation and only require the edge repair ship part to wrap around correctly.
As I thought about the ugly details of how to get the information into the tight inner loop, especially in a way that might not perform atrociously and would not make the common case of global CA checks any slower, I realized we don't really have to weaken the assumption so strongly. Something as simple as ignoring all CA checks from the last generation wrapping back around to the first will do. A combination of PD wildcards and forced on/off cells can implicitly make the CA checks we would care about true. And it's easy enough to ignore CA checks per-generation since we already build separate CA check tables for each position within a tile and, as long as U and W are "spacelike", the generation is determined completely by the position within the tile.
More on this later when I have sketched such a hack, or a constraint file that I would use with it, or both.
EDIT:
Here is a sample constraint file for trying to find a perturbing ship for that loaf with perfect clearance and 5 generations of interaction:
Code: Select all
| | | | | | | | | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR |
| | | | | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | ............................... | ............................... | ............................... | ............................... |
| LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | LLLuuuuuuuuuuuuuuuuuuuuuuuuuRRR | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... |
| ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... |
| ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | ............................... | 333............................ | 333............................ | 333............................ | 333............................ |
| ............................... | ............................... | ............................... | ............................... | 333............................ | 333............................ | 333............................ | 333............................ | 3333........................... | 3333........................... | 3333........................... | 3333........................... |
| 333............................ | 333............................ | 333............................ | 333............................ | 3333........................... | 3333........................... | 3333........................... | 3333........................... | 33333.......................... | 33333.......................... | 33333.......................... | 33333.......................... |
| 3333........................... | 3333........................... | 3333........................... | 3333........................... | 33333.......................... | 33333.......................... | 33333.......................... | 33333.......................... | 333333......................... | 333333......................... | 333333......................... | 333333......................... |
| 33333.......................... | 33333.......................... | 33333.......................... | 33333.......................... | 333333......................... | 333333......................... | 333333......................... | 333333......................... | 3333333........................ | 3333333........................ | 3333333........................ | 3333333........................ |
| 333333......................... | 333333......................... | 333333......................... | 333333......................... | 3333333........................ | 3333333........................ | 3333333........................ | 3333333........................ | 33333333....................... | 33333333....................... | 33333333....................... | 33333333....................... |
| 3333333........................ | 3333333........................ | 3333333........................ | 3333333........................ | 33333333....................... | 33333333....................... | 33333333....................... | 33333333....................... | 333333333...................... | 333333333...................... | 333333333...................... | 333333333...................... |
| 33333333....................... | 33333333....................... | 33333333....................... | 33333333....................... | 333333333...................... | 333333333...................... | 333333333...................... | 333333333...................... | 3333333333..................... | 3333333333..................... | 3333333333..................... | 3333333333........W............ |
| 333333333.......*.............. | 333333333.......*.............. | 333333333.......*.............. | 333333333.......*.............. | 3333333333.......*............. | 3333333333.......*............. | 3333333333.......*............. | 3333333333.......*............. | 33333333333.......*............ | 33333333333.......*............ | 33333333333......WWW........... | 33333333333...WWWWWWW.......... |
| 3333333333.....*.*............. | 3333333333.....*.*............. | 3333333333.....*.*............. | 3333333333.....*.*............. | 33333333333.....*.*............ | 33333333333.....*.*............ | 33333333333.....*.*............ | 33333333333.....*.*............ | 333333333333.....*.*........... | 333333333333....WWWW........... | 333333333333WWWWWWWWW.......... | 333333333333...WWWWWW.......... |
| 33333333333...*..*............. | 33333333333...*..*............. | 33333333333...*..*............. | 33333333333...*..*............. | 333333333333...*..*............ | 333333333333...*..*............ | 333333333333...*..*............ | 333333333333...*..*............ | 3333333333333...WWWW........... | 3333333333333WWWWWWWW.......... | 333333333333WWWWWWWWW.......... | 3333333333333....WWWWW......... |
| 333333333333...**.............. | 333333333333...**.............. | 333333333333...**.............. | 333333333333...**.............. | 3333333333333...**............. | 3333333333333...**............. | 3333333333333...**............. | 3333333333333..WWW............. | 33333333333333WWWWWW........... | 3333333333333WWWWWWW........... | 333333333333WWWWWWWWW.......... | 33333333333333....WWWW......... |
| 3333333333333.................. | 3333333333333.................. | 3333333333333.................. | 3333333333333.................. | 33333333333333................. | 33333333333333................. | 33333333333333.WW.............. | 33333333333333WWWW............. | 33333333333333WWWWW............ | 3333333333333WWWWWWW........... | 333333333333WWWWWWWWW.......... | 3333333333333333...WWW......... |
| 33333333333333................. | 33333333333333................. | 33333333333333................. | 33333333333333................. | 333333333333333................ | 3333333333333333............... | 3333333333333333............... | 33333333333333WWW.............. | 33333333333333WWWWW............ | 3333333333333WWWWWWW........... | 333333333333WWWWWWWWW.......... | 33333333333333333...WW......... |
| 333333333333333................ | 3333333333333333............... | 3333333333333333............... | 3333333333333333............... | 33333333333333333.............. | 33333333333333333.............. | 33333333333333333.............. | 33333333333333333.............. | 33333333333333WWWWW............ | 3333333333333WWWWWWW........... | 333333333333WWWWWWWWW.......... | 333333333333333333...W......... |
| 33333333333333333.............. | 33333333333333333.............. | 33333333333333333.............. | 33333333333333333.............. | 333333333333333333............. | 333333333333333333............. | 333333333333333333............. | 333333333333333333............. | 3333333333333333333............ | 3333333333333WWWWWWW........... | 333333333333WWWWWWWWW.......... | 3333333333333333333............ |
| 333333333333333333............. | 333333333333333333............. | 333333333333333333............. | 333333333333333333............. | 3333333333333333333............ | 3333333333333333333............ | 3333333333333333333............ | 3333333333333333333............ | 33333333333333333333........... | 33333333333333333333........... | 333333333333WWWWWWWWW.......... | 33333333333333333333........... |
| 3333333333333333333............ | 3333333333333333333............ | 3333333333333333333............ | 3333333333333333333............ | 33333333333333333333........... | 33333333333333333333........... | 33333333333333333333........... | 33333333333333333333........... | 333333333333333333333.......... | 333333333333333333333.......... | 333333333333333333333.......... | 333333333333333333333.......... |
| 33333333333333333333........... | 33333333333333333333........... | 33333333333333333333........... | 33333333333333333333........... | 333333333333333333333.......... | 333333333333333333333.......... | 333333333333333333333.......... | 333333333333333333333.......... | 3333333333333333333333......... | 3333333333333333333333......... | 3333333333333333333333......... | 3333333333333333333333......... |
| 333333333333333333333.......... | 333333333333333333333.......... | 333333333333333333333.......... | 333333333333333333333.......... | 3333333333333333333333......... | 3333333333333333333333......... | 3333333333333333333333......... | 3333333333333333333333......... | 33333333333333333333333........ | 33333333333333333333333........ | 33333333333333333333333........ | 33333333333333333333333........ |
| 3333333333333333333333......... | 3333333333333333333333......... | 3333333333333333333333......... | 3333333333333333333333......... | 33333333333333333333333........ | 33333333333333333333333........ | 33333333333333333333333........ | 33333333333333333333333........ | 333333333333333333333333....... | 333333333333333333333333....... | 333333333333333333333333....... | 333333333333333333333333....... |
| 33333333333333333333333........ | 33333333333333333333333........ | 33333333333333333333333........ | 33333333333333333333333........ | 333333333333333333333333....... | 333333333333333333333333....... | 333333333333333333333333....... | 333333333333333333333333....... | 3333333333333333333333333...... | 3333333333333333333333333...... | 3333333333333333333333333...... | 3333333333333333333333333...... |
| 333333333333333333333333....... | 333333333333333333333333....... | 333333333333333333333333....... | 333333333333333333333333....... | 3333333333333333333333333...... | 3333333333333333333333333...... | 3333333333333333333333333...... | 3333333333333333333333333...... | 33333333333333333333333333..... | 33333333333333333333333333..... | 33333333333333333333333333..... | 33333333333333333333333333..... |
| 3333333333333333333333333...... | 3333333333333333333333333...... | 3333333333333333333333333...... | 3333333333333333333333333...... | 33333333333333333333333333..... | 33333333333333333333333333..... | 33333333333333333333333333..... | 33333333333333333333333333..... | 333333333333333333333333333.... | 333333333333333333333333333.... | 333333333333333333333333333.... | 333333333333333333333333333.... |
| 33333333333333333333333333..... | 33333333333333333333333333..... | 33333333333333333333333333..... | 33333333333333333333333333..... | 333333333333333333333333333.... | 333333333333333333333333333.... | 333333333333333333333333333.... | 333333333333333333333333333.... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333... |
| 333333333333333333333333333.... | 333333333333333333333333333.... | 333333333333333333333333333.... | 333333333333333333333333333.... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333333 | 3333333333333333333333333333333 | 3333333333333333333333333333333 | 3333333333333333333333333333333 |
| 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333... | 3333333333333333333333333333333 | 3333333333333333333333333333333 | 3333333333333333333333333333333 | 3333333333333333333333333333333 | | | | |
| 3333333333333333333333333333333 | 3333333333333333333333333333333 | 3333333333333333333333333333333 | 3333333333333333333333333333333 | | | | | | | | |
It is sketched for geometry 3c12d-down. 3c/12d was the smallest multiple of c/4d that I believe will contain all the bits I needed. Here is how it breaks down:
Generations 1-6: A diagonal half-plane shape of 3's marches NW towards a single loaf. The 3's make this essentially a c/4d pattern and 6 is enough generations that the gen 4 to gen 5 (which is forced to look like gen 1) CA checks enforce that they wrap around correctly as c/4d.
Generation 7: The first uncertain cells show up when the 3's brush up against the loaf.
Generations 8-11: The W's expand outwards at approximately the speed of light (I replace any cell I could not guarantee the value of from prior generations with a W).
Generation 12: Here I have forced there to be a separation between the left half of the pattern which must have returned to the half plane of 3's and the right half of the pattern which is still wildcards. There will be no CA check from gen 12 to gen 1 but the 3's force the left part of gen 12 to look like gen 4 and so the CA check from gen 4 to gen 5 will cover the left half of this. The right half of the pattern is forgotten and its future out of scope of the search.
I will have to go write some code before I can actually run this and/or start fiddling with the choice of clearance, interaction generation count, and target object.
EDIT 2:
Oh, this might be cooking something... Here is the longest partial from the above constraint run with 11 mid_steps:
Code: Select all
x = 409, y = 23, rule = LifeHistory
F33.F33.F33.F33.F33.F33.F33.F33.F.29B3.F.29B3.F.29B3.F.29B3.F$F33.F
33.F33.F33.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B
3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B
3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.
F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F
3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F
3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.
29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.
29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.
29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.
29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B
3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B
2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F
2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.15BA
13B.F3.15BA13B.F3.15BA13B.F3.15BA13B.F2.16BA12B2.F2.16BA12B2.F2.16BA
12B2.F2.16BA12B2.F.17BA11B3.F.17BA11B3.F.17BA11B3.F.17BA11B3.F$F3.14B
ABA12B.F3.14BABA12B.F3.14BABA12B.F3.14BABA12B.F2.15BABA11B2.F2.15BABA
11B2.F2.15BABA11B2.F2.15BABA11B2.F.16BABA10B3.F.16BABA10B3.F.16BABA
10B3.F.16BAB2A9B3.F$F3.13BA2BA12B.F3.13BA2BA12B.F3.13BA2BA12B.F3.13BA
2BA12B.F2.14BA2BA11B2.F2.14BA2BA11B2.F2.14BA2BA11B2.F2.14BA2BA11B2.F.
15BA2BA10B3.F.15BA2BA10B3.F.15BA2B2A9B3.F.17B3A9B3.F$F3.14B2A13B.F3.
14B2A13B.F3.14B2A13B.F3.14B2A13B.F2.15B2A12B2.F2.15B2A12B2.F2.15B2A
12B2.F2.15B2A12B2.F.11BA3B3A11B3.F.10B2A2BA3BA10B3.F.10B2A17B3.F.9B3A
17B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.11BA17B2.F2.10B2A17B2.F2.10B2A
17B2.F2.9B3A3BA13B2.F.10B2A3B3A11B3.F.10BABA16B3.F.9B2ABABA14B3.F.9BA
3BA15B3.F$F3.11BA17B.F3.10B2A17B.F3.10B2A17B.F3.9B3A17B.F2.10B2A17B2.
F2.10BABA16B2.F2.9B2ABABA14B2.F2.9BA3BA15B2.F.10BABA3BA12B3.F.10BAB3A
2BA11B3.F.10BA3BA14B3.F.10BA3B2A13B3.F$F3.10B2A17B.F3.10BABA16B.F3.9B
2ABABA14B.F3.9BA3BA15B.F2.10BABA2BA13B2.F2.10BAB4A13B2.F2.10BA3BA14B
2.F2.10BA3B2A13B2.F.11B2AB2A13B3.F.11B2ABA14B3.F.10BABABA14B3.F.9B2AB
A16B3.F$F3.10BABA2BA13B.F3.10BAB4A13B.F3.10BA3BA14B.F3.10BA3B2A13B.F
2.11B2AB2A13B2.F2.11B2A16B2.F2.10BABABA14B2.F2.9B2ABA16B2.F.14B2ABA
11B3.F.10BA6BA11B3.F.10B3A4BA11B3.F.9B2ABA2B2A12B3.F$F3.11B2AB2A13B.F
3.11B2A16B.F3.10BABABA14B.F3.9B2ABA16B.F2.14B2ABA11B2.F2.10BA6BA11B2.
F2.10B6ABA11B2.F2.9B2ABA2B2A12B2.F.10B2ABA2B2A11B3.F.9BA3B5A11B3.F.9B
A3B3ABA11B3.F.12BABA2BA11B3.F$F3.14B2ABA11B.F3.10BA6BA11B.F3.10B6ABA
11B.F3.9B2ABA2B2A12B.F2.10B2ABA2B2A11B2.F2.9BA3B5A11B2.F2.9BA4BA2BA
11B2.F2.12BABA2BA11B2.F.9B4A16B3.F33.F33.F33.F$F3.10B2ABA2B2A11B.F3.
9BA3B5A11B.F3.9BA4BA2BA11B.F3.12BABA2BA11B.F2.9B4A16B2.F2.8BA6B2A12B
2.F33.F33.F33.F33.F33.F33.F$F3.9B4A16B.F3.8BA6B2A12B.F33.F33.F33.F33.
F33.F33.F33.F33.F33.F33.F!
Gen 12 is especially interesting as it shows the left side matching e.g. gen 4 but the right side a separated, still-active region of what loaf has become. TBD how to sort out resulting active regions that we can make something of from those we probably can't...
EDIT 3:
Oooh, or here's a partial with an active region heading the right direction (east) and 4 Y rows of c/4d already:
Code: Select all
x = 409, y = 22, rule = LifeHistory
F33.F33.F33.F33.F33.F33.F33.F33.F.29B3.F.29B3.F.29B3.F.29B3.F$F33.F
33.F33.F33.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B
3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B
3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.
F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F
3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F
3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.
29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.
29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.
29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.
29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B
3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B
2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.29B.F3.29B.F3.29B.F3.29B.F
2.29B2.F2.29B2.F2.29B2.F2.29B2.F.29B3.F.29B3.F.29B3.F.29B3.F$F3.15BA
13B.F3.15BA13B.F3.15BA13B.F3.15BA13B.F2.16BA12B2.F2.16BA12B2.F2.16BA
12B2.F2.16BA12B2.F.17BA11B3.F.17BA11B3.F.17BA11B3.F.17BA11B3.F$F3.14B
ABA12B.F3.14BABA12B.F3.14BABA12B.F3.14BABA12B.F2.15BABA11B2.F2.15BABA
11B2.F2.15BABA11B2.F2.15BABA11B2.F.16BABA10B3.F.16BABA10B3.F.16BABA
10B3.F.16BABA10B3.F$F3.13BA2BA12B.F3.13BA2BA12B.F3.13BA2BA12B.F3.13BA
2BA12B.F2.14BA2BA11B2.F2.14BA2BA11B2.F2.14BA2BA11B2.F2.14BA2BA11B2.F.
15BA2BA10B3.F.15BA2BA10B3.F.15BA2BA10B3.F.18B2A9B3.F$F3.14B2A13B.F3.
14B2A13B.F3.14B2A13B.F3.14B2A13B.F2.15B2A12B2.F2.15B2A12B2.F2.15B2A
12B2.F2.15B2A12B2.F.16B2A11B3.F.15B3A11B3.F.18BA10B3.F.12BA4B2A10B3.F
$F3.29B.F3.29B.F3.29B.F3.29B.F2.29B2.F2.29B2.F2.29B2.F2.12BA16B2.F.
16BA12B3.F.12B2AB3A11B3.F.11B3A3BA11B3.F.11BA2BA14B3.F$F3.29B.F3.29B.
F3.29B.F3.12BA16B.F2.29B2.F2.12B2A15B2.F2.11B3A15B2.F2.11BA2BA14B2.F.
11B4A14B3.F.10B2A2BA14B3.F.11B4A14B3.F.8BAB2A2BA14B3.F$F3.29B.F3.12B
2A15B.F3.11B3A15B.F3.11BA2BA14B.F2.11B4A14B2.F2.10B2A2BA14B2.F2.11B4A
14B2.F2.8BAB2A2BA14B2.F.9B2AB2A15B3.F.8BA6BA13B3.F.7B3A19B3.F.7BABABA
17B3.F$F3.11B4A14B.F3.10B2A2BA14B.F3.11B4A14B.F3.8BAB2A2BA14B.F2.9B2A
B2A15B2.F2.8BA6BA13B2.F2.7B3A19B2.F2.7BABABA17B2.F.8B3AB4A13B3.F.7B2A
20B3.F.7B2A3BA16B3.F.6BA6B2A14B3.F$F3.9B2AB2A15B.F3.8BA6BA13B.F3.7B3A
19B.F3.7BABABA17B.F2.8B3AB4A13B2.F2.7B2A20B2.F2.7B2A3BA16B2.F2.6BA6B
2A14B2.F.6B2A2BA2BA15B3.F.11B3A15B3.F.7BA2BA2B3A13B3.F.5B2AB2ABA17B3.
F$F3.8B3AB4A13B.F3.7B2A20B.F3.7B2A3BA16B.F3.6BA6B2A14B.F2.6B2A2BA2BA
15B2.F2.11B3A15B2.F2.7BA2BA2B3A13B2.F2.5B2AB2ABA17B2.F33.F33.F33.F33.
F$F3.6B2A2BA2BA15B.F3.11B3A15B.F3.7BA2BA2B3A13B.F3.5B2AB2ABA17B.F33.F
33.F33.F33.F33.F33.F33.F33.F!