qfind - a spaceship search program
- ihatecorderships
- Posts: 309
- Joined: April 11th, 2021, 12:54 pm
- Location: Falls Church, VA
Re: qfind - a spaceship search program
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:However, I don't get any spaceships.
Code: Select all
./qfind -r B3/S2-i34q -p 5 -y 1 -w 3 -s odd
-- Kalan Warusa
Don't drink and drive, think and derive.
Don't drink and drive, think and derive.
Re: qfind - a spaceship search program
No, it's logical width 1. It will actually be width 3.
- ihatecorderships
- Posts: 309
- Joined: April 11th, 2021, 12:54 pm
- Location: Falls Church, VA
Re: qfind - a spaceship search program
What's the difference?
-- Kalan Warusa
Don't drink and drive, think and derive.
Don't drink and drive, think and derive.
Re: qfind - a spaceship search program
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!
- LaundryPizza03
- Posts: 2324
- Joined: December 15th, 2017, 12:05 am
- Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"
Re: qfind - a spaceship search program
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.LaundryPizza03 wrote: ↑May 17th, 2021, 1:15 amThe version called by the clang command is 12.0.0. I can't determine the version I installed via llvm-project.Sokwe wrote: ↑May 3rd, 2021, 5:53 pmI 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.LaundryPizza03 wrote: ↑May 3rd, 2021, 10:18 amI 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'
Code: Select all
x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
Re: qfind - a spaceship search program
I think you should try out installing either:LaundryPizza03 wrote: ↑July 10th, 2021, 9:33 pmAnyone 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.
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
Re: qfind - a spaceship search program
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"?
How much of current CA technology can I redevelop "on a desert island"?
Re: qfind - a spaceship search program
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
- LaundryPizza03
- Posts: 2324
- Joined: December 15th, 2017, 12:05 am
- Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"
Re: qfind - a spaceship search program
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?dexter1 wrote: ↑July 12th, 2021, 5:26 pmI think you should try out installing either:LaundryPizza03 wrote: ↑July 10th, 2021, 9:33 pmAnyone 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.LaundryPizza03 wrote: ↑May 17th, 2021, 1:15 amThe version called by the clang command is 12.0.0. I can't determine the version I installed via llvm-project.
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...
Code: Select all
x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
Re: qfind - a spaceship search program
git clone https://github.com/Matthias-Merzenich/qfind, then cd qfind. Compiling using the command in readme should do.LaundryPizza03 wrote: ↑February 25th, 2022, 12:08 amSince 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?
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
- LaundryPizza03
- Posts: 2324
- Joined: December 15th, 2017, 12:05 am
- Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"
Re: qfind - a spaceship search program
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:pzq_alex wrote: ↑February 27th, 2022, 1:04 amgit clone https://github.com/Matthias-Merzenich/qfind, then cd qfind. Compiling using the command in readme should do.LaundryPizza03 wrote: ↑February 25th, 2022, 12:08 amSince 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
g++ qfind.cpp -o qfind -Xpreprocessor -fopenmp -lomp
Code: Select all
x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
qfind v2.2 released (Re: qfind - a spaceship search program)
qfind v2.2 released
Changes:
A precompiled Windows executable is attached below, as had been requested for previous versions: This was compiled under Mingw-w64 using
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.
A precompiled Windows executable is attached below, as had been requested for previous versions: This was compiled under Mingw-w64 using
Code: Select all
g++ qfind.cpp -static -O3 -fopenmp -o qfind
-Matthias Merzenich
Re: qfind - a spaceship search program
Nothing much to report. I recompiled qfind using this command:
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.
Code: Select all
g++ qfind.cpp -o qfind-f -O3 -m64 -mavx2 -fopenmp -funroll-loops -fno-stack-protector -ffast-math -march=native
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
Re: qfind v2.2 released (Re: qfind - a spaceship search program)
Every spaceship RLE outputted by v2.2 ends with "2!", which is technically invalid but Golly/LifeViewer accepts them as well.Sokwe wrote: ↑June 21st, 2022, 8:41 amqfind v2.2 released
<changes>
As usual, please report any bugs or strange behavior you find.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
Re: qfind - a spaceship search program
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?
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"?
How much of current CA technology can I redevelop "on a desert island"?
Re: qfind - a spaceship search program
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
qfind v2.3 released (Re: qfind - a spaceship search program)
qfind v2.3 released
Changes:
A precompiled Windows executable is attached below, as had been requested for previous versions: This was compiled under Mingw-w64 using
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.
A precompiled Windows executable is attached below, as had been requested for previous versions: This was compiled under Mingw-w64 using
Code: Select all
g++ qfind.cpp -static -O3 -fopenmp -o qfind
-Matthias Merzenich
Re: qfind - a spaceship search program
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:
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"?
How much of current CA technology can I redevelop "on a desert island"?
Re: qfind - a spaceship search program
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
- Drelectron8
- Posts: 34
- Joined: March 5th, 2023, 4:54 am
- Location: Queenstown, Singapore
- Contact:
Re: qfind - a spaceship search program
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!
~Drelectron8
Re: qfind - a spaceship search program
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:Drelectron8 wrote: ↑July 19th, 2023, 6:30 amI'm sorry, but how does this search work? Where do I put the code in?
Code: Select all
qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2
Code: Select all
qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2 > output.txt
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
-Matthias Merzenich
Re: qfind - a spaceship search program
How do you run a search with a given partial result?
I tried the -l command but that didn't work.
I tried the -l command but that didn't work.
By: C.R. Hilton, currently working on another cool spaceship.
Re: qfind - a spaceship search program
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