qfind - a spaceship search program

[Sokwe]

That's a good sign, although the true measure will be on longer searches than the VM's test searches.

The thing is, since a few improvements were implemented to get an overall 5-15% speedup, it's hard to tell whether the new lookup tables actually had a significant effect on the speed, plus there's all sorts of noise from these searches... I could run a few benchmarks, maybe.

Unfortunately on a quick test with 3c/7 logical-width-10 odd-symmetric, the original high-memory style with "--tables pair" is a bit over twice as fast as the low-memory two-table version with "--tables factored". But the memory saving means it could be used at much higher widths. I wonder if explaining or giving it gfind's De Bruijn graph code could help it intuit a better way to connect the two half-row tables.

[LuveelVoom]

Unfortunately on a quick test with 3c/7 logical-width-10 odd-symmetric, the original high-memory style with "--tables pair" is a bit over twice as fast as the low-memory two-table version with "--tables factored". But the memory saving means it could be used at much higher widths. I wonder if explaining or giving it gfind's De Bruijn graph code could help it intuit a better way to connect the two half-row tables.

Hmm. I will remind myself to try this when I get credits back, since that sounds like that would be a significant speedup.

[Sokwe]

Unfortunately on a quick test with 3c/7 logical-width-10 odd-symmetric, the original high-memory style with "--tables pair" is a bit over twice as fast as the low-memory two-table version with "--tables factored". But the memory saving means it could be used at much higher widths. I wonder if explaining or giving it gfind's De Bruijn graph code could help it intuit a better way to connect the two half-row tables.

Hmm. I will remind myself to try this when I get credits back, since that sounds like that would be a significant speedup.

I wouldn't get your hopes too high. It just might be worth asking it to be a bit more clever in some way with recombining the rows from the "factored" table. Ultimately, breaking the table into two halves is naturally going to make qfind do more work during the search. It's still a lot faster than some other programs, and it might be substantially useful in other rules where qfind is the ideal program but is limited by width.

If you want, I can try the 16->32 bit transition with the AI when I get credits back, since it seems like it would be faster for an AI to do a bulk slight-variation replacement task than a human.

This change isn't really necessary at this point, as it's something that could be done probably pretty much any time in the process, and it confers little advantage unless one wants to search at logical width greater than 14. Generally, qfind excels over other methods at high periods, and at high periods a width-15 search is generally isn't going to be viable. There are probably a few use cases, but again, this change can be made later. It might be best to limit the changes for now so I don't get lost in the differences as I try to understand the proposed modifications.

I'm most interested in the two ideas I suggested earlier:

1. Fix the gcd > 1 bug when using hashing without resorting to just a simple phase-matching requirement (which makes gcd > 1 searches take longer than they really should)
2. Change the tree structure and row hashing so that it doesn't throw out viable parts of the graph when it detects a duplicate node (so, e.g., it doesn't throw out tagalongs).

I suspect the first idea would be more difficult for the AI than the second, but who knows?

[LuveelVoom]

As a demo of this new tech, this partial took about 0.8 kiloseconds (13 minutes) to find on my machine, peak memory usage around 100 megabytes, with the command ./qfind -r B3/S23-q4i -v 3c/7 -w 12 -s o -f 1:

By the way, w12o max 3c/7o partial:

Code: Select all

x = 21, y = 35, rule = B3/S23-q4i
6b2o5b2o$7b2o3b2o$5b3o5b3o$4b2o9b2o$8bo3bo$4b6ob6o$4b2o2bo3bo2b
2o$4bo11bo$8bo3bo$5bo2bo3bo2bo$5bobo5bobo$6b3o3b3o$3b2o2bo5bo2b2o
$3b3ob2o3b2ob3o$3bob4o3b4obo2$5bo9bo$2b4obo5bob4o$bob2ob3o3b3ob2o
bo$o8bobo8bo$o3b2o3bobo3b2o3bo$o4bob2o3b2obo4bo$bo4bo7bo4bo$bo6b
o3bo6bo$3ob2o3bobo3b2ob3o$3b5obobob5o$2b2obo3bobo3bob2o$9bobo$3o
2b3o2bo2b3o2b3o$2o3b3o5b3o3b2o$b3o4bo3bo4b3o$3b2obo3bo3bob2o$3bo
5b3o5bo$4b2obob3obob2o$3bo2bo7bo2bo!

Now when I turned off factored tables, it hit 30 gigabytes of ram at depth 4, and I terminated it there since it didn't hit the next step within 10 minutes.

Factored tables might be "slower", but it was faster in this case since the search was... slowed down a bit... having to access 30 gigabytes of ram constantly.

[Sokwe]

As a demo of this new tech, this partial took about 0.8 kiloseconds (13 minutes) to find on my machine, peak memory usage around 100 megabytes, with the command ./qfind -r B3/S23-q4i -v 3c/7 -w 12 -s o -f 1:
...
Factored tables might be "slower", but it was faster in this case since the search was... slowed down a bit... having to access 30 gigabytes of ram constantly.

Width-12 searches for most speeds in most rules will peak at over 64 GB of RAM, so very few people can run them without dipping into virtual memory to make up for the lack of RAM. Once virtual memory starts being used, the search slows down enormously. So the factored tables will be a great help. Even with a 50% - 60% slow down, it should still be faster than any other search for finding many long ships or dealing with search spaces with repeating components. The LLM version defaults to the factored table for widths 10 and above, but I would have width-10 searches default to the non-factored table, as they tend to take less than 2 GB, which is manageable on almost any modern computer.

My prioritization right now is

1. Bug fixes
2. Understanding the faster lookAhead() function
3. Understanding the smaller table generation
4. Implementing the optional factored tables
5. Refactoring the entire code base

This may change as I work through these things or if you provide some new version.

Thanks again for doing this. It's certainly a fascinating exercise that looks like it will provide noticeable improvements to qfind.

[LuveelVoom]

Width-12 searches for most speeds in most rules will peak at over 64 GB of RAM, so very few people can run them without dipping into virtual memory to make up for the lack of RAM. Once virtual memory starts being used, the search slows down enormously. So the factored tables will be a great help. Even with a 50% - 60% slow down, it should still be faster than any other search for finding many long ships or dealing with search spaces with repeating components.

Scary to think that with these new improvements the width 14 cap might actually become relevant... I assume the refactoring stuff will include the 16->32 transition?

Edit: Searches at widths 13 and 14 sometimes produce these errors:

Screenshot 2026-10-10 at 9.24.57 AM.png (361.44 KiB) Viewed 68 times

Does this indicate that the search has become nonexhaustive?

[Sokwe]

Searches at widths 13 and 14 sometimes produce these errors:
...
Does this indicate that the search has become nonexhaustive?

No, this is a safeguard in case a bug occurs, but it only discards depth-first extension rows, so it doesn't impact the exhaustiveness of the search. That being said, it shouldn't ever do this, and the fact that it does indicates there is a bug. What was the search command that caused this to happen? Of course if it's in a width 13 or 14 search I have no way to tell if the bug is present in the original or only in the LLM-modified version.

The problem here is that when it saves the depth-first extension rows, it has to keep a separate list of pointers to these rows that is aligned with the search queue. During doCompact(), the search queue gets repacked, so the list of pointers to the extension rows also needs to be repacked to match. Something is apparently going wrong either there or when the extension rows are being saved.

I actually would rather the tree implementation be changed so that the pointer to the extension rows is an intrinsic part of the queue nodes. This would be part of the overhaul that would allow it to cover the whole search space and not throw out pushalongs. While the gfind tree/queue implementation that qfind currently uses is quite clever, it's not appropriate for this feature and needs to be replaced. However, I've never been sure what the ideal replacement would look like, resulting in a bit of decision paralysis for me. The AI might have some ideas in this regard.

[LuveelVoom]

No, this is a safeguard in case a bug occurs, but it only discards depth-first extension rows, so it doesn't impact the exhaustiveness of the search. That being said, it shouldn't ever do this, and the fact that it does indicates there is a bug. What was the search command that caused this to happen? Of course if it's in a width 13 or 14 search I have no way to tell if the bug is present in the original or only in the LLM-modified version.

The search command in this case was ./qfind -r B3/S23-a5 -v 2c/5 -w 13 -s o.

Additionally, the AI has managed to pull together a version with some magic change that makes it way faster at higher widths (./qfind -r B3/S23-q4i -v 3c/7 -w 13 -s o seems to be about 5 times faster). It is attached. (Again, I don't know if it's exhaustive). This is probably the end of development because my family is sliiiightly upset that I've been burning all of their usage on the family account

[Sokwe]

This is probably the end of development because my family is sliiiightly upset that I've been burning all of their usage on the family account

After I implement these suggested improvements, we might be able to find a way to more judiciously use the AI, if your family is willing and you're still up for it. Give it a few weeks, maybe a few months. There's no rush. It's going to take me a while to sift through all this, but I definitely intend to implement the improved lookAhead(), smaller tables, and factored tables, assuming I find no bugs. Thanks again.

[LuveelVoom]

Demonstration of these new changes:

w13o max 3c/7 partial.

Code: Select all

x = 25, y = 22, rule = B3/S23-q4i
4b2o13b2o$3b2o15b2o$4b3o11b3o$6b2o4bo4b2o$3bo7bobo7bo$2b6o2bo3bo2b6o$
2b2o2b2o3bobo3b2o2b2o$2b2o3b2ob5ob2o3b2o$3bo4b2o5b2o4bo$4b2o3bo5bo3b2o
$5bo13bo$5b2o11b2o$4bo15bo$3bo2bo11bo2bo$2bo2b2ob2o5b2ob2o2bo$6bo3bo3b
o3bo$2bo2b2o2bo5bo2b2o2bo$2bo2b4o7b4o2bo$6bob2o5b2obo$2bobo2bo9bo2bob
o$3o4b2o7b2o4b3o$o3b2o3bo5bo3b2o3bo!

3.2ks (54 minutes), peak ram 370 megabytes.

Might be worth doing that 16->32 move.


Edit: Wait, it's smaller. Is that bad? Shouldn't it be larger?