zfind discussion

For scripts to aid with computation or simulation in cellular automata.
dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: zfind discussion

Post by dani » June 27th, 2018, 12:36 am

Could there be a way to find puffers using ntqfind/ntzfind? Kind of like the puffer switch in gfind...

The way I could see to implement this (admittedly I've never looked at the src code of gfind, though) is to check if the ship goes through two different cycles without losing any rows the second time around, but I don't quite know.

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

Re: zfind discussion

Post by AforAmpere » January 30th, 2019, 6:14 pm

Is there a way to do multithreading in zfind 3.0 or later?
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: zfind discussion

Post by Moosey » February 1st, 2019, 6:32 pm

Where do I find an nttable.c?
Where do I find nttable.c?
Where do I find nttable.c?
Ntzfind error.png (9.98 KiB) Viewed 16228 times
not active here but active on discord

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » February 1st, 2019, 8:56 pm

AforAmpere wrote:Is there a way to do multithreading in zfind 3.0 or later?
There's no functional multithreading implementation available that I'm aware of. There are several possibilities for how it could be done, including merging some of the zfind3 changes into qfind. I recall rokicki mentioning that some of the changes would be tricky to merge though.
Moosey wrote:Where do I find an nttable.c?
Ntzfind error.png
Instructions here: http://conwaylife.com/forums/viewtopic. ... ind#p53277

A better alternative is to use zfind3. See discussion earlier in this thread. http://conwaylife.com/forums/viewtopic. ... 074#p57074
Code: https://github.com/rokicki/ntzfind
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

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

Re: zfind discussion

Post by Sokwe » February 4th, 2019, 1:18 am

wildmyron wrote:I recall rokicki mentioning that some of the changes would be tricky to merge [into qfind] though.
I think the two difficulties are the following:
  • Since the lookup table is generated as-needed, each update to the table will have to be atomic. This might slow the search early on, but I hope it would become negligible after a little while.
  • The lookahead is done slightly differently in qfind for searches faster than c/3, so the hash function needs to be changed slightly.
Anyway, qfind needs to be made more thread-safe in general. Sadly, I've been too busy to work on it.
-Matthias Merzenich

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: zfind discussion

Post by calcyman » February 4th, 2019, 5:03 am

Sokwe wrote:
wildmyron wrote:I recall rokicki mentioning that some of the changes would be tricky to merge [into qfind] though.
I think the two difficulties are the following:
  • Since the lookup table is generated as-needed, each update to the table will have to be atomic. This might slow the search early on, but I hope it would become negligible after a little while.
  • The lookahead is done slightly differently in qfind for searches faster than c/3, so the hash function needs to be changed slightly.
Anyway, qfind needs to be made more thread-safe in general. Sadly, I've been too busy to work on it.
Looking at the code, it seems that making the lookup table generation threadsafe should be relatively straightforward, and doesn't require locking the table for more than a nanosecond or two. In particular, there's only one line:

https://github.com/rokicki/ntzfind/blob ... d.cpp#L422

in which the new row pointer is added to the table. So that can be replaced with (pseudocode):

Code: Select all

-- acquire mutex;
-- see whether gInd3[(row1<<width)+row2] is equal to zero;
-- if it is zero, replace it with the row pointer;
-- if it is nonzero, free the row you've just created (because another thread has already created it before you);
-- release mutex;
and the final line should return gInd3[(row1<<width)+row2] instead of row to account for the case where you've freed the row.

It's something of a 'better to ask for forgiveness than permission' approach: you generate the row, possibly unnecessarily (because another thread might be doing the same thing at the same time), and only check at the moment you add the row to the lookup table.

Also, gInd3 should be changed to an array of type std::atomic_uintptr_t just in case someone is using a processor such as ARM which lacks atomic 64-bit stores. That way, we don't need to check the mutex when reading the lookup table, because gInd3[(row1<<width)+row2] changes atomically from 0 to row.

The other (minor) change is that you need a gWork array for each thread in the program. Easiest would be to replace:

Code: Select all

int *gWork ;
[...]
gWork = (int *)calloc(sizeof(int), 3LL << width) ;
with:

Code: Select all

int *gWorkConcat;
[...]
gWorkConcat = (int *)calloc(sizeof(int), (3LL * n_threads) << width);
and then, inside the body of makeRow:

Code: Select all

int *gWork = gWorkConcat + ((3LL * thread_number) << width);
What do you do with ill crystallographers? Take them to the mono-clinic!

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: zfind discussion

Post by Naszvadi » February 24th, 2019, 8:04 am

There are 32 outer-totalistic Neumann rules with 16 non-isomorphic among them, they are:
  • B0/SV:B01c2cn3c4c/S
  • B0/S1V:B01c2cn3c4c/S1e2ak3inqy4ny5e
  • B0/S0V:B01c2cn3c4c/S01c2cn3c4c
  • B0/S01V:B01c2cn3c4c/S01ce2ackn3cinqy4cny5e
  • B04/SV:B01c2cn3c4ce5c6cn7c8/S
  • B04/S1V:B01c2cn3c4ce5c6cn7c8/S1e2ak3inqy4ny5e
  • B04/S0V:B01c2cn3c4ce5c6cn7c8/S01c2cn3c4c
  • B04/S01V:B01c2cn3c4ce5c6cn7c8/S01ce2ackn3cinqy4cny5e
  • B02/SV:B01c2cein3acjkr4acikqtwz5ajkr6ei/S
  • B02/S1V:B01c2cein3acjkr4acikqtwz5ajkr6ei/S1e2ak3inqy4ny5e
  • B02/S0V:B01c2cein3acjkr4acikqtwz5ajkr6ei/S01c2cn3c4c
  • B02/S01V:B01c2cein3acjkr4acikqtwz5ajkr6ei/S01ce2ackn3cinqy4cny5e
  • B024/SV:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S
  • B024/S1V:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S1e2ak3inqy4ny5e
  • B024/S0V:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S01c2cn3c4c
  • B024/S01V:B01c2cein3acjkr4aceikqtwz5acjkr6cein7c8/S01ce2ackn3cinqy4cny5e
I hope my ruleconverter script is bug-free :D.

Does ntzfind support Neumann blinking and/or isotropic blinking rules? Some of the above already have known gliders (c/2, c2/4. c/12d). Are there any experiences with such kind of rules?

As a test drive, tlife is supported well (after commenting out knightship configuration macro definitions)

Code: Select all

user@errorlevel:0:~/github.com/rokicki/ntzfind$ ./ntzfind b3/s2-i34q p5 k1 w3 a rntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind b3/s2-i34q p5 k1 w3 a r
Rule: b3/s2-i34q
Period: 5
Offset: 1
Width:  3
Symmetry: asymmetric
Depth limit: 2000
Stop search if a ship is found.
Use randomized search order.
Starting search

.o.
o.o
...
ooo
...
Length: 22
Spaceship found. (1)

Current depth: 2001
Calculations: 2070
CPU time: 0.020634 seconds
Search terminated: spaceship found.
user@errorlevel:0:~/github.com/rokicki/ntzfind$ export LC_ALL=C; ./ntzfind B01c2cein3acjkr4acikqtwz5ajkr6ei/S p4 k2 w4 u r
ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B01c2cein3acjkr4acikqtwz5ajkr6ei/S p4 k2 w4 u r
Rule: B01c2cein3acjkr4acikqtwz5ajkr6ei/S
Period: 4
Offset: 2
Width:  4
Symmetry: odd
Depth limit: 2000
Stop search if a ship is found.
Use randomized search order.
Starting search
Segmentation fault (core dumped)
user@errorlevel:139:~/github.com/rokicki/ntzfind$ 
I also observed that the above ntzfind version has difficulties with b2*/s rules, too.

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

Re: zfind discussion

Post by LaundryPizza03 » August 5th, 2019, 7:27 am

Does ntzfind work with knightships?

Why doesn't it work with some relativistic speeds, e.g. 9c/10 orthogonal?

Code: Select all

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

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

Re: zfind discussion

Post by LaundryPizza03 » August 5th, 2019, 7:59 am

What does "segmentation fault" mean?

Code: Select all

./ntzfind B2/S p3 k1 w15 u > b2s-2c6o.txt
Segmentation fault: 11

Code: Select all

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

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » August 5th, 2019, 11:25 am

LaundryPizza03 wrote:Does ntzfind work with knightships?
Provided that the line #define KNIGHT at the top of the file has not been commented out, yes ntzfind works with knightships. The help text has not been updated to reflect this change. Knight ship searches have the same limitations as for the regular zfind: x-offset can only be 1 and one phase of the ship has width w-1 for a width w search.
LaundryPizza03 wrote:Why doesn't it work with some relativistic speeds, e.g. 9c/10 orthogonal?
The maximum speed that zfind supports is c/2. I don't know the algorithm well enough to explain this limitation.
LaundryPizza03 wrote:What does "segmentation fault" mean?

Code: Select all

./ntzfind B2/S p3 k1 w15 u > b2s-2c6o.txt
Segmentation fault: 11
In general it means the program crashed. In this particular case it means there was not enough RAM available to continue the search. zfind's memory usage increases exponentially with the search width. With ntzfind a width 10 search requires around 2.5GB and width 11 requires up to 19GB. Width 15 is well beyond the feasible RAM requirements for an ntzfind search. Almost all the memory requirement is due to a large lookup table which is used to determine the evolution of the rows of the ship in the rule being searched. Because ntzfind builds this table dynamically (as required) some searches will require less than the maximum memory requirement to get a result. This means it is possible to run brief width 12 searches on a desktop machine before the available RAM is exhausted. In combination with the 'r' option for random row sorting, ntzfind can sometimes find a result at width 12 even though it can't complete the search.

Edit although, as you've seen with B2/S there are some searches where the allowed row evolution is so limited that even wider searches can be completed.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

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

Re: zfind discussion

Post by AforAmpere » August 5th, 2019, 11:54 am

wildmyron wrote: The maximum speed that zfind supports is c/2. I don't know the algorithm well enough to explain this limitation.
That's not quite true. Searching for a 2c/3 in B2ac3ae/S1c2i3i works just fine. It seems that sometimes the search requires higher widths than it should, but these work below, as well as searches for 7c/8 and 8c/9 in their respective 5s rules.

This 5c/6 search works just fine, for some reason:

Code: Select all

./ntzfind3_1 B2ace3cejr4cjnqwyz5-cy6-ci8/S2-ce3cjknq4kqrw5aeky6-ik78 p6 k5 w8 u
This 6c/7 works too, somehow:

Code: Select all

./ntzfind3_1 B2ack3-cinr4ciqr5aeq6acn8/S02ein3acijn4ainqty5ciky6k7c8 p7 k6 w8 u
I have no clue why some things break, and some don't.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » August 5th, 2019, 12:46 pm

AforAmpere wrote:
wildmyron wrote: The maximum speed that zfind supports is c/2. I don't know the algorithm well enough to explain this limitation.
That's not quite true. Searching for a 2c/3 in B2ac3ae/S1c2i3i works just fine. It seems that sometimes the search requires higher widths than it should, but these work below, as well as searches for 7c/8 and 8c/9 in their respective 5s rules.
Well I freely admit to having no idea what's going on there. I don't recall anyone every saying that search speeds above c/2 should work, but human memory being what it is I could be wrong there as well.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

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

Re: zfind discussion

Post by Sokwe » August 17th, 2019, 2:02 am

AforAmpere wrote:
wildmyron wrote: The maximum speed that zfind supports is c/2. I don't know the algorithm well enough to explain this limitation.
That's not quite true. Searching for a 2c/3 in B2ac3ae/S1c2i3i works just fine.
The look-ahead step accepts or rejects a new row by searching for a slight extension (if none is found, the new row is rejected). If the speed is faster than c/2 some of these extension rows will overlap with existing rows in the current partial result. If these overlapping rows don't match, you might accept an invalid row. I can't remember why exactly this causes crashes. the exact circumstances causing a crash may not occur in all such searches. However, I wouldn't trust such a search to be complete.

The original version of zfind only worked at speeds less than c/3. zdr modified it to work up to c/2 and I think I modified that modification a bit. Then Tom found a bug in my implementation, so modified it a bit more.

Searches for fast subluminal ships generally complete very quickly, which eliminates most of the benefit of zfind over gfind. For this reason, I never bothered to get zfind to work for these fast ship searches.
-Matthias Merzenich

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

Re: zfind discussion

Post by LaundryPizza03 » February 17th, 2020, 9:57 am

A weird thing happened when searching for a 2c/6o. A c/3 (unsimplified) popped out.

Code: Select all

x = 17, y = 30, rule = B2n3/S23-q
8bo$7bobo$6bo3bo$4b3o3b3o$3b2o7b2o$2bo11bo$b3o9b3o2$b2o2b2o3b2o2b2o$b
2o2bo5bo2b2o$bobobobobobobobo$3bo4bo4bo$2bo3bobobo3bo$3bo9bo$2b6ob6o2$
2o6bo6b2o$bo4bo3bo4bo$bo4b2ob2o4bo$bobobobobobobobo$4b2o5b2o$6bo3bo$6b
o3bo$4bo7bo2$4b2o5b2o2$4b3o3b3o$4bo7bo$5bo5bo!

Code: Select all

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

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

Re: zfind discussion

Post by AforAmpere » February 17th, 2020, 11:10 am

LaundryPizza03 wrote:
February 17th, 2020, 9:57 am
A weird thing happened when searching for a 2c/6o. A c/3 (unsimplified) popped out.

Code: Select all

Ship
That's normal. Zfind doesn't check if the ship is at full period or not unless told to. You can use the f command to give a length after which the partial must be full period.
I manage the 5S project, which collects all known spaceship speeds in Isotropic Non-totalistic rules. I also wrote EPE, a tool for searching in the INT rulespace.

Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.

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

Re: zfind discussion

Post by Sokwe » February 17th, 2020, 8:30 pm

LaundryPizza03 wrote:
February 17th, 2020, 9:57 am
A weird thing happened when searching for a 2c/6o. A c/3 (unsimplified) popped out.
If you want to find a period-6 ship, qfind might be better than zfind.

Edit: If you want to find a symmetric 2c/6 ship of width 17, I recommend running qfind with the following settings:

Code: Select all

./qfind B2n3/S23-q p6 k2 w9 u m3 q19 d x > 2c6-output.txt
If you have multiple processors available, you can also include the command tNN where NN is the number of threads you want qfind to use.
-Matthias Merzenich

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

Re: zfind discussion

Post by LaundryPizza03 » March 20th, 2020, 10:32 pm

I did a search for a c/5 orthogonal at width 15 on odd symmetry. It was so long that it required a depth greater than the default.

Code: Select all

#C My ship, via ntzfind
x = 15, y = 518, rule = B36/S125
b2o9b2o$2bobo5bobo$bo3bo3bo3bo$6bobo2$5b5o2$7bo$2bo3bobo3bo$bo2bobobob
o2bo$bob2o2bo2b2obo$bobo2bobo2bobo$2bo9bo$4b2obob2o$4bo5bo$bob2ob3ob2o
bo$bo5bo5bo$4bo5bo$2bobo5bobo$b2ob2o3b2ob2o$b5o3b5o$4bobobobo$4bobobob
o$3b2ob3ob2o$4bob3obo$7bo$2bobo5bobo$5b5o$2bobo5bobo$7bo2$3bobobobobo$
2bob2obob2obo$4bo5bo$3b4ob4o$2bobo5bobo2$2bo9bo$5bobobo$4bobobobo$bo
11bo$4o3bo3b4o$2ob2o5b2ob2o$b3o7b3o$4bo5bo$4bobobobo$5b2ob2o$5bo3bo$3b
obo3bobo$2bo2bo3bo2bo2$4bo5bo$3bo2bobo2bo$4bobobobo$2bo9bo$4bo5bo2$2ob
3o3b3ob2o$2bobobobobobo$3obobobobob3o$2b2o7b2o$4bo5bo$3bo2bobo2bo$2bo
4bo4bo$2bo9bo$2b2o2b3o2b2o$6b3o$6b3o$3b3obob3o$6bobo$6bobo$2b3o5b3o$2b
o2bo3bo2bo2$b3o7b3o$bo2bo5bo2bo$3bo7bo$ob3o5b3obo$3b2o2bo2b2o$2b2o2bob
o2b2o$3b2o2bo2b2o$3bobo3bobo$2bobo2bo2bobo$5bo3bo$2bobobobobobo2$4bo2b
o2bo$3bo3bo3bo$2b2o3bo3b2o$bo2bo5bo2bo$bo2bo5bo2bo$2bobo5bobo$4bo5bo$b
5o3b5o$bobo7bobo$2b3o5b3o$4bo5bo$5bo3bo$2bobo5bobo$2bobo5bobo$3bo2bobo
2bo$7bo$4bo5bo$5b5o2$b3o7b3o$2bob2o3b2obo$bob4ob4obo$2bo9bo$b2o9b2o$b
2o9b2o$2bo9bo$2bobo5bobo$3bo7bo2$2bobobobobobo2$5bobobo$6bobo$3bo2bobo
2bo$4bo5bo$5bo3bo$3b2o5b2o$7bo$bob2o2bo2b2obo$b2o2bo3bo2b2o$obobo2bo2b
obobo$3o4bo4b3o$bob3o3b3obo$7bo$5b2ob2o$2b2o7b2o$2bobo5bobo$3b2obobob
2o$4b2obob2o$7bo2$3bo2bobo2bo$3bo7bo$4bo5bo2$4b2o3b2o$3b2obobob2o2$2bo
9bo$4bo5bo$2bobo5bobo$2bo9bo$b2o3bobo3b2o$2obobo3bobob2o$3bobo3bobo2$
4bobobobo$5bo3bo$5bobobo2$bo11bo$o2bobobobobo2bo$bo5bo5bo$3bo2b3o2bo$
3bo7bo$3bob2ob2obo$3bo2bobo2bo2$4bo5bo$2bobo5bobo$4bob3obo$2bob2o3b2ob
o$3b9o$4bo5bo2$4bo5bo$2b2obo3bob2o$2bo4bo4bo$4bo2bo2bo$3bob2ob2obo$6bo
bo2$4bo5bo2$5bo3bo$3bo2b3o2bo$2b4o3b4o$6b3o2$4b2o3b2o$4b2o3b2o2$5bo3bo
$2bo9bo$2b2ob5ob2o$3bobo3bobo$3b2o5b2o$5bo3bo$7bo$5bobobo$6b3o$3b2o5b
2o$5bo3bo$6b3o$bo2bobobobo2bo$b2o3bobo3b2o$2bo4bo4bo$2bo3b3o3bo$o5bobo
5bo$3bo7bo$obo2b2ob2o2bobo$4bo2bo2bo3$3bobo3bobo$4bo5bo$5b2ob2o$5bobob
o2$6b3o$5b2ob2o$5bobobo$6b3o$7bo$4bo5bo$2bo3bobo3bo$bo2b2o3b2o2bo$6bob
o$5bo3bo$4b2o3b2o$3b2o5b2o$6bobo$6bobo$6b3o$5bobobo$5b5o$3b3o3b3o$2bo
2b2ob2o2bo$6bobo$5bo3bo$4bo5bo$3b2o5b2o$3b3o3b3o$6b3o$2bo4bo4bo$2bo9bo
$2bobo5bobo$2bo2b2ob2o2bo$ob2o7b2obo$3bobo3bobo$2o11b2o$ob2o7b2obo$bob
o7bobo$bobo7bobo$bobo7bobo$2bo9bo$2bobo5bobo$2bob2o3b2obo2$4bo5bo$4b2o
3b2o$3b3o3b3o$bobob2ob2obobo$b2o2bobobo2b2o$3bobobobobo2$4bo5bo$3b2o5b
2o$4b2o3b2o$4b7o$2bob2obob2obo$3bo7bo$4bo5bo$2b2o2bobo2b2o$7bo$5bo3bo$
4bo5bo$2bo9bo$b3o2bobo2b3o$b2obobobobob2o$5bo3bo$4b2o3b2o$5bo3bo$6bobo
2$5bobobo$5b2ob2o$bo2bob3obo2bo$ob2o2bobo2b2obo$bobo7bobo$bo2bo5bo2bo$
2b3o5b3o$4b2o3b2o$b2o9b2o$5bo3bo$2bo2bo3bo2bo$bob3o3b3obo$4bo5bo$5bo3b
o$7bo$6bobo$3bob2ob2obo$3b2o5b2o2$3bo2bobo2bo$3b2obobob2o$b2o9b2o3$2o
11b2o$bo11bo$2bo3bobo3bo$3bo3bo3bo$2bo2bo3bo2bo$6bobo$bo2b2obob2o2bo$
3b3o3b3o$4bobobobo$2bo9bo$2bo2b5o2bo$3b2o5b2o2$6b3o$5b2ob2o$5bobobo$5b
5o$4b2obob2o$5bo3bo$3b3o3b3o$2bo3bobo3bo$2bo3bobo3bo$3bob5obo$6bobo2$
5b2ob2o$5bobobo$6bobo2$6b3o$6b3o$3bo3bo3bo$2bob2o3b2obo2$6bobo$2b2o7b
2o$bobo7bobo$2b2obobobob2o$3b2o5b2o$3bo3bo3bo2$2b2o2bobo2b2o2$6bobo$5b
2ob2o$4bobobobo$4b2obob2o$bo11bo$2o3bobobo3b2o$5obobob5o$b2o2bo3bo2b2o
2$6bobo$6bobo$6bobo$3bo2bobo2bo$4b2o3b2o$6bobo$6b3o$4bo5bo$3bob2ob2obo
$3bo3bo3bo$2bo4bo4bo$2b4o3b4o$4b2o3b2o$5o5b5o$b3o7b3o$b3ob5ob3o$2bo9bo
2$6b3o$5bo3bo2$4b2o3b2o$4bobobobo$4bo5bo$6b3o$5b5o$2b3ob3ob3o$b2obo2bo
2bob2o$2bo3b3o3bo$3bo7bo$2b2o2bobo2b2o$2b2o2b3o2b2o$b6ob6o$2o11b2o$2o
11b2o$4bo5bo$2bobo5bobo$5b5o$4bob3obo$3bobobobobo$b2o2bo3bo2b2o$2b2obo
3bob2o$2b11o$b2ob7ob2o$5bo3bo$5bo3bo2$3bo2b3o2bo$2bo3bobo3bo$2bo4bo4bo
$4b3ob3o$7bo$4bo5bo$7bo$2bobobobobobo$2bobo2bo2bobo$7bo$3bo7bo$2b2o3bo
3b2o$2bobo5bobo$4b2o3b2o$4bobobobo$bo3b2ob2o3bo$2o2bo5bo2b2o$2ob4ob4ob
2o$bo3bo3bo3bo$2bob2o3b2obo$3bo7bo2$b2ob2o3b2ob2o$2bo2bo3bo2bo$3bobo3b
obo$4bobobobo$b2obobobobob2o$b3o2bobo2b3o$bobo3bo3bobo$6bobo$bo2bo5bo
2bo$6bobo$2bobo2bo2bobo$bobo2bobo2bobo$b2o9b2o$5b2ob2o$4b7o$3b3obob3o$
3b2ob3ob2o$3bob2ob2obo$4b3ob3o$b2o9b2o$b2o2b2ob2o2b2o$6b3o$7bo$6b3o$5b
o3bo$2bo2b5o2bo$3bobobobobo$2bo2bo3bo2bo$4bo5bo$2b2o2bobo2b2o$bo2bo2bo
2bo2bo$o4bobobo4bo$4bobobobo$obobobobobobobo$4bo5bo$4bob3obo$4b2obob2o
$5b2ob2o$6bobo$3bobo3bobo$2bo9bo$bob2o5b2obo$2b3o5b3o$bo2bobobobo2bo$
3b2obobob2o$4bo5bo$4bo2bo2bo$5bo3bo$3bobo3bobo$4bo5bo$4bo5bo$3b2obobob
2o$3bobo3bobo$3bobo3bobo$5bobobo$2bo9bo$4b7o$3bob5obo$4bobobobo$bo11bo
$2b3o5b3o$2bo9bo$4bobobobo$6bobo$2b2o7b2o$bo2bo5bo2bo$bo11bo$2b2o7b2o
3$2bob2o3b2obo$bo2bo5bo2bo$b2obo5bob2o2$bo11bo$bo11bo2$bobo2bobo2bobo$
2bo2b2ob2o2bo$5bo3bo$5bo3bo$6bobo4$5b5o$5bobobo$4bo5bo$bo5bo5bo$bo5bo
5bo$2b4o3b4o$4bo5bo!
However, it turns out that Lewis Patterson found a much shorter ship at the same width in 2015. qfind gives the same result.

Code: Select all

#C Patterson, 2015
x = 15, y = 45, rule = B36/S125
3o9b3o$b2obo5bob2o$ob2o7b2obo$5bo3bo$bo3bo3bo3bo$4b2o3b2o$6bobo$2bobob
obobobo$2bo2bo3bo2bo$3bobo3bobo$5bo3bo$7bo$4bo2bo2bo$3b3o3b3o$b2obo5bo
b2o$bo5bo5bo$3b2obobob2o$5b2ob2o$5b2ob2o$2b5ob5o$2bo2bo3bo2bo$bob2o5b
2obo$o13bo$2o3bo3bo3b2o$3bob2ob2obo$5bo3bo$bobobo3bobobo$bo11bo$6bobo$
5b2ob2o2$7bo$4b2obob2o$7bo$5bobobo$3bobo3bobo$5b5o$5bo3bo$5bo3bo$4b3ob
3o2$7bo$7bo$7bo$7bo!

Code: Select all

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

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: zfind discussion

Post by praosylen » March 20th, 2020, 11:49 pm

LaundryPizza03 wrote:
March 20th, 2020, 10:32 pm
I did a search for a c/5 orthogonal at width 15 on odd symmetry. It was so long that it required a depth greater than the default.

Code: Select all

rle
However, it turns out that Lewis Patterson found a much shorter ship at the same width in 2015. qfind gives the same result.

Code: Select all

rle
This is expected, since zfind searches depth-first — there's no guarantee that the first ship found will be the shortest. If you want to find shorter ships, you can either search for multiple ships with the s option or restrict the length with the m option (or both), IIRC.
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: zfind discussion

Post by Naszvadi » March 21st, 2020, 8:13 am

Currently which software has support for searching spaceships (in two-state rules) with one or more of this constraints:
  • in B0 life-like rules
  • in B0 isotropic nontotalistic rules
  • with speed c/1
  • with average speed c/1
  • with average speed faster than c/2
  • on hexagonal grid
  • with vonNeumann neighbourhood (must support B0!) - the second implicit covers this, however

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: zfind discussion

Post by wildmyron » March 21st, 2020, 12:57 pm

Naszvadi wrote:
March 21st, 2020, 8:13 am
Currently which software has support for searching spaceships (in two-state rules) with one or more of this constraints:
Not sure this thread is the best place for this topic, but I'll give it a go.
  • in B0 life-like rules
gfind, WLS, JLS, LLS, rlifesrc
  • in B0 isotropic nontotalistic rules
LLS, rlifesrc
  • with speed c/1
gfind (p1 only), WLS, JLS, LLS, rlifesrc
  • with average speed c/1
Not sure what you are asking for here - do you mean in rules with range > 1?
I wrote a dinky SMT based solver which can find small spaceships in MiniBugs, but it's not really very useful.
  • with average speed faster than c/2
most of them I think, though zfind doesn't always work properly
  • on hexagonal grid
yfind (isotropic only and no B0, IIRC)
  • with vonNeumann neighbourhood (must support B0!) - the second implicit covers this, however
I don't know of any specific to vN rules.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

AlephAlpha
Posts: 66
Joined: October 6th, 2017, 1:50 am

Re: zfind discussion

Post by AlephAlpha » April 2nd, 2020, 9:00 am

wildmyron wrote:
March 21st, 2020, 12:57 pm
Naszvadi wrote:
March 21st, 2020, 8:13 am
Currently which software has support for searching spaceships (in two-state rules) with one or more of this constraints:
Not sure this thread is the best place for this topic, but I'll give it a go.
  • in B0 life-like rules
gfind, WLS, JLS, LLS, rlifesrc
  • in B0 isotropic nontotalistic rules
LLS, rlifesrc
  • with speed c/1
gfind (p1 only), WLS, JLS, LLS, rlifesrc
  • with average speed c/1
Not sure what you are asking for here - do you mean in rules with range > 1?
I wrote a dinky SMT based solver which can find small spaceships in MiniBugs, but it's not really very useful.
  • with average speed faster than c/2
most of them I think, though zfind doesn't always work properly
  • on hexagonal grid
yfind (isotropic only and no B0, IIRC)
  • with vonNeumann neighbourhood (must support B0!) - the second implicit covers this, however
I don't know of any specific to vN rules.
rlifesrc supports hexagonal grid, and vonNeumann neighbourhood, and any non-isotropic Life-like rules (using MAP notation). It uses a rule parser which can automatically convert all these rules to non-isotropic Moore neighbourhood rules.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: zfind discussion

Post by Naszvadi » June 18th, 2020, 9:52 am

AlephAlpha wrote:
April 2nd, 2020, 9:00 am
wildmyron wrote:
March 21st, 2020, 12:57 pm
Naszvadi wrote:
March 21st, 2020, 8:13 am
Currently which software has support for searching spaceships (in two-state rules) with one or more of this constraints:
Not sure this thread is the best place for this topic, but I'll give it a go.
  • in B0 life-like rules
gfind, WLS, JLS, LLS, rlifesrc
  • in B0 isotropic nontotalistic rules
LLS, rlifesrc
  • with speed c/1
gfind (p1 only), WLS, JLS, LLS, rlifesrc
  • with average speed c/1
Not sure what you are asking for here - do you mean in rules with range > 1?
I wrote a dinky SMT based solver which can find small spaceships in MiniBugs, but it's not really very useful.
  • with average speed faster than c/2
most of them I think, though zfind doesn't always work properly
  • on hexagonal grid
yfind (isotropic only and no B0, IIRC)
  • with vonNeumann neighbourhood (must support B0!) - the second implicit covers this, however
I don't know of any specific to vN rules.
rlifesrc supports hexagonal grid, and vonNeumann neighbourhood, and any non-isotropic Life-like rules (using MAP notation). It uses a rule parser which can automatically convert all these rules to non-isotropic Moore neighbourhood rules.
@AlephAlpha

Tried out rlifesrc. No clue if B0 or B0/V rules can be specified anyhow.
Latest master had been used:

Code: Select all

/github.com/AlephAlpha/rlifesrc$ git log -1 --oneline
2b3e4a1 (HEAD -> master, origin/master, origin/HEAD) :pencil2: typo
Testdrive succeeded with custom rule:

Code: Select all

/github.com/AlephAlpha/rlifesrc/target/debug$ ./rlifesrc 5 5 2 1 --rule b368/s23 --no-tui --transform 'F-'
x = 5, y = 5, rule = b368/s23
..oo.$
.oooo$
oo.oo$
.oo..$
.....!
However, does not want to accept b0 rulestrings. Any help is appreciated and kindly welcome!

AlephAlpha
Posts: 66
Joined: October 6th, 2017, 1:50 am

Re: zfind discussion

Post by AlephAlpha » June 18th, 2020, 10:58 pm

Naszvadi wrote:
June 18th, 2020, 9:52 am

@AlephAlpha

Tried out rlifesrc. No clue if B0 or B0/V rules can be specified anyhow.
Latest master had been used:

Code: Select all

/github.com/AlephAlpha/rlifesrc$ git log -1 --oneline
2b3e4a1 (HEAD -> master, origin/master, origin/HEAD) :pencil2: typo
Testdrive succeeded with custom rule:

Code: Select all

/github.com/AlephAlpha/rlifesrc/target/debug$ ./rlifesrc 5 5 2 1 --rule b368/s23 --no-tui --transform 'F-'
x = 5, y = 5, rule = b368/s23
..oo.$
.oooo$
oo.oo$
.oo..$
.....!
However, does not want to accept b0 rulestrings. Any help is appreciated and kindly welcome!
Thanks for reporting this bug. When I added the feature to limit the number of living cells, I neglected B0 rules, where there are infinite living cells on generations.

Before it is fixed, you can use the "release" build (compile with `cargo build --release` and the target file is in the folder target/release), and do not use the feature to limit the number of living cells.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: zfind discussion

Post by Naszvadi » June 21st, 2020, 7:17 am

AlephAlpha wrote:
June 18th, 2020, 10:58 pm
Naszvadi wrote:
June 18th, 2020, 9:52 am
foobar
Thanks for reporting this bug. When I added the feature to limit the number of living cells, I neglected B0 rules, where there are infinite living cells on generations.

Before it is fixed, you can use the "release" build (compile with `cargo build --release` and the target file is in the folder target/release), and do not use the feature to limit the number of living cells.
Wow, thanks!

Some recipes, thumb rules are:
If someone wants to search for a diagonal glider c/(2*n) with period 2*n that flips in every nth generation, must invoke rlifesrc like this:

Code: Select all

./rlifesrc 7 7 6 1 0 --rule B02/S1V --no-tui --transform 'F\' -a|sed /^x/i$'\x5b'/code$'\x5d'$'\x5b'code$'\x5d'

Code: Select all

x = 7, y = 7, rule = B02/S1V
.......$
..o....$
.ooo...$
....oo.$
...o...$
.....o.$
.......!

Code: Select all

x = 7, y = 7, rule = B02/S1V
.......$
.......$
..oo...$
..o.o..$
.......$
....oo.$
.......!

Code: Select all

x = 7, y = 7, rule = B02/S1V
.......$
.......$
..o....$
...oo..$
...o.o.$
.....o.$
.......!

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

Re: zfind discussion

Post by LaundryPizza03 » October 23rd, 2020, 7:38 pm

For some reason ntzfind requires some extra padding when doing knight searches:

Code: Select all

ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B3/S23 p4 k1 x1 w4
Rule: B3/S23
Period: 4
Offset: 1
Width:  4
Symmetry: asymmetric
Horizontal offset: 1
Phase 0 has width 3
Depth limit: 2000
Stop search if a ship is found.
Starting search
.o..
.oo.
Length: 7
Search complete: 0 spaceships found.
Calculations: 205
CPU time: 0.000102 seconds

Code: Select all

ntzfind 3.0 by "zdr", Matthias Merzenich, Aidan Pierce, and Tomas Rokicki, 24 February 2018
- ./ntzfind B3/S23 p4 k1 x1 w5
Rule: B3/S23
Period: 4
Offset: 1
Width:  5
Symmetry: asymmetric
Horizontal offset: 1
Phase 0 has width 4
Depth limit: 2000
Stop search if a ship is found.
Starting search

..o..
..oo.
.o.o.
Length: 12
Spaceship found. (1)

Current depth: 2001
Calculations: 2664
CPU time: 0.001952 seconds
Search terminated: spaceship found.
Notice that this does not happen for orthogonal searches.

Code: Select all

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

Post Reply