Census Program Idea

[Lewis]

Would it be possible to write a program that can be downloaded, used to collect statistics from randomly generated life games, then automatically send the data to a website, where a continuously-updated cumulative census would be generated. If enough people downloaded and used the software, it would be a fairly quick way of generating the statistics, and would probably find some new small oscillators.

[PM 2Ring]

Sounds feasible. We could call it the Game Of Life Distributed Oscillator Research Engine, or GOLD_ORE.

I think it makes sense to use existing software to do the actual searching, and just write "wrapper" software to handle the distribution & gathering of data. Plus something to crunch the results.

[Macbi]

I don't think more census results would be that interesting. What I'd much prefer to see would be a depth-first search of all life patterns, sorted by bounding box. It would certainly generate as much interesting stuff, but would be a lot more complete. Either that or we could analyze more glider collisions.

[Nathaniel]

I'd of course be willing to lend my server to a task like this, though I'm not sure I'm familiar enough with Python/Perl and/or the relevant coding techniques to actually make a program that would do something like has been suggested here.

What I'd much prefer to see would be a depth-first search of all life patterns, sorted by bounding box. It would certainly generate as much interesting stuff, but would be a lot more complete. Either that or we could analyze more glider collisions.

That'd be very interesting, but much more difficult to do from the "distributed computing" perspective I think because you'd have to find a way to make it so that users aren't doing all the same calculations at the same time, yet they do all the calculations eventually (whereas with the random starting configuration set-up, that's not an issue).

I would *love* to see this done for glider collisions though.

[Awesomeness]

This would probably have to be done on one computer, probably the server. I have learned from my own experience with programming and things like networks and torrents that anyone can send "poisoned", messed-up data, and plus, it would probably take more CPU to download the results than to run it yourself. I don't know, that's just my opinion. Sorry if I'm being a pessimist. =/

[Nathaniel]

This would probably have to be done on one computer, probably the server. I have learned from my own experience with programming and things like networks and torrents that anyone can send "poisoned", messed-up data, and plus, it would probably take more CPU to download the results than to run it yourself. I don't know, that's just my opinion. Sorry if I'm being a pessimist. =/

It's not difficult to remedy the "poisoned" data concern by keeping the internet-related code closed-source and sending, along with the data, a salted hash of the results, where only the original coder of the script knows the salt. If the hash isn't incorrect on the server, then it simply ignores the results that the person sent in.

Also, many counting-type problems are prime for this type of thing. Take counting still lifes, for example. I've left scripts running for days on my computer to catalogue still lifes in various rules. It'd be great to have multiple computers for this type of thing, and have the results automatically catalogued and updated online.

[apg]

Wouldn't a Golly script be ideal for this, considering the powerful qlife and hlife algorithms that Golly implements? Using one of these algorithms (probably qlife) would generate results faster than using no speed optimisations, wouldn't it?

[PM 2Ring]

I agree with Nathaniel that a glider collision census would be more interesting than yet another oscillator search. But maybe I'm a little biased, considering my love of glider circuitry.

A distributed approach to these sorts of things would require the server to farm out the data to be examined to avoid unwanted duplications. I'm pretty sure that's what they do with things like prime searches, SETI and the protein folding project, but I have no idea about the mechanics of such projects. My computer is old & slow, so I haven't bothered to participate in such things.

I know a little bit about handling CGI in Python, but I've only done very simple things so far, like storing data from an HTML form into a CSV database, and a basic business card maker, that generates a PostScript & PDF file from form data. But I'm quite happy to contribute Python code if someone else tells me what to do. Also, I'm a competent C programmer (sorry, no C++), but I've never done any CGI or related stuff using C.

[Nathaniel]

Wouldn't a Golly script be ideal for this, considering the powerful qlife and hlife algorithms that Golly implements? Using one of these algorithms (probably qlife) would generate results faster than using no speed optimisations, wouldn't it?

Yeah, Golly would be glorious, my only concern with it is I don't know if it can be used to run portions of compiled code or not, and the internet-sending code would have to be pre-compiled (for security reasons mentioned above). I know basically nothing about Python - I just google the commands etc I need when I write a script since I have enough other programming experience to piece it together. Does anyone know if/how you can run a pre-compiled python script in Golly?

Edit: Ah! It seems we could compile a Python script to do the real grunt work, and then just have another Python script interact with Golly and call the compiled script as an exe.

Edit again: Excellent, I've got a working example of a pre-compiled methuselah search Python script now. I'll start running a server-side script and hopefully have a proof-of-concept uploaded sometime this week.

[Nathaniel]

Does anyone know if there is a pre-existing census Golly script out there anywhere? It'd be glorious if one already existed, rather than having to write one up from scratch.

And on that note, if none do exist, does anyone even have any idea how to go about writing a semi-efficient one?

[Elithrion]

Also, many counting-type problems are prime for this type of thing. Take counting still lifes, for example. I've left scripts running for days on my computer to catalogue still lifes in various rules. It'd be great to have multiple computers for this type of thing, and have the results automatically catalogued and updated online.

Or you could make a more efficient program (not that I'm making it in my free time either or anything, I guess) But yes, this idea sounds nice, although too vague for me to contribute much.

[Nathaniel]

Also, many counting-type problems are prime for this type of thing. Take counting still lifes, for example. I've left scripts running for days on my computer to catalogue still lifes in various rules. It'd be great to have multiple computers for this type of thing, and have the results automatically catalogued and updated online.

Or you could make a more efficient program (not that I'm making it in my free time either or anything, I guess) But yes, this idea sounds nice, although too vague for me to contribute much.

Yeah, I'm vaguely-kinda-maybe hoping to implement your algorithm as the "online" one. We'll see how my free time ends up getting divided though

[PM 2Ring]

The Oscar script isn't very complicated. I think it can be made recursive without too much difficulty. My idea is that when parts of the pattern are sufficiently disconnected, they get their own bounding box & the program then analyzes that portion to see if it repeats. Of course, these sub-patterns may re-connect with further growth, which complicates things a bit. I'll look at it over the next few days & see what I can come up with.

To force the Python interpreter to create a .pyc file, you simply have to import the module. From memory, I don't think using a .pyc is adequate as a strong security measure, but I admit I know nothing about Python bytecode.

[Nathaniel]

I should probably mention that the proof-of-concept might be a bit further off than I expected due to some unexpectedness with Golly. In particular, two things have come up:

1. The golly.randfill() Python function doesn't seem to use a different seed each time Golly loads, and I can't seem to find a way to enforce a new one. Thus, every time you open Golly and run the script, you get the same "random" pattern sequence. Joy.

2. The Golly temp file fills up after 65536 patterns have been created. It sounds like a lot at first, but my computer goes through that many in just over an hour or so, and then the temp file fills up, causing the script to crash.

If anyone knows of a workaround for either or both of those problems, I'd be very appreciative. If not, I suppose I could always e-mail Andrew to what he thinks the odds of a fix getting implemented for Golly 2.1 are (if these indeed are bugs and not me missing something).

[PM 2Ring]

1. The golly.randfill() Python function doesn't seem to use a different seed each time Golly loads, and I can't seem to find a way to enforce a new one. Thus, every time you open Golly and run the script, you get the same "random" pattern sequence. Joy.

2. The Golly temp file fills up after 65536 patterns have been created. It sounds like a lot at first, but my computer goes through that many in just over an hour or so, and then the temp file fills up, causing the script to crash.

Point 1 is easy to fix: just use Python's random number generator, rather than Golly's. Python's random module let's you use a custom RNG if you want to, but the default Mersenne Twister is pretty good & has a huge period.

Point 2 is a bit of a worry. A workaround would be to stop the search before the overflow point, and then quit & restart Golly. I think I can automate this smoothly, at least on Linux (I don't know much about Windows), but I'll get back to you after I've had some sleep .

[Andrew]

1. The golly.randfill() Python function doesn't seem to use a different seed each time Golly loads, and I can't seem to find a way to enforce a new one. Thus, every time you open Golly and run the script, you get the same "random" pattern sequence. Joy.

Yoiks! I'm amazed nobody has reported this bug until now. Turns out I wasn't calling srand() to initialize the seed for later rand() calls. Actually, I never realized I had to call srand(). I've only been using C/C++ for the last 4 or 5 years, so there is still a lot of stuff I don't know! Sorry about the bug -- I hope it hasn't caused others too much grief. I've fixed it in the 2.1 code and hope to do a beta release next week some time. If anybody here wants to help test it they should join the golly-test mailing list:

http://lists.sourceforge.net/lists/listinfo/golly-test

2. The Golly temp file fills up after 65536 patterns have been created. It sounds like a lot at first, but my computer goes through that many in just over an hour or so, and then the temp file fills up, causing the script to crash.

Not sure what you mean by "Golly temp file fills up". Can you provide more details? If it's something I can fix I'll definitely do so for the 2.1 release.

[Nathaniel]

Not sure what you mean by "Golly temp file fills up". Can you provide more details?

Sure thing. I ran my script again this morning, and this is what happened:

- Everything goes peachy for 45 mins or so
- After approximately 32,000 methuselah candidates were generated (I don't know the exact number, it only prints out results every 10,000 methuselahs), I get the following error:

Golly error

error.png (20.04 KiB) Viewed 22644 times

- I look in my Golly Temp folder, and I see this:

Temp folder

err2.png (109.01 KiB) Viewed 22643 times

[Andrew]

Nathaniel, please email that script to me and I'll try to fix the problem soon.

[Nathaniel]

Just an update that the script now is working like a charm thanks to Andrew. However, I'm on planes and various things like that over the next week or so, so the online demo script won't be available for a little bit yet.

[PM 2Ring]

The Oscar script isn't very complicated. I think it can be made recursive without too much difficulty. My idea is that when parts of the pattern are sufficiently disconnected, they get their own bounding box & the program then analyzes that portion to see if it repeats.

After some thought, I don't think that I can do this very efficiently in Python. But I have another plan of attack. We want to find oscillators arising in random soups, but Oscar gets confused by spaceships (unless the whole pattens is a spaceship). But the set of naturally-occuring spaceships is quite small, and they are only a problem if they head off to infinity. So my new plan is to just track the bounding box & if it's expanding in a suspicious way, search the boundary of the bounding box for natural spaceships & if any are found heading off into the wild blue yonder, kill them.

[Nathaniel]

OK guys, the proof of concept is now online and functional. See this page:

http://www.conwaylife.com/soup/

Download the .zip file that is linked to from there, extract it in your Golly Python script folder, and let it run! It searches for long-lived random 20x20 patterns and uploads any that will make the Top 50 list to the internet. After results are verified by hand, they get a green checkmark next to them (go to the link above to see what I mean). Until they are verified, their lifespan is an estimate.

Let me know if you have any problems running the script. Also let me know if you find a way to hack/cheat it (eg. manually uploads results, upload fake data, etc). I think it's pretty hack-proof, but I could well be wrong, and this is a test run for a reason.

Also, the script should also work fine for other Life-like rules, though there is not yet a place to view the results. Feel free to do some searching in other rules though, and the results will be saved in the online database for the time when other Top 50 tables are available to be viewed.

Edit: And Elithrion gets the prize for being the first other person to get on the scoreboard

[Elithrion]

Yes, my lurking ways pay off (although it took me an embarrassingly long time to find the python dll for Golly [you can also tell that I'm probably the least enthusiastic life enthusiast here >.>])! What would be a notable lifespan for a pattern this size, anyway? Over 30k generations, perhaps?

[Nathaniel]

What would be a notable lifespan for a pattern this size, anyway? Over 100k generations, perhaps?

As far as I know, none of this size has been found to surpass Lidka at 29055 generations (Okrasinski himself found Lidka by searching 20x20 random patterns, and presumably cleaned it up slightly).

Edit: Wily Elith, thinking you could edit your post without me noticing

[Lewis]

I keep getting this error:

error.PNG (9.34 KiB) Viewed 22555 times

[Elithrion]

Yes, I looked at the long-lived list and noticed that I was being silly with the number of generations. Although I figured these patterns are liable to have lots more cells than the classical methuselahs, so I thought I could high-ball it, but I suppose the bounding box is also highly relevant. Also, I notice that some previously verified >12k generations patterns have vanished off the list - de-verified, are they? So, does the search yield many false positives? And on a slightly related note, how about a link from the results page to the conwaylife.com/?p=longsoupX page, for X=1,...,50, and the pages displaying the pattern? That way some manual pattern-gazing can be facilitated (although I hear I could just paste the RLE into Golly, but Golly's busy and stuff).

[edit:] a "number of soups searched" scorecard would also be amusing and interesting, since I really have no idea how quickly it's running right now (except that I'm fairly confident it's not updating the Golly view after every search). *goes off requesting random features*