zfind discussion

For scripts to aid with computation or simulation in cellular automata.
User avatar
danny
Posts: 969
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA
Contact:

Re: zfind discussion

Post by danny » 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.
she/her // danielle

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.

AforAmpere
Posts: 1050
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 and wildmyron 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
- Finish a rule with ships with period >= f_e_0(n) (in progress)

User avatar
Moosey
Posts: 2712
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board.
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 5472 times
I am a prolific creator of many rather pathetic googological functions

My CA rules can be found here

Also, the tree game
Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"

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

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 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.

Sokwe
Moderator
Posts: 1494
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
Posts: 2104
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: 383
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: 483
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: 483
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: 1297
Joined: August 9th, 2013, 12:45 am

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 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.

AforAmpere
Posts: 1050
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 and wildmyron 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
- Finish a rule with ships with period >= f_e_0(n) (in progress)

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

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 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.

Sokwe
Moderator
Posts: 1494
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

Post Reply