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

A new GoL searching program

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

A new GoL searching program

Postby Alegend » July 3rd, 2012, 3:43 pm

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.
Alegend
 
Posts: 31
Joined: October 5th, 2009, 3:20 pm

Re: A new GoL searching program

Postby Paul Tooke » July 5th, 2012, 12:18 pm

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!
Paul Tooke
 
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: A new GoL searching program

Postby Alegend » July 5th, 2012, 5:43 pm

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.
Alegend
 
Posts: 31
Joined: October 5th, 2009, 3:20 pm

Re: A new GoL searching program

Postby velcrorex » July 5th, 2012, 7:43 pm

Have you taken a look at this article by David Eppstein which describes how gfind works?
-Josh Ball.
User avatar
velcrorex
 
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: A new GoL searching program

Postby Paul Tooke » July 5th, 2012, 7:54 pm

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.
Paul Tooke
 
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK

Re: A new GoL searching program

Postby Alegend » July 6th, 2012, 3:47 pm

Unmodified gfind 4.9 is what I'm using.
Alegend
 
Posts: 31
Joined: October 5th, 2009, 3:20 pm

Re: A new GoL searching program

Postby velcrorex » July 6th, 2012, 4:43 pm

I am also very interested in any edits you may have made to gfind.
-Josh Ball.
User avatar
velcrorex
 
Posts: 339
Joined: November 1st, 2009, 1:33 pm

Re: A new GoL searching program

Postby EricG » July 6th, 2012, 7:28 pm

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!
EricG
 
Posts: 199
Joined: August 19th, 2011, 5:41 pm
Location: Chicago-area, USA

Re: A new GoL searching program

Postby Sokwe » July 8th, 2012, 12:29 am

@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?
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1479
Joined: July 9th, 2009, 2:44 pm

Re: A new GoL searching program

Postby Paul Tooke » July 8th, 2012, 7:46 am

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.
Paul Tooke
 
Posts: 111
Joined: May 19th, 2010, 7:35 am
Location: Cambridge, UK


Return to Scripts

Who is online

Users browsing this forum: No registered users and 0 guests