Page 1 of 1

A new GoL searching program

PostPosted: July 3rd, 2012, 3:43 pm
by Alegend
I've been thinking about trying to search for c/8 or c/9 spaceships, but the existing programs out there are either too slow, or too complicated to understand. So, I figured I'd make my own.

However, I have no earthly idea, on how to begin. I would like to have a program that's about as fast as gfind, but simpler to implement, and understand.

Re: A new GoL searching program

PostPosted: July 5th, 2012, 12:18 pm
by Paul Tooke
If you're doing c/8 and c/9 searches then the only programs I know of which are likely to find something before hell freezes over are gfind and afind, the latter being Eugene Langvagens gfind look-alike.

What is it about gfind that you find too complicated to understand? The (occasionally cryptic) options or the algorithms? If it's the options there are folks here (me at least) who may be able to help. If it is the algorithms then I wish you the best of luck in writing a competitor: finding spaceships at these velocities is hard!

Re: A new GoL searching program

PostPosted: July 5th, 2012, 5:43 pm
by Alegend
Mostly the algorithms. I've tried and tried to decipher them, but to no avail. It might just be because gfind is 2000 lines of C code.

Re: A new GoL searching program

PostPosted: July 5th, 2012, 7:43 pm
by velcrorex
Have you taken a look at this article by David Eppstein which describes how gfind works?

Re: A new GoL searching program

PostPosted: July 5th, 2012, 7:54 pm
by Paul Tooke
velcrorex: You added what I was going to reply with whilst I was logging in!
Alegend: I strongly support velcrorex's answer. As I said, these kind of searches are hard and therefore need clever algorithms. To improve on the state-of-the-art you need to understand what has preceded you. Sorry, but TANSTAAFL!

EDIT:
Alegend, are you using an unmodified copy of gfind? If you are, and you let me know which version you are using, I can show you a neat little trick that can speed up high period searches a fair bit.

Re: A new GoL searching program

PostPosted: July 6th, 2012, 3:47 pm
by Alegend
Unmodified gfind 4.9 is what I'm using.

Re: A new GoL searching program

PostPosted: July 6th, 2012, 4:43 pm
by velcrorex
I am also very interested in any edits you may have made to gfind.

Re: A new GoL searching program

PostPosted: July 6th, 2012, 7:28 pm
by EricG
I'm also very interested!

In addition to any speed-ups mentioned above, I'm interested in learning how to use gfind to do non-totalistic 2 state searches.

In the JustFriends Rule archive hosted by David Bell, there is an amazing cache of old email (in the file named "spaceships"). Among those email messages, there is mention of a modification to gfind by Paul Tooke which allows it to search for spaceships in JustFriends. (And perhaps it can search on similar non-totalistic rules as well?)

Paul, I completely understand any reluctance you might have about releasing code that isn't polished, but anything, of any quality or degree of polishedness, that you would be willing to share on these topics would be greatly appreciated!

Thanks!

Re: A new GoL searching program

PostPosted: July 8th, 2012, 12:29 am
by Sokwe
@Paul
I would also like to see any modifications you've made to gfind. On a somewhat related note, what searches have you completed in the range of p6 to 8?

Re: A new GoL searching program

PostPosted: July 8th, 2012, 7:46 am
by Paul Tooke
Hmm. Me and my big mouth. I should have known that this would happen. When I mentioned the potential speed-up, all I really had in mind was producing a modified version of gfind which allowed the specification of the minimum deepening increment. Explaining all of the modifications that I've made to gfind that I've made since I started using it in early 2000 is a different kettle of fish entirely. Ok, I will give it a go but it's a bit OT here and really deserves a topic of its own. Look for a topic entitled something like "Adapting gfind" appearing in this forum. I'll address the modifications mentioned here first.

In a similar vein, Sokwe wrote:
what searches have you completed in the range of p6 to 8?

As I'm sure you're probably aware, the answer to this question really belongs in the Online Database of Unsuccessful GFIND Searches topic. I''ll look through my results and post an update there. Hopefully I'll also remember to add a caveat about the need for independent confirmation of negative results. BTW your range is a bit restrictive. I've also done p9 and p11 searches and I'm fairly confident that there is more interesting stuff to be found at c/5 orthogonal.