LLSSS min height search results

[amling]

... finding spaceships of minimal height.

I can however take a look with what I have for free (my attention and 120GB) and see what I can do.

I'll dump the results and/or any extensive essays about the philosophy of Z^3 geometry here.

I'm going to start with the "staggered" windows. For 1c/N they match the unstaggered windows only they have a possible finer grain measurement.

For c/2 height 7.5 longest partial was:

Code: Select all

| ............ | ............ |
| ............ | ............ |
| .......*.*.. | ........*... |
| ......*..*.. | .....****... |
| .....**..... | .....*.*.... |
| .....*.*.... | ....*..*.... |
| ....*.*..*.. | ...*........ |
| ...***.**... | ...*.****... |
| ...*........ | ..*......... |
| ...******... | ...******... |
| .........*.. | ...*........ |
| ...*.*.*.... | ..***..*.... |
| ..**..**.*.. | ..*..*.*.... |
| ...**..*.... |              |

Height 8 finds the known ship.

For c/3 height 4 2/3 longest partial was:

Code: Select all

| ......... | ......... | ......... |
| ......... | ......... | ......... |
| .....*... | ....*.... | ....*.... |
| ...**.... | ...*.*... | ...*.*... |
| ...**.... | ...*.*... | ..**..... |
| .....*... | ...*..... | ....*.... |
| ...*..... | ......... | ..**..... |
| ...*.*... | ..**..... | ..***.... |
| ...*.*... | ...*.*... | ......... |
| ....*.... | ..*.*.... | ..*..*... |
| ..**..... | ..***.... | ..*.*.... |
| ...*..... | ......... | ..*...... |
| ...***... | ...*.*... | ...*..... |
| ....*.... | ...**.... | ...*.*... |
| ......*.. | ....*.... | ....*.... |
| ....**... | ....*.*.. | ...**.... |
| ....**... | ....**... | ......... |
| ......... | ...**.... | ..*..*... |
| ..**..... | ..**..... | ..*...... |
| ...***... | ..*..*... | ..**..... |
| ....*.... | ......... | ...*.*... |
| ...**.... | ...***... | ...*.*... |
| ....*.... | ...**.... | ...*..... |
| ......... | .....*... | ....*.... |
| .....**.. | ......... | ......... |
| ......... | ....*.... | ....**... |
| ....***.. | ....**... | ......... |
| ....*.... | ...**.*.. | ..*.*.... |
| ....*.*.. |           |           |

Height 5 finds the known ship.

For c/4 height 7 1/4 the longest partial was:

Code: Select all

| ............ | ............ | ............ | ............ |
| ............ | ............ | ............ | ............ |
| ....*....... | ...*........ | ...**....... | ..*.*....... |
| ..**...*.... | ...**..**... | ..***..*.... | ..*...*..... |
| ....*..**... | ...*..*..... | ...****..... | ..*..**..... |
| .......**... | ......*..... | ............ | ....*.*..... |
| .......*.... | ............ | ......*..... | ......*..... |
| ......**.... | ......***... | ......***... | .....**.*... |
| .......*.... | .......*.... | .....*..*... | ......*.*... |
| ....***..... | ....*.*..... | ............ | ....*....... |
| ....**...... | ...*........ | ...**....... | ...**....... |
| ....**...... | ....*.*..... | ...**....... | ............ |
| ......*..... | ....*.*..... | ....*.*..... | ....*....... |
| .....*...... | .....*...... | ....*.*..... | ....*.**.... |
| ....*....... | ....*.*..... | ...**.*..... | ...**....... |
| ....*.**.... | ...**..*.... | ............ | ...*.***.... |
| ....*...*... | ...**....... | ..*...**.... | ............ |
| ....***..... | ...**.**.... | ............ | ...****..... |
| ....*..*.... | ....*....... | ...***...... | ....*....... |
| .....*...... | ............ | ............ | .....*...... |
| ............ | ....*....... | ...**....... | ...*........ |
| ...**....... | ...**....... | ..*...*..... | ..*......... |
| ...*........ | ..**.***.... | ..*....*.... | ..*...**.... |
| ...*.****... | ....****.... | ...**..*.... | ...**....... |
| ......*..... | ............ | ....*....... | ...**..*.... |
| ....**...... | .....***.... | .....***.... | ....*..*.... |
| ......*.*... | ......*..... | .....***.... | ............ |
| ......**.... | ............ | ......*..... | .....***.... |
| .....**..... | .....*.*.... | ............ | .....*...... |
| .....*...... | ....*....... | ....*.*..... | ....*....... |
| .....**..... | ....**...... | ....**...... | ....**...... |
| .....*.*.... | .....*...... | ............ | ......*..... |
| ............ | ....***..... | ....***..... | ....*.*..... |
| ....**...... | ............ | ....*.*..... | ....*....... |
| ............ | ....*.*..... | ......**.... | ....*..*.... |
| ....*.**.... | .....***.... | ....**.*.... | ...***...... |
| ...*..**.... | ...*...*.... | ..**.*.**... | ..*..*...... |
| ...***...... | ..**.*..*... | ..**..***... | ..**.*..*... |
| ...*...**... | ...*...*.... | .....*...... | ........*... |
| .....**..... | ..***.***... | ..*****.*... | ...****..... |
| ..**.....*.. | ......*..... | ............ | ............ |
| .......*.... | ....**.**... | ....*....... |              |

Height 7.5 finds the ship linked from the wiki (although it says "height 8" there).

For 2c/4 height 4.5 the longest partial was:

Code: Select all

|  ......... |  ......... | .........  | .........  |
|  ......... |  ......... | .........  | .........  |
|  ......... |  .....*... | .........  | .........  |
|  ....***.. |  .....*... | .....*...  | ....*....  |
|  ......... |  ...*..... | ...**....  | ...***...  |
|  ...**.... |  ..***.... | ...*..*..  | ...***...  |
|  ..**..... |  ....**... | ......*..  |            |

Height 5 finds the LWSS.

[amling]

I'll dump ... any extensive essays about the philosophy of Z^3 geometry here.

I guess the shortest version is that I find it undesireable that a c/2 ship, measured as a 2c/4 ship, has a different height when using unstaggered height. With staggered height it has the same height as Nc/2N for any N.

The most concise fully-mathed-up version is that when gcd(n, d) = 1, Z^2/(-n, d) is isomorphic to Z and measuring by the envelope in that Z seems like a more obvious choice. For gcd-with velocities there is still an obvious map from Z^2/(-kn, kd) -> Z^2/(-n, d) =~ Z and still the same obvious choice of measurement. In either case this corresponds to staggered height (rescaled to measure in terms of cells instead of in terms of that generator of Z^2/(-n, d)).

I guess the essay's not as extensive as I thought. Maybe I'll draw some pictures/grids later to try to illustrate what I mean...

[amling]

For c/5 height 7.4 longest partial was:

Code: Select all

| ............ | ............ | ............ | ............ | ............ |
| ............ | ............ | ............ | ............ | ............ |
| ............ | ............ | .....*...... | ............ | ............ |
| ............ | ....***..... | ....*..*.... | ............ | ............ |
| ...*****.... | ....****.... | ............ | ...**....... | ...**....... |
| ......*.*... | ...**.*.*... | ...**...*... | ...*..**.... | ..**.***.... |
| ..*......*.. | .......*.... | ...*****.... | ...*..**.... | ..**..**.... |
| ..*...*..... | ..*..*...... | ......*..... | ..*......... | ..*..*.*.... |
| ...**.*..... | ...*..*..... | ..******.... | ..****.*.... | ..****.**... |
| ......*.**.. | ...*..**.... | ...*...*.... | .....*.**... | .....*.**... |
| ....**...... | ....***..... | ...*...*.... | ..***....... | ..***....... |
| ...*.*...... | ...*.*...... | ...*........ | ...*........ | ............ |
| ....*....... | ...***...... | ..**.*...... | ..***....... | ..*.*....... |
| ...*..*..... | ...*........ | ..*......... | ..*......... | ..*......... |
| ....**...... | ...**.*..... | ...**....... | ...**....... | ...***...... |
| ....*.*..... | ....*.*..... | ....*..*.... | ....**...... | ............ |
| ......***... | ....*...*... | ....*....... | ...**.*..... | ...*..*..... |
| ....**.**... | .....*...... | ....***..... | ....*.*..... | ....*.**.... |
| ......*.**.. | .....**..... | .....**..... | ....*..*.... | ....*..*.... |
| .......***.. | .......*.*.. | ......*..... | .....***.... | .......*.... |
| ............ | ............ | ........*... | ....**...... | ...*...*.... |
| ...**..***.. | ...**...*... | ...***...... | ...***.*.... | ...*........ |
| ....*....... | ...**.*..... | ...*..*.*... | ...*.*.*.... | ...*.*.**... |
| .....**.**.. | .....****... | ........*... | .......*.... | ....*....... |
| .......*.... | .....*.*.... | ............ | .....*...... | .....*.*.... |
| .....*..**.. | ....**..*... | ....***..... | .....***.... | .......*.... |
| ....****.... | ....*....... | .......**... | ...**.**.... | ...**..*.... |
| ......**.... | ...**..**... | ..*.*....... | ..*......... | ..*.**...... |
| ..**.....*.. | ..**........ | ..**........ | ..*.*....... | .....*...... |
| ...*........ | .....*...... | ....*....... | ....*.*..... |              |

Height 7.6 found the spider.

[amling]

2c/5 (staggered) height 9.2 longest partial was:

Code: Select all

|  .............. |  .............. |  .............. | ..............  | ..............  |
|  .............. |  .............. |  .............. | ..............  | ..............  |
|  ......*...*... |  .............. |  ......*....... | ......**......  | ......**......  |
|  ......*...*... |  .....***...... |  .....****..... | ......*..*....  | .....******...  |
|  .....*.*...... |  ....*..*.**... |  ....*..**..... | .....*...**...  | ....*...*.....  |
|  ....***..**... |  ....***....... |  ....*.....*... | ....***..**...  | ....*....**...  |
|  .............. |  .....*****.... |  ....*....*.... | .....**.......  | ....*..*......  |
|  .......**..... |  .......**..... |  .....*........ | ......*.......  | ..............  |
|  .......**..... |  ......*..*.... |  ......*..*.... | ......**......  | ......**......  |
|  .......**..... |  ......***..... |  .....*...*.... | .........**...  | ......*.......  |
|  .....*........ |  ......***..... |  ........*..... | .....*........  | ....**...*....  |
|  ....*..*...... |  ....**........ |  ...**......... | ....**..*.....  | ....***.......  |
|  ....*......... |  ...**.***..... |  ...*..**...... | ...*..*.......  | ...*....*.....  |
|  ....***.**.... |  ....**........ |  ...**......... | ....*****.....  | ...**.**......  |
|  .............. |  ......*....... |  ......*....... | ....*.........  | ....*...*.....  |
|  ....**........ |  ....**........ |  ....**........ | .....***......  | ....***.......  |
|  ....*..*...... |  ....*......... |  ...*..*....... | ....*.........  | ....*.........  |
|  .....*.*...... |  ....**.*...... |  ....*****..... | .....*...*....  | ....**........  |
|  .....*.***.*.. |  .......**..... |  .....*..*..... | .....*....*...  | .....**..**...  |
|  .............. |  ......**..*... |  ......***..... | ......*..*....  | ......*.***...  |
|  .......*...*.. |  .............. |  ......**...... | .......*.*....  | ......**.*....  |
|  .............. |  .......*...... |  .............. | .......**.....  | .......**.....  |
|  .......***.... |  ......*..*.... |  ......*....... | ..............  | .......*......  |
|  ......***..... |  .....*........ |  .....*........ | ......*.......  | ......*.......  |
|  ....**.**..... |  ....*....*.... |  ....*...*..... | ....***.......  | ....*.*.......  |
|  ....**.**..... |  ...*...**..... |  ...**...*..... | ....*.........  | ...**.*.......  |
|  ....**........ |  ....*......... |  ....**........ | ....*.*.......  | ....*.*.......  |
|  ......***..... |  .....****..... |  .....*..*..... | .....**.......  | .....***......  |
|  .......*...... |  ......***..... |  ........*..... | ........**....  | ..............  |
|  ....*......... |  ...***........ |  ...*...*...... | ..............  | ..............  |
|  ...***........ |  ...***........ |  ..*........... | ...**.........  | ..***.........  |
|  ..*...*....... |  ..*...**...... |  ..*....*...... | ..**..........  | ..*..*........  |
|  ...****.**.... |  ...**.**...... |  ..*.*......... | ...*.**.*.....  | ..**.***......  |
|  ....*......... |  ...**.*....... |  ...**.*.*..... | ....**.*......  | .......**.....  |
|  .......***.... |  .......*.*.... |  .....***...... | .....*...*....  | ....**.**.....  |
|  .......***.... |  ......*....... |  ......**...... | ......*.*.....  | ..............  |
|  .......**..... |  ......*....... |  .............. | ..............  | .......*......  |
|  .......***.... |  .........*.... |  .............. | ......*.......  | ......**......  |
|  ......**.*.... |  .....*...*.... |  ....***.*..... | .....*.**.....  | .....*..*.....  |
|  ....**.*...... |  ....**.*...... |  ....**..*..... | ....*..**.....  | ....*...*.....  |
|  ....*..*...... |  ...*...*...... |  ...*.......... | ....*.*.......  | ...**.****....  |
|  ....****.*.... |  ....*****..... |  ....*...*..... | ....**...**...  | ....**..*.*...  |
|  .............. |  .....**.*..... |  ....*...**.... | ........***...  | ..............  |
|  .........*.... |  ......*.*..... |  ........*..... | ........**....  | .......*......  |
|  .....***.*.... |  .....***...... |  .....*..*..... | .....*..**....  | ....**..**....  |
|  ....*..*...... |  ....*..*...... |  ...**..*...... | ....**........  | ....**........  |
|  ....*...*..... |  ...**......... |  ...*.......... | ....*.........  | ....*.*.......  |
|  ....**........ |  ....**........ |  .....*........ | .....**.......  | ....****......  |
|  ..........*... |  ....*......... |  ....*.*....... | ....*..**.....  | ....*..***....  |
|  ....*.*.*..*.. |  .....**.*.*... |  ...***.**.*... | ....**..*.*...  | ...***.**.*...  |
|  ...*..****.... |  ..**....***... |  ..*...*...*... | ...*.....**...  | ..*..*....*...  |
|  ..**.**...*... |  ..****..**.... |  ..*..*.*...... | ..***...**....  | ..*.*...*.....  |
|  ......*....... |  ....*..*..*... |  ..*....*.*.... | ...*......*...  | ..*..*....*...  |
|  .....**..*.*.. |  ...**.**...... |  ...*******.... | ....**....*...  | ....**........  |
|  ..***.*....... |  ..*.....*.*... |  ....*.*....... | .....*........  | .....*.****...  |
|  ...**.**.*.... |  ....*.*....... |  ..*....*...... |                 |                 |

2c/5 height 9.4 filled memory (even 120G) and died.

c/6 height 7 1/6 longest partial was:

Code: Select all

| ............ | ............ | ............ | ............ | ............ | ............ |
| ............ | ............ | ............ | ............ | ............ | ............ |
| .....*...... | ....*....... | ............ | ....*....... | ............ | ....*....... |
| ...**....... | ....*....... | ...***...... | ....*....... | ...***...... | ...*.*...... |
| ............ | ....*....... | ............ | ...*.*...... | ...*.*...... | ..**........ |
| .....*...... | ............ | ....*....... | ....**...... | ...*.**..... | ..**........ |
| ....*....... | ....***..... | ....**...... | ...*.*...... | ...*.**..... | ...*...*.... |
| ...*.*.*.... | ...*........ | ...*.*...... | ..*..*...... | ..**.**..... | ..*......... |
| ...****..... | ...*........ | ..***....... | ..*..*...... | ...***...... | ..**.**..... |
| ....****.... | ...*...*.... | ....*....... | ....*....... | ............ | ....*....... |
| ........*... | .....*..*... | ........*... | .......*.... | .......*.... | .......*.... |
| .......*.*.. | ......**.... | ......**.... | ......*.*... | ......*.*... | ......*.*... |
| ......**.... | ............ | ......**.... | ......**.... | .....*..*... | ......*.*... |
| ......***... | .....*..*... | ............ | .....*.*.... | .......*.... | ......*..... |
| ......*..... | .....*..*... | .....**..... | ............ | .....*...... | .....*...... |
| .....*.*.... | ....**...... | ............ | .....**..... | .....**..... | .....**..... |
| ....**...... | ....***..... | ...*..*..... | .....*...... | ............ | ....*.*..... |
| ............ | ....**...... | ....*.*..... | ...**.*..... | ...**.*..... | ...**.**.... |
| ....*....*.. | ............ | ....**...... | ....*.*..... | ...**.**.... | ...**.**.... |
| ........*... | .....*...... | .....*...... | .....**..... | ......*..... | .....***.... |
| .....**..... | .....***.... | ....*..*.... | ....**...... | ............ | .....*...... |
| .....**..... | .....**..... | ....*....... | ....***..... | ....*.*..... | .....*...... |
| ............ | .....***.... | .....*.*.... | ......*..... | ......*..... | .....*.*.... |
| ......*.*... | .......*.... | .......*.... | .......**... | ........*... | .......*.... |
| ......*..... | .....**..... | ......**.... | ......**.... | ......*..... | .....**..... |
| ......*.*... | .......*.... | .....*...... | ....*..*.... | .....***.... | .....***.... |
| ............ | .....*...... | ....***..... | ....*....... | ............ | ............ |
| ....**...... | ....**...... | .....**..... | ............ | ...***...... | ...***...... |
| ...*.*...... | ...*.*...... | ...*.*...... | ..**.**..... | ..*..*...... | ..*......... |
| ...*........ | ...*........ | ..**........ | ..***....... | ..*.****.... | ..*....**... |
| ....****.... | ...*...**... | .......**... | .......**... | ...**..**... | ...**....... |
| ....**.**... | ........*... | .......**... | .....*..*... | .......**... | ....*.***... |
| .....*.*.... | .....*...... | ....***..... | ....*....... | .....*...... | ......*..... |
| .....*.**... | ....**.*.... | ...*.**..... | ......*..... | .....*...... | ....**...... |
| ....*..*.*.. | ...**....... | ............ | ....*..*.... | ....*...*... | ....*.*.*... |
| ...**.**.... | ..*.*....... | ....*.**.... | ....*****... | ....*.***... | ....**.**... |
| ..**..**.... | .....****... | ...*.*.**... | ..*.*....... | ..**........ |              |

c/6 height 7 1/3 filled memory and died.

Maybe LLSSS is not a good choice for this with no memory/CPU tradeoff to fall back on. I might try with LGOL although I'm not optimistic and I doubt it's better than whatever Sokwe used in 2015. I also had a crazy idea for a memory/CPU tradeoff for fixed-board LLSSS but it's gonna be extremely slow and a lot of code. TBD.

[Sokwe]

I came back to this topic because I've been expanding the minimum height tables on the spaceship search status page.

I doubt it's better than whatever Sokwe used in 2015.

The c/7 height-8, c/6 height-9, and 2c/5 height-10 searches were actually done in 2010 or 2011 with WLS. In the c/6 and c/7 cases, the search was split up over dozens of computers in a computer lab I had some relatively exclusive access to on weekends (although I'm sure I wasn't supposed to be running Life searches). These took long enough that they might still be hard to replicate even with modern tools and hardware.

The 2c/5 search was done on my personal computer, but it took weeks, or maybe months. I can't remember.

2c/5 height 9.4 filled memory (even 120G) and died...

Maybe LLSSS is not a good choice for this with no memory/CPU tradeoff to fall back on. I might try with LGOL although I'm not optimistic and I doubt it's better than whatever Sokwe used in 2015.

I am wondering if at least the height-10 2c/5 result could still be confirmed with LGOL. Is there any difficulty in this, or would it just take too much time? If it's a matter of the search taking up valuable computer resources, I'd be willing to run it, but I don't know how to set it up, and I've never used LGOL. My goal would primarily be to confirm that there are no (2,0)c/5 ships that fit in a height-10 bounding box through their whole period, but I wouldn't mind knowing the fine-grain staggered minimum as well.

[amling]

Maybe LLSSS is not a good choice for this with no memory/CPU tradeoff to fall back on. I might try with LGOL although I'm not optimistic and I doubt it's better than whatever Sokwe used in 2015.

I am wondering if at least the height-10 2c/5 result could still be confirmed with LGOL. Is there any difficulty in this, or would it just take too much time? If it's a matter of the search taking up valuable computer resources, I'd be willing to run it, but I don't know how to set it up, and I've never used LGOL. My goal would primarily be to confirm that there are no (2,0)c/5 ships that fit in a height-10 bounding box through their whole period, but I wouldn't mind knowing the fine-grain staggered minimum as well.

Sadly LGOL makes LLSSS look user friendly so it's gonna be a bit of a mess. Running staggered heights of an integer number of rows up to 12 requires no real code, just the usual "edit 100% of main_lgol to configure your search". This is pushed up to 20240220-2c5-min-height. Run as `cargo run --release 06` e.g. to run height 6 (staggered envelope though, as should be clear in partials).

I have run this just now and some highlights from the output are:

Code: Select all

20240220 10:50:21 [DEBUG] Checks3: compiling table of 17 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 0
20240220 10:50:22 [DEBUG] Checks3: compiling table of 17 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 0
20240220 10:50:23 [DEBUG] Checks3: compiling table of 19 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 8
20240220 10:50:26 [DEBUG] Checks3: compiling table of 18 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 8
20240220 10:50:27 [DEBUG] Checks3: compiling table of 17 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 16
20240220 10:50:28 [DEBUG] Checks3: compiling table of 17 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 16
20240220 10:50:29 [DEBUG] Checks3: compiling table of 11 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 16
20240220 10:50:29 [DEBUG] Checks3: compiling table of 16 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 24
20240220 10:50:30 [DEBUG] Checks3: compiling table of 16 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 24
20240220 10:50:30 [DEBUG] Checks3: compiling table of 13 bits for bgc = GolBgcWrapper(GolBgc1), idx0 = 24
20240220 10:50:30 [INFO] Checks3: compilation took 8.759647413s

Due to the way LGOL picks bits it's going to require somewhat more expensive precompilation than LLSSS. This precompilation should scale linearly with the height. You can set environment variable LGOL_MAX_TABLE_SIZE to something lower (e.g. 9) if you want it to generate smaller tables (quicker to generate, slower to run).

Code: Select all

20240220 10:50:30 [INFO] q 1 (16 B), kns 2 (80 B), total 96 B
20240220 10:50:30 [INFO] Completed BFS step to depth 1 (LGolDepth { r1ld8: 1 })
20240220 10:50:30 [DEBUG] Firstest:
20240220 10:50:30 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:50:30 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:50:30 [DEBUG] |  ...... |  ..???? |  ?????? | ??????  | ??????  |
20240220 10:50:30 [DEBUG] Random partial:
20240220 10:50:30 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:50:30 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:50:30 [DEBUG] |  *.*..* |  ..???? |  ?????? | ??????  | ??????  |
20240220 10:50:30 [INFO] q 150 (2.34 KB), kns 2 (80 B), total 2.42 KB

LGOL doesn't show any bounding zeros, just the window of actually variable cells. You can see it's shifted in later generations.

Code: Select all

20240220 10:50:31 [INFO] q 48276096 (736.63 MB), kns 2 (80 B), total 736.63 MB
20240220 10:50:32 [INFO] par: threads 8/8, completed 179/737
20240220 10:50:34 [INFO] par: threads 8/8, completed 597/737
20240220 10:50:42 [INFO] Completed BFS step to depth 5 (LGolDepth { r1ld8: 0 })

It will output these "par:" lines if a step is taking sufficiently long to try to give some idea of what's happening and/or evidence it is still running.

Code: Select all

20240220 10:50:42 [INFO] End "" -> ():
20240220 10:50:42 [INFO] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:50:42 [INFO] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:50:42 [INFO] |  ...... |  ...... |  ...... | ......  | ......  |

"End" means (as I've configured it) that it got back to all zeros. This one is the trivial one, but if there were any ships you'd get more.

Code: Select all

20240220 10:50:59 [INFO] q 85065276 (1.27 GB), kns 48276097 (1.80 GB), total 3.07 GB
20240220 10:51:01 [INFO] par: threads 8/8, completed 123/800
20240220 10:51:03 [INFO] par: threads 8/8, completed 375/800
20240220 10:51:06 [INFO] ws.q 6241056 (95.23 MB), ws.q2 78824220 (4.11 GB), kns 48276097 (1.80 GB), total 6.00 GB, deepening...
20240220 10:51:06 [INFO] Deepened ws.q 6241056 => 6241056, foresight 1 in 42.881109ms
20240220 10:51:07 [INFO] Deepened ws.q2 78824220 => 78824220, foresight 0 in 380.58697ms
20240220 10:51:08 [INFO] Rebuilt kns from 48276097 to 113464 (1 roots) in 903.147573ms
20240220 10:51:08 [INFO] Deepening pass 6.00 GB => 4.21 GB completed in 1.328057661s
20240220 10:51:11 [INFO] Completed BFS step to depth 10 (LGolDepth { r1ld8: 0 })

As LGOL continues on it stores a big tree of partials ("kns" is what it's named above), only appending until it fills memory. By default the code will assume 2 GB, but you can set, as I have here, e.g. BFS_MEM_GB=6 for 6 GB. Note that this is its internal estimate of memory which is inaccurate to say the least. You may want to experiment with values to see what's right for your computer. When the tree reaches the limit, as it did here, it stops and prunes the queue/tree, possibly doing additional filtering via DFS on each node. "Foresight" represents more or less the depths it is searching to to. Values 1 and 0, as seen here, really mean it's just cleaning up unused tree bits. You will certainly see occasional foresight 1/0 passes as it cleans up after itself every time it fills memory, but...

You may also see repeated passes with increasing foresight. This is what happens when your search really exceeds your memory and LGOL is using its nearly limitless capacity to trade off time/memory. I say nearly limitless, but in reality we are only willing to wait for so long and the deeper the DFSing gets the slower it gets, quite badly. Unfortunately it's very hard to tell how long searches are going too take from any of this. Usually I run a sequence of smaller widths up to whatever I'm actually hoping to run to try to get some extrapolated sense.

Code: Select all

20240220 10:51:33 [INFO] Completed BFS step to depth 56 (LGolDepth { r1ld8: 1 })
20240220 10:51:33 [DEBUG] Firstest:
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:51:33 [DEBUG] |  ...... |  ....*. |  ...**. | ....**  | ....*.  |
20240220 10:51:33 [DEBUG] |  ...*** |  ...**. |  ..*..* | ...*..  | ...*..  |
20240220 10:51:33 [DEBUG] |  ...*.. |  ..**.* |  ..**.. | ...*..  | ..**..  |
20240220 10:51:33 [DEBUG] |  ...*.* |  ...... |  ...**. | ...***  | ...**.  |
20240220 10:51:33 [DEBUG] |  .....* |  ....*. |  ...... | ......  | ....*.  |
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  ...... | ......  | ...*..  |
20240220 10:51:33 [DEBUG] |  ..*..* |  .**... |  .**... | ..***.  | .****.  |
20240220 10:51:33 [DEBUG] |  .**..* |  .*...* |  .*.**. | .**..*  | .*..*.  |
20240220 10:51:33 [DEBUG] |  .*.**. |  ...**. |  *..**. | .*....  | *.....  |
20240220 10:51:33 [DEBUG] |  **.... |  ***... |  .***.. | .**...  | *.**..  |
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  .*..*. | *.*.*.  | *.....  |
20240220 10:51:33 [DEBUG] |  ...... |  ..???? |  ?????? | ??????  | ??????  |
20240220 10:51:33 [DEBUG] Random partial:
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  ...... | ......  | ......  |
20240220 10:51:33 [DEBUG] |  ...... |  ....*. |  ...**. | ....**  | ....*.  |
20240220 10:51:33 [DEBUG] |  ...*** |  ...**. |  ..*..* | ...*..  | ...*..  |
20240220 10:51:33 [DEBUG] |  ...*.. |  ..**.* |  ..**.. | ...*..  | ..**..  |
20240220 10:51:33 [DEBUG] |  ...*.* |  ...... |  ...**. | ...***  | ...**.  |
20240220 10:51:33 [DEBUG] |  .....* |  ....*. |  ...... | ......  | ....*.  |
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  ...... | ......  | ...*..  |
20240220 10:51:33 [DEBUG] |  ..*..* |  .**... |  .**... | ..***.  | .****.  |
20240220 10:51:33 [DEBUG] |  .**..* |  .*...* |  .*.**. | .**..*  | .*..*.  |
20240220 10:51:33 [DEBUG] |  .*.**. |  ...**. |  *..**. | .*....  | *.....  |
20240220 10:51:33 [DEBUG] |  **.... |  ***... |  .***.. | .**...  | *.**..  |
20240220 10:51:33 [DEBUG] |  ...... |  ...... |  *..*.. | *.*.*.  | *....*  |
20240220 10:51:33 [DEBUG] |  ...*.* |  .*???? |  ?????? | ??????  | ??????  |
20240220 10:51:33 [INFO] q 778 (12.16 KB), kns 134922125 (5.03 GB), total 5.03 GB
20240220 10:51:33 [INFO] Completed BFS step to depth 57 (LGolDepth { r1ld8: 2 })
20240220 10:51:33 [INFO] Dumping 0 final partials at lookback 0...
20240220 10:51:33 [INFO] Dumped 0 final partials at lookback 0.
20240220 10:51:33 [INFO] bfs/ex1/bfs_expand/expand loop/expand: 46 calls, 27.907697394s own time, 27.907697394s total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/expand: 12 calls, 12.046897717s own time, 12.046897717s total time
20240220 10:51:33 [INFO] bfs/ex2/q4 foldover: 11 calls, 10.873720048s own time, 10.873720048s total time
20240220 10:51:33 [INFO] bfs/ex1/bfs_expand/rebalance: 46 calls, 7.274370114s own time, 7.274370114s total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/rebalance: 11 calls, 1.800962219s own time, 1.800962219s total time
20240220 10:51:33 [INFO] bfs/ex1/bfs_expand: 46 calls, 1.300115889s own time, 36.512236319s total time
20240220 10:51:33 [INFO] bfs/ex2/q3 reverse: 11 calls, 577.881637ms own time, 577.881637ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/deepen q2/deepen: 1 calls, 380.578167ms own time, 380.578167ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand: 11 calls, 260.552984ms own time, 15.443650549s total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns/reindex pins: 1 calls, 247.861265ms own time, 247.861265ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns/compact: 1 calls, 181.071725ms own time, 181.071725ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns/walk pins: 1 calls, 169.821379ms own time, 169.821379ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns/compute new positions: 1 calls, 144.039084ms own time, 144.039084ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns/reindex self: 1 calls, 116.746236ms own time, 116.746236ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns: 1 calls, 44.952272ms own time, 904.49233ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/deepen q/deepen: 1 calls, 42.871428ms own time, 42.871428ms total time
20240220 10:51:33 [INFO] bfs/ex1/bfs_expand/q3 foldover: 46 calls, 29.777693ms own time, 29.777693ms total time
20240220 10:51:33 [INFO] bfs/partials: 57 calls, 16.468441ms own time, 16.468441ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/q3 foldover: 11 calls, 7.013135ms own time, 7.013135ms total time
20240220 10:51:33 [INFO] bfs: 1 calls, 2.650084ms own time, 63.42672372s total time
20240220 10:51:33 [INFO] bfs/ex1/bfs_expand/expand loop: 46 calls, 275.229µs own time, 27.907972623s total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop: 11 calls, 186.419µs own time, 13.375122211s total time
20240220 10:51:33 [INFO] bfs/ex2: 11 calls, 76.187µs own time, 26.895328421s total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/deepen q2: 1 calls, 49.218µs own time, 380.627385ms total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/deepen q: 1 calls, 46.932µs own time, 42.91836ms total time
20240220 10:51:33 [INFO] bfs/ex1: 46 calls, 35.807µs own time, 36.512272126s total time
20240220 10:51:33 [INFO] bfs/partials tree: 58 calls, 4.648µs own time, 4.648µs total time
20240220 10:51:33 [INFO] bfs/ex2/bfs_expand/expand loop/rebuild kns/compact roots: 1 calls, 369ns own time, 369ns total time
20240220 10:51:33 [INFO] bfs took 63.426928771s
20240220 10:51:34 [INFO] Done

Eventually it finished.

As an example from the next height up, here is it thrashing against the memory limit until it eventually DFSes deep enough to choke through:

Code: Select all

20240220 10:56:43 [INFO] Completed BFS step to depth 9 (LGolDepth { r1ld8: 3 })
20240220 10:56:43 [DEBUG] Firstest:
20240220 10:56:43 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:56:43 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:56:43 [DEBUG] |  ....... |  ....... |  ....... | .......  | .....*.  |
20240220 10:56:43 [DEBUG] |  ....... |  ....... |  ....... | ...????  | ???????  |
20240220 10:56:43 [DEBUG] Random partial:
20240220 10:56:43 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:56:43 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:56:43 [DEBUG] |  ..*.*.* |  ...*..* |  ...*.*. | ...*.*.  | ..*..**  |
20240220 10:56:43 [DEBUG] |  ..*..** |  .*****. |  .*.*..* | ..*????  | ???????  |
20240220 10:56:43 [INFO] q 283558052 (4.23 GB), kns 2254557 (86.00 MB), total 4.31 GB
20240220 10:56:47 [INFO] par: threads 8/8, completed 16/800
20240220 10:56:48 [INFO] ws.q 271942406 (4.05 GB), ws.q2 125376773 (1.87 GB), kns 2254557 (86.00 MB), total 6.00 GB, deepening...
20240220 10:56:49 [INFO] par: threads 8/8, completed 132/800
20240220 10:56:51 [INFO] par: threads 8/8, completed 279/800
20240220 10:56:55 [INFO] par: threads 8/8, completed 616/800
20240220 10:56:57 [INFO] Deepened ws.q 271942406 => 119410804, foresight 2 in 9.137599005s
20240220 10:56:58 [INFO] par: threads 8/8, completed 21/800
20240220 10:56:59 [INFO] Deepened ws.q2 125376773 => 99889783, foresight 1 in 1.280879899s
20240220 10:56:59 [INFO] Rebuilt kns from 2254557 to 1313478 (1 roots) in 504.864938ms
20240220 10:56:59 [INFO] Deepening pass 6.00 GB => 3.32 GB completed in 10.923722123s
20240220 10:57:00 [INFO] par: threads 8/8, completed 46/800
20240220 10:57:02 [INFO] ws.q 109709563 (1.63 GB), ws.q2 290024850 (4.32 GB), kns 1313478 (50.11 MB), total 6.01 GB, deepening...
20240220 10:57:03 [INFO] par: threads 8/8, completed 206/800
20240220 10:57:05 [INFO] par: threads 8/8, completed 533/800
20240220 10:57:07 [INFO] Deepened ws.q 109709563 => 109709563, foresight 3 in 4.569973039s
20240220 10:57:08 [INFO] par: threads 8/8, completed 20/800
20240220 10:57:10 [INFO] par: threads 8/8, completed 61/800
20240220 10:57:10 [INFO] Deepened ws.q2 290024850 => 257644432, foresight 2 in 3.307265308s
20240220 10:57:11 [INFO] Rebuilt kns from 1313478 to 1313478 (1 roots) in 799.642034ms
20240220 10:57:11 [INFO] Deepening pass 6.01 GB => 5.52 GB completed in 8.677362606s
20240220 10:57:11 [INFO] ws.q 108617316 (1.62 GB), ws.q2 291052226 (4.34 GB), kns 1313478 (50.11 MB), total 6.00 GB, deepening...
20240220 10:57:12 [INFO] par: threads 8/8, completed 95/800
20240220 10:57:14 [INFO] par: threads 8/8, completed 141/800
20240220 10:57:18 [INFO] par: threads 8/8, completed 324/800
20240220 10:57:25 [INFO] Deepened ws.q 108617316 => 50094743, foresight 4 in 13.666118979s
20240220 10:57:26 [INFO] par: threads 8/8, completed 8/800
20240220 10:57:28 [INFO] par: threads 8/8, completed 23/800
20240220 10:57:32 [INFO] par: threads 8/8, completed 53/800
20240220 10:57:33 [INFO] Deepened ws.q2 291052226 => 127615515, foresight 3 in 8.371579712s
20240220 10:57:34 [INFO] Rebuilt kns from 1313478 to 788948 (1 roots) in 458.28309ms
20240220 10:57:34 [INFO] Deepening pass 6.00 GB => 2.68 GB completed in 22.496539549s
20240220 10:57:35 [INFO] par: threads 8/8, completed 96/800
20240220 10:57:37 [INFO] par: threads 8/8, completed 164/800
20240220 10:57:38 [INFO] ws.q 37157625 (566.98 MB), ws.q2 363758054 (5.42 GB), kns 788948 (30.10 MB), total 6.00 GB, deepening...
20240220 10:57:39 [INFO] par: threads 8/8, completed 272/800
20240220 10:57:41 [INFO] par: threads 8/8, completed 321/800
20240220 10:57:45 [INFO] par: threads 8/8, completed 484/800
20240220 10:57:53 [INFO] par: threads 8/8, completed 704/800
20240220 10:57:56 [INFO] Deepened ws.q 37157625 => 4799068, foresight 5 in 18.082256259s
20240220 10:57:57 [INFO] par: threads 8/8, completed 0/800
20240220 10:57:59 [INFO] par: threads 8/8, completed 14/800
20240220 10:58:03 [INFO] par: threads 8/8, completed 23/800
20240220 10:58:11 [INFO] par: threads 8/8, completed 46/800
20240220 10:58:25 [INFO] Deepened ws.q2 363758054 => 40221562, foresight 4 in 28.851239426s
20240220 10:58:25 [INFO] Rebuilt kns from 788948 to 211733 (1 roots) in 100.597466ms
20240220 10:58:25 [INFO] Deepening pass 6.00 GB => 695.04 MB completed in 47.034439556s
20240220 10:58:26 [INFO] Completed BFS step to depth 10 (LGolDepth { r1ld8: 4 })
20240220 10:58:26 [DEBUG] Firstest:
20240220 10:58:26 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:58:26 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:58:26 [DEBUG] |  ....... |  ....... |  ....... | .......  | .....*.  |
20240220 10:58:26 [DEBUG] |  ....... |  ....... |  ....... | ....***  | ....???  |
20240220 10:58:26 [DEBUG] Random partial:
20240220 10:58:26 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:58:26 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 10:58:26 [DEBUG] |  ...*.** |  ....... |  ....... | ..*....  | ..*....  |
20240220 10:58:26 [DEBUG] |  .*..... |  .*.*..* |  ***.*.* | .*.*.**  | .*.*???  |
20240220 10:58:26 [INFO] q 60135757 (917.60 MB), kns 211733 (8.08 MB), total 925.68 MB

Please give the pushed branch a spin. As-is it's only staggered envelopes but I believe it should be enough to get a sense of whether or not LGOL has any shot of completing what you want. If you decide you like what you see, just let me know and I will dig into implementing some hacks to limit some cells to zero and thereby allow unstaggered envelope searches.

EDIT:

I sketched a pretty sloppy version of unstaggered windows (pushed as 20240220-2c5-min-height-unstaggered). It integrates as what LGOL calls a "constraint" which is maybe mid-way through the process. Earlier would likely perform better but to do any earlier involves wading into super complex table precompilation code which I would really rather not do. Later (as some sort of post-expansion filter) would not really be any easier and would likely perform materially worse anyway.

Due to being somewhat generic the numbers are maybe off by one from what you'd expect. It runs a normal LGOL search which is staggered but then restricts all generations to have the intersection of their X coordinate windows. So e.g. If you run `cargo run --release 07` it shows this:

Code: Select all

20240220 12:10:32 [INFO] Stagger constraint:
20240220 12:10:32 [INFO] |  ??????. |  ??????. |  ??????. | .??????  | .??????  |

You can see each generation is still 7 wide but it's indicating it's going to force one cell on one edge or the other off when it gets there, making this unstaggered height 6. This is sufficiently generic that it should work for any wacky choice of s2s geometry, but that delta between staggered and unstaggered may vary. You can always read this "Stagger constraint:" printout to see what it is going to do.

That same search (`cargo run --release 07`) goes on to print as final partials:

Code: Select all

20240220 12:11:37 [INFO] Completed BFS step to depth 63 (LGolDepth { r1ld8: 3 })
20240220 12:11:37 [DEBUG] Firstest:
20240220 12:11:37 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 12:11:37 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 12:11:37 [DEBUG] |  ....... |  ....*.. |  ...**.. | ....**.  | ....*..  |
20240220 12:11:37 [DEBUG] |  ...***. |  ...**.. |  ...**.. | ...*...  | ...*...  |
20240220 12:11:37 [DEBUG] |  ...*... |  ...*... |  ...*... | ...*...  | ..**...  |
20240220 12:11:37 [DEBUG] |  ....... |  ....*.. |  ...**.. | ...**..  | ...**..  |
20240220 12:11:37 [DEBUG] |  ....**. |  ...*.*. |  ...*.*. | .......  | ...**..  |
20240220 12:11:37 [DEBUG] |  ...***. |  ...*.*. |  ..**... | ...*...  | .......  |
20240220 12:11:37 [DEBUG] |  ....... |  ..*.... |  ..*.*.. | ..*..*.  | .**..*.  |
20240220 12:11:37 [DEBUG] |  ..**... |  ..**... |  .*.*... | .**.**.  | ......*  |
20240220 12:11:37 [DEBUG] |  ...*... |  .*.*... |  **.*... | .**.**.  | .*.....  |
20240220 12:11:37 [DEBUG] |  .**.... |  **..... |  ....*.. | ...****  | ..**...  |
20240220 12:11:37 [DEBUG] |  **.***. |  **..**. |  **..**. | ...????  | ???????  |
20240220 12:11:37 [DEBUG] Random partial:
20240220 12:11:37 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 12:11:37 [DEBUG] |  ....... |  ....... |  ....... | .......  | .......  |
20240220 12:11:37 [DEBUG] |  .....*. |  ....... |  ....*.. | ....**.  | ....**.  |
20240220 12:11:37 [DEBUG] |  ....*.. |  ...***. |  ...**.. | ...*..*  | ...*...  |
20240220 12:11:37 [DEBUG] |  ...**.. |  ...*... |  ..**.*. | ...**..  | ...*...  |
20240220 12:11:37 [DEBUG] |  ....**. |  ...*.*. |  ....... | ....**.  | ...***.  |
20240220 12:11:37 [DEBUG] |  .....*. |  .....*. |  ....*.. | .......  | .......  |
20240220 12:11:37 [DEBUG] |  ....*.. |  ....... |  ....... | .......  | .......  |
20240220 12:11:37 [DEBUG] |  ..****. |  ..*..*. |  .**.... | ..**...  | ..***..  |
20240220 12:11:37 [DEBUG] |  ..*..*. |  .**..*. |  .*...*. | ..*.**.  | .**..*.  |
20240220 12:11:37 [DEBUG] |  .*..... |  .*.**.. |  ...**.. | .*..**.  | .*.....  |
20240220 12:11:37 [DEBUG] |  .***.*. |  ***.... |  ****... | ..***..  | .**....  |
20240220 12:11:37 [DEBUG] |  *...... |  ....... |  .....*. | .*.????  | ???????  |
20240220 12:11:37 [INFO] q 184 (2.88 KB), kns 112316241 (4.18 GB), total 4.18 GB

Which is at least a little evidence it's working as expected. I'll leave it to you to experiment and see if anything is within range for your computing and time resources.

[Sokwe]

Thanks! I'll work off of 20240220-2c5-min-height-unstaggered for now, which compiled and ran fine. I have a few very simple questions that you shouldn't bother going into too much detail in answering.

By default the code will assume 2 GB, but you can set, as I have here, e.g. BFS_MEM_GB=6 for 6 GB. Note that this is its internal estimate of memory which is inaccurate to say the least. You may want to experiment with values to see what's right for your computer.

Is there any reason not to give the breadth first search as much memory as I have available? That is, could it run slower with a higher memory setting? (for an example of how this could happen, to simplify qfind, I only used multithreading during the depth first lookahead, so setting the BFS memory too large means qfind never enters the depth first search and so doesn't take advantage of multithreading).

Due to the way LGOL picks bits it's going to require somewhat more expensive precompilation than LLSSS. This precompilation should scale linearly with the height. You can set environment variable LGOL_MAX_TABLE_SIZE to something lower (e.g. 9) if you want it to generate smaller tables (quicker to generate, slower to run).

Just to be clear, the "precompilation" refers to runtime-calculated tables, rather than compiled code, right? Or do I have to change the code and recompile for different heights?

Due to being somewhat generic the numbers are maybe off by one from what you'd expect.

Does this mean I need to run `cargo run --release 11` to eliminate height 10?

[amling]

Is there any reason not to give the breadth first search as much memory as I have available? That is, could it run slower with a higher memory setting? (for an example of how this could happen, to simplify qfind, I only used multithreading during the depth first lookahead, so setting the BFS memory too large means qfind never enters the depth first search and so doesn't take advantage of multithreading).

The short answer is I would give it all the memory you got. I can think of at least a few ways it could be slower, but I think on the whole bigger is better and I have always run all my searches on computers where I have ~60 GB with "48 GB" limits.

One way is smaller working set is better and for searches that are not at their worst bottleneck most of memory is full of useless tree that could be cleaned up, but we don't garbage collect these things until we hit the memory ceiling.

Another is that less memory means more DFS pruning and the DFS pruning's handling of cycles is different and while in some ways it's worse, in some ways it could be better. The main BFS search's check for cycles is an expensive hash lookup in a hash we maintain of the path of nodes we're currently expanding while for the DFS pruning search we just don't worry about it and let cycles be found repeatedly until they hit the depth limit and fail the prune.

Due to the way LGOL picks bits it's going to require somewhat more expensive precompilation than LLSSS.

Just to be clear, the "precompilation" refers to runtime-calculated tables, rather than compiled code, right? Or do I have to change the code and recompile for different heights?

Yeah, it's all runtime "precompilation" of the tables that drive the CA checks. I just mean to say don't be alarmed if it takes a long time to start up before it starts outputting the first partials. If you find that table computation too slow you can tune it.

Due to being somewhat generic the numbers are maybe off by one from what you'd expect.

Does this mean I need to run `cargo run --release 11` to eliminate height 10?

Yeah, with that it should output that "Stagger constraint:" display with ten question marks in each generation.

[Sokwe]

The main BFS search's check for cycles is an expensive hash lookup in a hash we maintain of the path of nodes we're currently expanding while for the DFS pruning search we just don't worry about it and let cycles be found repeatedly until they hit the depth limit and fail the prune.

This cycle elimination makes me wonder, could LGOL potentially be used with little to no modification to eliminate the possibility of an unstaggered height-8 (2,0)c/6 ship? There is a known height-9 ship, and at height 7, a 2c/6 search with Nicolay's WLS 6.3 returns 5 ships, all with period 3. However, at height 8 there are infinitely many p3 ships, and WLS 6.3 has no cycle elimination, so it can't rule out the possibility of a p6 ship.

I would consider this 2c/6 search more important than reaffirming old results.

[amling]

The main BFS search's check for cycles is an expensive hash lookup in a hash we maintain of the path of nodes we're currently expanding while for the DFS pruning search we just don't worry about it and let cycles be found repeatedly until they hit the depth limit and fail the prune.

This cycle elimination makes me wonder, could LGOL potentially be used with little to no modification to eliminate the possibility of an unstaggered height-8 (2,0)c/6 ship? There is a known height-9 ship, and at height 7, a 2c/6 search with Nicolay's WLS 6.3 returns 5 ships, all with period 3. However, at height 8 there are infinitely many p3 ships, and WLS 6.3 has no cycle elimination, so it can't rule out the possibility of a p6 ship.

I would consider this 2c/6 search more important than reaffirming old results.

"Could" and "are you gonna like it" are not always the same question... you can definitely run that search and in a theoretical sense it should be finite and terminate[able]. The problems are (a) it may take a very, very long time, and (b) its notion of separation is only the strongest, namely two full rows of zeros, and so it's going to output possibly quite a fountain of useless combinations of the known ships barely brushing up against each other.

If you change "(-2, 0, 5)" to "(-2, 0, 6)" in src/entry.rs on the 2c/5 unstaggered branch it should be ready to go to do this search (for 2c/6 the unstaggered envelope size and program argument will be off by one so `cargo run --release 09` for 8 unstaggered height). I would advise running smaller heights first to see how long they take and to see how you feel about the uselessly duplicated output.

EDIT:

I completed unstaggered height 6 just to test this and it took about an hour on my very highly-loaded laptop with `BFS_MEM_GB=6`. Even from just the one ship it finds 11 "ends" or "cycles" that to human eyes are clearly recombinations of the one ship, but in LGOL's technical sense are all valid/distinct paths/cycles in the graph of 2-row states. As an example the longest partial was this:

Code: Select all

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

Technically each slice of 2 rows is unique and nonzero, but it's obviously silly. I assume by width 8 it's going to be an avalanche of this crud. If you do go on to run width 8 and you want to figure out "was there any non-c/3 stuff in this log file", that is probably something a little shell scripting and `grid-tool pd-fold 2c6-s2s 2` can do the hard work on. I guess let me know when/if you go there.

[Sokwe]

it's going to output possibly quite a fountain of useless combinations of the known ships barely brushing up against each other....

As an example the longest partial was this:

Code: Select all

...

Technically each slice of 2 rows is unique and nonzero

Does it only check if the current partial result has a cycle, and not whether the latest 2-row block added was already seen in the overall graph of all partial results? It would seem that graph-wide duplicate row elimination would prevent it from finding two ships right next to each other. Of course, it would need to not drop any unique part of the graph in the current partial result that precedes the duplicate rows.

qfind gives an example of how not to do things. I think I've explained this before, but if qfind sees a new 2-full-rows chunk that's already in the graph, it discards that branch. Unfortunately, even though that branch was currently at a previously seen state, some earlier part of the branch might not have occurred in any other part of the graph. Thus qfind basically can't find pushalongs, as their back end is a spaceship that would have already showed up earlier in the search.

I don't really know how LGOL works, so I don't know if this could be reasonably or even possibly implemented. It's very low priority, anyway. The discussion you're having with David Bell is much more important. I could probably write a qfind-like search that could accomplish my goal in this case. I might do that if nobody else finds a way to eliminate 2c/6 height-8 anytime soon.

[amling]

it's going to output possibly quite a fountain of useless combinations of the known ships barely brushing up against each other....

As an example the longest partial was this:

Code: Select all

...

Technically each slice of 2 rows is unique and nonzero

Does it only check if the current partial result has a cycle, and not whether the latest 2-row block added was already seen in the overall graph of all partial results? It would seem that graph-wide duplicate row elimination would prevent it from finding two ships right next to each other. Of course, it would need to not drop any unique part of the graph in the current partial result that precedes the duplicate rows.

qfind gives an example of how not to do things. I think I've explained this before, but if qfind sees a new 2-full-rows chunk that's already in the graph, it discards that branch. Unfortunately, even though that branch was currently at a previously seen state, some earlier part of the branch might not have occurred in any other part of the graph. Thus qfind basically can't find pushalongs, as their back end is a spaceship that would have already showed up earlier in the search.

I don't really know how LGOL works, so I don't know if this could be reasonably or even possibly implemented. It's very low priority, anyway. The discussion you're having with David Bell is much more important. I could probably write a qfind-like search that could accomplish my goal in this case. I might do that if nobody else finds a way to eliminate 2c/6 height-8 anytime soon.

What LGOL has, or is possibly close to having:

What LGOL calls "cycle" detection only finds 2 row slices that are a parent in the tree and thus form, well, a cycle. I have never wanted to not detect and prune these (as they're guaranteed to be repeatable forever) although I have occasionally deleted the printing out of them for searches where they are numerous and not helpful.

LGOL has a feature called "deduplication" where it will track globally and forever certain slices it has seen and refuse to enter them (a second time). By default this is off, or rather is enabled for no slices. I have occasionally used it configured with all slices but this tends to balloon up and occupy a lot of memory that it will never release. More often I have used it with some subset of slices big enough to split the graph up somewhat, but small enough to not take up too much memory. As an example, I have certainly had it save all reduced period slices, and that is something we might try here (saving all strict c/3 slices in this 2c/6 search). This feature (in any form) is not something I remember using a lot and the only win for it I can remember offhand is the search for the zebra stripes space clearer 5c/5 corner.

I have had at one time or another a fairly hacked-up branch where it would refuse to enter a slice that was present elsewhere in the tree still in consideration (which I seem to recall being told is what e.g. gfind does), but this has never been cleaned up and shipped in any form. I don't even recall if I ever used it in a successful search for anything.