qfind - a spaceship search program

[Drelectron8]

Oh, my goodness, thanks so much for helping me bro!

Does qfind appear to be working properly now? With the example input given above, the output should look like this:

Code: Select all

qfind v2.3 by Matthias Merzenich, 19 March 2023
Input: qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 1


Rule: B3/S23
Period: 10
Offset: 1
Width:  5
Symmetry: even
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Lookahead caching disabled
Number of threads: 2
Starting search
Queue full, depth 9, deepening 3, 131k/165k -> 70k/96k
Queue full, depth 9, deepening 6, 131k/174k -> 59k/82k
Queue full, depth 10, deepening 8, 131k/185k -> 46k/85k
Queue full, depth 13, deepening 8, 131k/391k -> 46k/177k
Queue full, depth 15, deepening 9, 131k/365k -> 47k/191k
Queue full, depth 16, deepening 11, 131k/360k -> 39k/171k
Queue full, depth 18, deepening 12, 131k/342k -> 41k/180k
Queue full, depth 19, deepening 14, 131k/358k -> 35k/165k
...

Remember that it can be very useful to send the output to a file. To do this, add " > filename.txt" to the end of your input line, where "filename" is the name of the desired output file. For example, by giving the following input:

Code: Select all

qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 2 > output.txt

a file called "output.txt" containing the program output will be created in the same folder as qfind.exe.

Run "qfind --help" to see a full list of options.

Does the search also work for strobing rules? It doesn't seem like it can, am I missing something?

[Sokwe]

Does the search also work for strobing rules? It doesn't seem like it can, am I missing something?

Unfortunately, qfind does not support strobing rules. qfind uses a lookup table to extend partial results, and the change in edge conditions in strobing rules would require a substantial rework of the lookup table construction, so I don't plan to add support any time soon.

[Drelectron8]

Does the search also work for strobing rules? It doesn't seem like it can, am I missing something?

Unfortunately, qfind does not support strobing rules. qfind uses a lookup table to extend partial results, and the change in edge conditions in strobing rules would require a substantial rework of the lookup table construction, so I don't plan to add support any time soon.

Are there any search programs that do support strobing rules you would like to recommend me?

[Sokwe]

Are there any search programs that do support strobing rules you would like to recommend me?

I'm not sure which programs support strobing rules. I know gfind supports Life-like strobing rules although it's a bit buggy. You could try rlifesrc, ikpx 2.2, LLSSS, and LLS to see if any of them do what you want.

[Drelectron8]

Are there any search programs that do support strobing rules you would like to recommend me?

I'm not sure which programs support strobing rules. I know gfind supports Life-like strobing rules although it's a bit buggy. You could try rlifesrc, ikpx 2.2, LLSSS, and LLS to see if any of them do what you want.

Okay, so I've been using rlifesrc for a while now, and I noticed, does this program search for just oscillators or spaceships and oscillators? Because it looks like there isn't a single spaceship that I found yet from this search program, it just keeps on giving oscillators.

[confocaloid]

[...]
Okay, so I've been using rlifesrc for a while now, and I noticed, does this program search for just oscillators or spaceships and oscillators? Because it looks like there isn't a single spaceship that I found yet from this search program, it just keeps on giving oscillators.

I can find the turtle in B3/S23, by going to Settings and setting width 13, height 12, period 3, dx 1, dy 0, then clicking "Apply settings" and "Start".

This is probably offtopic in this thread. Is there an existing forum thread for rlifesrc-related questions/issues?

[Drelectron8]

[...]
Okay, so I've been using rlifesrc for a while now, and I noticed, does this program search for just oscillators or spaceships and oscillators? Because it looks like there isn't a single spaceship that I found yet from this search program, it just keeps on giving oscillators.

I can find the turtle in B3/S23, by going to Settings and setting width 13, height 12, period 3, dx 1, dy 0, then clicking "Apply settings" and "Start".

This is probably offtopic in this thread. Is there an existing forum thread for rlifesrc-related questions/issues?

It works! Thanks so much for helping me!

[DroneBetter]

With the search

Code: Select all

./qfind -k -r B36/S245 -p 8 -y 2 -q 19 -t 8 -s o -w 5 -m 6144

qfind returns (many duplicates of) two spaceships, xq8_wh8r8hz08pl0lp8zx727zx9l9z08ld5dl8z02ve0ev2z2mtxtm2z047efe74 and xq8_04qh4hq4zgeqxqegz0mmd0dmmz014bsb41z0odvkvdozw1k8k1z0suorouszxg4gzw3btb3zce01010ecz27cxc72z1pusgsup1z3deb3bed3z23d555d32zwor1roz0oatbtaoz654x456zcrrc0crrcz42k8g8k24zx8i8z0gej2jegzwoo9ooz046pfp64zcettltteczxk3kz08cn1nc8zw6aca6zw20302, but the second is actually xq8_37n303n73z34s4g4s43zxorozwt9m9tzwc9e9czw7t5t7z266565662zxlhlz02qf6fq2zwi535izx333 (which it doesn't find) behind a p4 spaceship with which it never interacts. Is qfind to be considered nonexhaustive for period-multiplied searches?

[Sokwe]

Is qfind to be considered nonexhaustive for period-multiplied searches?

Unfortunately ordinary qfind can be buggy when gcd(period,displacement) > 1, unless you turn off duplicate elimination with "-h 0" (see this post for details). A period-multiplied search can only be considered exhaustive if there are no ships (even at periods dividing the full period) and "-h 0" is used.

Even when gcd(period,displacement) = 1, qfind is not exhaustive (i.e., it doesn't necessarily find all ships) unless there are no ships. This is because duplicate elimination can discard pushalongs. So a qfind search can only be considered exhaustive when there are no ships to find.

I wrote a version of qfind that, when used properly, is exhaustive (available here), but it can really only be used when there are a very small number of spaceships to find (otherwise it will generate an unfathomably large number of small files). For each duplicate partial result it eliminates, it saves that partial to a file. Once the search is complete, it can be run with an alternate parameter to process all the files and construct a "basis" of spaceships, a set of spaceships such that every possible set of rows contained in a spaceship of that width is represented in a spaceship from the set. Unfortunately, this set will have tons of duplicates, including many, many spaceships following other spaceships.

[Sokwe]

I'm working on an update to qfind. I already fixed a few bugs in the source code; nothing that affects the validity of the results, but the could have caused some unexpected crashes or searching with invalid rules like Bk/S.

I also added two features:

• A timestamp to get a sense of how the search is progressing
• The ability to specify forbidden conditions in the rule with a '~'. For example, a search with the rule string B3~78/S23~8 searches for spaceships in B3/S23 that never have a dead cell with 7 or 8 live neighbors and never have a live cell with 8 live neighbors; a search with the rule string B3~6/S23 searches for spaceships that work in both Life and HighLife; etc.

I want to make a few more modifications before I push a v2.4. At least the following:

• Check to see if a rule is valid for searching (e.g., give an error if the rule contains B1c) (Edit: done)
• Check to see if a rule actually supports gutter ships when using gutter symmetry (Edit: done)
• Change how state dumping works and make some form of state dumping the default

Please let me know if you have any comments or suggestions and especially if you find any bugs.

[dexter1]

Please let me know if you have any comments or suggestions and especially if you find any bugs.

I'm currently reviewing your latest commits to my fork and am running some benchmark tests. I also have some quality-of-life improvements, like adding a Makefile and wrapping all thread/openmp dependent code to be placed behind #ifdef _OPENMP (which is set by the '-fopenmp' option) to allow for compiling without OpenMP support.
I'll try today to create one or more small pull requests for your evaluation.

[Sokwe]

I'm currently reviewing your latest commits to my fork and am running some benchmark tests. I also have some quality-of-life improvements, like adding a Makefile and wrapping all thread/openmp dependent code to be placed behind #ifdef _OPENMP (which is set by the '-fopenmp' option) to allow for compiling without OpenMP support.
I'll try today to create one or more small pull requests for your evaluation.

Thanks!

Edit: By the way, your last merge used my significantly bugged update in the forbidden conditions code in praseRule(). I pushed a fix yesterday, so please merge with the latest version.

I'm not sure what the advantage of having a Makefile would be on such a small project, but I'm always open to making things more accessible. You make a good point about putting OpenMP-dependent code behind preprocessor directives.

Please let me know what you learn from your benchmarking.

Edit: I see you've backported to c, which is great! I've been meaning to do this, but hadn't gotten around to it.

[Sokwe]

I've made some more changes to the source code, notably overhauling the option parsing. Importantly, I replaced the -p (period) and -y (translation) options with a -v (velocity) option. Velocity should be input in the form <translation>c/<period>. I've also changed the meaning of the -a option and added new options. Use the option --help for a complete list of options.

As always, let me know if you have any comments or suggestions, and especially if you find any mistakes or bugs.

I've added the following features since v2.3 (some of which I already mentioned):

• A timestamp to get a sense of how the search is progressing
• The ability to specify forbidden conditions in the rule with a '~' (tilde). See above for an example.
• A minimum dump interval, so that the search will wait at least the given number of seconds between dumps (still depends on when queue compaction occurs). I set the default to 1800 seconds (30 minutes), so now dumping is on by default.
• A new dump mode, "overwrite" (should I call it "alternating" instead?), which is now the default. Instead of a number suffix, this mode saves dumps with an alternating color suffix, either "blue" or "gold" (chosen to be colorblind friendly). The original dump mode with number suffixes is now called "sequential". This can be set with the --dump-mode option.
• A check to see if the given rule has been proven to have no spaceships. An error is given if patterns can't escape some bound. I only give a warning in cases where no ships exist because back ends can't die, since one might still want to look for wickstretchers in these rules.
• A check to see if gutter-symmetric patterns are supported in the given rule when using gutter symmetry. Additionally, if a rule supports skewed gutter ships but not bilateral gutter ships, qfind now correctly prints the skewed spaceship. I believe the disallowed birth conditions for each skew type are the following (let me know if someone else has already determined this, so I can verify my work):
  • Skew 0: B2ce4ci6i
  • Skew 1: B1c2kn3ny4yz5r6i
  • Skew 2: B12aikn3cqr4cnyz5er6i
  Here are examples of spaceships with each skew type. These ships are in their minimal rules and do not work with the other skew types (and are not made of two non-interacting asymmetric ships)

  Code: Select all

  #C Skew-0 ship
  x = 15, y = 11, rule = B3-ey/S2-n3-c
  4bo5bo$3b3o3b3o$2bo2bo3bo2bo$b3o7b3o$2bobo5bobo$4b2o3b2o$o4bo3bo4bo$5b
  o3bo$2o3bo3bo3b2o$2bo2bo3bo2bo$4bo5bo!

  Code: Select all

  #C Skew-1 ship
  x = 11, y = 12, rule = B3aijr4aijknqr5-akr6ae7e/S3-cky6aek
  6b5o$5o3bo$2bo3bo3bo$o3bo$6b5o$5o3bobo$obo3b3o$2b3obob3o$3obobo2bo$bo
  2bo2bobo$bobo4bo$2bo!

  Code: Select all

  #C Skew-2 ship
  x = 13, y = 9, rule = B2ce3aijn4aijrt5ijnqy6a/S3-cr
  10bo$9bo$2bo4bob2obo$3bo5b2obo$ob2obo6bo$ob2o5bo2bo$o7b3o$o2bo$2b3o!

I'm currently reviewing your latest commits to my fork and am running some benchmark tests. I also have some quality-of-life improvements, like adding a Makefile and wrapping all thread/openmp dependent code to be placed behind #ifdef _OPENMP (which is set by the '-fopenmp' option) to allow for compiling without OpenMP support.
I'll try today to create one or more small pull requests for your evaluation.

If you don't get around to this, do you mind if I incorporate some of your changes anyway? Specifically, the #ifdef _OPENMP wrapping and backporting to c?

[dexter1]

If you don't get around to this, do you mind if I incorporate some of your changes anyway? Specifically, the #ifdef _OPENMP wrapping and backporting to c?

I saw your updates to the master branch and prepared two patch files yesterday, one for the _OPENMP wrapping (small) and one for the c backport (big) These patches should apply cleanly to commit f8eba5b. I'll post them as soon as i get home.

EDIT:
The attachment contains two patch files, "c.patch" and "openmp_define.patch" .The "c.patch" reverses function overloading and the call-by-reference operator '&' in some of the functions. An extension rename from '.cpp' to '.c' should suffice.

[Sokwe]

"c.patch" and "openmp_define.patch"

Thanks! These are now successfully merged. I'm especially grateful for the conversion (backporting was the wrong word, sorry) back to c. Of course, the code should now be compiled with a c compiler, rather than a c++ compiler. I edited the readme to reflect this.

The header file common.h is large and complicated enough that I should probably split it into multiple files, but I'm not sure what a good structure for this is. I'll start looking into it, but if anyone has a link to a good resource on this, please let me know.

[dexter1]

The header file common.h is large and complicated enough that I should probably split it into multiple files, but I'm not sure what a good structure for this is. I'll start looking into it, but if anyone has a link to a good resource on this, please let me know.

I haven't come across an easy recipe for doing this (yet), so this process is somewhat laborious. However, i have an old 'refactoring' branch where i initiated some work in transferring functions from 'common.h' into separate source files. Merging that branch with the current code will be problematic, but it might give you some insights:

The idea is that any function which does not rely on global variables can be moved to a separate source file and a header file declaring its function prototype. Other functions can have arguments added to reference global variables so they can get the same treatment.
Due to the size of 'common.h' it will take some time and effort to shrink that file.

[confocaloid]

[...]
As always, let me know if you have any comments or suggestions, and especially if you find any mistakes or bugs.
[...]

The following command prints many duplicate copies of the same spaceship in the same phase and in the same orientation:

Code: Select all

./qfind -r B3578/S23 -v c/4 -s asymmetric -w 9

Code: Select all

x = 9, y = 103, rule = B3578/S23
4bo$4b2o$4bob2o$3b3obo$2bo4b2o$2bob2ob2o$4bo2bo$3bo2bo2$2b3o$3b
2o$bobo$b3o$b3o$3b2o$bo3bo$2bo$2bo$2bo$bo$bobo$bobo$2bo$bo2bo$5b
o$2bob2o$3b2o$2b4o$2bo$3o$3bobo$3obo$o3b3o$2bob2o$2bo2bo$3bo$2ob
2o$2o2$3b2o$3bo$3bobo$6bo$2bo3bo$2bo3b2o$b2o2b2o$2o3b2o$3o2b2o$b
ob2obo2$bob3o$b3o$2o$o2bo$b2o$2bo3bo$4b4o$2b4obo$2bobo$b3o$2b2o$
2b2o$3b2o$4bo$bo2bo$4bo$bobo$bo$bo$2bo$b2o$bo$2b2o$b2obo$b3o2$b3o
$bo2$bo$4o2$4bo$2b3o2$4b2o2$3b3o$2b2o$b2obo$2b2o$2b2o$4bo$4b3o$2b
4o$2b3obo$5bo$7o$3o$bo5bo$3b5o$5b2o$5b2o!

[Sokwe]

The following command prints many duplicate copies of the same spaceship in the same phase and in the same orientation:

At the moment, qfind only avoids printing a pattern twice in a row. With an asymmetric search it finds one orientation, then the other, so now it has printed two "different" ships, and thus it is allowed to print the first one again. Since you have output enabled while deepening, it can find the same ship in the same orientation multiple times during the deepening step.

I should just have qfind hash every ship it finds so that it can do proper duplicate output elimination. I'll add that to the list of things to do for this coming update.

[CARuler]

qfind-v2.1-windows.zip
This was compiled under Mingw-w64 using

Code: Select all

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

it doesn't work for me

[confocaloid]

it doesn't work for me

Please describe the problem. "It doesn't work" isn't descriptive enough to help other people understand your problem. Is there some error message? What did you do?

[CARuler]

it doesn't open upon me pressing the open button I can see it flash before it closes

[confocaloid]

it doesn't open upon me pressing the open button I can see it flash before it closes

qfind needs to be invoked from the command line, with appropriate parameters that depend on what kind of spaceships you want to find.
Similarly to many other search programs in existence, qfind is a CLI software tool ("command line interface").

[Sokwe]

it doesn't open upon me pressing the open button I can see it flash before it closes

I think the following instructions will work on Windows 10/11 when using the downloaded executable:

1. In the file explorer, navigate to the folder containing qfind.
2. Hold down the shift key and right click on the folder containing qfind. There should be an option that says something like "open PowerShell here". Choose that option.
3. A new window with a command line pops up. You should now be able to run qfind by typing "./qfind [options...]" and hitting enter (where "[options...]" represents your chosen input). Run "./qfind --help" to get a list of available options.

Example search input:

Code: Select all

./qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 3

This should find the copperhead. Notice that I used "-t 3". This sets the number of threads for the search. You will probably want to change this value for your computer. Typically, you would probably want to use one less than the number of CPU cores your computer has.

Let me know if you're still having trouble after this.

Edit: also, you linked to qfind v2.1. Please use qfind v2.3 instead.

[CARuler]

it's running, although the you described wasn't actually what happed

[Sokwe]

it's running, although the you described wasn't actually what happed

Can you give more details? What happened or didn't happen? Can you copy and paste the program output here? When I ran the above search, this is what I got:

Code: Select all

qfind v2.3 by Matthias Merzenich, 19 March 2023
Input: ./qfind -r B3/S23 -p 10 -y 1 -w 5 -s even -t 3


Rule: B3/S23
Period: 10
Offset: 1
Width:  5
Symmetry: even
Queue size: 2^20
Hash table size: 2^20
Minimum deepening increment: 3
Lookahead caching disabled
Number of threads: 3
Starting search
Queue full, depth 9, deepening 3, 131k/165k -> 70k/96k
Queue full, depth 9, deepening 6, 131k/174k -> 59k/82k
Queue full, depth 10, deepening 8, 131k/185k -> 46k/85k
Queue full, depth 13, deepening 8, 131k/391k -> 46k/177k
Queue full, depth 15, deepening 9, 131k/365k -> 47k/191k
Queue full, depth 16, deepening 11, 131k/360k -> 39k/171k
Queue full, depth 18, deepening 12, 131k/342k -> 41k/180k
Queue full, depth 19, deepening 14, 131k/358k -> 35k/165k
Queue full, depth 23, deepening 13, 131k/547k -> 36k/238k
Queue full, depth 26, deepening 13, 131k/478k -> 35k/238k
Queue full, depth 28, deepening 14, 131k/436k -> 32k/223k
Queue full, depth 32, deepening 13, 131k/588k -> 28k/245k
Queue full, depth 36, deepening 12, 131k/533k -> 25k/247k
Queue full, depth 42, deepening 9, 131k/755k -> 27k/278k
Queue full, depth 49, deepening 5, 131k/868k -> 41k/370k
Queue full, depth 53, deepening 4, 131k/712k -> 45k/359k
Queue full, depth 55, deepening 5, 131k/617k -> 32k/267k
Queue full, depth 61, deepening 3, 131k/722k -> 39k/295k
Queue full, depth 64, deepening 3, 131k/657k -> 34k/253k
Queue full, depth 69, deepening 3, 131k/710k -> 30k/205k
Queue full, depth 79, deepening 3, 99k/983k -> 25k/164k
Queue full, depth 83, deepening 3, 131k/474k -> 18k/138k
Queue full, depth 113, deepening 3, 97k/983k -> 62k/112k
Queue full, depth 114, deepening 5, 131k/206k -> 56k/101k
Queue full, depth 114, deepening 8, 131k/204k -> 47k/92k
Queue full, depth 116, deepening 9, 131k/286k -> 46k/141k
Queue full, depth 117, deepening 11, 131k/284k -> 49k/147k
Queue full, depth 119, deepening 12, 131k/285k -> 54k/173k
Queue full, depth 120, deepening 14, 131k/319k -> 48k/166k
Queue full, depth 121, deepening 16, 131k/310k -> 46k/166k
Queue full, depth 122, deepening 18, 131k/323k -> 42k/167k
Queue full, depth 125, deepening 18, 131k/535k
x = 8, y = 12, rule = B3/S23
3b2o$b2o2b2o$3b2o$o6bo$bo4bo$3b2o$3o2b3o$2o4b2o3$3b2o$2bo2bo!

 -> 37k/230k
Queue full, depth 128, deepening 18, 131k/478k -> 36k/251k
Queue full, depth 130, deepening 19, 131k/441k -> 32k/234k
Queue full, depth 134, deepening 18, 131k/609k -> 31k/269k
Queue full, depth 138, deepening 17, 131k/588k -> 30k/287k
Queue full, depth 141, deepening 17, 131k/545k -> 26k/265k
Queue full, depth 144, deepening 17, 131k/527k -> 27k/249k
Queue full, depth 146, deepening 18, 131k/431k -> 30k/225k
Queue full, depth 148, deepening 19, 131k/423k -> 35k/223k
Queue full, depth 149, deepening 21, 131k/405k -> 34k/210k
Queue full, depth 151, deepening 22, 131k/381k -> 34k/207k
Queue full, depth 152, deepening 24, 131k/380k -> 29k/187k
Queue full, depth 154, deepening 25, 131k/359k -> 30k/188k
Queue full, depth 156, deepening 26, 131k/359k -> 29k/187k
Queue full, depth 158, deepening 27, 131k/404k -> 24k/185k
Queue full, depth 162, deepening 26, 131k/492k -> 23k/216k
Queue full, depth 164, deepening 27, 131k/444k -> 18k/192k
Queue full, depth 170, deepening 24, 131k/638k -> 19k/242k
Queue full, depth 175, deepening 22, 131k/598k -> 18k/254k
Queue full, depth 181, deepening 19, 131k/672k -> 18k/267k
Queue full, depth 187, deepening 16, 131k/726k -> 20k/288k
Queue full, depth 191, deepening 15, 131k/563k -> 22k/281k
Queue full, depth 194, deepening 15, 131k/541k -> 21k/246k
Queue full, depth 199, deepening 13, 131k/617k -> 24k/267k
Queue full, depth 205, deepening 10, 131k/753k -> 30k/325k
Queue full, depth 210, deepening 8, 131k/818k -> 32k/339k
Queue full, depth 216, deepening 5, 131k/795k -> 46k/420k
Queue full, depth 220, deepening 4, 131k/833k -> 42k/384k
Queue full, depth 224, deepening 3, 131k/799k -> 37k/333k
Queue full, depth 233, deepening 3, 73k/983k -> 19k/182k
Queue full, depth 271, deepening 3, 4.3k/983k -> 1.5k/14k
Search complete.

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

x = 10, y = 31, rule = B3/S23
4b2o$2b2o2b2o$4b2o$bo6bo$2bo4bo$4b2o$b3o2b3o$b2o4b2o3$4b2o$3bo2b
o2$3bo2bo$2bo4bo$bo6bo$o8bo$2ob4ob2o2$4b2o$3bo2bo$2b6o$3ob2ob3o3$
2b2o2b2o$b3o2b3o$2bo4bo2$3bo2bo$2b2o2b2o!