qfind - a spaceship search program

[NNlk05]

Then why are diagonal searches possible in both of qfind's predecessors (gfind and (nt)zfind)?

As bubblegum said, qfind only supports orthogonal spaceship searches, and I have no intention of adding support for non-orthogonal ships. Based on experiments with zfind, non-orthogonal ship searching with qfind would be slower than the same searches with WLS or ikpx2.

[ThePlayzr]

This should be very easy (and might not even be worth a post, but then it won't happen), but can you make it so all of the 32k/137k -> 2.3k/100k stuff (I don't know what's it really called) are always accurate to 3 digits? It would just make it a lot easier for me to track progress in my slow searches and see better when it is increasing or decreasing.

[NNlk05]

This should be very easy (and might not even be worth a post, but then it won't happen), but can you make it so all of the 32k/137k -> 2.3k/100k stuff (I don't know what's it really called) are always accurate to 3 digits? It would just make it a lot easier for me to track progress in my slow searches and see better when it is increasing or decreasing.

I think the right part is common.h.static void deepen(void):

Code: Select all

   /* report what's happening */
   printf("%d, deepening %d, ", i, deepeningAmount);
   putnum(qTail - qHead);
   printf("/");
   putnum(qTail);
   fflush(stdout);
   

[NNlk05]

I just realized that qfind outputed a prousto-spaceship here:

Updated stamp collection:

Code: Select all

x = 301, y = 286, rule = B34wyz/S2-n3History
8.3D$10.D$8.3D8.A4.AB5.2A266.D$8.D9.BAB2.B2A4.A.A265.B2D$8.3D8.A4.2AB
2.A.B265.BDBD$24.BA3.2A265.4B$192.E.4E.E4.D8.3E2.3E74.4B$117.3E4.D3.3E
8.3E6.3E2.D4.3E5.D5.E8.E5.D3.2E.4E.2E3.D24.D27.D5.3E5.D22.4B$19.A6.A7.
2A80.E3.E3.D2.E2.E7.E2.E5.E2.E2.D3.E3.E4.D4.3E6.3E4.D2.E2.2E2.2E2.E2.
D8.E.E2.E.E8.D27.D7.E5.D21.4B$18.BAB4.BAB5.A2BA5.B2.B2AB2.B64.E3.E3.D
5.E10.E8.E2.D3.E3.E4.D4.E3.4E3.E4.D5.E4.E5.D8.E.E2.E.E8.D27.D6.E6.D20.
4B$17.2A.2A4.A2B3.A4BA3.3AB4AB3A71.D5.E6.E3.E4.E3.E2.D12.D9.2E9.D3.E.
E4.E.E3.D24.D7.3E7.3E7.D13.D19.4B$18.BAB4.2BA4.A4BA4.BA2B2A2BAB64.2E.
2E3.D2.E.E11.E4.E3.E2.D3.2E.2E4.D7.2E2.2E7.D4.E6.E4.D4.3E2.2E2.2E2.3E
4.D4.E.2E2.E5.E2.2E.E4.D13.D17.5B$8.3D8.A6.BAB4.A2BA7.B4.B65.E5.E2.D13.
E.E9.E2.D4.E.E5.D.4E.E6.E.4E.D4.2E4.2E4.D3.2E.3E6.3E.2E3.D2.2E.E.E11.
E.E.2E2.D13.D17.6B$10.D16.A6.2A80.E3.E3.D22.E.E3.D12.D.3E.2E6.2E.3E.D
16.D3.2E14.2E3.D2.2E.2E.3E5.3E.2E.2E2.D13.D16.7B$8.3D113.D28.D12.D3.E
.2E6.2E.E3.D16.D4.E.2E8.2E.E4.D2.5E13.5E2.D13.D16.8B$10.D106.3D4.D28.
D12.D.2E2.2E6.2E2.2E.D16.D6.E10.E6.D27.D3.3D7.D12.2B.B3D6B$8.3D27.4B75.
D6.D28.D12.D.E.2E10.2E.E.D16.D7.E2.3D3.E7.D27.D3.D9.D12.4BD9B$18.A2.A
2BA2.A8.B.4A.B73.D6.D28.D12.D20.D6.3D7.D10.D13.D27.D3.D9.D11.5B2D8B$17.
B4A2B4AB6.4A2.4A72.D6.D10.3D.3D11.D2.3D.3D3.D6.E6.E6.D6.D9.D5.3E2.D5.
3E5.D10.D.D.3D10.D3.D9.D11.6B.5B2CB$18.B3A2B3AB6.AB2AB2.B2ABA71.3D4.D
12.D.D13.D4.D.D5.D3.E2.2E4.2E2.E3.D6.D9.D10.D13.D10.D.D.D12.D3.3D3.2D
2.D10.6B2.3BCB2CB$20.B4.B7.A3B6.3BA77.D10.3D.D13.D2.3D.D5.D20.D6.D9.D
6.E3.3D4.E6.D10.3D.D12.D9.D.D.D9.8B.3B3CB$34.2A8.2A70.5D3.D10.D3.D13.
D4.D.D5.D7.3D.3D6.D6.3D7.D3.3E12.3E3.D12.D.D12.D2.5D2.D.D.D8.8B2.4BC3B
$124.D10.3D.3D11.D2.3D.3D3.D9.D.D8.D16.D2.3E4.5D5.3E2.D12.D.3D10.D9.D
.D.D8.7B4.8B$25.B11.A86.D28.D12.D7.3D.D8.D4.7D5.D24.D27.D9.2D2.D8.B2C
5B4.6B$24.3A9.ABA7.3B8.A.AB56.3D4.D9.9D10.D.9D2.D7.D3.D8.D16.D4.E.3E.
D.D2.3E.E4.D9.9D9.D3.D.D7.D8.B2CBC3B5.6B$18.2AB2.BABAB7.A3BA5.3AB.B5.
AB2A2B57.D4.D28.D12.D7.3D.3D6.D6.3D7.D7.2E.D.D2.2E7.D27.D3.D.D7.D9.B3C
3B5.6B$18.2BA3.2A.2A5.BAB.2BA3.B3AB3A3.A4B2A.A53.3D4.D12.D.D13.D4.3D5.
D20.D8.D7.D7.E2.3D3.E7.D10.3D.3D10.D3.3D7.D8.3BC4B6.5B$18.2BA4.BABAB5.
B2ABA5.A.3AB5.A.4B2AB52.D6.D12.D.D13.D4.D7.D6.9D5.D6.3D7.D7.2E3.D2.2E
7.D12.D3.D10.D5.D7.D7.8B7.2B$18.2AB5.3A7.2AB8.B2A8.A5B53.3D4.D12.3D13.
D4.3D5.D20.D8.D7.D7.2E3.D2.2E7.D10.3D.3D10.D5.D7.D8.6B$27.B9.B21.2A.A
61.D14.D13.D4.D.D5.D9.3D8.D6.3D7.D5.E2.E6.E2.E5.D10.D3.D12.D13.D7.6B$
124.D14.D13.D4.3D5.D9.D10.D23.2E8.2E6.D10.3D.3D10.D13.D7.6B$124.D51.3D
100.5B$24.A153.D101.2B$22.A3BA17.A22.A108.3D$22.5B15.A3BA19.BAB$21.A5B
A14.5B18.A3BA$20.AB5ABA8.2A2.A5BA2.2A11.2B2AB2A2B$18.BA2B.3B.2BAB6.A2.
AB5ABA2.A11.2B2A.2A2B$18.BA3B.B.3BAB7.3AB.3B.B3A9.B2.2B2A.2A2B2.B$17.
2BA3BA.A3BA2B27.3A.2B2A.2A2B.3A$18.BA3B.B.3BAB7.3AB.3B.B3A9.B2.2B2A.2A
2B2.B$18.BA2B.3B.2BAB6.A2.AB5ABA2.A11.2B2A.2A2B$20.AB5ABA8.2A2.A5BA2.
2A11.2B2AB2A2B$21.A5BA14.5B18.A3BA$22.5B15.A3BA19.BAB$22.A3BA17.A22.A
$24.A5$24.A20.A$23.BAB18.BAB$24.A18.A3BA$21.7B13.2B2AB2A2B13.A2BA$21.
7B13.2B2A.2A2B13.4B$8.D.D9.9A11.3B2A.2A3B11.A4BA$8.D.D8.2B7A2B8.BAB.B
2A.2AB.BAB8.AB4ABA$8.3D7.2A2B5.2B2A6.3AB.B2A.2AB.B3A6.A2BA2.A2BA$10.D
8.2B7A2B8.BAB.B2A.2AB.BAB8.AB4ABA$10.D9.9A11.3B2A.2A3B11.A4BA$21.7B13.
2B2A.2A2B13.4B$21.7B13.2B2AB2A2B13.A2BA$24.A18.A3BA$23.BAB18.BAB$24.A
20.A5$46.A$24.2A18.A3BA$22.A4BA16.5B$22.6B15.A5BA$21.A6BA13.AB5ABA$20.
AB6ABA10.BA2B.3B.2BAB$19.A2BA4.A2BA9.BA3B.B.3BAB$20.AB6ABA9.2BA3BA.A3B
A2B$21.A6BA10.2BA3BA.A3BA2B$22.6B12.BA3B.B.3BAB$22.A4BA12.BA2B.3B.2BA
B$24.2A16.AB5ABA$43.A5BA$44.5B$44.A3BA$46.A5$66.A$65.ABA$44.2A17.BA3B
AB$26.A12.2A2.A2BA2.2A8.2A.2BA3BA2B.2A$25.ABA11.A2.AB2ABA2.A8.A2.AB.A
BA.BA2.A$9.3D11.BA3BAB10.4A2B4A10.3AB2.A2.B3A$9.D13.BA3BAB$9.3D9.2AB.
ABA.B2A8.4A2B4A10.3AB2.A2.B3A$11.D8.A.AB2.A2.BA.A6.A2.AB2ABA2.A8.A2.A
B.ABA.BA2.A$9.3D8.A11.A6.2A2.A2BA2.2A8.2A.2BA3BA2B.2A$19.2A11.2A10.2A
17.BA3BAB$65.ABA$66.A7$9.3D11.2B9.B$9.D11.2B3A7.BAB$9.3D8.3B3A6.AB3AB
$9.D.D8.3A.3A4.A2B.3AB$9.3D9.3A3B5.AB2ABA$21.3A2B7.2AB$22.2B10.B8$23.
A$9.3D10.BAB$9.D.D9.2B3A$9.3D8.3B.BAB$9.D.D7.3A3.3A$9.3D8.BAB.3B$21.3A
2B$22.BAB$23.A4$24.2A$24.A.A$25.AB$24.2B$24.4B$23.BA4BAB$23.3A3B2A2B.
2A$9.3D11.2BA2B2A3BA.A$9.D.D10.4B2.4B.BA$9.3D7.AB.4B2.4B$11.D6.A.A3B2A
2BA2B$9.3D6.2A.2B2A3B3A$23.BA4BAB$26.4B$28.2B$27.BA$27.A.A$28.2A8$22.
B2A$5.D3.3D9.2BABA$5.D3.D.D9.5B$5.D3.D.D9.2BA2B$5.D3.D.D9.2B3A$5.D3.3D
10.3B4$22.B2A3B$5.D3.D.D10.A2BA2B$5.D3.D.D9.BA3BA2B$5.D3.3D10.BA2BAB$
5.D5.D9.2BA3BAB$5.D5.D10.2BA2BA$22.3B2AB3$25.B3.B$24.3B.BAB$22.7B2A2B
$21.3BA3BA5B$4.3D2.3D9.2BABA3B3A2B$6.D2.D10.BABA4BA3BA2B$4.3D2.3D7.B2A
BAB5ABA4B$4.D4.D.D8.2BAB3A.2A5B$4.3D2.3D9.4BA3.A4B$20.5B2A.3ABA2B$19.
4BAB5ABAB2AB$20.2BA3BA4BABAB$21.2B3A3BABA2B$21.5BA3BA3B$22.2B2A7B$24.
BAB.3B$25.B3.B8$29.B.3B$23.4B.6B$22.12B$5.D.D.3D9.14B$5.D.D.D.D7.5B2A
9B$5.3D.3D5.6B2A8B$7.D.D.D5.7B3A4B$7.D.3D6.7B2A3B$18.6B.4B$18.3B.B9$28.
2B$28.5B$19.2B6.B3A2B$19.5B3.3BA2B$18.6B2.3B2AB$18.6B.2A6B$17.8B4A3B$
16.10B3A2B$5.3D.3D3.12BA4B$5.D3.D5.17B$5.3D.3D3.17B$7.D.D.D3.4BA12B$5.
3D.3D4.2B3A10B$15.3B4A8B$14.6B2A.6B$15.B2A3B2.6B$14.2BA3B3.5B$14.2B3A
B6.2B$14.5B$17.2B7$9.3B.B$9.6B.4B$9.12B$8.14B$8.9B2A5B$10.8B2A6B$12.4B
3A7B$13.3B2A7B$5.3D.3D2.4B.6B$5.D.D.D10.B.3B.B$5.3D.3D12.2B2A$7.D.D.D
12.2B2A$5.3D.3D8.B.3B.B$14.4B.6B$13.3B2A7B$12.4B3A7B$10.8B2A6B$8.9B2A
5B$8.14B$9.12B$9.6B.4B$9.3B.B9$29.B.3B$23.4B.6B$22.12B$21.14B2.6B$3D.
3D.3D8.5B2A10B.B3A2B$2.D3.D.D8.6B2A8B3.BA6B$3D.3D.3D6.7B3A4B6.A4BA$2.
D3.D.D.D7.7B2A3B6.6BAB$3D.3D.3D7.6B.4B8.2B3AB$18.3B.B14.6B!

Code: Select all

x = 10, y = 27, rule = B34wyz/S2-n3History
$8.A$7.BAB$7.ABA$7.3B$7.3B$4.A2.B2A$2.2ABA.2AB$2.3B4AB$2.5BA2B$2.5A3B
$2.2B2A4B$2.8B$2.4BA3B$2.3BA4B$2.2BABA3B$2.B2A5B$.A2BA5B$.A2BA5B$.2B2A
BA3B$.4BABA2B$.9B$.4BA4B$.4BA4B$.4BA2BAB$.6BA2B$.4B2A3B!

[Sokwe]

Are you planning to add support for searching diagonal and oblique spaceship speeds? What about photons and oscillators?

Unfortunately, none of those types of searches work well with qfind's method.

Diagonal spaceships: memory usage in qfind limits the search width to 10 or 11, which is typically much too narrow to find diagonal spaceships. I also tried implementing diagonal searches in zfind (which qfind is largely based on), but the search was slower than the equivalent search in JLS.

Photons: qfind's row ordering (taken from gfind) does not support photons. The method used by MPPS is much better for searching for high-period photons, and LLSSS is far better at finding p1 photons than qfind could ever be, so I see no reason to try to hack support for photons into qfind.

Oscillators: the methods for effective oscillator searching are typically quite different from spaceship searching. You are better off using other tools. I recommend LLS.

[R2INT]

I found a very small c/7 spaceship in B35/S126 that caused problems for qfind:

Code: Select all

x = 15, y = 5, rule = B35/S126
bob3o3b3obo$ob2o2bobo2b2obo$obobo5bobobo$bob4ob4obo$3b2o5b2o!

It was found with a queue size of 23 after 17 minutes. Decreasing it to 22 results in this output, which prints "Success called on search root!" when encountering the spaceship:

Code: Select all

qfind v2.4b by Matthias Merzenich, 4 September 2025
Input: -t 24 -r B35/S126 -q 22 -h 22 -v c/7 -s o -w 8


Rule: B35/S126
speed: c/7
Width: 8
Symmetry: odd
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^22
Hash table size: 2^22
Minimum deepening increment: 3
Lookahead caching disabled
Number of threads: 24

04/08/26 13:42:45 Starting search
04/08/26 13:42:46 Queue full, depth 6, deepening 3, 524k/551k -> 397k/424k
04/08/26 13:43:25 Queue full, depth 6, deepening 6, 524k/557k -> 365k/396k
04/08/26 13:43:55 Queue full, depth 6, deepening 9, 524k/563k -> 400k/437k
04/08/26 13:44:27 Queue full, depth 6, deepening 12, 524k/569k -> 361k/403k
04/08/26 13:44:58 Queue full, depth 6, deepening 15, 524k/575k -> 350k/397k
04/08/26 13:45:25 Queue full, depth 6, deepening 18, 524k/582k -> 308k/359k
04/08/26 13:45:45 Queue full, depth 7, deepening 20, 524k/590k -> 297k/357k
04/08/26 13:46:03 Queue full, depth 7, deepening 23, 524k/600k -> 257k/322k
04/08/26 13:46:19 Queue full, depth 7, deepening 26, 524k/607k -> 224k/294k
04/08/26 13:46:35 Queue full, depth 7, deepening 29, 524k/613k -> 206k/281k
04/08/26 13:46:49 Queue full, depth 7, deepening 32, 524k/622k -> 185k/267k
04/08/26 13:47:01 Queue full, depth 7, deepening 35, 524k/630k -> 168k/256k
04/08/26 13:47:11 Queue full, depth 7, deepening 38, 524k/639k -> 153k/248k
04/08/26 13:47:19 Queue full, depth 9, deepening 39, 524k/864k -> 168k/411k
04/08/26 13:47:31 Queue full, depth 9, deepening 42, 524k/873k -> 168k/443k
04/08/26 13:47:46 Queue full, depth 10, deepening 44, 524k/888k -> 171k/478k
04/08/26 13:48:02 Queue full, depth 11, deepening 46, 524k/922k -> 172k/509k
04/08/26 13:48:17 Queue full, depth 11, deepening 49, 524k/930k -> 156k/483k
04/08/26 13:48:34 Queue full, depth 11, deepening 52, 524k/931k -> 145k/473k
04/08/26 13:49:02 Queue full, depth 12, deepening 54, 524k/931kSuccess called on search root!
 -> 147k/495k
04/08/26 13:49:21 Search complete.

0 spaceships found.
Maximum depth reached: 12
Longest partial result:

x = 9, y = 1, rule = B35/S126
o7bo!

Queue size 23, which found the spaceship:

Code: Select all

qfind v2.4b by Matthias Merzenich, 4 September 2025
Input: -t 24 -r B35/S126 -q 23 -h 23 -v c/7 -s o -w 8


Rule: B35/S126
speed: c/7
Width: 8
Symmetry: odd
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^23
Hash table size: 2^23
Minimum deepening increment: 3
Lookahead caching disabled
Number of threads: 24

04/08/26 13:49:44 Starting search
04/08/26 13:49:44 Queue full, depth 6, deepening 3, 1.0M/1.1M -> 731k/784k
04/08/26 13:51:54 Queue full, depth 6, deepening 6, 1.0M/1.1M -> 694k/755k
04/08/26 13:53:29 Queue full, depth 6, deepening 9, 1.0M/1.1M -> 679k/756k
04/08/26 13:55:04 Queue full, depth 7, deepening 11, 1.0M/1.1M -> 644k/736k
04/08/26 13:56:37 Queue full, depth 7, deepening 14, 1.0M/1.1M -> 556k/659k
04/08/26 13:57:45 Queue full, depth 7, deepening 17, 1.0M/1.1M -> 476k/589k
04/08/26 13:58:41 Queue full, depth 7, deepening 20, 1.0M/1.1M -> 436k/562k
04/08/26 13:59:28 Queue full, depth 7, deepening 23, 1.0M/1.2M -> 392k/532k
04/08/26 14:00:11 Queue full, depth 7, deepening 26, 1.0M/1.2M -> 352k/506k
04/08/26 14:00:40 Queue full, depth 7, deepening 29, 1.0M/1.2M -> 312k/478k
04/08/26 14:01:10 Queue full, depth 9, deepening 30, 1.0M/1.6M -> 353k/816k
04/08/26 14:01:42 Queue full, depth 9, deepening 33, 1.0M/1.7M -> 343k/862k
04/08/26 14:02:21 Queue full, depth 10, deepening 35, 1.0M/1.7M -> 349k/926k
04/08/26 14:03:04 Queue full, depth 11, deepening 37, 1.0M/1.8M -> 353k/986k
04/08/26 14:03:45 Queue full, depth 11, deepening 40, 1.0M/1.8M -> 315k/921k
04/08/26 14:04:27 Queue full, depth 12, deepening 42, 1.0M/1.8M -> 311k/958k
04/08/26 14:05:01 Queue full, depth 12, deepening 45, 1.0M/1.8M -> 280k/916k
04/08/26 14:05:31 Queue full, depth 13, deepening 47, 1.0M/1.8M -> 261k/939k
04/08/26 14:05:59 Queue full, depth 14, deepening 49, 1.0M/2.0M -> 242k/1.0M
04/08/26 14:06:30 Queue full, depth 15, deepening 51, 1.0M/2.1M
x = 15, y = 5, rule = B35/S126
bob3o3b3obo$ob2o2bobo2b2obo$obobo5bobobo$bob4ob4obo$3b2o5b2o!

 -> 222k/1.0M
04/08/26 14:06:55 Queue full, depth 16, deepening 53, 1.0M/2.2M -> 203k/1.1M

[LaundryPizza03]

The following command:

Code: Select all

./qfind -r B256/S04 -v 2c/5 -w 11 -s e

gives:

Code: Select all

x = 20, y = 34, rule = B256/S04
8b4o$7b2o2b2o2$8bo2bo$7bo4bo$9b2o$7bo4bo3$6bo6bo$5bo8bo$3bobo8bobo$6b
2o4b2o$3bo5b2o5bo$7bo4bo2$6bo2b2o2bo$8bo2bo$4bo10bo$8b4o$7bo4bo$6bo6bo
$6bo2b2o2bo$2bo14bo$3bo2bobo2bobo2bo$3bob3o4b3obo$3bobo8bobo$3bo3bob2o
bo3bo$3bobobo4bobobo$5b2o2b2o2b2o$bo16bo$2bobo10bobo$2bobo10bobo$o4bob
o4bobo4bo!

which is shorter than the result with the same command at width 10. However, AforAmpere found that adding "-t 10" gives the following longer result:

Code: Select all

x = 22, y = 47, rule = B256/S04
2bo2bo10bo2bo2$3b2o12b2o$2bo2bo10bo2bo$b6o8b6o$2bo2bo10bo2bo3$bo4bo8bo
4bo2$4bo2b2o4b2o2bo$3b3o10b3o$3bo3b2o4b2o3bo$5bo3bo2bo3bo$3bo14bo$9bo
2bo$5b2obo4bob2o$bo2bo4bo2bo4bo2bo$4bobobo4bobobo$4bo2bo6bo2bo$4b2o2bo
4bo2b2o$3b2o3bo4bo3b2o$4bo4bo2bo4bo$4b4o6b4o$10b2o$bo2b2o3bo2bo3b2o2bo
$b2o3bo2b4o2bo3b2o$o6b3o2b3o6bo$2b3o4bo2bo4b3o$2bobo4bo2bo4bobo$bo2b3o
2bo2bo2b3o2bo$4b5o4b5o$10b2o2$5bo10bo$4bobo3b2o3bobo$4bo2bo6bo2bo$bo5b
3o2b3o5bo$o6bo6bo6bo$2bobo2bo6bo2bobo$2bo16bo$bo2bob2obo2bob2obo2bo2$
2b2o2bo8bo2b2o$3bo4bo4bo4bo$o4bo4b2o4bo4bo$2b2obo10bob2o!

[AforAmpere]

A strange thing LaundryPizza03 found, these two searches that differ only in thread count reach significantly different maximum depths. I'm not sure what the cause is, but it feels like a bug:

Code: Select all

./qfind -r B256/S04 -v 2c/5 -w 11 -s e
./qfind -r B256/S04 -v 2c/5 -w 11 -s e -t 10

Outputs:

Code: Select all

qfind v2.4b by Matthias Merzenich, 8 September 2025
Input: -r B256/S04 -v 2c/5 -w 11 -s e


Rule: B256/S04
speed: 2c/5
Width: 11
Symmetry: even
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^15
Hash table size: 2^15
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 23

19/09/26 22:24:31 Starting search
19/09/26 22:24:31 Queue full, depth 4, deepening 3, 4.1k/4.2k -> 860/935
19/09/26 22:24:32 Queue full, depth 4, deepening 6, 4.1k/4.2k -> 854/969
19/09/26 22:24:33 Queue full, depth 4, deepening 9, 4.1k/4.3k -> 816/974
19/09/26 22:24:35 Queue full, depth 4, deepening 12, 4.1k/4.4k -> 721/974
19/09/26 22:24:40 Queue full, depth 6, deepening 13, 4.0k/5.7k -> 808/1.6k
19/09/26 22:24:42 Queue full, depth 6, deepening 16, 4.1k/5.1k -> 660/1.4k
19/09/26 22:24:45 Queue full, depth 6, deepening 19, 4.1k/5.1k -> 619/1.4k
19/09/26 22:24:48 Queue full, depth 7, deepening 21, 4.0k/5.5k -> 598/1.7k
19/09/26 22:24:51 Queue full, depth 9, deepening 22, 4.1k/6.2k -> 579/2.1k
19/09/26 22:24:52 Queue full, depth 10, deepening 24, 4.0k/6.4k -> 557/2.3k
19/09/26 22:24:54 Queue full, depth 11, deepening 26, 4.0k/6.5k -> 523/2.3k
19/09/26 22:24:56 Queue full, depth 12, deepening 28, 4.1k/7.1k -> 436/2.4k
19/09/26 22:24:57 Queue full, depth 13, deepening 30, 4.0k/7.0k -> 394/2.4k
19/09/26 22:24:59 Queue full, depth 15, deepening 31, 4.0k/6.8k -> 362/2.4k
19/09/26 22:24:59 Queue full, depth 16, deepening 33, 4.1k/7.2k -> 316/2.3k
19/09/26 22:25:01 Queue full, depth 18, deepening 34, 4.0k/7.2k -> 299/2.3k
19/09/26 22:25:01 Queue full, depth 20, deepening 35, 4.0k/7.1k -> 279/2.4k
19/09/26 22:25:02 Queue full, depth 21, deepening 37, 4.1k/6.7k -> 250/2.1k
19/09/26 22:25:03 Queue full, depth 22, deepening 39, 4.0k/6.8k -> 226/2.1k
19/09/26 22:25:04 Queue full, depth 23, deepening 41, 4.0k/6.4k -> 231/1.9k
19/09/26 22:25:05 Queue full, depth 24, deepening 43, 4.0k/6.3k -> 213/1.7k
19/09/26 22:25:06 Queue full, depth 26, deepening 44, 4.1k/6.3k -> 202/1.7k
19/09/26 22:25:06 Queue full, depth 27, deepening 46, 4.0k/6.1k -> 188/1.6k
19/09/26 22:25:07 Queue full, depth 28, deepening 48, 4.1k/6.1k -> 170/1.6k
19/09/26 22:25:08 Queue full, depth 30, deepening 49, 4.1k/6.1k -> 171/1.5k
19/09/26 22:25:09 Queue full, depth 31, deepening 51, 4.1k/6.0k -> 148/1.4k
19/09/26 22:25:09 Queue full, depth 33, deepening 52, 4.1k/6.1k -> 136/1.4k
19/09/26 22:25:09 Queue full, depth 35, deepening 53, 4.1k/6.0k -> 118/1.3k
19/09/26 22:25:10 Queue full, depth 36, deepening 55, 4.1k/5.9k -> 110/1.2k
19/09/26 22:25:12 Queue full, depth 38, deepening 56, 4.1k/5.7k -> 115/1.2k
19/09/26 22:25:13 Queue full, depth 40, deepening 57, 4.1k/5.8k -> 106/1.2k
19/09/26 22:25:13 Queue full, depth 41, deepening 59, 4.1k/5.5k -> 105/1.0k
19/09/26 22:25:13 Queue full, depth 43, deepening 60, 4.1k/5.6k -> 111/1.0k
19/09/26 22:25:14 Queue full, depth 44, deepening 62, 4.1k/5.4k -> 117/987
19/09/26 22:25:18 Queue full, depth 46, deepening 63, 4.1k/5.5k -> 147/1.1k
19/09/26 22:25:19 Queue full, depth 47, deepening 65, 4.1k/5.4k -> 217/1.2k
19/09/26 22:25:22 Queue full, depth 48, deepening 67, 4.1k/5.3k -> 219/1.3k
19/09/26 22:25:23 Queue full, depth 49, deepening 69, 4.1k/5.3k -> 265/1.3k
19/09/26 22:25:25 Queue full, depth 50, deepening 71, 4.1k/5.5k -> 253/1.4k
19/09/26 22:25:26 Queue full, depth 51, deepening 73, 4.0k/5.4k -> 279/1.5k
19/09/26 22:25:28 Queue full, depth 52, deepening 75, 4.1k/5.6k -> 266/1.6k
19/09/26 22:25:28 Queue full, depth 53, deepening 77, 4.1k/5.7k -> 264/1.8k
19/09/26 22:25:29 Queue full, depth 54, deepening 79, 4.0k/6.0k -> 245/1.8k
19/09/26 22:25:30 Queue full, depth 55, deepening 81, 4.0k/6.1k -> 207/1.7k
19/09/26 22:25:31 Queue full, depth 56, deepening 83, 4.0k/6.6k -> 159/1.7k
19/09/26 22:25:32 Queue full, depth 58, deepening 84, 4.0k/6.0k -> 141/1.6k
19/09/26 22:25:32 Queue full, depth 59, deepening 86, 4.0k/6.0k -> 122/1.5k
19/09/26 22:25:32 Queue full, depth 61, deepening 87, 4.0k/6.1k -> 111/1.5k
19/09/26 22:25:33 Queue full, depth 62, deepening 89, 4.0k/5.9k -> 100/1.4k
19/09/26 22:25:33 Queue full, depth 64, deepening 90, 4.1k/6.1k -> 87/1.5k
19/09/26 22:25:34 Queue full, depth 66, deepening 91, 4.1k/6.0k -> 76/1.4k
19/09/26 22:25:34 Queue full, depth 68, deepening 92, 4.1k/5.9k -> 69/1.3k
19/09/26 22:25:34 Queue full, depth 70, deepening 93, 4.0k/5.9k -> 63/1.3k
19/09/26 22:25:35 Queue full, depth 72, deepening 94, 4.1k/5.8k -> 52/1.1k
19/09/26 22:25:35 Queue full, depth 74, deepening 95, 4.0k/5.5k -> 48/1.1k
19/09/26 22:25:35 Queue full, depth 75, deepening 97, 4.1k/5.4k -> 43/978
19/09/26 22:25:35 Queue full, depth 78, deepening 97, 4.0k/6.7k -> 41/1.0k
19/09/26 22:25:36 Queue full, depth 80, deepening 98, 4.1k/6.5k -> 37/973
19/09/26 22:25:36 Queue full, depth 83, deepening 98, 4.1k/5.7k -> 38/960
19/09/26 22:25:36 Queue full, depth 85, deepening 99, 4.0k/6.6k -> 34/995
19/09/26 22:25:36 Queue full, depth 88, deepening 99, 4.1k/6.5k -> 33/930
19/09/26 22:25:36 Queue full, depth 92, deepening 98, 4.0k/6.7k -> 32/995
19/09/26 22:25:36 Queue full, depth 95, deepening 98, 4.0k/8.2k -> 30/939
19/09/26 22:25:36 Queue full, depth 98, deepening 98, 4.1k/5.7k -> 29/900
19/09/26 22:25:36 Queue full, depth 101, deepening 98, 4.0k/5.6k -> 29/911
19/09/26 22:25:36 Queue full, depth 104, deepening 98, 4.0k/5.7k -> 29/877
19/09/26 22:25:37 Queue full, depth 106, deepening 99, 4.1k/6.3k -> 27/671
19/09/26 22:25:37 Queue full, depth 108, deepening 100, 4.1k/5.2k -> 28/706
19/09/26 22:25:37 Queue full, depth 110, deepening 101, 4.1k/5.5k -> 28/751
19/09/26 22:25:37 Queue full, depth 112, deepening 102, 4.1k/5.7k -> 28/739
19/09/26 22:25:37 Queue full, depth 116, deepening 101, 4.1k/6.9k -> 27/777
19/09/26 22:25:37 Queue full, depth 118, deepening 102, 4.0k/6.0k -> 26/592
19/09/26 22:25:37 Queue full, depth 121, deepening 102, 4.1k/5.4k -> 26/599
19/09/26 22:25:37 Queue full, depth 125, deepening 101, 4.0k/7.8k -> 26/682
19/09/26 22:25:37 Queue full, depth 129, deepening 100, 4.0k/7.4k -> 25/584
19/09/26 22:25:37 Queue full, depth 134, deepening 98, 4.0k/7.7k -> 23/647
19/09/26 22:25:37 Queue full, depth 141, deepening 94, 4.0k/10k -> 23/571
19/09/26 22:25:37 Queue full, depth 144, deepening 94, 4.1k/5.2k -> 15/559
19/09/26 22:25:37 Queue full, depth 149, deepening 92, 4.0k/9.5k -> 0/0
19/09/26 22:25:37 Search complete.

0 spaceships found.
Maximum depth reached: 149
Longest partial result:

x = 12, y = 29, rule = B256/S04
4b4o$3b2o2b2o2$4bo2bo$3bo4bo$5b2o$3bo4bo4$2bo6bo$5b2o2$4b4o$bo8b
o$4bo2bo$3bo4bo$2bo6bo$2bo2b2o2bo$2bobo2bobo$2bo6bo$2bo2b2o2bo$5b
2o$2bobo2bobo2$o10bo$3bob2obo$3bo4bo$o2bo4bo2bo!

Code: Select all

qfind v2.4b by Matthias Merzenich, 8 September 2025
Input: -r B256/S04 -v 2c/5 -w 11 -s e -t 10


Rule: B256/S04
speed: 2c/5
Width: 11
Symmetry: even
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^15
Hash table size: 2^15
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 10

19/09/26 22:14:08 Starting search
19/09/26 22:14:08 Queue full, depth 4, deepening 3, 4.1k/4.2k -> 849/922
19/09/26 22:14:09 Queue full, depth 4, deepening 6, 4.1k/4.2k -> 849/965
19/09/26 22:14:10 Queue full, depth 4, deepening 9, 4.1k/4.3k -> 807/965
19/09/26 22:14:11 Queue full, depth 4, deepening 12, 4.1k/4.4k -> 722/974
19/09/26 22:14:13 Queue full, depth 6, deepening 13, 4.1k/5.7k -> 798/1.6k
19/09/26 22:14:15 Queue full, depth 6, deepening 16, 4.0k/5.1k -> 651/1.4k
19/09/26 22:14:17 Queue full, depth 6, deepening 19, 4.0k/5.1k -> 610/1.4k
19/09/26 22:14:20 Queue full, depth 7, deepening 21, 4.0k/5.5k -> 586/1.7k
19/09/26 22:14:24 Queue full, depth 9, deepening 22, 4.1k/6.2k -> 569/2.0k
19/09/26 22:14:26 Queue full, depth 10, deepening 24, 4.1k/6.4k -> 546/2.2k
19/09/26 22:14:29 Queue full, depth 11, deepening 26, 4.0k/6.5k -> 516/2.3k
19/09/26 22:14:32 Queue full, depth 12, deepening 28, 4.0k/7.1k -> 435/2.4k
19/09/26 22:14:35 Queue full, depth 14, deepening 29, 4.0k/7.1k -> 424/2.6k
19/09/26 22:14:37 Queue full, depth 15, deepening 31, 4.0k/7.0k -> 352/2.4k
19/09/26 22:14:39 Queue full, depth 16, deepening 33, 4.0k/7.2k -> 306/2.3k
19/09/26 22:14:42 Queue full, depth 18, deepening 34, 4.1k/7.2k -> 290/2.3k
19/09/26 22:14:44 Queue full, depth 20, deepening 35, 4.1k/7.1k -> 272/2.3k
19/09/26 22:14:45 Queue full, depth 21, deepening 37, 4.1k/6.7k -> 240/2.1k
19/09/26 22:14:47 Queue full, depth 22, deepening 39, 4.1k/6.8k -> 219/2.0k
19/09/26 22:14:48 Queue full, depth 23, deepening 41, 4.1k/6.3k -> 224/1.9k
19/09/26 22:14:49 Queue full, depth 24, deepening 43, 4.0k/6.2k -> 203/1.7k
19/09/26 22:14:50 Queue full, depth 26, deepening 44, 4.1k/6.3k -> 190/1.7k
19/09/26 22:14:51 Queue full, depth 27, deepening 46, 4.0k/6.1k -> 178/1.6k
19/09/26 22:14:51 Queue full, depth 28, deepening 48, 4.0k/6.1k -> 160/1.5k
19/09/26 22:14:52 Queue full, depth 30, deepening 49, 4.1k/6.0k -> 160/1.5k
19/09/26 22:14:52 Queue full, depth 31, deepening 51, 4.1k/6.0k -> 134/1.4k
19/09/26 22:14:52 Queue full, depth 33, deepening 52, 4.0k/6.0k -> 130/1.4k
19/09/26 22:14:53 Queue full, depth 35, deepening 53, 4.0k/6.0k -> 108/1.3k
19/09/26 22:14:53 Queue full, depth 36, deepening 55, 4.0k/5.8k -> 98/1.2k
19/09/26 22:14:54 Queue full, depth 38, deepening 56, 4.0k/5.7k -> 108/1.2k
19/09/26 22:14:54 Queue full, depth 40, deepening 57, 4.0k/5.8k -> 103/1.1k
19/09/26 22:14:54 Queue full, depth 41, deepening 59, 4.1k/5.5k -> 98/1.0k
19/09/26 22:14:55 Queue full, depth 43, deepening 60, 4.1k/5.5k -> 102/999
19/09/26 22:14:57 Queue full, depth 44, deepening 62, 4.0k/5.4k -> 120/995
19/09/26 22:14:58 Queue full, depth 46, deepening 63, 4.0k/5.4k -> 141/1.1k
19/09/26 22:14:59 Queue full, depth 47, deepening 65, 4.0k/5.4k -> 214/1.2k
19/09/26 22:15:02 Queue full, depth 48, deepening 67, 4.1k/5.3k -> 213/1.3k
19/09/26 22:15:04 Queue full, depth 49, deepening 69, 4.1k/5.4k -> 258/1.3k
19/09/26 22:15:07 Queue full, depth 50, deepening 71, 4.1k/5.8k -> 246/1.4k
19/09/26 22:15:09 Queue full, depth 51, deepening 73, 4.1k/5.5k -> 272/1.6k
19/09/26 22:15:13 Queue full, depth 52, deepening 75, 4.1k/5.7k -> 260/1.7k
19/09/26 22:15:15 Queue full, depth 53, deepening 77, 4.0k/5.8k -> 255/1.8k
19/09/26 22:15:16 Queue full, depth 55, deepening 78, 4.1k/6.6k -> 243/2.0k
19/09/26 22:15:18 Queue full, depth 56, deepening 80, 4.1k/6.2k -> 184/1.7k
19/09/26 22:15:20 Queue full, depth 57, deepening 82, 4.1k/6.1k -> 153/1.7k
19/09/26 22:15:20 Queue full, depth 59, deepening 83, 4.0k/6.5k -> 130/1.6k
19/09/26 22:15:21 Queue full, depth 60, deepening 85, 4.1k/6.1k -> 116/1.6k
19/09/26 22:15:22 Queue full, depth 62, deepening 86, 4.1k/6.0k -> 108/1.6k
19/09/26 22:15:23 Queue full, depth 64, deepening 87, 4.0k/6.2k -> 95/1.6k
19/09/26 22:15:23 Queue full, depth 66, deepening 88, 4.1k/6.2k -> 84/1.6k
19/09/26 22:15:24 Queue full, depth 68, deepening 89, 4.1k/6.2k -> 70/1.5k
19/09/26 22:15:25 Queue full, depth 70, deepening 90, 4.1k/6.5k -> 59/1.4k
19/09/26 22:15:25 Queue full, depth 72, deepening 91, 4.1k/6.0k -> 51/1.3k
19/09/26 22:15:26 Queue full, depth 74, deepening 92, 4.1k/5.6k -> 47/1.2k
19/09/26 22:15:26 Queue full, depth 76, deepening 93, 4.0k/5.7k -> 39/1.1k
19/09/26 22:15:27 Queue full, depth 78, deepening 94, 4.1k/6.0k -> 31/974
19/09/26 22:15:27 Queue full, depth 81, deepening 94, 4.0k/5.9k -> 31/1.0k
19/09/26 22:15:27 Queue full, depth 84, deepening 94, 4.1k/6.1k -> 30/934
19/09/26 22:15:28 Queue full, depth 86, deepening 95, 4.1k/6.1k -> 26/929
19/09/26 22:15:28 Queue full, depth 90, deepening 94, 4.0k/7.7k -> 22/964
19/09/26 22:15:28 Queue full, depth 93, deepening 94, 4.0k/7.3k -> 22/990
19/09/26 22:15:28 Queue full, depth 97, deepening 93, 4.0k/8.7k -> 20/929
19/09/26 22:15:28 Queue full, depth 100, deepening 93, 4.1k/5.6k -> 17/871
19/09/26 22:15:28 Queue full, depth 104, deepening 92, 4.0k/5.9k -> 21/839
19/09/26 22:15:28 Queue full, depth 106, deepening 93, 4.1k/6.2k -> 20/811
19/09/26 22:15:29 Queue full, depth 109, deepening 93, 4.1k/6.3k -> 21/804
19/09/26 22:15:31 Queue full, depth 111, deepening 94, 4.1k/5.5k -> 19/717
19/09/26 22:15:31 Queue full, depth 115, deepening 93, 4.0k/7.5k -> 19/754
19/09/26 22:15:31 Queue full, depth 118, deepening 93, 4.0k/6.3k -> 16/707
19/09/26 22:15:31 Queue full, depth 123, deepening 91, 4.1k/8.0k -> 15/574
19/09/26 22:15:31 Queue full, depth 129, deepening 88, 4.1k/9.4k -> 16/626
19/09/26 22:15:31 Queue full, depth 137, deepening 83, 4.1k/13k -> 14/707
19/09/26 22:15:31 Queue full, depth 142, deepening 81, 4.0k/7.4k -> 15/675
19/09/26 22:15:31 Queue full, depth 145, deepening 81, 4.1k/5.2k -> 13/697
19/09/26 22:15:32 Queue full, depth 152, deepening 77, 4.1k/15k -> 11/569
19/09/26 22:15:32 Queue full, depth 171, deepening 61, 2.3k/30k -> 10/680
19/09/26 22:15:32 Queue full, depth 195, deepening 40, 4.0k/27k -> 4/406
19/09/26 22:15:32 Search complete.

0 spaceships found.
Maximum depth reached: 238
Longest partial result:

x = 22, y = 47, rule = B256/S04
2bo2bo10bo2bo2$3b2o12b2o$2bo2bo10bo2bo$b6o8b6o$2bo2bo10bo2bo3$b
o4bo8bo4bo2$4bo2b2o4b2o2bo$3b3o10b3o$3bo3b2o4b2o3bo$5bo3bo2bo3bo
$3bo14bo$9bo2bo$5b2obo4bob2o$bo2bo4bo2bo4bo2bo$4bobobo4bobobo$4b
o2bo6bo2bo$4b2o2bo4bo2b2o$3b2o3bo4bo3b2o$4bo4bo2bo4bo$4b4o6b4o$10b
2o$bo2b2o3bo2bo3b2o2bo$b2o3bo2b4o2bo3b2o$o6b3o2b3o6bo$2b3o4bo2bo
4b3o$2bobo4bo2bo4bobo$bo2b3o2bo2bo2b3o2bo$4b5o4b5o$10b2o2$5bo10b
o$4bobo3b2o3bobo$4bo2bo6bo2bo$bo5b3o2b3o5bo$o6bo6bo6bo$2bobo2bo6b
o2bobo$2bo16bo$bo2bob2obo2bob2obo2bo2$2b2o2bo8bo2b2o$3bo4bo4bo4b
o$o4bo4b2o4bo4bo$2b2obo10bob2o!

Increasing hash and queue size to 17 also gives the longer partial and max depth:

Code: Select all

qfind v2.4b by Matthias Merzenich, 8 September 2025
Input: -r B256/S04 -v 2c/5 -w 11 -s e -h 17 -q 17


Rule: B256/S04
speed: 2c/5
Width: 11
Symmetry: even
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^17
Hash table size: 2^17
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 23

19/09/26 22:28:14 Starting search
19/09/26 22:28:14 Queue full, depth 4, deepening 3, 16k/16k -> 2.2k/2.4k
19/09/26 22:28:16 Queue full, depth 5, deepening 5, 16k/17k -> 2.4k/3.0k
19/09/26 22:28:18 Queue full, depth 6, deepening 7, 16k/20k -> 2.2k/4.2k
19/09/26 22:28:22 Queue full, depth 6, deepening 10, 16k/19k -> 1.9k/3.8k
19/09/26 22:28:26 Queue full, depth 8, deepening 11, 16k/26k -> 2.1k/5.7k
19/09/26 22:28:29 Queue full, depth 9, deepening 13, 16k/23k -> 1.8k/6.1k
19/09/26 22:28:32 Queue full, depth 10, deepening 15, 16k/24k -> 1.6k/5.9k
19/09/26 22:28:35 Queue full, depth 12, deepening 16, 16k/26k -> 1.4k/7.0k
19/09/26 22:28:38 Queue full, depth 14, deepening 17, 16k/28k -> 1.4k/7.6k
19/09/26 22:28:42 Queue full, depth 16, deepening 18, 16k/27k -> 1.4k/8.1k
19/09/26 22:28:44 Queue full, depth 18, deepening 19, 16k/29k -> 1.3k/8.4k
19/09/26 22:28:46 Queue full, depth 20, deepening 20, 16k/28k -> 1.2k/8.5k
19/09/26 22:28:47 Queue full, depth 22, deepening 21, 16k/28k -> 1.2k/8.6k
19/09/26 22:28:48 Queue full, depth 23, deepening 23, 16k/27k -> 1.2k/7.8k
19/09/26 22:28:49 Queue full, depth 24, deepening 25, 16k/26k -> 1.1k/7.2k
19/09/26 22:28:50 Queue full, depth 26, deepening 26, 16k/26k -> 1.0k/7.1k
19/09/26 22:28:51 Queue full, depth 28, deepening 27, 16k/26k -> 987/7.2k
19/09/26 22:28:52 Queue full, depth 29, deepening 29, 16k/25k -> 835/6.4k
19/09/26 22:28:52 Queue full, depth 31, deepening 30, 16k/25k -> 747/6.4k
19/09/26 22:28:53 Queue full, depth 33, deepening 31, 16k/25k -> 676/6.2k
19/09/26 22:28:53 Queue full, depth 35, deepening 32, 16k/27k -> 610/5.9k
19/09/26 22:28:54 Queue full, depth 37, deepening 33, 16k/25k -> 577/5.7k
19/09/26 22:28:55 Queue full, depth 39, deepening 34, 16k/24k -> 543/5.6k
19/09/26 22:28:55 Queue full, depth 41, deepening 35, 16k/27k -> 491/5.3k
19/09/26 22:28:55 Queue full, depth 43, deepening 36, 16k/24k -> 507/5.2k
19/09/26 22:28:56 Queue full, depth 44, deepening 38, 16k/23k -> 531/4.8k
19/09/26 22:28:57 Queue full, depth 46, deepening 39, 16k/22k -> 621/4.9k
19/09/26 22:29:03 Queue full, depth 47, deepening 41, 16k/23k -> 780/4.7k
19/09/26 22:29:12 Queue full, depth 48, deepening 43, 16k/21k -> 949/4.8k
19/09/26 22:29:18 Queue full, depth 49, deepening 45, 16k/23k -> 1.0k/5.1k
19/09/26 22:29:23 Queue full, depth 50, deepening 47, 16k/21k -> 1.1k/5.5k
19/09/26 22:29:25 Queue full, depth 52, deepening 48, 16k/24k -> 1.1k/6.0k
19/09/26 22:29:26 Queue full, depth 52, deepening 51, 16k/22k -> 1.0k/5.6k
19/09/26 22:29:28 Queue full, depth 54, deepening 52, 16k/23k -> 989/6.0k
19/09/26 22:29:28 Queue full, depth 55, deepening 54, 16k/23k -> 832/6.0k
19/09/26 22:29:29 Queue full, depth 56, deepening 56, 16k/23k -> 697/5.7k
19/09/26 22:29:30 Queue full, depth 58, deepening 57, 16k/24k -> 606/5.8k
19/09/26 22:29:31 Queue full, depth 59, deepening 59, 16k/24k -> 526/5.5k
19/09/26 22:29:31 Queue full, depth 61, deepening 60, 16k/24k -> 472/5.5k
19/09/26 22:29:32 Queue full, depth 63, deepening 61, 16k/24k -> 413/5.5k
19/09/26 22:29:33 Queue full, depth 65, deepening 62, 16k/25k -> 373/5.4k
19/09/26 22:29:33 Queue full, depth 67, deepening 63, 16k/25k -> 343/5.5k
19/09/26 22:29:34 Queue full, depth 69, deepening 64, 16k/25k -> 307/5.4k
19/09/26 22:29:34 Queue full, depth 72, deepening 64, 16k/25k -> 286/5.3k
19/09/26 22:29:35 Queue full, depth 74, deepening 65, 16k/24k -> 242/4.8k
19/09/26 22:29:35 Queue full, depth 76, deepening 66, 16k/24k -> 211/4.4k
19/09/26 22:29:36 Queue full, depth 79, deepening 66, 16k/24k -> 181/4.2k
19/09/26 22:29:36 Queue full, depth 82, deepening 66, 16k/25k -> 167/4.0k
19/09/26 22:29:37 Queue full, depth 85, deepening 66, 16k/25k -> 146/3.9k
19/09/26 22:29:37 Queue full, depth 88, deepening 66, 16k/24k -> 131/3.9k
19/09/26 22:29:37 Queue full, depth 92, deepening 65, 16k/34k -> 109/3.5k
19/09/26 22:29:37 Queue full, depth 96, deepening 64, 16k/29k -> 97/3.3k
19/09/26 22:29:38 Queue full, depth 99, deepening 64, 16k/28k -> 90/2.8k
19/09/26 22:29:38 Queue full, depth 104, deepening 62, 16k/33k -> 82/2.7k
19/09/26 22:29:38 Queue full, depth 107, deepening 62, 16k/26k -> 80/2.3k
19/09/26 22:29:38 Queue full, depth 110, deepening 62, 16k/30k -> 74/2.0k
19/09/26 22:29:38 Queue full, depth 113, deepening 62, 16k/31k -> 75/2.0k
19/09/26 22:29:39 Queue full, depth 118, deepening 60, 16k/29k -> 72/2.1k
19/09/26 22:29:39 Queue full, depth 123, deepening 58, 16k/31k -> 68/2.2k
19/09/26 22:29:39 Queue full, depth 129, deepening 55, 16k/45k -> 75/2.2k
19/09/26 22:29:39 Queue full, depth 137, deepening 50, 16k/52k -> 67/2.4k
19/09/26 22:29:39 Queue full, depth 143, deepening 47, 16k/34k -> 74/2.3k
19/09/26 22:29:39 Queue full, depth 148, deepening 45, 16k/49k -> 77/2.4k
19/09/26 22:29:39 Queue full, depth 155, deepening 41, 16k/46k -> 64/2.2k
19/09/26 22:29:40 Queue full, depth 169, deepening 30, 16k/122k -> 67/2.5k
19/09/26 22:29:40 Queue full, depth 193, deepening 9, 6.5k/122k -> 177/3.8k
19/09/26 22:29:40 Search complete.

0 spaceships found.
Maximum depth reached: 238
Longest partial result:

x = 22, y = 47, rule = B256/S04
2bo2bo10bo2bo2$3b2o12b2o$2bo2bo10bo2bo$b6o8b6o$2bo2bo10bo2bo3$b
o4bo8bo4bo2$4bo2b2o4b2o2bo$3b3o10b3o$3bo3b2o4b2o3bo$5bo3bo2bo3bo
$3bo14bo$9bo2bo$5b2obo4bob2o$bo2bo4bo2bo4bo2bo$4bobobo4bobobo$4b
o2bo6bo2bo$4b2o2bo4bo2b2o$3b2o3bo4bo3b2o$4bo4bo2bo4bo$4b4o6b4o$10b
2o$bo2b2o3bo2bo3b2o2bo$b2o3bo2b4o2bo3b2o$o6b3o2b3o6bo$2b3o4bo2bo
4b3o$2bobo4bo2bo4bobo$bo2b3o2bo2bo2b3o2bo$4b5o4b5o$10b2o2$5bo10b
o$4bobo3b2o3bobo$4bo2bo6bo2bo$bo5b3o2b3o5bo$o6bo6bo6bo$2bobo2bo6b
o2bobo$2bo16bo$bo2bob2obo2bob2obo2bo2$2b2o2bo8bo2b2o$3bo4bo4bo4b
o$o4bo4b2o4bo4bo$2b2obo10bob2o!

[Sokwe]

A strange thing LaundryPizza03 found, these two searches that differ only in thread count reach significantly different maximum depths. I'm not sure what the cause is, but it feels like a bug:

Outputs:

Code: Select all

qfind v2.4b by Matthias Merzenich, 8 September 2025
Input: -r B256/S04 -v 2c/5 -w 11 -s e
...
19/09/26 22:25:37 Queue full, depth 144, deepening 94, 4.1k/5.2k -> 15/559
19/09/26 22:25:37 Queue full, depth 149, deepening 92, 4.0k/9.5k -> 0/0
19/09/26 22:25:37 Search complete.

0 spaceships found.
Maximum depth reached: 149
...

Code: Select all

qfind v2.4b by Matthias Merzenich, 8 September 2025
Input: -r B256/S04 -v 2c/5 -w 11 -s e -t 10
...
19/09/26 22:15:32 Queue full, depth 195, deepening 40, 4.0k/27k -> 4/406
19/09/26 22:15:32 Search complete.

0 spaceships found.
Maximum depth reached: 238
...

Increasing hash and queue size to 17 also gives the longer partial and max depth:

It's not a bug, but it is confusing. Notice that in the first case it ends with "-> 0/0". This means that all potential partial results were eliminated during the depth-first look-ahead step, meaning the search could not continue in the breadth first step. That is why the "maximum depth" is only 149. Notice that it says "depth 149, deepening 92". Now, 149 + 92 = 241 is just slightly greater than the true maximum depth of 238.

The reason changing the number of threads affects this is probably because it changes the time when early exit occurs from the depth-first step. With fewer threads, the early exit occurs later, meaning more partials get checked. You can see this when it enters the depth-first step for the first time. At that moment, the state of the search is the same no matter how many threads you used, but then with 23 threads is says "-> 860/935" while with 10 threads it says "-> 849/922". This means in the former case 860 partials survived the depth-first pruning (some of them which were just dropped without checking due to the early exit from the depth-first step) while the latter case had only 849 partials survive the pruning. This continually has an impact on the order of the search going forward, including at what depths it reaches the depth-first step and thus also how much it deepens.

Changing the queue and hash sizes can also impact this. Increasing the queue size means that the queue will reach deeper depths during the breadth-first step, and thus it will use shallower depth-first limits. This decreases the likelihood that the search ends with the "-> 0/0" that results in an inaccurately short "longest" partial result.

So I don't think it's a bug, but some adjustments should be made (maybe a different final report message) to make it more clear what's happening when you get "-> 0/0" at the end of a search.

[LuveelVoom]

I am unable to compile qfind. When I attempt to, I get the following error:

Code: Select all

gcc-16 -std=c11 -fopenmp -march=native -O3 -Wall -Wextra -o qfind qfind.c 
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX15.sdk/usr/include/stdio.h:61,
                 from common.h:7,
                 from qfind.c:97:
/opt/homebrew/Cellar/gcc/16.2.0/lib/gcc/current/gcc/aarch64-apple-darwin24/16/include-fixed/_stdio.h:78:10: fatal error: _bounds.h: No such file or directory
   78 | #include <_bounds.h>
      |          ^~~~~~~~~~~
compilation terminated.

[Sokwe]

I am unable to compile qfind. When I attempt to, I get the following error:

This looks to me like a problem with GCC, rather than qfind, but I'm not sure how to resolve it. Maybe try reinstalling GCC with the command

Code: Select all

brew reinstall gcc

If that doesn't work, I'm not sure what to do. If you ever figure out the problem and solution, please post it here for other users who might encounter the same error.

[LuveelVoom]

I have fixed the bug above and can now run qfind
How did I fix it? I don't know. I screwed around in my gcc install for like 3 hours and it eventually worked. I don't know what component of that ended up getting it to work.


I have a question. Recently, I've been going on a bit of a binge with using LLMs to assist with search programs. "I've" been building a tool to generate input files for LLSSS, and "I" recently made a fork of ntcatforce that's multithreaded (I'll probably publish this after intense bug-hunting and testing. If anyone wants to try and stress-test/poke around for bugs in the ntcatforce fork or the LLSSS partial builder, DM me, and I'll get back to you once I finalize the layout and features.)

Would you be OK with me looking through qfind's code with the help of an LLM and seeing if it can spot any optimizations? Of course, I won't publish anything it produces; what I would do is describe the optimization it claims would work (after some sanity filtering, since I'm sure it will come up with some stuff which is just flat out wrong), and if it's helpful and wouldn't make qfind non-exhaustive, it might be able to be implemented.

The reason I'm not going to publish it is:
1. It would be rude for me to make a fork of qfind when I am basically unable to code C and relying on the crutch of something which makes weird buggy code.
2. It would be an unmitigated disaster if any optimization results in the program becoming non-exhaustive. I absolutely do not think it is worth risking screwing up a ton of spaceship tables for a slight gain in speed or memory use.

Is this idea OK with you, or should I hold off on doing it? The other two programs so far have been fine because:

-The LLSSS partial builder is a frontend program that makes an existing component of the program easier to use, and doesn't change any components of the backend; also, amling has given me tips on how to make sure it doesn't mislead the end-user
-ntcatforce has been abandoned for years and years, is a far far simpler program than LLSSS, and doesn't have any serious consequences if screwed with (whereas any messing around in LLSSS could result in a myriad of hard-to-fix bugs.)

Would scanning for optimizations fall into the "ok to use LLMs to help with" category?


Oh, also, sokwe, since you're a mod, could you rename "Luveelvoom's script ideas" to "Luveelvoom's scripts and ideas"? Thanks Fixed, pretend this is a strikethrough since phpBB doesn't have those for some reason

[MDA]

[…]

[…] could you rename "Luveelvoom's script ideas" to "Luveelvoom's scripts"? Thanks

You don’t need a moderator to do that, since you can do that yourself by editing the first post.

[Sokwe]

Would you be OK with me looking through qfind's code...

I have no problem with people using my part of qfind's code in whatever way they want. In fact, I would greatly appreciate anyone trying to work with qfind, especially if they share their findings here.

Since I copied a good chunk of the code from other sources, David Eppstein, zdr, Paul Tooke, Tomas Rokicki, Frank Everdij, Alex Greason, praosylen, and Adam P. Goucher have all essentially "contributed" code. I only ever got explicit permission from Rokicki who wanted to release his nt-zfind under the MIT license, but we were never able to contact zdr to achieve this.

I'm extremely confident that none of the above contributors would object to you using their code in your own projects.

Would scanning for optimizations fall into the "ok to use LLMs to help with" category?

I don't personally see why that would be a problem. Of course I would need to fully understand and likely rewrite any LLM code when adding it to the main project, but I have no objections to using such tools in this way. In fact, I encourage it.

[LuveelVoom]

I don't personally see why that would be a problem. Of course I would need to fully understand and likely rewrite any LLM code when adding it to the main project, but I have no objections to using such tools in this way. In fact, I encourage it.

Terrifyingly, it seems to have already reduced qfind's memory usage by 40% (and increased the speed by around 5%, but that's a lot less significant) and conveniently provided diff files! I will update as time goes on, if no better results emerge before I go to bed I will post the 40% reduction file here.

Personal testing w. qfind -r B3/S23 -v c/5 -w 10 -s even -f 1:
Peak mem use (no optimizations): 2.5gb
Peak mem use (optimizations): 1.48gb
Time w/o. optimizations: 150 sec
Time w. optimizations: 135 sec

The speed increase is apparently a lot more significant if you're on Linux, but I'm on MacOS so I can't test that.

Edit: Most recent version has a flag for reducing memory even further (to about -60% compared to base qfind) (flag is -DPACKLISTS), but it decreases speed by about 25%. Again, take all of this with lethal doses of salt until checked; the explanation is, um, annoying to read since it's AI-written (and I also couldn't check a lot of it).

[Sokwe]

Terrifyingly, it seems to have already reduced qfind's memory usage by 40% (and increased the speed by around 5%, but that's a lot less significant) and conveniently provided diff files! I will update as time goes on, if no better results emerge before I go to bed I will post the 40% reduction file here.

Thanks! If you would also share what LLM you used and just a little bit of your process, it might be informative.

The speed increase is apparently a lot more significant if you're on Linux, but I'm on MacOS so I can't test that.

How do you know? Does it run remote tests, or does it simply claim that?

the explanation is, um, annoying to read since it's AI-written (and I also couldn't check a lot of it).

I'd still be happy to read it, as it could help me better parse the code if I have some idea of the intent.

[LuveelVoom]

Thanks! If you would also share what LLM you used and just a little bit of your process, it might be informative.

I used Claude Opus 5.5. I gave it qfind's code and asked for a quick explanation of how it worked, then I had it do a sweep of the program to see which components of the search took the most time and memory. Once it outputted those, I gave it some optimization suggestions, which it proceeded to promptly reject all but one of and implement its own optimizations instead.

How do you know? Does it run remote tests, or does it simply claim that?

It has a sandbox which is running Linux. The even faster optimization comes from some sort of superpaging feature which MacOS does not support

I'd still be happy to read it, as it could help me better parse the code if I have some idea of the intent.

It is included in the .zip file!

These things are getting really powerful nowadays. I've got to go eventually write the guides and bugtest the other two programs "I'm" working on so that I can publish them. If anyone wants to beta-test, DM me.

[Sokwe]

I used Claude Opus 5.5. I gave it qfind's code and asked for a quick explanation of how it worked, then I had it do a sweep of the program to see which components of the search took the most time and memory. Once it outputted those, I gave it some optimization suggestions, which it proceeded to promptly reject all but one of and implement its own optimizations instead.

Thanks! I'm not sure what the most efficient use of your time (and money?) is, but a sweep for bugs might be in order. I'll certainly try to understand and implement any improvements. Also, I don't know if there's a way to get it to use more descriptive variable names, but that might help in parsing the new code. I can tell, for example, that dfLev is supposed to mean depthFirstLevel, but some of the variable names are shortened to the point of being opaque to me.

Keep me informed of anything else regarding this project, and feel free to post ideas here as well, as I might have some insight into their viability. I'm always open to suggestions.

Eventually (maybe soon) I want to refactor the code to be better organized, instead of just dumping nearly every function in a single file, but I'll save refactoring for sometime after I can implement any of these proposed improvements.

A not so interesting note: the change eliminates the old lookAhead() function, which is the last remnant of code essentially copied from the original zfind. If the new method gets implemented, the zfind code will have been ship of Theseused out of qfind, although the underlying ideas will remain basically the same.

[LuveelVoom]

Thanks! I'm not sure what the most efficient use of your time (and money?) is, but a sweep for bugs might be in order.

I have a plan, so this isn’t that much money. The whole thing cost about 20% of my weekly tokens. This is a hobby (well, ca is more like an obsession for me…), so the time taken isn’t really an issue to me

I'll certainly try to understand and implement any improvements. Also, I don't know if there's a way to get it to use more descriptive variable names, but that might help in parsing the new code. I can tell, for example, that dfLev is supposed to mean depthFirstLevel, but some of the variable names are shortened to the point of being opaque to me.

I’ll ask it to deobfuscate it today, along with a bug sweep.

Keep me informed of anything else regarding this project, and feel free to post ideas here as well, as I might have some insight into their viability. I'm always open to suggestions.

As the AI mentions in its readme, about 60% of branches (away from computer so I don’t remember exact terminology) are empty and useless and can be pruned. This would speed up the search greatly, but I’m not sure if it would preserve exhaustiveness and the AI couldn’t find a way to implement it.

I’ll attach a bug fixed and deobfuscated file later today.

Edit: Attached.

Edit 2: Potential additional 10% speedup on the way, stay tuned!

[LuveelVoom]

New version with a "--lookahead-depth" option which increases speed... sometimes.

Edit: The f**k? It just claimed it can reduce the memory by an exponential factor (halving the increase at each width). I'm probing it rn, will update post. I suspect it will break exhaustiveness.

Here is what it said, it's building a file rn, I'll update this post and add the second zip file when it finishes.

Found one asymptotic target. In real searches at width 9–10, essentially all lookup tables get built: 206 MB at w=9, 1.48 GB at w=10. That grows about 6.7× per width (heading toward 8×), so width 11 would need about 10 GB and width 12 about 70 GB. Width 11 and 12 runs didn’t finish their first deepening in 70 s here.

The rule computation already splits each row into a low half and a high half that overlap by 2 bits, and each half depends only on the matching halves of the three rows. So the per-pair tables can be replaced by two small global half-tables, joining the halves on the 2 overlap bits whenever a successor list is needed. That would change memory from roughly 8^w to about 2.8^w (≈3 MB at w=10, ≈170 MB at w=14). Existence tests stay a single bit test. I’m prototyping it now as a compile option, with a mode that reproduces the original row order exactly so output can be checked against the original.

It is now attached. (Supposedly-ram-free-qfind). Will not use factored tables (the memory improvement) below w10 unless you do --tables factored!!! be careful!!

Edit: Ampere found the copperhead in about 3 seconds and NNlk05 in about 8, with max mem usage of 4MB. Um. We don't know if it's exhaustive, though.

There may be bugs in qfind, or something? Methinks if this turns out to be exhaustive then this might be worth going to 3.0 for.

[Docsy]

In the CHANGES.md file, the LLM notes that it now rejects inputting a width over 14 due to "crashing". It also is rejecting -q below 4 for the same reason.

[Sokwe]

It just claimed it can reduce the memory by an exponential factor (halving the increase at each width). I'm probing it rn, will update post. I suspect it will break exhaustiveness.

Here is what it said, it's building a file rn, I'll update this post and add the second zip file when it finishes.

Found one asymptotic target. In real searches at width 9–10, essentially all lookup tables get built: 206 MB at w=9, 1.48 GB at w=10. That grows about 6.7× per width (heading toward 8×), so width 11 would need about 10 GB and width 12 about 70 GB. Width 11 and 12 runs didn’t finish their first deepening in 70 s here.

The rule computation already splits each row into a low half and a high half that overlap by 2 bits, and each half depends only on the matching halves of the three rows. So the per-pair tables can be replaced by two small global half-tables, joining the halves on the 2 overlap bits whenever a successor list is needed. That would change memory from roughly 8^w to about 2.8^w (≈3 MB at w=10, ≈170 MB at w=14). Existence tests stay a single bit test. I’m prototyping it now as a compile option, with a mode that reproduces the original row order exactly so output can be checked against the original.

It sounds like it's trying to do what has been proposed many, times by many people: build two lookup tables, one for each of the left and right half of each row and fuse them together. I've always meant try this, but I never got around to implementing it. I'm curious to see if the AI gets the nuance of it correct. Years ago I started sketching this up, but I never finished. I'm of the suspicion that it would negatively impact speed, but I'm not sure.

I actually have some ideas that maybe the AI can help figure out. There's one big bug, noted many times by many people, when gcd(period, offset) > 1. Basically, two nodes in the search tree can look identical, but if they have different phases, then they aren't necessarily truly the same. However, they sometimes are? Maybe? By forcing the hash function to consider phase for gcd > 1 searches, you end up with a lot of spaceships following other spaceships, because the new ship starts on a different phase. I'd like to figure out how to get the "true" identity of a node in this case, rather than just using a 2^period rows branch, which technically doesn't work with gcd > 1.

Ultimately then, I also want to modify qfind so that it can essentially output spaceships covering the whole valid search space, much like knight2. Currently, when qfind encounters a node that exists earlier in the graph, it eliminates it, and thus its parents might become unused and then stripped out in the compaction step. This means, for example, that qfind can't find pushalongs when using duplicate row elimination. What I want it to do is keep those nodes and just connect them to the duplicate node, so that if a completion starting from that node is found, it can print multiple spaceships containing that node with different front ends. Ultimately, for every node in the graph that is actually part of a complete spaceship at that width, I want the search to print a spaceship containing that node.

I’ll attach a bug fixed and deobfuscated file later today.

Thanks! Unfortunately, the deobfuscation got applied to my previously existing variable names, when I was really only wanting it to apply to new variables added by the LLM.

In the CHANGES.md file, the LLM notes that it now rejects inputting a width over 14 due to "crashing". It also is rejecting -q below 4 for the same reason.

The way qfind is currently constructed, it can't go above width 14. This is a result of taking the tree structure from gfind and using unsigned 16-bit integers to store the nodes. gfind, and thus qfind, uses the top two bits as a pointer into another table that tells it what a node's parent is. Since original qfind would require astronomical amounts of memory for a width-15 search, I've always considered this not to be a problem. If the above change where the lookup tables are split into two halves is made, then it would be better to just use 32-bit unsigned integers for the nodes.

A setting of -q below 4 makes the queue size so small that it can mess up the funny way that the tree is structured (it has to skip certain entries sometimes, which I think means the queue can run out of space without managing to add new nodes).

[LuveelVoom]

It sounds like it's trying to do what has been proposed many, times by many people: build two lookup tables, one for each of the left and right half of each row and fuse them together. I've always meant try this, but I never got around to implementing it. I'm curious to see if the AI gets the nuance of it correct. Years ago I started sketching this up, but I never finished. I'm of the suspicion that it would negatively impact speed, but I'm not sure.

I actually have some ideas that maybe the AI can help figure out. There's one big bug, noted many times by many people, when gcd(period, offset) > 1. Basically, two nodes in the search tree can look identical, but if they have different phases, then they aren't necessarily truly the same. However, they sometimes are? Maybe? By forcing the hash function to consider phase for gcd > 1 searches, you end up with a lot of spaceships following other spaceships, because the new ship starts on a different phase. I'd like to figure out how to get the "true" identity of a node in this case, rather than just using a 2^period rows branch, which technically doesn't work with gcd > 1.

I will ask it about these two ideas; unfortunately, I am currently out of credits. The memory method doesn't seem to have slowed down the search by any significant amount, shockingly, so qfind has around the same level of memory usage as gfind now while still having the speed of qfind. Terrifying.

Ultimately then, I also want to modify qfind so that it can essentially output spaceships covering the whole valid search space, much like knight2. Currently, when qfind encounters a node that exists earlier in the graph, it eliminates it, and thus its parents might become unused and then stripped out in the compaction step. This means, for example, that qfind can't find pushalongs when using duplicate row elimination. What I want it to do is keep those nodes and just connect them to the duplicate node, so that if a completion starting from that node is found, it can print multiple spaceships containing that node with different front ends. Ultimately, for every node in the graph that is actually part of a complete spaceship at that width, I want the search to print a spaceship containing that node.

Hmm, this seems like it would slow things down a lot? Would it not, and I'm just confused?

Thanks! Unfortunately, the deobfuscation got applied to my previously existing variable names, when I was really only wanting it to apply to new variables added by the LLM.

I can ask it to fix that... whenever I get my credits back. I wonder if there's some quick way to fix it by cross-checking the old and new files.

If the above change where the lookup tables are split into two halves is made, then it would be better to just use 32-bit unsigned integers for the nodes.

Would this be a difficult change to do?

[Sokwe]

unfortunately, I am out of credits.

That's fine, because I already have so much stuff to churn through that I wouldn't be able to do anything with it right now anyway. I'm going to focus on the things you've already posted and try to implement them in a way I find satisfying.

The memory method doesn't seem to have slowed down the search by any significant amount, shockingly, so qfind has around the same level of memory usage as gfind now while still having the speed of qfind. Terrifying.

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

Ultimately then, I also want to modify qfind so that it can essentially output spaceships covering the whole valid search space, much like knight2. Currently, when qfind encounters a node that exists earlier in the graph, it eliminates it, and thus its parents might become unused and then stripped out in the compaction step. This means, for example, that qfind can't find pushalongs when using duplicate row elimination. What I want it to do is keep those nodes and just connect them to the duplicate node, so that if a completion starting from that node is found, it can print multiple spaceships containing that node with different front ends. Ultimately, for every node in the graph that is actually part of a complete spaceship at that width, I want the search to print a spaceship containing that node.

Hmm, this seems like it would slow things down a lot? Would it not, and I'm just confused?

No, it shouldn't slow the search down at all (it would actually probably speed it up in some cases). Basically, it wouldn't do any extra work. It would just do more bookkeeping so that it doesn't eliminate things like pushalongs. Currently, the search deletes a node if it is already in the tree. Under this change, it wouldn't delete the node, but it would remove it from the queue and would instead declare that there is a node at that point matching an existing node, and would point to that existing node. I've never attempted to implement this, because I've never been sure of a good way to do it. It would likely require a major rewrite and perhaps a complete replacement of the tree and queue structure.

Thanks! Unfortunately, the deobfuscation got applied to my previously existing variable names, when I was really only wanting it to apply to new variables added by the LLM.

I can ask it to fix that... whenever I get my credits back. I wonder if there's some quick way to fix it by cross-checking the old and new files.

It's not urgent at all. Right now I'm just trying to understand the proposed changes.

If the above change where the lookup tables are split into two halves is made, then it would be better to just use 32-bit unsigned integers for the nodes.

Would this be a difficult change to do?

Probably not for the AI. It's a matter of tracking down relevant references to those 16-bit integers, especially anywhere that i didn't use the "row" custom type. In fact, you might want to instruct it to be something switchable with a compiler flag, like -DWIDE or something. If it were implemented properly, it would pretty much just need to make row into uint32_t instead of uint16_t, and it might need to change the node typedef as well. If the memory use doesn't go up much and the speed doesn't change, it could be fully switched to a 32-bit width.

[LuveelVoom]

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.

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.