qfind - a spaceship search program

For scripts to aid with computation or simulation in cellular automata.
User avatar
cgoler2
Posts: 224
Joined: March 10th, 2021, 2:32 pm
Location: Living in a half-bakery

Re: qfind - a spaceship search program

Post by cgoler2 » May 24th, 2021, 6:26 pm

Try enabling lookahead caching.

User avatar
ihatecorderships
Posts: 309
Joined: April 11th, 2021, 12:54 pm
Location: Falls Church, VA

Re: qfind - a spaceship search program

Post by ihatecorderships » May 24th, 2021, 6:52 pm

However, I don't get any spaceships.
I'm not sure if this works or not, because cygwin is taking a long time to download, but maybe you should change -w 1 to -w 3 so the input looks like this:

Code: Select all

./qfind -r B3/S2-i34q -p 5 -y 1 -w 3 -s odd
It seems to be searching for spaceships with width 1.
-- Kalan Warusa
Don't drink and drive, think and derive.

User avatar
cgoler2
Posts: 224
Joined: March 10th, 2021, 2:32 pm
Location: Living in a half-bakery

Re: qfind - a spaceship search program

Post by cgoler2 » May 24th, 2021, 7:12 pm

No, it's logical width 1. It will actually be width 3.

User avatar
ihatecorderships
Posts: 309
Joined: April 11th, 2021, 12:54 pm
Location: Falls Church, VA

Re: qfind - a spaceship search program

Post by ihatecorderships » May 24th, 2021, 7:15 pm

cgoler2 wrote:
May 24th, 2021, 7:12 pm
No, it's logical width 1. It will actually be width 3.
What's the difference?
-- Kalan Warusa
Don't drink and drive, think and derive.

User avatar
cgoler2
Posts: 224
Joined: March 10th, 2021, 2:32 pm
Location: Living in a half-bakery

Re: qfind - a spaceship search program

Post by cgoler2 » May 24th, 2021, 7:18 pm

I made a mistake somewhere. Try width 2.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: qfind - a spaceship search program

Post by dvgrn » May 24th, 2021, 7:39 pm

cgoler2 wrote:
May 24th, 2021, 7:18 pm
I made a mistake somewhere. Try width 2.
Looks healthy -- thanks again! So ./qfind -r B3/S2-i34q -p 5 -y 1 -w 2 -s odd makes a good instant test of qfind. What shows up is a T-pentomino, but the t-tetromino is one of the phases:

Code: Select all

x = 3, y = 3, rule = B3/S2-i34q
bo$bo$3o!

Code: Select all

$ ./qfind -r B3/S2-i34q -p 5 -y 1 -w 2 -s odd
qfind v2.1 by Matthias Merzenich, 3 May 2021
Input: ./qfind -r B3/S2-i34q -p 5 -y 1 -w 2 -s odd


Rule: B3/S2-i34q
Period: 5
Offset: 1
Width:  2
Symmetry: odd
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 5
Lookahead caching disabled
Number of threads: 1
Starting search

x = 3, y = 3, rule = B3/S2-i34q
bo$bo$3o!

Search complete.

1 spaceship found.
Maximum depth reached: 33
Longest partial result:

x = 3, y = 3, rule = B3/S2-i34q
bo$bo$3o!

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: qfind - a spaceship search program

Post by LaundryPizza03 » July 10th, 2021, 9:33 pm

LaundryPizza03 wrote:
May 17th, 2021, 1:15 am
Sokwe wrote:
May 3rd, 2021, 5:53 pm
LaundryPizza03 wrote:
May 3rd, 2021, 10:18 am
I could make and set up LLVM according to these directions, but I couldn't use OpenMP using the -fopenmp tag.

Code: Select all

> cd ~/qfind
> g++ qfind.cpp -static -O3 -fopenmp -o qfind
clang: error: unsupported option '-fopenmp'
clang: error: unsupported option '-fopenmp'
I suspect you would want to use clang++, not g++ (since g++ is part of GCC, not LLVM). It appears MacOS calls clang++ when you use g++, but I'm not sure whether it's calling the version you just installed or the version that comes with MacOS. I think the MacOS clang doesn't automatically support OpenMP. You might be able to determine whether the correct version of clang is being used by running "clang --version" and comparing the results to whatever you installed. If you do figure out what the problem is, it might be helpful to other users to post your solution here.
The version called by the clang command is 12.0.0. I can't determine the version I installed via llvm-project.
Anyone else got an idea? I'm having trouble locating useful information about installing OpenMP on macOS Big Sur. I can't set up -fopenmp using sudo becuase I am not logged in as a system administrator.

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
dexter1
Posts: 71
Joined: February 26th, 2020, 8:46 am

Re: qfind - a spaceship search program

Post by dexter1 » July 12th, 2021, 5:26 pm

LaundryPizza03 wrote:
July 10th, 2021, 9:33 pm
Anyone else got an idea? I'm having trouble locating useful information about installing OpenMP on macOS Big Sur. I can't set up -fopenmp using sudo becuase I am not logged in as a system administrator.
I think you should try out installing either:
1) An LLVM version which supports openMP, as Sokwe hinted. See this thread for details.
2) libomp as a development library (i.e. with headers) next to the default Apple llvm compiler. Mentioned in the same thread as above.

Both solutions require you using non standard paths to the compilers and libraries, so this is a bit fiddly...
Frank Everdij

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: qfind - a spaceship search program

Post by pzq_alex » February 19th, 2022, 4:16 am

What happened?

Code: Select all

pzq@REDACTED:~/qfind$ ./qfind -r B2e3aiq/S2ce3a4aqr5ijnq -p 3 -y 1 -w 13 -s odd
qfind v2.1 by Matthias Merzenich, 3 May 2021
Input: ./qfind -r B2e3aiq/S2ce3a4aqr5ijnq -p 3 -y 1 -w 13 -s odd


Rule: B2e3aiq/S2ce3a4aqr5ijnq
Period: 3
Offset: 1
Width:  13
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
Starting search
Killed
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: qfind - a spaceship search program

Post by Sokwe » February 19th, 2022, 8:54 am

pzq_alex wrote:
February 19th, 2022, 4:16 am
What happened?
You probably ran out of memory. Very few if any computers will have the necessary RAM to run a logical-width 13 qfind search (width 11 typically takes over 20 gigabytes). Try ikpx2 or rlifesrc instead.

Edit: you may have been able to complete width 11 and 12 searches in this case, because at those widths there are no long partial results, so the search finishes before it uses too much memory. However, any width 11+ search that lasts for more than a few seconds will use an unreasonable amount of memory.
-Matthias Merzenich

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: qfind - a spaceship search program

Post by LaundryPizza03 » February 25th, 2022, 12:08 am

dexter1 wrote:
July 12th, 2021, 5:26 pm
LaundryPizza03 wrote:
July 10th, 2021, 9:33 pm
LaundryPizza03 wrote:
May 17th, 2021, 1:15 am
The version called by the clang command is 12.0.0. I can't determine the version I installed via llvm-project.
Anyone else got an idea? I'm having trouble locating useful information about installing OpenMP on macOS Big Sur. I can't set up -fopenmp using sudo becuase I am not logged in as a system administrator.
I think you should try out installing either:
1) An LLVM version which supports openMP, as Sokwe hinted. See this thread for details.
2) libomp as a development library (i.e. with headers) next to the default Apple llvm compiler. Mentioned in the same thread as above.

Both solutions require you using non standard paths to the compilers and libraries, so this is a bit fiddly...
Since the last time I brought this up, I've installed Homebrew on my computer for an unrelated purpose. How can I install qfind using brew?

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: qfind - a spaceship search program

Post by pzq_alex » February 27th, 2022, 1:04 am

LaundryPizza03 wrote:
February 25th, 2022, 12:08 am
Since the last time I brought this up, I've installed Homebrew on my computer for an unrelated purpose. How can I install qfind using brew?
git clone https://github.com/Matthias-Merzenich/qfind, then cd qfind. Compiling using the command in readme should do.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

User avatar
LaundryPizza03
Posts: 2295
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: qfind - a spaceship search program

Post by LaundryPizza03 » February 27th, 2022, 5:29 pm

pzq_alex wrote:
February 27th, 2022, 1:04 am
LaundryPizza03 wrote:
February 25th, 2022, 12:08 am
Since the last time I brought this up, I've installed Homebrew on my computer for an unrelated purpose. How can I install qfind using brew?
git clone https://github.com/Matthias-Merzenich/qfind, then cd qfind. Compiling using the command in readme should do.
Thanks. If you have a macOS platform with Homebrew, first clone the qfind repository, and install llvm and libomp with Homebrew. Then in the qfind directory, compile qfind by writing:

Code: Select all

g++ qfind.cpp -o qfind -Xpreprocessor -fopenmp -lomp

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

qfind v2.2 released (Re: qfind - a spaceship search program)

Post by Sokwe » June 21st, 2022, 8:41 am

qfind v2.2 released

Changes:
  • The output spaceships and partial results are now oriented so that they travel upward. This matches the orientation needed for get-rows.lua.
  • The partial results given by the preview command (-u) now include the extension rows.
  • I fixed two heap overflow "bugs" that I think never occurred in practice. The first was a check for an index to be nonnegative that occurred after an array was potentially accessed at that index. This would only be a problem if qfind tried to print a spaceship "partial" with only blank rows, which shouldn't occur under normal use. The fix was to perform the index check first.

    The second potential "bug" was identified by user "#9 se fan: ihatecorderizing" on Discord using address-sanitizer. It was the result of a call to memcmp() for data sets of differing lengths. However, these data sets were guaranteed to be different significantly before the length of the shorter data set so this would only be a problem if memcmp() was comparing memory out of order, which seems doubtful. The fix does not affect performance.
As usual, please report any bugs or strange behavior you find.

A precompiled Windows executable is attached below, as had been requested for previous versions:
qfind-v2.2-windows.zip
(139.27 KiB) Downloaded 44 times
This was compiled under Mingw-w64 using

Code: Select all

g++ qfind.cpp -static -O3 -fopenmp -o qfind
-Matthias Merzenich

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: qfind - a spaceship search program

Post by pzq_alex » July 9th, 2022, 10:08 pm

Nothing much to report. I recompiled qfind using this command:

Code: Select all

g++ qfind.cpp -o qfind-f -O3 -m64 -mavx2 -fopenmp -funroll-loops -fno-stack-protector -ffast-math -march=native
When running the search for copperhead (./qfind -r B3/S23 -p 10 -y 1 -w 5 -s e), qfind-f appeared to be 1 second faster than raw qfind or so. So, this may be faster than qfind when running big searches (on 64-bit machines with avx2, of course) at the risk of being more unsafe.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: qfind v2.2 released (Re: qfind - a spaceship search program)

Post by pzq_alex » July 20th, 2022, 10:48 pm

Sokwe wrote:
June 21st, 2022, 8:41 am
qfind v2.2 released
<changes>
As usual, please report any bugs or strange behavior you find.
Every spaceship RLE outputted by v2.2 ends with "2!", which is technically invalid but Golly/LifeViewer accepts them as well.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: qfind - a spaceship search program

Post by pzq_alex » September 21st, 2022, 8:27 am

Anyway, question:

If I have run get-rows.lua on a row of some partial, and fed it to qfind as initrows.txt, how do I recover the full ship from the partial and the output of qfind?
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: qfind - a spaceship search program

Post by Sokwe » September 21st, 2022, 9:33 am

pzq_alex wrote:
September 21st, 2022, 8:27 am
If I have run get-rows.lua on a row of some partial, and fed it to qfind as initrows.txt, how do I recover the full ship from the partial and the output of qfind?
Annoyingly, you will need to manually attach the output completed back end to the partial you used for the input. Keep in mind that the output partial may be in a different phase than the input partial, so you may need to advance the input partial by a few generations to match them up.

It would be nice if it let you input the entire front end of the spaceship (even if its wider than the desired search area) so that it could output the complete ship, but I haven't gotten around to adding such a feature.
-Matthias Merzenich

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

qfind v2.3 released (Re: qfind - a spaceship search program)

Post by Sokwe » March 19th, 2023, 1:34 am

qfind v2.3 released

Changes:
  • I added an option (-k) to suppress output of subperiodic objects. This option is a toggle (default: subperiodic output enabled) and additionally applies to previewing partial results. If you ran qfind with the -k option, then any dump files from that run will also have this option enabled so "./qfind -l dumpfile -u" would then give only full-period partials while "./qfind -l dumpfile -u -k" would give all partials.
  • I added an option (-o) to search for waves with symmetric boundary conditions. Valid symmetry types are odd, even, gutter, and disabled. I did not include support for asymmetric waves because it would have required rewriting the code for duplicate row elimination and I wasn't sure how to go about it.
  • In qfind-s the width can now be set at run-time. There was essentially no code that was actually using the compile-time WIDTH anyway.
  • In qfind-s the PERIOD and OFFSET can now be set in the command line when compiling. For example, to compile qfind-s for c/6 searching with g++ I can run

    Code: Select all

    g++ qfind-s.cpp -O3 -fopenmp -march=native -o qfind-c6 -D PERIOD=6 -D OFFSET=1
  • I changed the default minimum deepening increment to 3. I found that for higher-period searches using the period as the default deepening increment causes far too deep lookahead that greatly increases the time between queue compaction and state dumping.
  • I fixed a minor bug causing '2' to be printed before '!' in all RLE ouput.
As usual, please report any bugs or strange behavior you find.

A precompiled Windows executable is attached below, as had been requested for previous versions:
qfind-v2.3-windows.zip
(170.4 KiB) Downloaded 33 times
This was compiled under Mingw-w64 using

Code: Select all

g++ qfind.cpp -static -O3 -fopenmp -o qfind
-Matthias Merzenich

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: qfind - a spaceship search program

Post by pzq_alex » May 7th, 2023, 7:55 am

One small question: how does the hash table work in qfind (and gfind)? Does it handle collisions at all?

simple.hpp, lines 637-640 read:

Code: Select all

/* set node (NOT child) to be visited */
static inline void setVisited(node b) {
   if (hash != 0) hash[ hashFunction(PARENT(b),ROW(b)) ] = b;
}
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: qfind - a spaceship search program

Post by Sokwe » May 7th, 2023, 7:19 pm

pzq_alex wrote:
May 7th, 2023, 7:55 am
One small question: how does the hash table work in qfind (and gfind)? Does it handle collisions at all?
gfind (and thus qfind) avoids false positives (as long as gcd(period,offset) == 1) when checking to see if the new node has been seen previously, but that's about it.

Elements in the hash table point to a corresponding node in the search tree. When it checks to see if a new node b is already in the search tree, it compares node b to the node stored at hash[hashFunction(b)]. If the nodes are identical, then the new node b has already been seen so it is not added to the search tree. However, if the nodes are not identical, then node b will be added to the search tree, and hash[hashFunction(b)] will point to node b, overwriting whatever node was pointed to previously. So when reading the hash table, hash collisions are dealt with by checking the new node against the previously hashed node. When writing to the hash table, hash collisions are dealt with by overwriting the previous value.

All of this could be improved by rewriting the breadth-first infrastructure. The only reason it works the way it does is that I copied code from gfind for my own convenience. The reason gfind works this way is probably to save on memory, which is not much of a concern anymore.

If gcd(period,offset) > 1, then the hash table check could give false positives (more likely at very small widths). In order to prevent this, you could additionally check that the phase of the nodes match. I've never properly dealt with this, as I'm not sure of the best way to do it.
-Matthias Merzenich

User avatar
Drelectron8
Posts: 34
Joined: March 5th, 2023, 4:54 am
Location: Queenstown, Singapore
Contact:

Re: qfind - a spaceship search program

Post by Drelectron8 » July 19th, 2023, 6:30 am

I'm sorry, but how does this search work? Where do I put the code in?

Code: Select all

x = 20, y = 28, rule = B01356/S012345
17b3o$5b6o$4b5ob10o$3b15o$4b4ob9o$5b5o6$17b3o$4b6o$3b5ob11o$2b16o$3b4o
b10o$4b5o6$17b3o$2b7o$b6ob12o$18o$b5ob11o$2b6o!
-Time's just a short-living, the Wickstretchers will remain after all is done with.
~Drelectron8

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: qfind - a spaceship search program

Post by Sokwe » July 19th, 2023, 12:01 pm

Drelectron8 wrote:
July 19th, 2023, 6:30 am
I'm sorry, but how does this search work? Where do I put the code in?
It's a command line program. If you are using Windows you can download a zip file from the bottom of this post containing the executable file. After extracting the zip file to the desired folder, you will need to open a command prompt window and navigate to that folder (using the cd command, look online for how to change directories in windows command prompt for more details). Once you have navigated to the right folder, you can run the program by typing its name and a space-separated list of options and then pressing the enter key. For example, typing the following would search for a c/10 orthogonal spaceship with even symmetry and logical width 5 (full width 10 due to even symmetry) using two threads:

Code: Select all

qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2
Run "qfind --help" to get a list of all options. It can also be helpful to send output to a file by adding " > filename" to the end of the line. For example:

Code: Select all

qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2 > output.txt
If you are using an operating system other than windows, you will need to compile the code. You will probably have to look online for how to do this for your operating system.

Once you've compiled the code, running it is pretty much the same as on Windows. You will need to open the command terminal and navigate to the correct directory. To run the program, you will probably need to type "./qfind" instead of just "qfind". For example:

Code: Select all

./qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2 > output.txt
I hope this helps.
-Matthias Merzenich

User avatar
C_R_116
Posts: 468
Joined: April 15th, 2021, 2:49 pm
Location: At my home doing other random stuff.

Re: qfind - a spaceship search program

Post by C_R_116 » August 5th, 2023, 8:58 pm

How do you run a search with a given partial result?

I tried the -l command but that didn't work.
By: C.R. Hilton, currently working on another cool spaceship.

Sokwe
Moderator
Posts: 2643
Joined: July 9th, 2009, 2:44 pm

Re: qfind - a spaceship search program

Post by Sokwe » August 6th, 2023, 4:22 am

C_R_116 wrote:
August 5th, 2023, 8:58 pm
How do you run a search with a given partial result?

I tried the -l command but that didn't work.
To extend a partial result, use the -e command. You will first need a file containing the rows you want to start from. This file can be created by the Golly Lua script getrows.lua (follow the instructions in the code comments). This will create a file called initrows.txt. Make sure initrows.txt is in the same folder as qfind, and then include "-e initrows.txt" in your command line options.

The -l command is for loading a search state saved with the -d command. The -d command causes qfind to periodically save the state of the search to a file so that it can be restarted from that point and doesn't need to be started from the beginning.
-Matthias Merzenich

Post Reply