git pull claims it's already up to date.wildmyron wrote: ↑April 6th, 2020, 12:42 pmThat is very strange, I don't see that result when I run the same search in my build of qfind (current github version)LaundryPizza03 wrote: ↑April 6th, 2020, 7:04 amqfind gave me some weird results on asymmetric. For example, some results at width 9 in B3578/S23 appear to be broken:Rather, each of these results turns out to be half of a guttersymmetric ship.Code: Select all
<snip rle>
Code: Select all
./qfind B3578/S23 p3 k1 w9 a
qfind and zfind both don't check if gutter symmetry is valid in the specified rule. Running such a search will give invalid results.It's unclear what would happen in rules like B36/S23 that have no gutter or skewgutter symmetry.Code: Select all
<snip rle>
qfind  a spaceship search program
 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
Code: Select all
x = 4, y = 3, rule = B3q4z5y/S234k5j
2b2o$b2o$2o!
The latest edition of newgliders.db.txt and oscillators.db.txt have 31150 spaceships and 1205 oscillators from outertotalistic rules. You are invited to help!
Re: qfind  a spaceship search program
Yep. I'm getting failed ships in this rule:
Code: Select all
D:\qfindmaster>a B2ac3acikq4ci5e/S01e2ei3a p5 k1 w10 d
qfind v1.1 by Matthias Merzenich, 7 January 2020
 a B2ac3acikq4ci5e/S01e2ei3a p5 k1 w10 d
Rule: B2ac3acikq4ci5e/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 = B2ac3acikq4ci5e/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 = B2ac3acikq4ci5e/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 = B2ac3acikq4ci5e/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 = B2ac3acikq4ci5e/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 = B2ac3acikq4ci5e/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
 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
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 = B3q4z5y/S234k5j
2b2o$b2o$2o!
The latest edition of newgliders.db.txt and oscillators.db.txt have 31150 spaceships and 1205 oscillators from outertotalistic rules. You are invited to help!
Re: qfind  a spaceship search program
These failed ships seem to all leave the left side of their width10 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.
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.LaundryPizza03 wrote: ↑April 8th, 2020, 3:22 amI 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.
Matthias Merzenich

 Posts: 1146
 Joined: July 1st, 2016, 3:58 pm
Re: qfind  a spaceship search program
There may be some sort of bug with qfind when doing really long searches. For example, this search gets stuck at depth 59879:
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?
Code: Select all
./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u
Wildmyron and I manage the 5S project, which collects all known spaceship speeds in Isotropic Nontotalistic rules.
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Things to work on:
 Find a (7,1)c/8 ship in a Nontotalistic rule
Re: qfind  a spaceship search program
Sorry for not responding earlier. I didn't notice this question.AforAmpere wrote: ↑May 13th, 2020, 1:37 amThere may be some sort of bug with qfind when doing really long searches. For example, this search gets stuck at depth 59879: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?Code: Select all
./qfind B2ce3jry4e5iy7e/S12ik3aeinr4aeir5i6c7e p19 k4 w2 u
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
The MM/NN before the arrow indicates the values before the depthfirst stage is applied. The numbers after the arrow likewise represent the values after the depthfirst 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 depthfirst 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 depthfirst 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
Matthias Merzenich
Re: qfind  a spaceship search program
How do I restart a qfind search from a dump file?
Re: qfind  a spaceship search program
Code: Select all
./qfind s FILENAME
Code: Select all
./qfind s dump0011
Matthias Merzenich
Re: qfind  a spaceship search program
How do I make qfind dump automatically, and how do I adjust the dumping interval?
Re: qfind  a spaceship search program
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
Matthias Merzenich
Re: qfind  a spaceship search program
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?
EDIT: I should probably try ./qfind c first.
EDIT 2: Ok, but how do I put in more than one partial?
Re: qfind  a spaceship search program
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.