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 171 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?

[Sokwe]

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!

it's smaller. Is that bad? Shouldn't it be larger?

It should probably be longer than the longest at the lower width, although if the search ends with "-> 0/0" it could fail to print the true longest partial as mentioned here. Can you post the full output of both searches?

[LuveelVoom]

It should probably be longer than the longest at the lower width, although if the search ends with "-> 0/0" it could fail to print the true longest partial as mentioned here. Can you post the full output of both searches?

Aha, it did end with -> 0/0. That explains it.

By the way, here's a new version, which has a supposed additional speed increase option under some circumstances. To avoid filling the credit buffer, I told it to do minimal testing, so this probably has all sorts of problems.

Seems to be about a 30% increase. It claims it is incompatible with the above speed boost, though. (from my testing, the change is faster up to around w11, where they are approximately tied, and the previous method overtakes it around w12.)

Sorry for spamming these... I'm feeling a little guilty for getting it to make changes I barely understand, and ergo not writing the changelogs, which goes against my philosophy of "don't do any writing with AI". I suppose these are just implementations of ideas for you to look at rather than final results, though. (I am going to personally write the guides for partial-cutter and ntcatforce+).


Edit: I'm throwing some different ideas at it, in case another breakthrough similar to the memory change shows up; it probably won't, though...

Edit 2: Nope, it didn't.

[otismo]

can anyone please convert this python script to lua

Code: Select all

import golly as g

letters = g.parse("""2bobobo2bobo4bo3b2o5bo4bo2bobo4bo20bo$2bobobo2bobo3b4ob2o2bobobo3bobo
3bobobobo3bo14bo$2bo5b5obo8bo2bobo5bo3bo2b3o4bo13bo$2bo6bobo3b3o4bo4bo
6bo3bobobobob5o4b3o4bo$2bo5b5o5bo2bo4bobobo3bo3bo3bo5bo13bo$9bobo2b4o
2bo2b2obo2bo4bo3bo9bo12bo$2bo6bobo4bo6b2o2b2obo4bobo15bo5bobo$52bo3$b
3o3bo3b3o3b3o5bo2b5o2b3o2b5o2b3o3b3o26b3o$o3bob2o2bo3bobo3bo3b2o2bo5bo
3bo5bobo3bobo3bo9b2o7b2o4bo3bo$o3bo2bo6bo5bo2bobo2bo5bo8bo2bo3bobo3bo
7b2o3b5o3b2o6bo$obobo2bo5bo4b2o2bo2bo3b3o2b4o5bo3b3o3b4obo2bobo15bo4bo
$o3bo2bo4bo7bob5o5bobo3bo3bo3bo3bo5bo7b2o3b5o3b2o4bo$o3bo2bo3bo4bo3bo
4bo2bo3bobo3bo3bo3bo3bobo3bo9b2o7b2o$b3o2b3ob5o2b3o5bo3b3o3b3o4bo4b3o
3b3o2bo2bo21bo$60bo3$2b2o4bo3b4o3b3o2b3o3b5ob5o2b3o2bo3bob3ob5obo3bobo
5bo5bobo3bo2b3o$bo2bo2bobo2bo3bobo3bobo2bo2bo5bo5bo3bobo3bo2bo5bo2bo2b
o2bo5b2o3b2ob2o2bobo3bo$o2b2obo3bobo3bobo5bo3bobo5bo5bo5bo3bo2bo5bo2bo
bo3bo5bobobobobobobobo3bo$obobobo3bob4o2bo5bo3bob4o2b4o2bob2o2b5o2bo5b
o2b2o4bo5bobobobobobobobo3bo$o2b2ob5obo3bobo5bo3bobo5bo5bo3bobo3bo2bo
5bo2bobo3bo5bo2bo2bobobobobo3bo$bo4bo3bobo3bobo3bobo2bo2bo5bo5bo3bobo
3bo2bo2bo2bo2bo2bo2bo5bo5bobo2b2obo3bo$2b3obo3bob4o3b3o2b3o3b5obo6b3o
2bo3bob3o2b2o3bo3bob5obo5bobo3bo2b3o4$4o3b3o2b4o3b3o2b5obo3bobo3bobo5b
obo3bobo3bob5ob2obo3b2o3bo$o3bobo3bobo3bobo3bo3bo3bo3bobo3bobo2bo2bobo
3bobo3bo5bobo2bo4bo2bobo$o3bobo3bobo3bobo7bo3bo3bobo3bobo2bo2bo2bobo2b
o3bo4bo2bo3bo3bobo3bo$4o2bo3bob4o3b3o4bo3bo3bo2bobo2bobobobo3bo4bobo4b
o3bo3bo3bo$o5bo3bobobo7bo3bo3bo3bo2bobo2bobobobo2bobo4bo4bo4bo3bo3bo$o
5bo2bo2bo2bo2bo3bo3bo3bo3bo3bo4bo3bo2bo3bo3bo3bo5bo4bo2bo$o6b2obobo3bo
2b3o4bo4b3o4bo4bo3bo2bo3bo3bo3b5ob2o3bob2o7b5o4$o8bo15bo9b2o7bo5bo3bob
o4bo$bo7bo15bo8bo9bo11bo4bo$4b3o2bob2o3b3o3b2obo2b3o2b4o2b2obobob2o2bo
3bobo2bobo2bobob2o2bob2o3b3o$3bo3bob2o2bobo3bobo2b2obo3bo2bo3bo2b2ob2o
2bobo3bobobo2bo2b2obo2bob2o2bobo3bo$3bo3bobo3bobo5bo3bob5o2bo3bo3bobo
3bobo3bob2o3bo2bo2bo2bobo3bobo3bo$3bo2b2ob2o2bobo3bobo2b2obo6bo3bo2b2o
bo3bobo3bobobo2bo2bo2bo2bobo3bobo3bo$4b2obobob2o3b3o3b2obo2b3o3bo4b2ob
obo3bobo3bobo2bo2bobo2bo2bobo3bo2b3o$42bo11bo$39b3o10b2o2$24bo41bobobo
$24bo40bo2bo2bo$ob2o3b2obobob2o2b4ob4obo3bobo3bobo3bobo3bobo3bob5o2bo
2bo2bo3bo2bo$2o2bobo2b2ob2o3bo6bo3bo3bobo3bobobobo2bobo2bo3bo4bo2bo3bo
3bobobobo$o3bobo3bobo5b3o3bo3bo3bo2bobo2bobobo3bo3bo3bo3bo4bo2bo2bo2bo
2bo$2o2bobo2b2obo8bo2bo3bo2b2o2bobo2bobobo2bobo2bo2b2o2bo5bo2bo2bo$ob
2o3b2obobo4b4o4b2o2b2obo3bo4bobo2bo3bo2b2obob5o3bobobo$o9bo45bo$o9bo
42b3o!""")
ltuples = tuple(zip(*[iter(letters)]*2))
lpositions = {' ': (0, 0, 1), '!': (2, 0, 1), '"': (4, 0, 3), '#': (8, 0, 5), '$': (14, 0, 5), '%': (20, 0, 5), '&': (26, 0, 5), "'": (32, 0, 1), '(': (34, 0, 2), ')': (37, 0, 2), '*': (40, 0, 5), '+': (46, 0, 5), ',': (52, 0, 2), '-': (55, 0, 3), '.': (59, 0, 1), '/': (61, 0, 3), '0': (0, 10, 5), '1': (6, 10, 3), '2': (10, 10, 5), '3': (16, 10, 5), '4': (22, 10, 5), '5': (28, 10, 5), '6': (34, 10, 5), '7': (40, 10, 5), '8': (46, 10, 5), '9': (52, 10, 5), ':': (58, 10, 1), ';': (60, 10, 2), '<': (63, 10, 5), '=': (69, 10, 5), '>': (75, 10, 5), '?': (81, 10, 5), '@': (0, 20, 5), 'A': (6, 20, 5), 'B': (12, 20, 5), 'C': (18, 20, 5), 'D': (24, 20, 5), 'E': (30, 20, 5), 'F': (36, 20, 5), 'G': (42, 20, 5), 'H': (48, 20, 5), 'I': (54, 20, 3), 'J': (58, 20, 5), 'K': (64, 20, 5), 'L': (70, 20, 5), 'M': (76, 20, 7), 'N': (84, 20, 5), 'O': (90, 20, 5), 'P': (0, 30, 5), 'Q': (6, 30, 5), 'R': (12, 30, 5), 'S': (18, 30, 5), 'T': (24, 30, 5), 'U': (30, 30, 5), 'V': (36, 30, 5), 'W': (42, 30, 7), 'X': (50, 30, 5), 'Y': (56, 30, 5), 'Z': (62, 30, 5), '[': (68, 30, 2), '\\': (71, 30, 3), ']': (75, 30, 2), '^': (78, 30, 5), '_': (84, 30, 5), '`': (0, 40, 2), 'a': (3, 40, 5), 'b': (9, 40, 5), 'c': (15, 40, 5), 'd': (21, 40, 5), 'e': (27, 40, 5), 'f': (33, 40, 4), 'g': (38, 40, 5), 'h': (44, 40, 5), 'i': (50, 40, 1), 'j': (52, 40, 3), 'k': (56, 40, 4), 'l': (61, 40, 2), 'm': (64, 40, 7), 'n': (72, 40, 5), 'o': (78, 40, 5), 'p': (0, 50, 5), 'q': (6, 50, 5), 'r': (12, 50, 4), 's': (17, 50, 5), 't': (23, 50, 4), 'u': (28, 50, 5), 'v': (34, 50, 5), 'w': (40, 50, 5), 'x': (46, 50, 5), 'y': (52, 50, 5), 'z': (58, 50, 5), '{': (64, 50, 3), '|': (68, 50, 1), '}': (70, 50, 3), '~': (74, 50, 5)}

g.show("Click to start typing from that point")
while True:
    event = g.getevent()
    if event.startswith("click"):
        _, xs, ys, _, _ = event.split()
        ocx = cx = int(xs)
        cy = int(ys)
        break
    else:
        g.doevent(event)
g.getevent(False)

for c in g.getstring("Enter text:"):
    if c == '\n':
        cy += 10
        cx = ocx
        continue
    lx, ly, width = lpositions[c]
    clist = [(xi-lx, yi-ly) for (xi, yi) in ltuples if lx <= xi < lx+width and ly <= yi < ly+9]
    clist = [z for t in clist for z in t]
    g.putcells(clist, cx, cy)
    cx += width+1

Thank You !

[LuveelVoom]

Hmm, I've never seen this before. Is this normal? Or is this a bug with my program?

Screenshot 2026-10-10 at 8.50.51 PM.png (147.03 KiB) Viewed 39 times

...and suddenly, qfind switched from 13 threads to 1?
...and stopped outputting anything? EDIT: Nope... it just outputted this:

Code: Select all

10/10/26 20:42:52 Queue full, depth 164, deepening 136, 4.1k/11k -> 1/689  [5201.0s, peak mem 270 MB, tables+index 35 MB]

Weird.

Attached is the most recent file.

EDIT 2: It just completed. However, it completed with -> 0/0, so I have no clue if this is the longest partial; it's w23o 3c/8o. Tsk. Anyone up for running from the last save (it will only open w the custom build above) and seeing if they can get the actual longest partial?

Code: Select all

x = 21, y = 21, rule = B3/S23
10bo$9b3o$8b5o$7bo2bo2bo$8b5o2$8bo3bo$b3o4bo3bo4b3o$b3o3b2o3b2o
3b3o$bo2bob2obobob2obo2bo$2b2o5bobo5b2o$2bo2b3obobob3o2bo$2b3o3b
o3bo3b3o$5bo3bobo3bo$2bobo3bo3bo3bobo$2bob4obobob4obo$2b3o3b2ob2o
3b3o$2b3obo7bob3o$2b2o3b3ob3o3b2o$bo6bo3bo6bo$3o15b3o!

This -> 0/0 bug keeps popping up.

EDIT 3: Here is a version which supposedly has the bug fixed. I'm rerunning it right now. It should complete in around 30 minutes; if so, we will have the longest w23o 3c/8 partial, as long as this version of qfind is exhaustive (which it may not be, so nobody go updating SSSP!)

EDIT 4: Aha!

Code: Select all

x = 23, y = 36, rule = B3/S23
9b5o$9b5o$8bo5bo2$7bo2bobo2bo$3bo4b3ob3o4bo$3b3o3b5o3b3o$2bo4bo
7bo4bo$4b2obo2b3o2bob2o$3bo5b2ob2o5bo$4b3obobobobob3o$10bobo$4bo
b5ob5obo$3b2o4bo3bo4b2o$4b2obobo3bobob2o$3b2obo2bo3bo2bob2o$9b2o
b2o$2bo4bo7bo4bo$2bo17bo$2b2o5b2ob2o5b2o$5bob2o5b2obo$2b5o9b5o$b
o4bo9bo4bo$b5o11b5o$bo5bo7bo5bo$4b3obo5bob3o$4o4b2o3b2o4b4o$3o5b
2o3b2o5b3o$bo5b3o3b3o5bo$2b2o4b2o3b2o4b2o$5bo4b3o4bo$o3bo2b2o5b2o
2bo3bo$b2obo3bo5bo3bob2o$4b2o4bobo4b2o$b2ob2o11b2ob2o$o5b5ob5o5b
o!

[Sokwe]

Hmm, I've never seen this before. Is this normal? Or is this a bug with my program?
...
...and suddenly, qfind switched from 13 threads to 1?
...and stopped outputting anything? EDIT: Nope... it just outputted this:

Code: Select all

10/10/26 20:42:52 Queue full, depth 164, deepening 136, 4.1k/11k -> 1/689  [5201.0s, peak mem 270 MB, tables+index 35 MB]

The output indicates that only one queue node survived the depth-first pruning. The search could possibly finish checking all other queue nodes, leaving only one thread with anything to do, but this should have triggered the early exit code to leave the deepening step. It's hard to know if this is a result of the LLM modifications or something present in the original, as this is apparently a width 12+ search, so takes more than my 64 GB of RAM with qfind v2.4b.