qfind - a spaceship search program

[very]

i was invited to outline a method to halve the lookup tables

the idea is basically the same as scourge. instead of storing the whole lookup table for solutions x such that r1 r2 x evolves into r3, you only store the first L+1 bits, and enforce the first L evolution constraints, and make another lookup table where you store the last W-L+1 bits and enforce the last W-L evolution constraints

then to look up a full width r1 r2 r3 you look up their respective halves and take the pairs of x that share the same center 2 bits, since they can be spliced together into a row that satisfies all evolution constraints

this is already pretty much implemented in qfind with lowbit/highbit during makerow, but would need a lot of changing of lookahead

my code is here https://gitlab.com/terezi/scourge/-/blo ... type=heads i couldn't get it to be faster than SAT at width 22ish, but it might be a poor lookahead implementation

[CARuler]

can someone tell me how to make qfind upload to catagolue

[Sokwe]

can someone tell me how to make qfind upload to catagolue

It would be helpful if you could give more detail on what your goal is here, but qfind cannot upload to catagolue directly. You would instead need to run the output through apgsearch. Note that if you use the dump feature, you can get a list of partial results from a loaded dump file using the preview feature. Use the "--help" option in qfind to see the full list of options.

Edit: (unrelated note to self) trying to load a saved state from the following search in v2.4b causes a segfault:

Code: Select all

./qfind -r B2cen3aj4ai5aj6i/S1e2eik3enr4iq5i -w 5 -v c/8 -s a -t 3 -q 16 --dump-interval 1

[confocaloid]

can someone tell me how to make qfind upload to catagolue

In short, that could be done by compiling apgsearch separately, choosing something like "qfind_stdin_test" as the destination census name, and then running qfind with the output piped into apgsearch.

Here is what I did to find p3 orthogonal c/3 spaceships in the B38/S23 CA, using qfind with "-s odd -w 9".

No warranty express or implied.

Note: if you want to actually submit the spaceships (as I did) then remove the part " -t 1 " in the last invocation. Otherwise, it will just save a log file locally (which you will be able to open with a text editor and view the apgcodes) and quit without submitting anything.

Code: Select all

# mkdir test
# cd test

# git clone https://github.com/Matthias-Merzenich/qfind.git
# cd qfind
# gcc qfind.c -O3 -fopenmp -march=native -o qfind
# cd ..

# git clone https://gitlab.com/apgoucher/apgmera.git --recursive
# cd apgmera
# ./recompile.sh --rule b38s23 --symmetry qfind_stdin_test
# cd ..

# ./qfind/qfind -r B38/S23 -v c/3o -s odd -w 9 | ./apgmera/apgluxe -t 1 -L 1 -n 10000 -i 0

[vilc]

I found a strange bug in qfind v2.4b. With this command (or any command with a similar rule and this combination of speed, symmetry and width):

Code: Select all

qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4

The output is:

Code: Select all

qfind v2.4b by Matthias Merzenich, 13 September 2024
Input: qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4


Rule: B2ek3cij4ci/S2ce
speed: 2c/5
Width: 4
Symmetry: odd
Dump interval: 1800 seconds
Dump mode: overwrite
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 1

08/05/25 11:32:36 Starting search
08/05/25 11:32:36 Search complete.

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

P¯‗;

The partial diplayed at the end is always corrupt.
I compiled qfind on Windows with gcc 13.2.0 and mingw-w64, using the command given in readme.txt.

[confocaloid]

I found a strange bug in qfind v2.4b. [...]

Confirmed on Ubuntu with each of the following commands:

Code: Select all

# ./qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
# ./qfind -r B2ek3cij4ci/S2ce -v 2c/7 -s o -w 5
# ./qfind -r B2ek3cij4ci/S2ce -v 3c/7 -s o -w 5

Instead of a partial result, there are several "random-looking" bytes at the end, different when the test is repeated several times.

[AforAmpere]

Also happens on v2.3 with the corresponding command, and width 4 or 5:

Code: Select all

qfind v2.3 by Matthias Merzenich, 19 March 2023
Input: ./qfind -r B2ek3cij4ci/S2ce -p 5 -y 2 -s o -w 5


Rule: B2ek3cij4ci/S2ce
Period: 5
Offset: 2
Width:  5
Symmetry: odd
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Cache memory per thread: 32 megabytes
Number of threads: 1

08/05/25 21:56:27 Starting search
08/05/25 21:56:27 Search complete.

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

��,0^

[Sokwe]

I found a strange bug in qfind v2.4b. With this command (or any command with a similar rule and this combination of speed, symmetry and width):

Code: Select all

qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4

The output is:

Code: Select all

...

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

P¯‗;

The partial diplayed at the end is always corrupt.
I compiled qfind on Windows with gcc 13.2.0 and mingw-w64, using the command given in readme.txt.

I've known about this bug for a long time, and it only seems to occur when the search finishes at an extremely shallow depth with no spaceships found. I suspect this is a result of printing the pattern buffer before it's been written. I intend to fix it eventually, but I consider it a low priority. Let me know if you find an example search where it occurs for a longer final partial.

[dexter1]

I've known about this bug for a long time, and it only seems to occur when the search finishes at an extremely shallow depth with no spaceships found. I suspect this is a result of printing the pattern buffer before it's been written.

Correct. Valgrind confirms that patternBuf is used before assignment:

Code: Select all

$ valgrind ./qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
.
.
09/05/25 22:50:36 Starting search
09/05/25 22:50:36 Search complete.

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

==22532== Conditional jump or move depends on uninitialised value(s)
==22532==    at 0x484ED19: strlen (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==22532==    by 0x48EDD30: __vfprintf_internal (vfprintf-internal.c:1517)
==22532==    by 0x48D779E: printf (printf.c:33)
==22532==    by 0x114A0F: finalReport (common.h:3069)
==22532==    by 0x116F2B: main (qfind.c:501)

file common.h line 3069 is where patternBuf is used:

Code: Select all

   3068    if (params[P_LONGEST] && aborting != 3){ /* aborting == 3 means we reached ship limit */
   3069       if (patternBuf) printf("Longest partial result:\n\n%s",patternBuf);
   3070       else printf("No partial results found.\n");

Using gdb to run the program while watching changes in patternBuf gives the following:

Code: Select all

$ gdb qfind
.
Reading symbols from qfind...
(gdb) watch patternBuf
Hardware watchpoint 1: patternBuf
(gdb) run -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
Starting program: /home/frank/Documents/GOL/qfind/qfind -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
qfind v2.4b by Matthias Merzenich, 21 September 2024
Input: -r B2ek3cij4ci/S2ce -v 2c/5 -s o -w 4
.
09/05/25 23:02:36 Starting search

Hardware watchpoint 1: patternBuf

Old value = 0x0
New value = 0x55555556d8b0 "\340\254\341\367\377\177"
0x000055555555a314 in bufferPattern (b=3, pRows=0x0, nodeRow=0, lastRow=0, printExpected=0) at /home/frank/Documents/GOL/qfind/common.h:944
944	      patternBuf = (char*)malloc(((2 * MAXWIDTH + 4) * sxsAllocRows + 300) * sizeof(char));
(gdb) continue
Continuing.
09/05/25 23:03:06 Search complete.

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

����[Inferior 1 (process 23201) exited normally]
(gdb) 

Conclusion: The patternBuf is indeed being allocated in file common.h line 944 but it is never written into or cleared, leaving it filled with random data.
The most pragmatic way to fix this bug is by allocating the buffer using calloc. This fills the buffer with zeroes, which happen to be string terminators. Any subsequent call to a printf-like function with an uninitialized patternBuf as argument prints a null-string with length 0 instead of some random junk.

[mmmmmmmmm]

I have put qfind into visual studio code. How do I run it with an input? How do I run it in a different rule?

[Sokwe]

I have put qfind into visual studio code. How do I run it with an input? How do I run it in a different rule?

Are you using Windows and trying to compile from the source code? In that case I would highly recommend compiling qfind under Windows Subsystem for Linux instead. It also compiles fine using MinGW-w64. As I recall, qfind would need a very slight modification to compile with Visual Studio, because VS is a stickler for something regarding OpenMP (I can't remember the details at the moment). I think it compiles with clang with some warnings which I intend to address at some point.

Please let me know if you have any difficulty with this or if you have any further questions.

Also, I moved your post to the qfind discussion thread.

[ThePlayzr]

Since you mention Visual Studio, I assume you're using Windows and trying to compile from the source code. In that case I would highly recommend compiling qfind under Windows Subsystem for Linux instead. As I recall, qfind would need a very slight modification to compile with Visual Studio, because VS is a stickler for something regarding OpenMP (I can't remember the details at the moment). It also compiles fine using MinGW-w64.

Please let me know if you have any difficulty with this or if you have any further questions.

Also, I moved your post to the qfind discussion thread.

I am trying to do the exact same thing, funnily, so this is very helpful. I am going to try using MinGW-w64 to use it now.

[Sokwe]

I don't think my laptop is able to do compile qfind like that

Sorry, I'm having a bit of trouble understanding. Are you using Windows? If so, is there a problem with using Windows Subsystem for Linux?

[ThePlayzr]

I don't think my laptop is able to do compile qfind like that

Sorry, I'm having a bit of trouble understanding. Are you using Windows? If so, is there a problem with using Windows Subsystem for Linux?

Yes, I do use windows, but I use a thinkpad laptop.
erm, how do I use mingw-w64 to compile qfind?

[Sokwe]

how do I use mingw-w64 to compile qfind?

Again, I would primarily recommend using Windows Subsystem for Linux. However, you can install MinGW-w64 by following the instructions here. You can then open a terminal in your qfind folder and run the installation command given in the qfind readme:

Code: Select all

gcc qfind.c -O3 -fopenmp -march=native -o qfind

[ThePlayzr]

I read the instruction page, but I cannot find the 'bin' folder inside mingw-w64. I downloaded it here. What is this version's equivalent of the 'bin' folder?

[Sokwe]

I read the instruction page, but I cannot find the 'bin' folder inside mingw-w64. I downloaded it here. What is this version's equivalent of the 'bin' folder?

You seem to have downloaded only the source code. What you need is either pre-built binaries or an installer. One source of pre-built binaries is from the link given in the tutorial. Other sources are available in the "pre-built toolchains" section of this webpage.

Another way to install gcc is to first install MSYS2, and then use the MSYS2 package manager to install gcc, although I've never done this myself, so I can't give further advice.

And again, I recommend Windows Subsystem for Linux (WSL2) first. I created the MinGW-w64 tutorial for those who, for whatever reason, couldn't use WSL2.

[ThePlayzr]

...

You seem to have downloaded only the source code. What you need is either pre-built binaries or an installer. One source of pre-built binaries is from the link given in the tutorial. Other sources are available in the "pre-built toolchains" section of this webpage.

Another way to install gcc is to first install MSYS2, and then use the MSYS2 package manager to install gcc, although I've never done this myself, so I can't give further advice.

And again, I recommend Windows Subsystem for Linux (WSL2) first. I created the MinGW-w64 tutorial for those who, for whatever reason, couldn't use WSL2.

I do not have administrator rights, which is why I am trying to use MinGW-w64. Also, do I not need the source code that I downloaded?

[Sokwe]

do I not need the source code that I downloaded?

No, you do not need the source code. Instead, I recommend following the instructions in the tutorial exactly as they are written. If you have any trouble with this or any further questions, please let me know. You might also want to install Git Bash (see the previous section in the tutorial).

Edit: if you get it working, please give this post a like.

[ThePlayzr]

do I not need the source code that I downloaded?

No, you do not need the source code. Instead, I recommend following the instructions in the tutorial exactly as they are written. If you have any trouble with this or any further questions, please let me know. You might also want to install Git Bash (see the previous section in the tutorial).

Edit: if you get it working, please give this post a like.

I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy

[Resu]

I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy

Are you using a administrator account?

[ThePlayzr]

I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy

Are you using a administrator account?

I do not have administrator rights on this device.

[Resu]

I do not have administrator rights on this device.

Can you contact your administrator?
Also, are you actually allowed to install qfind on that device?
What are you doing to cause the ‘your administrator has caused windows security to block this action' message?

[Sokwe]

I installed minGW-w64, put it on the path, compiled the file, I did everything. but after all that, 'your administrator has caused windows security to block this action' ughhhh whyyyyy

Can you give any more details? What are the exact steps you take that cause the error? Does the error say anything more than "your administrator has caused windows security to block this action"?

[Sokwe]

I'm not really finished with qfind v2.4, but I haven't worked on it in almost a year, and in light of the above questions I decided I should at least provide a portable Windows executable for the latest version.

Here is a zip archive containing a Windows executable for x86-64 CPUs:

qfind-v2.4b-windows-x86_64.zip

(224.03 KiB) Downloaded 42 times

This was compiled under MinGW-w64 with the MSVCRT runtime library using the following command:

Code: Select all

gcc qfind.c -static -O3 -fopenmp -march=x86-64 -o qfind

If anyone has any trouble getting this to work on their machine, please let me know.

I'm curious to know if there's a desire or need for a pre-compiled Windows executable for ARM64 CPUs. I don't actually know anything about cross-compiling for the ARM64 architecture, but if there's interest I wouldn't mind giving it a shot.