zfind discussion
- Majestas32
- Posts: 549
- Joined: November 20th, 2017, 12:22 pm
- Location: 'Merica
Re: zfind discussion
Go to the qfind thread
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i
Currently looking for help searching these rules.
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i
Currently looking for help searching these rules.
- praosylen
- Posts: 2449
- Joined: September 13th, 2014, 5:36 pm
- Location: Pembina University, Home of the Gliders
- Contact:
Re: zfind discussion
qfind/ntqfind don't support diagonal or oblique spaceship searches, and as such the "x" parameter is ignored.dani 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.
Last edited by praosylen on February 18th, 2020, 12:22 am, edited 1 time in total.
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...
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...
Re: zfind discussion
Oh, okay. That explains why it can find the c/2's just fine. Drat :cA for awesome wrote: qfind/ntqfind don't support diagonal or oblique spaceship searches, and as such the "x" parameter is ignored.
Re: zfind discussion
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
Thanks!
-tom
- praosylen
- Posts: 2449
- Joined: September 13th, 2014, 5:36 pm
- Location: Pembina University, Home of the Gliders
- Contact:
Re: zfind discussion
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).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
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...
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...
Re: zfind discussion
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.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 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.
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.
Semi-active here - recovering from a severe case of LWTDS.
Re: zfind discussion
I'm fine with that.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.
-Matthias Merzenich
Re: zfind discussion
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.
EDIT: You could release it as the orignal code and a patch, and state that the license only applies to the patch.
- Majestas32
- Posts: 549
- Joined: November 20th, 2017, 12:22 pm
- Location: 'Merica
Re: zfind discussion
The Majestas32 license
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i
Currently looking for help searching these rules.
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i
Currently looking for help searching these rules.
Re: zfind discussion
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.
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.
Re: zfind discussion
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?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.
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.
Re: zfind discussion
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.
all pulling in the same direction here, so I'm not too concerned.
Re: zfind discussion
I have essentially already done that, not for legal reasons, but because zdr's code was completely unreadable.dvgrn wrote:Is a quick rewrite possible, to put things on a firmer legal footing?
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
Re: zfind discussion
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 . . .
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 . . .
Re: zfind discussion
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:it's already sufficiently faster that many precious CPU cycles can be
saved.
I'm not sure what you mean by this. Do you mean that width-11 searches aren't always complete? Could they miss something?rokicki wrote:The main thing I've focused on is letting wider searches be done,
if not exhaustively, then opportunistically.
-Matthias Merzenich
Re: zfind discussion
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 . . .
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 . . .
Re: zfind discussion
@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:
I made the following minor changes to the search order randomization code to get it to compile:
It seems to work the way I expect it should and should be gcc compatible?
I compiled with MSVC 2017 using this command:
Code: Select all
cl /O2 /favor:INTEL64 ntzfind.cpp
Code: Select all
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
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.
Semi-active here - recovering from a severe case of LWTDS.
Re: zfind discussion
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:
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 . . .
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:
Code: Select all
....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.
knight2/knightt vs ntzfind? I see some reports of extreme width
results (25!) for knightt that I don't see ntzfind approaching . . .
Re: zfind discussion
Thanks.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.
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: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).
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: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.
- 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.
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.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:
I think this was already done by knight2;Code: Select all
<snip rle>
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.
Semi-active here - recovering from a severe case of LWTDS.
Re: zfind discussion
Hmm, my reading of that page says they were run by knight2 (and unattributed). Am I misreading it?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 ...
Asymmetric searches are now twice as fast (so three or more times faster in aggregate); I only search one of the two mirror reflections.
Re: zfind discussion
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.rokicki wrote:Hmm, my reading of that page says they were run by knight2 (and unattributed). Am I misreading it?
-Matthias Merzenich
- Apple Bottom
- Posts: 1034
- Joined: July 27th, 2015, 2:06 pm
- Contact:
Re: zfind discussion
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.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).
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!
Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_
Proud member of the Pattern Raiders!
-
- Posts: 1334
- Joined: July 1st, 2016, 3:58 pm
Re: zfind discussion
Can the code from zfind 1.6 be potentially addable, so larger width knightship searches could run?
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.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.
Re: zfind discussion
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.AforAmpere wrote:Can the code from zfind 1.6 be potentially addable, so larger width knightship searches could run?
-
- Posts: 1334
- Joined: July 1st, 2016, 3:58 pm
Re: zfind discussion
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:
Code: Select all
./ntzfind3_1 B2cei3a/S02i3i p3 k1 x1 w10 a
Code: Select all
x = 3, y = 3, rule = B2cei3a/S02i3i
obo2$2bo!
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.
Things to work on:
- Find (7,1)c/8 and 9c/10 ships in non-B0 INT.
- EPE improvements.