qfind - a spaceship search program

For scripts to aid with computation or simulation in cellular automata.
User avatar
LaundryPizza03
Posts: 1051
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 » April 6th, 2020, 4:11 pm

wildmyron wrote:
April 6th, 2020, 12:42 pm
LaundryPizza03 wrote:
April 6th, 2020, 7:04 am
qfind gave me some weird results on asymmetric. For example, some results at width 9 in B3578/S23 appear to be broken:

Code: Select all

<snip rle>
Rather, each of these results turns out to be half of a gutter-symmetric ship.
That is very strange, I don't see that result when I run the same search in my build of qfind (current github version)

Code: Select all

./qfind B3578/S23 p3 k1 w9 a

Code: Select all

<snip rle>
It's unclear what would happen in rules like B36/S23 that have no gutter or skew-gutter symmetry.
qfind and zfind both don't check if gutter symmetry is valid in the specified rule. Running such a search will give invalid results.
git pull claims it's already up to date.

Code: Select all

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

The latest edition of new-gliders.db.txt and oscillators.db.txt have 31150 spaceships and 1205 oscillators from outer-totalistic rules. You are invited to help!

Hunting
Posts: 3526
Joined: September 11th, 2017, 2:54 am

Re: qfind - a spaceship search program

Post by Hunting » April 6th, 2020, 8:23 pm

LaundryPizza03 wrote:
April 6th, 2020, 7:04 am
qfind gave me some weird results on asymmetric.
Yep. I'm getting failed ships in this rule:

Code: Select all

D:\qfind-master>a B2-ac3acikq4ci5e/S01e2ei3a p5 k1 w10 d
qfind v1.1 by Matthias Merzenich, 7 January 2020
- a B2-ac3acikq4ci5e/S01e2ei3a p5 k1 w10 d

Rule: B2-ac3acikq4ci5e/S01e2ei3a
Period: 5
Offset: 1
Width:  10
Dump state after queue compaction
Queue size: 2^23
Hash table size: 2^21
Minimum deepening increment: 5
Cache memory per thread: 32 megabytes
Number of threads: 1
Starting search
Queue full, depth 5, deepening 5, 1.0M/1.0M -> 8.6k/13k
State dumped to dump0001
Queue full, depth 41, deepening 5, 124k/7.8M -> 2.6k/14k
State dumped to dump0002
Queue full, depth 94, deepening 5, 222k/7.8M -> 6.0k/25k
State dumped to dump0003
Queue full, depth 147, deepening 5, 97k/7.8M -> 2.4k/13k
State dumped to dump0004
Queue full, depth 231, deepening 5, 233k/7.8M -> 5.7k/26k
State dumped to dump0005
Queue full, depth 273, deepening 5, 175k/7.8M -> 6.3k/30k
State dumped to dump0006
Queue full, depth 313, deepening 5, 150k/7.8M -> 3.3k/20k
State dumped to dump0007

x = 10, y = 65, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3bo$3b2obo$3b2obo$2b2o2b
2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o$ob3o$3b2o$2bo$ob2o2b
o2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bobo2bo$o$bo$o3bobo$b3o$
o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o2$obo$bobo$6bo$3bobo$
4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3bo2bobo$2bobo$bo6bo$2b
obo2bo$bo$o2b2o!

Queue full, depth 348, deepening 5, 682k/7.8M -> 17k/66k
State dumped to dump0008
Queue full, depth 360, deepening 5, 1.0M/7.2M -> 24k/97k
State dumped to dump0009
Queue full, depth 371, deepening 5, 879k/7.8M -> 25k/113k
State dumped to dump0010
Queue full, depth 375, deepening 6, 1.0M/2.3M -> 22k/98k
State dumped to dump0011
Queue full, depth 381, deepening 5, 1.0M/3.3M -> 33k/142k
State dumped to dump0012
Queue full, depth 385, deepening 6, 1.0M/2.6M -> 23k/113k
State dumped to dump0013
Queue full, depth 389, deepening 7, 1.0M/2.2M -> 17k/91k
State dumped to dump0014
Queue full, depth 394, deepening 7, 1.0M/2.6M -> 18k/97k
State dumped to dump0015
Queue full, depth 398, deepening 8, 1.0M/2.0M -> 16k/84k
State dumped to dump0016
Queue full, depth 402, deepening 9, 1.0M/2.1M -> 11k/68k
State dumped to dump0017
Queue full, depth 407, deepening 9, 1.0M/2.4M -> 12k/68k
State dumped to dump0018
Queue full, depth 411, deepening 10, 1.0M/2.1M -> 11k/65k
State dumped to dump0019
Queue full, depth 416, deepening 10, 1.0M/2.3M -> 11k/67k
State dumped to dump0020
Queue full, depth 421, deepening 10, 1.0M/2.6M -> 11k/70k
State dumped to dump0021
Queue full, depth 426, deepening 10, 1.0M/3.1M -> 10k/71k
State dumped to dump0022
Queue full, depth 433, deepening 8, 1.0M/4.0M -> 15k/97k
State dumped to dump0023
Queue full, depth 438, deepening 8, 1.0M/2.5M -> 16k/97k
State dumped to dump0024
Queue full, depth 442, deepening 9, 1.0M/2.3M -> 14k/86k
State dumped to dump0025
Queue full, depth 446, deepening 10, 1.0M/1.8M -> 13k/81k
State dumped to dump0026
Queue full, depth 450, deepening 11, 1.0M/1.9M -> 11k/73k
State dumped to dump0027
Queue full, depth 455, deepening 11, 1.0M/2.7M -> 10k/75k
State dumped to dump0028
Queue full, depth 459, deepening 12, 1.0M/2.0M -> 8.9k/66k
State dumped to dump0029
Queue full, depth 463, deepening 13, 1.0M/1.6M -> 8.5k/62k
State dumped to dump0030
Queue full, depth 468, deepening 13, 1.0M/1.9M -> 9.4k/68k
State dumped to dump0031
Queue full, depth 472, deepening 14, 1.0M/1.8M -> 8.7k/66k
State dumped to dump0032
Queue full, depth 476, deepening 15, 1.0M/1.8M -> 8.0k/64k
State dumped to dump0033
Queue full, depth 480, deepening 16, 1.0M/1.8M -> 7.3k/62k
State dumped to dump0034
Queue full, depth 484, deepening 17, 1.0M/1.7M -> 6.5k/59k
State dumped to dump0035
Queue full, depth 488, deepening 18, 1.0M/1.9M -> 5.7k/57k
State dumped to dump0036
Queue full, depth 493, deepening 18, 1.0M/2.0M
x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$5bo
$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$bo$
4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3bo$
3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o$
ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bobo
2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o2$
obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3bo
2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!


x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo3bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$
5bo$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$
bo$4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3b
o$3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o
$ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bob
o2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o
2$obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3b
o2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!

 -> 5.9k/60k
State dumped to dump0037
Queue full, depth 496, deepening 20, 1.0M/1.4M
x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$5bo
$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$bo$
4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3bo$
3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o$
ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bobo
2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o2$
obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3bo
2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!


x = 10, y = 98, rule = B2-ac3acikq4ci5e/S01e2ei3a
4bo$o2bo3bo$o3bo$o4bo$o$b2o2bo2bo2$3bo$6bo$3bo2bo$6b2o$6bo$7bo$
5bo$7b2o$2bo2bo$5bobo$5b2o3$2bo2bo2$4b2o$5bo$4b2o$4bobo$2bo3b2o$
bo$4bo$bob2o$5bo$4b2o$5bo$4bo$3b2o$3b2o$4b2o$4bo2bo$4bo2bo$3b2o3b
o$3b2obo$3b2obo$2b2o2b2o$3bo$3bo$9bo$3bob2obo$3bo$bo2$bo$2bo$2b2o
$ob3o$3b2o$2bo$ob2o2bo2$2o$b3o$3b2obo$3bo$6bo$3bob3o$3b2o2bo$bob
o2bo$o$bo$o3bobo$b3o$o$8bo$obo$2b2o$4bobo2bo$7b2o$bo$3bo3bo$5b2o
2$obo$bobo$6bo$3bobo$4bo$2bobo$bo2b2o$2bob2o$6bo$7bobo$8bo$7bo$3b
o2bobo$2bobo$bo6bo$2bobo2bo$bo$o2b2o!
^C
None of these RLEs are ship.
Saka wrote:
Yesterday, 3:51 am
Anyway I will not contribute to this language if it stays like this.
Moosey wrote:
February 5th, 2019, 7:51 pm
“New knightship tagalong!”
“Quick, hide it!”
LeapLife - DirtyLife - LispLife

User avatar
LaundryPizza03
Posts: 1051
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 » April 8th, 2020, 3:22 am

I also note that while gfind and zfind support at least some speeds and periods greater than c/2, qfind does not work at all for such speeds. Even a simple search such as ./qfind B2/S p1 x1 w3 v aborts instantly without returning any of the three main photons in that rule.

Code: Select all

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

The latest edition of new-gliders.db.txt and oscillators.db.txt have 31150 spaceships and 1205 oscillators from outer-totalistic rules. You are invited to help!

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

Re: qfind - a spaceship search program

Post by Sokwe » April 8th, 2020, 5:41 am

Hunting wrote:
April 6th, 2020, 8:23 pm
LaundryPizza03 wrote:
April 6th, 2020, 7:04 am
qfind gave me some weird results on asymmetric.
Yep. I'm getting failed ships in this rule:
These failed ships seem to all leave the left side of their width-10 bounding box at some point in their evolution. If you disallow these births, the pattern operates normally. This bug probably appeared when I updated to add Tom's code. Unfortunately, I don't have time to work on it right now.
LaundryPizza03 wrote:
April 8th, 2020, 3:22 am
I also note that while gfind and zfind support at least some speeds and periods greater than c/2, qfind does not work at all for such speeds. Even a simple search such as ./qfind B2/S p1 x1 w3 v aborts instantly without returning any of the three main photons in that rule.
qfind is not designed to work for any speeds above c/2 (if it works, it's a fluke and not intended behavior). Due to the width limitations, I don't think qfind would be useful for finding such ships anyway. It's better to use gfind in those cases.
-Matthias Merzenich

AforAmpere
Posts: 1146
Joined: July 1st, 2016, 3:58 pm

Re: qfind - a spaceship search program

Post by AforAmpere » May 13th, 2020, 1:37 am

There may be some sort of bug with qfind when doing really long searches. For example, this search gets stuck at depth 59879:

Code: Select all

./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u
Changing the hash table size does not affect anything, but increasing the BFS queue size seems to delay when qfind gets stuck. Ntzfind doesn't seem to have problems finding a ship with these parameters. Sokwe, do you know what could be causing this?
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules.

Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule

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

Re: qfind - a spaceship search program

Post by Sokwe » July 19th, 2020, 7:10 pm

AforAmpere wrote:
May 13th, 2020, 1:37 am
There may be some sort of bug with qfind when doing really long searches. For example, this search gets stuck at depth 59879:

Code: Select all

./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u
Changing the hash table size does not affect anything, but increasing the BFS queue size seems to delay when qfind gets stuck. Ntzfind doesn't seem to have problems finding a ship with these parameters. Sokwe, do you know what could be causing this?
Sorry for not responding earlier. I didn't notice this question.

This isn't a bug, but rather a limitation in qfind's method. Here is the output showing clearly where qfind gets "stuck":

Code: Select all

Starting search
Queue full, depth 40811, deepening 19, 299/7.8M -> 182/4.7M
Queue full, depth 52355, deepening 19, 305/7.8M -> 173/6.6M
Queue full, depth 56914, deepening 19, 259/7.8M -> 173/7.3M
Queue full, depth 58710, deepening 19, 234/7.8M -> 175/7.6M
Queue full, depth 59420, deepening 19, 265/7.8M -> 173/7.7M
Queue full, depth 59697, deepening 19, 283/7.8M -> 176/7.8M
Queue full, depth 59811, deepening 19, 256/7.8M -> 181/7.8M
Queue full, depth 59853, deepening 19, 272/7.8M -> 180/7.8M
Queue full, depth 59870, deepening 21, 265/7.8M -> 177/7.8M
Queue full, depth 59877, deepening 33, 213/7.8M -> 167/7.8M
Queue full, depth 59879, deepening 50, 185/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 69, 167/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 88, 164/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 107, 164/7.8M -> 164/7.8M
Queue full, depth 59879, deepening 126, 164/7.8M -> 164/7.8M
Notice that at each step you get "164/7.8M -> 164/7.8M". When you see "MM/NN", MM is the current number of partial results, and NN is the total number of rows in the current search tree (this includes all the rows in each of the MM partial results). The 'q' parameter essentially sets a limit on what NN can be. If the search tree reaches the size set by 'q', then a depth-first step is triggered to try to eliminate some of the partial results, and thus free up some memory to continue the breadth-first search.

The MM/NN before the arrow indicates the values before the depth-first stage is applied. The numbers after the arrow likewise represent the values after the depth-first stage. As can be seen from the output above, once the search reaches a depth of 59879 the deepening steps are unable to eliminate any of the partial results. Therefore no memory is freed and the breadth first search cannot continue. It then tries another depth-first round, going even deeper than before, but still it cannot eliminate any partial results. It could be that each partial result has a subsequent repeating pattern, and the depth-first search will never be able to eliminate any of the partial results. In this case you truly are stuck.

The solution is to run the search with a higher 'q' value. For example, running

Code: Select all

./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u q26
gives me a spaceship of length ~11488. Another thing you can do is run your initial search with the 'd' parameter. When the search gets "stuck", you can stop it and edit the latest dump file to increase the 'q' paremeter (increase the value on line 10 in the dump file). As a warning, only use a dump file for which the program has given the output "State dumped to dumpXXXX". This indicates that writing to the dump file has completed. It is possible to kill the program while the dump file is being written, so if that message hasn't appeared, the latest dump file might be incomplete.
-Matthias Merzenich

User avatar
wwei23
Posts: 1531
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: qfind - a spaceship search program

Post by wwei23 » October 9th, 2020, 10:14 am

How do I restart a qfind search from a dump file?

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

Re: qfind - a spaceship search program

Post by Sokwe » October 13th, 2020, 5:40 pm

wwei23 wrote:
October 9th, 2020, 10:14 am
How do I restart a qfind search from a dump file?

Code: Select all

./qfind s FILENAME
where "FILENAME" is the name of the dump file. For example,

Code: Select all

./qfind s dump0011
-Matthias Merzenich

User avatar
wwei23
Posts: 1531
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: qfind - a spaceship search program

Post by wwei23 » October 15th, 2020, 10:28 pm

How do I make qfind dump automatically, and how do I adjust the dumping interval?

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

Re: qfind - a spaceship search program

Post by Sokwe » October 17th, 2020, 4:20 am

wwei23 wrote:
October 15th, 2020, 10:28 pm
How do I make qfind dump automatically, and how do I adjust the dumping interval?
Use the 'd' parameter to dump the state after each queue compaction. You can read qfind's parameter descriptions by running

Code: Select all

./qfind c
The state dumps after each deepening step completes, so there is no direct way to "adjust the dumping interval". You can do things like changing the queue size with the 'q' parameter or changing the minimum deepening increment with the 'm' parameter to affect the length of time the deepening step takes.
-Matthias Merzenich

User avatar
wwei23
Posts: 1531
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: qfind - a spaceship search program

Post by wwei23 » October 17th, 2020, 7:02 pm

Can I feed qfind partials? If so, how?
EDIT: I should probably try ./qfind c first.
EDIT 2: Ok, but how do I put in more than one partial?

wildmyron
Posts: 1464
Joined: August 9th, 2013, 12:45 am

Re: qfind - a spaceship search program

Post by wildmyron » October 17th, 2020, 10:54 pm

wwei23 wrote:
October 17th, 2020, 7:02 pm
Can I feed qfind partials? If so, how?
EDIT: I should probably try ./qfind c first.
EDIT 2: Ok, but how do I put in more than one partial?
There's currently no way to put in more than one partial. You need to run separate searches for each partial, or you could do some manual tinkering with dump files to craft one which has multiple partials included. This would require either studying and understanding the dump file format or hoping that Sokwe will provide a tool to combine dump files / add multiple partials. :)
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

Post Reply