ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

zfind discussion

For scripts to aid with computation or simulation in cellular automata.

Re: zfind discussion

Postby Majestas32 » January 28th, 2018, 12:49 am

Go to the qfind thread
I type all my RLE's by hand. Golly is for wimps.
User avatar
Majestas32
 
Posts: 374
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: zfind discussion

Postby A for awesome » January 28th, 2018, 11:34 am

danny wrote:Ntqfind Seems to be broken. I compiled the rule B2en3ij4a5e7e8/S1c2cek3-a4aiqw5aky and it isn't giving me spaceships, not even the small c/4 diagonal.

qfind/ntqfind don't support diagonal or oblique spaceship searches, and as such the "x" parameter is ignored.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1600
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby danny » January 28th, 2018, 1:34 pm

A for awesome wrote:qfind/ntqfind don't support diagonal or oblique spaceship searches, and as such the "x" parameter is ignored.

Oh, okay. That explains why it can find the c/2's just fine. Drat :c
call me danny.

i ain't happy, i'm feeling glad,
i got sunshine, in a bag,
i'm useless, but not for long,
my future is coming on.
User avatar
danny
 
Posts: 426
Joined: October 27th, 2017, 3:43 pm
Location: i love to eat bees

Re: zfind discussion

Postby rokicki » February 26th, 2018, 7:37 pm

Howdy! I'm hacking on ntzfind and am using github. I'd like to make sure I don't step on any toes as I continue my work. Would any of the contributors mind a MIT license? I'd like to get this figured out before I get too far along.
Thanks!

-tom
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby A for awesome » February 26th, 2018, 7:48 pm

rokicki wrote:Howdy! I'm hacking on ntzfind and am using github. I'd like to make sure I don't step on any toes as I continue my work. Would any of the contributors mind a MIT license? I'd like to get this figured out before I get too far along.
Thanks!

-tom

I don't care, personally — honestly, I never even thought to ask about licensing myself, so my work should be considered fair game for anyone to steal as they see fit (with the original contributors' consent, of course).
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce
User avatar
A for awesome
 
Posts: 1600
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: zfind discussion

Postby wildmyron » February 26th, 2018, 11:45 pm

rokicki wrote:Howdy! I'm hacking on ntzfind and am using github. I'd like to make sure I don't step on any toes as I continue my work. Would any of the contributors mind a MIT license? I'd like to get this figured out before I get too far along.
Thanks!

-tom

For reference, the original version of zfind posted by @zdr is here. I don't think there was any indication of licensing terms and @zdr was only active on the forum for a month, roughly 2 years ago.

I believe the only other major contributor has been @Sokwe.
Last edited by wildmyron on February 27th, 2018, 4:59 am, edited 1 time in total.
wildmyron
 
Posts: 722
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby Sokwe » February 27th, 2018, 12:28 am

rokicki wrote:I'm hacking on ntzfind and am using github. I'd like to make sure I don't step on any toes as I continue my work. Would any of the contributors mind a MIT license? I'd like to get this figured out before I get too far along.

I'm fine with that.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1228
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby Macbi » February 27th, 2018, 4:16 am

Is it possible to not have a license on github? Given that the orignal authors didn't give one it's probably fine for us to modify their code, but it seems a bit rude to release their code under some license without asking them.

EDIT: You could release it as the orignal code and a patch, and state that the license only applies to the patch.
User avatar
Macbi
 
Posts: 373
Joined: March 29th, 2009, 4:58 am

Re: zfind discussion

Postby Majestas32 » February 27th, 2018, 11:04 am

The Majestas32 license
I type all my RLE's by hand. Golly is for wimps.
User avatar
Majestas32
 
Posts: 374
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: zfind discussion

Postby rokicki » February 27th, 2018, 1:02 pm

I don't want to get into a software licensing discussion here, but: in the United States, copyright law (which is what governs source code) defaults to not granting any rights for distribution, modification, or execution of any code. So in principle, just because zdr posted his code doesn't mean any of us can legally run it, or modify it. At any point zdr can legally step up and assert his rights and forbid any use or distribution of his code---including *all* derivative works (whether in patch form or not). This is why I posted my query; I'd like to get this resolved before investing too much time on this project.

I have removed the license from my repository, based on the feedback I have received so far; without zdr's blessing I probably cannot license what is clearly a derivative work. Even though I intend to freely share and collaborate, without the original author's clearly stated intent, I can't assert a license to the derived work.

This also means I cannot protect myself against liability claims, and I cannot assert other people's right to contribute. Which puts a real damper on my enthusiasm.
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby dvgrn » February 27th, 2018, 2:28 pm

rokicki wrote:This also means I cannot protect myself against liability claims, and I cannot assert other people's right to contribute. Which puts a real damper on my enthusiasm.

The original contribution was less than 200 lines of code, so I hope the enthusiasm doesn't get dampened _too_ much. Is a quick rewrite possible, to put things on a firmer legal footing?

It's absolutely true that no one in the United States can protect themselves against (frivolous) liability claims, no matter what they've done or haven't done. Anybody with money to pay a sufficiently ethically challenged lawyer can create legal trouble, and associated court costs, for anyone else... which generally requires paying more money to another lawyer to counter-sue and recover said costs.

However, given that the mysterious zdr's intention seemed to be to make the code publicly available...

and that zdr has not re-visited the conwaylife.com forums since that initial period almost two years ago...

the odds of zdr actually becoming interested in investing in the necessary legal fees to cause such trouble seem ... low enough that it would probably be worth buying liability insurance guarding against almost any other possible Unfortunate Event, before it's worth buying anti-zdr insurance.

-- However, given the incredibly silly liability laws in the US, I wouldn't be surprised if I'm legally obligated at this point to include the following disclaimer: I am neither a lawyer nor an insurance agent.
User avatar
dvgrn
Moderator
 
Posts: 4422
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: zfind discussion

Postby rokicki » February 27th, 2018, 3:09 pm

I'm having fun hacking on it! If zdr shuts me down, then that's what happens. I think we are
all pulling in the same direction here, so I'm not too concerned.
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby Sokwe » February 27th, 2018, 7:15 pm

dvgrn wrote:Is a quick rewrite possible, to put things on a firmer legal footing?

I have essentially already done that, not for legal reasons, but because zdr's code was completely unreadable.

There's not really much to zfind. It's just the gfind algorithm, but the de Bruijn graph technique for finding successor rows is replaced by a direct lookup table.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1228
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby rokicki » February 27th, 2018, 7:56 pm

I kind of enjoyed reading zdr's code; it was like he was programming in assembly language
for some processor that I am not familiar with. While Sokwe's rewrite made massive
improvements to the code in terms of readability, and without impacting performance, it
certainly does not satisfy any legal requirements for any sort of clean-room reimplementation
that would permit it to not be a derivative work of zdr's. In order for that to happen
someone who has never seen zdr's code would need to reimplement it based on some sort
of description of the functionality. At this point, I think anyone "interested" would be
already "poisoned" by having read the code.

I'm going to share the URL of the repository at this point, even though I'm far from done
with my changes; it's already sufficiently faster that many precious CPU cycles can be
saved. But I don't guarantee I haven't broken some functionality; indeed, I've definitely
broken the save/load functionality (it's pretty easy to fix but it's not high on my priority
list at the moment). The main thing I've focused on is letting wider searches be done,
if not exhaustively, then opportunistically. But it's also faster just in general.

github.com/rokicki/ntzfind

I do not plan to hold anyone's hand at this stage; if you don't know how to compile C++
code, or can't figure out how to get the code from github onto your computer, continue
to use the programs you are currently using. I compile it with this command:

g++ -O3 -march=native -o ntzfind ntzfind.cpp

You don't need the python script anymore; the code has full support for isotropic rule
parsing. There is no support for multithreading yet (I plan this soon) and no support for
knightship searches yet (also planned).

I'd be happy to hear of any problems or successes, and since I'm building on work that was
primarily done by others, I apologize if I've broken something important and I'm not trying
to grab any credit. I just think there's a lot of opportunity for further improvements
which may help us find even more interesting things . . .
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby Sokwe » February 27th, 2018, 8:53 pm

rokicki wrote:it's already sufficiently faster that many precious CPU cycles can be
saved.

This is the most important part to me. Can you maybe explain where you think the speed up is coming from. I hope that whatever you did can be added to qfind.

rokicki wrote:The main thing I've focused on is letting wider searches be done,
if not exhaustively, then opportunistically.

I'm not sure what you mean by this. Do you mean that width-11 searches aren't always complete? Could they miss something?
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1228
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby rokicki » February 27th, 2018, 9:17 pm

All I did to speed up the search was to put a cache in front of the lookAhead routine.

Sometimes the lookAhead routine can spend a lot of time (relatively speaking) trying
to decide if it's worth exploring a branch. I hash the relevant parameters and use a
direct-mapped cache to see if I've seen those parameters before, and if so, return the
result I got last time.

The key change is this one:

https://github.com/rokicki/ntzfind/comm ... e0df49be29

but I've refined it after finding that (especially for wide searches) a bigger cache
gives further improvements (I've made the cache size configurable, with a default of
32MB).

On the opportunistic searches: none of the search order parameters (o, n, r) change
whether things will be found or not, or the completeness of the search. It's just if a
search at width 11 might take fifty years, maybe you want to try exploring a random
part of the search space anyway . . .
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby wildmyron » February 28th, 2018, 2:44 am

@rokicki: Thank you for these improvements to zfind. Not having to recompile for isotropic rules is great, and the dynamic table generation is particularly nice for wide searches. On my memory constrained desktop (only 4G RAM) I can now complete some w10 searches (for example 2c/5 odd sym in tlife in 15s) where previously zfind is unable to build the lookup table in any reasonable time (due to thrashing). In a few (very) brief tests I saw search times for some negative results improve by a factor of 1.5, consistent with your results (considering the brevity of my tests).

I compiled with MSVC 2017 using this command:
cl /O2 /favor:INTEL64 ntzfind.cpp

I made the following minor changes to the search order randomization code to get it to compile:
diff --git a/ntzfind.cpp b/ntzfind.cpp
index 1fb5b6a..a550cc6 100644
--- a/ntzfind.cpp
+++ b/ntzfind.cpp
@@ -9,4 +9,5 @@
#include <stdint.h>
#include <string.h>
+#include <time.h>
#include "tab.cpp"

@@ -311,5 +312,5 @@ void makeTables() {
    if (sp[P_REORDER] == 2)
       for (int i=1; i<1<<width; i++)
-         gcount[i] = 1 + (lrand48() & 0x3fffffff) ;
+         gcount[i] = 1 + (rand() & 0x3fffffff) ;
    if (sp[P_REORDER] == 3)
       for (int i=1; i<1<<width; i++)
@@ -1060,5 +1061,5 @@ int main(int argc, char *argv[]){
    cache = (struct cacheentry *)calloc(sizeof(cacheentry), cachesize) ;
    if (sp[P_REORDER] == 2)
-      srand48(time(0)) ;
+      srand(time(0)) ;
    if(loadDumpFlag) loadState(argv[1],argv[2]);     //load search state from file
    else initializeSearch(argv[sp[P_INIT_ROWS]]);    //initialize search based on input parameters

It seems to work the way I expect it should and should be gcc compatible?
wildmyron
 
Posts: 722
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby rokicki » February 28th, 2018, 3:05 am

Great, thanks for the change! I'll make the change conditional on Windows, or maybe
I'll just embed the Mersenne twister code which should be good enough for what we
need.

I'd be careful letting your machine swap; you might use the R4000 option to limit max
memory consumption to 4GB (the program will exit if it thinks it will allocate more than
this).

Multithreading is not quite as trivial as I had hoped because the search tree appears to
generally be very oddly shaped so it's not trivial to split up the work---at least that's what
I'm seeing so far. I need to think on this some more.

First nontrivial result for me is negative CGOL 3c/8 (period 8 ) width 11 asym, which took

Search complete: 0 spaceships found.
Calculations: 108386M
CPU time: 5066.853431 seconds

Longest partial reported was this one:

....o......
...o.o.....
..o...o....
.oo...o....
.oo.ooo....
.....o.....
.o..o......
....o......
.ooo.......
....o......
..oo.oo....
.o.........
.o.....o...
.o.o...o...
oo.o.......
.o..oo.o...
oo..o.ooo..
oo....o....
..oo...o.o.
..o.o....oo
..oo.oo..oo
.o.o.ooooo.
ooo.oo.....
.o...o...o.


I think this was already done by knight2; can anyone weigh in on
knight2/knightt vs ntzfind? I see some reports of extreme width
results (25!) for knightt that I don't see ntzfind approaching . . .
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby wildmyron » February 28th, 2018, 6:57 am

rokicki wrote:Great, thanks for the change! I'll make the change conditional on Windows, or maybe
I'll just embed the Mersenne twister code which should be good enough for what we
need.

Thanks.
rokicki wrote:I'd be careful letting your machine swap; you might use the R4000 option to limit max
memory consumption to 4GB (the program will exit if it thinks it will allocate more than
this).

Well, that was from past experience with zfind 2.0. Occasionally I made the mistake of trying to run a w10 search on this machine and would have to kill it. I just tested the memory limit and it works very nicely. I'm pleased about that because when I was trying to compile glucose (with an older version of MSVC) I had to comment out the memory limits.
rokicki wrote:Multithreading is not quite as trivial as I had hoped because the search tree appears to
generally be very oddly shaped so it's not trivial to split up the work---at least that's what
I'm seeing so far. I need to think on this some more.

That's certainly a difficulty of breaking up DFS style searches - the search time tends to be dominated by a small number of branches. qfind's approach may give you some ideas, though I recollect @Sokwe has mentioned that the DFS phase (which is the multithreaded part) can be delayed by a single thread which takes much longer to search its branch than all the other threads. A possible approach:
  • For a search with N threads divide the search tree into N*M branches, and whenever a thread is available assign it the next branch until all branches have been assigned, then wait for the last thread to finish. N*M would probably need to be larger than w * p * 4 to ensure it breaks up the largest branches, and even then I suspect it would probably still suffer the same problem as qfind.
A more complex approach would allow breaking up an existing branch into two separate branches dynamically as threads become available, but unless you can find a clever way of determining where to break up the branch a lot of time would probably be wasted farming out branches which go almost nowhere.
rokicki wrote:First nontrivial result for me is negative CGOL 3c/8 (period 8 ) width 11 asym, which took

Search complete: 0 spaceships found.
Calculations: 108386M
CPU time: 5066.853431 seconds

Longest partial reported was this one:

<snip rle>


I think this was already done by knight2;

According to http://www.conwaylife.com/wiki/LifeWiki ... tatus_Page 3c/8 searches have been run at w11 for all symmetries with gfind by Paul Tooke (all negative results, obviously). There's almost no mention of 3c/8 on the Spaceship Discussion Thread, so I've no idea if w12 is feasible with gfind, but it's nice to see that result in under 2h.
wildmyron
 
Posts: 722
Joined: August 9th, 2013, 12:45 am

Re: zfind discussion

Postby rokicki » February 28th, 2018, 4:12 pm

wildmyron wrote:According to http://www.conwaylife.com/wiki/LifeWiki ... tatus_Page 3c/8 searches have been run at w11 for all symmetries with gfind by Paul Tooke ...


Hmm, my reading of that page says they were run by knight2 (and unattributed). Am I misreading it?

Asymmetric searches are now twice as fast (so three or more times faster in aggregate); I only search one of the two mirror reflections.
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby Sokwe » February 28th, 2018, 8:03 pm

rokicki wrote:Hmm, my reading of that page says they were run by knight2 (and unattributed). Am I misreading it?

You're reading it correctly. I was the one who ran the 3c/8 knight2 searches. As I recall, they never got very deep. I think each one took a few days, but I don't really remember.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1228
Joined: July 9th, 2009, 2:44 pm

Re: zfind discussion

Postby Apple Bottom » March 1st, 2018, 5:37 am

rokicki wrote:I don't want to get into a software licensing discussion here, but: in the United States, copyright law (which is what governs source code) defaults to not granting any rights for distribution, modification, or execution of any code. So in principle, just because zdr posted his code doesn't mean any of us can legally run it, or modify it. At any point zdr can legally step up and assert his rights and forbid any use or distribution of his code---including *all* derivative works (whether in patch form or not).


IANAL, but I believe this is not strictly correct -- you don't need a license to run code (that's why the FSF takes pains to point out that you don't need to accept the terms of the GNU GPL to run a GPL'ed program, for instance). A license you accept or a contract you enter may restrict your ability to run code, but absent either, a license is not required to run code. It's called "copyright" for a reason, after all. :)
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 895
Joined: July 27th, 2015, 2:06 pm

Re: zfind discussion

Postby AforAmpere » March 14th, 2018, 4:50 pm

Can the code from zfind 1.6 be potentially addable, so larger width knightship searches could run?
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 592
Joined: July 1st, 2016, 3:58 pm

Re: zfind discussion

Postby rokicki » March 14th, 2018, 7:43 pm

AforAmpere wrote:Can the code from zfind 1.6 be potentially addable, so larger width knightship searches could run?


Sure, or I can "backport" the changes I made into zfind 1.6. The table changes are fully separable. Concurrency and dynamic table generation don't play well together so for the initial stab at multithreading I did, I disabled the dynamic table generation, but width-11 and width-12 searches are still very possible.
rokicki
 
Posts: 43
Joined: August 6th, 2009, 12:26 pm

Re: zfind discussion

Postby AforAmpere » April 11th, 2018, 6:30 pm

The changes work, sometimes. Searching for the C/3 diagonal in Day and Night works just fine, but when searching with this rule, it does not find a C/3 diagonal for some reason, even though there is one in the rule at that size:
./ntzfind3_1 B2cei3a/S02i3i p3 k1 x1 w10 a

x = 3, y = 3, rule = B2cei3a/S02i3i
obo2$2bo!
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere
 
Posts: 592
Joined: July 1st, 2016, 3:58 pm

Previous

Return to Scripts

Who is online

Users browsing this forum: Majestas32 and 2 guests