Census Program Idea

For general discussion about Conway's Game of Life.
User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 4:01 pm

Lewis wrote:I keep getting this error:
After doing some quick Google searches, it appears as though this is caused by me compiling the script with Python 2.6 and you perhaps using an older version than that? What version of Python are you using?

If this is indeed the source of the error, I'll try to compile future versions of the script in a slightly older version of Python, but until then you should probably update anyways.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 4:05 pm

Elithrion wrote: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?
Not off the list entirely, just down quite a few spots (you'll see them verified lower on the list, in the 9k generations range). Some of your really high-count ones got inflated a lot because (using one specific example here) they created a glider in the middle of the debris that managed to escape without touching anything. Because it took another couple thousand generations for the glider to get sufficiently far away from the stationary debris for the script to be able to tell that things had settled down, the number got inflated quite a bit. Hence the unfortunate need for the "Verified?" column on the table.

As for adding features like clicking on the methuselah to view it in the ConwayLife.com player - I absolutely intend to add those features (as well as many more). This is just an early draft, to find and weed out problems that arise (such as the one posted by Lewis just now).

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: Census Program Idea

Post by Lewis » June 22nd, 2009, 4:10 pm

I fixed the problem. I hadn't un-installed the older version of Python when I got the newer version. I just needed to direct Golly to the 2.6 dll file. The program seems to be working for now.

Also, Will the program ever gather statistics of pattern frequencies or just finding long-lived patterns?

EDIT: Top of the scoreboard!!!! 17,759 generations!
EDIT 2: AND the final census contains A Beehive on Table!
Last edited by Lewis on June 22nd, 2009, 4:14 pm, edited 1 time in total.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 4:13 pm

Lewis wrote:I fixed the problem. I hadn't un-installed the older version of Python when I got the newer version. I just needed to direct Golly to the 2.6 dll file. The program seems to be working for now.

Also, Will the program ever gather statistics of pattern frequencies or just finding long-lived patterns?
Well, the goal is to add that functionality to it as well (as well as user statistics and all sorts of fun things), but I unfortunately have no real idea how to implement an effective census script. If anyone has ideas, I'm all ears, as I would love to get it implemented.

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: Census Program Idea

Post by Lewis » June 22nd, 2009, 4:17 pm

I bet the methuselah 'leaderboard' will get rather competitive quite quickly!

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Census Program Idea

Post by Macbi » June 22nd, 2009, 4:23 pm

I think all the census programs worked on a torus, so that you don't get weird edge effects. If you use 2048*2048 then (because the patterns tend to take less time than 2048 gens to settle down) they won't "know" that they're on a torus. Golly can't do tori yet though, can it?

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: Census Program Idea

Post by Lewis » June 22nd, 2009, 4:28 pm

How does the program handle puffers? Would it mess up the results on here or would that soup just be discarded?

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Census Program Idea

Post by Elithrion » June 22nd, 2009, 4:29 pm

I'm not sure if it's really worthwhile to have a census script - there are already vast censuses out there, so it might be more productive to just focus on searches (particularly methodical, as opposed to random, searches, which are to me much more interesting) for particular interesting objects. If you really want a census, I imagine that the best way to go about it would be to have the program count the objects produced, and store the resulting count on the computer (in some suitably encoded form?) until the end of the session, at which point the counts would be sent to the server. Maybe?

For a search, I imagine when you run the script it would message the server asking where it should start, the server would check the list of what areas are completed in a given search, and what programs are currently running, and then suggest a starting location and "direction" of search to the script. The script would then start the search and tell the server it's still running and how far it's gotten every five minutes or something. So, let's say it's a fresh search and two instances start - one is assigned the very beginning of the search and told to search forward, the second is assigned the end and told to search backward. Let's say five minutes later another one joins - it's assigned the 1/3 point of the segment between the two searchers and told to search forward as well. The server might ask the scripts to change direction/location on the 5 minute check-ins too. Or something like that? It doesn't sound like it should be insanely complicated, I don't think >.>
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 4:37 pm

Macbi wrote:I think all the census programs worked on a torus, so that you don't get weird edge effects. If you use 2048*2048 then (because the patterns tend to take less time than 2048 gens to settle down) they won't "know" that they're on a torus. Golly can't do tori yet though, can it?
Yeah, a torus would be idea, but, as you said, I don't think Golly supports toroidal universes. The vast census on Ostrasinski's website is based on a non-toroidal universe, though (just a "for the record").
Lewis wrote:How does the program handle puffers? Would it mess up the results on here or would that soup just be discarded?
Puffers (if they ever did come up) are no problem, they just artificially inflate the lifespan until they get away from the "core".
Elithrion wrote:If you really want a census, I imagine that the best way to go about it would be to have the program count the objects produced, and store the resulting count on the computer (in some suitably encoded form?) until the end of the session, at which point the counts would be sent to the server. Maybe?
Yep, I'm not worried about the sending the server aspect of it, I think I've got that figured out now. It's how to go about doing the actual counting (like in a really realistic coded, efficient kinda way).
For a search, I imagine when you run the script it would message the server asking where it should start, the server would check the list of what areas are completed in a given search, and what programs are currently running, and then suggest a starting location and "direction" of search to the script. The script would then start the search and tell the server it's still running and how far it's gotten every five minutes or something. So, let's say it's a fresh search and two instances start - one is assigned the very beginning of the search and told to search forward, the second is assigned the end and told to search backward. Let's say five minutes later another one joins - it's assigned the 1/3 point of the segment between the two searchers and told to search forward as well. The server might ask the scripts to change direction/location on the 5 minute check-ins too. Or something like that? It doesn't sound like it should be insanely complicated, I don't think >.>
Yep, I don't think that'd be hard to do at all. The only thing is I don't really know how to code any really cool scripts like glider collision-checkers and stuff like that. If anyone knows how to code something that would make for a good internet-y script like this, I'd be happy to give it the server treatment.

Edit: Also, I'd personally like to have a census script so that we can collect censuses of other Life-like rules (I imagine that Lewis has 2x2 in mind himself).

hkoenig
Posts: 259
Joined: June 20th, 2009, 11:40 am

Re: Census Program Idea

Post by hkoenig » June 22nd, 2009, 4:42 pm

<i>I think all the census programs worked on a torus</i>

It's not that hard to write an "unbounded" Life application. (Keep lists of cells instead of an array). Also, with a torus how do you really manage to handle escaping Gliders and such? If you are going to do a real census you need to let those objects escape and count 'em.

When I did the <a href="http://pentadecathlon.com/objects/census/census.php"> object survey </a> about a decade ago, I used various sized arrays up 1024x1024 at various densities. I found that that patterns just won't go much beyond 20,000 generations. (I arbitrarily stopped and saved patterns after a certain limit, like 15,000 gens, then finished them by hand. Just in case any infinite objects, like Switch Engines, did appear). No pattern with the larger bounds doubled in a size dimension (1024 -> 2048, for example).

You still get some edge artifacts. I believe the Ship census was a bit high because initial Herschels along the array edges could run to completion and often be left alone after that. And every Clock I encountered appeared in the first generation or two.

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: Census Program Idea

Post by Lewis » June 22nd, 2009, 4:43 pm

Nathaniel wrote: Edit: Also, I'd personally like to have a census script so that we can collect censuses of other Life-like rules (I imagine that Lewis has 2x2 in mind himself).
Could the census be used in rules with different neighborhoods? I'd be quite interested in running a census of B24/S13 in the Von Neumann neighborhood.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 4:49 pm

Lewis wrote:Could the census be used in rules with different neighborhoods? I'd be quite interested in running a census of B24/S13 in the Von Neumann neighborhood.
If Golly supports it, then there's no reason for it to not work with minimal modifications to the script.

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: Census Program Idea

Post by Lewis » June 22nd, 2009, 4:58 pm

Occasionally, the program says 'The pattern could not be uploaded and has been saved to a data file' or something. (the message only shows for a second or s obefore disappearing). What does this mean?

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 5:03 pm

Lewis wrote:Occasionally, the program says 'The pattern could not be uploaded and has been saved to a data file' or something. (the message only shows for a second or s obefore disappearing). What does this mean?
It means that, for one reason or another, the script couldn't make a connection to the server. All the files that the script tries to upload are saved on your harddrive though - do a search for "methuselah" and the files should appear (in Golly's data directory), and their filenames are "methuselah_XXXXX.rle", where "XXXXX" is the lifespan of the methuselah. It's not particularly important until a really big one slips through the cracks (eg. if you find one that says "methuselah_45235.rle", you might want to verify it and claim it ;))

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Census Program Idea

Post by Macbi » June 22nd, 2009, 5:06 pm

hkoenig wrote:
I think all the census programs worked on a torus
It's not that hard to write an "unbounded" Life application. (Keep lists of cells instead of an array). Also, with a torus how do you really manage to handle escaping Gliders and such? If you are going to do a real census you need to let those objects escape and count 'em.
On a torus no ships could "escape" so you just wouldn't count any. Although I guess if you were (un)lucky you could get one just whizzing round and round the torus. In an unbounded census the amount of spaceships produced would be proportional to the perimeter (presumably), whereas the amount of still lives would be proportional to the area, which is a bit odd.
Also:
Most users ever online was 6 on 17 minutes ago
w00t

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Census Program Idea

Post by Elithrion » June 22nd, 2009, 5:18 pm

A thought that's barely related to the topic at hand occurs to me - it seems like the current search could benefit from having the script "evolve" towards an optimal probability distribution. I assume right now it's something like uniform at 0.25 probability of a filled cell, so just having it shift by +-0.01 every, say, thousand attempts and seeing if the new frequency yields more outstanding patterns could be interesting. Making it more complicated than that (having the results coordinated via server and having the shifts be finer as more results are accumulated and having the distribution being used changed sometimes, for example) would also be nice.

This would be a pretty advanced feature and certainly not necessary in a proof of concept, but it's an appropriate enough topic to suggest it in :)
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Census Program Idea

Post by Elithrion » June 22nd, 2009, 5:46 pm

Nathaniel wrote:All the files that the script tries to upload are saved on your harddrive though - do a search for "methuselah" and the files should appear (in Golly's data directory), and their filenames are "methuselah_XXXXX.rle"
Also, where is this data directory? I appear to not be in possession of one (using Golly 2.0 if that's relevant) and a search of the whole harddrive for "methuselah" yielded no appropriate files despite the fact that I seem to have received that message a few times.
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 5:49 pm

Elithrion wrote:Also, where is this data directory? I appear to not be in possession of one (using Golly 2.0 if that's relevant) and a search of the whole harddrive for "methuselah" yielded no appropriate files despite the fact that I seem to have received that message a few times.
For me it's located at C:\Users\Nathaniel\appdata\Roaming\Golly

But it seems to vary wildly between different operating systems. I'll try saving it to a path relative to the Python script itself for the next version.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Census Program Idea

Post by Elithrion » June 22nd, 2009, 5:55 pm

Ah, it exists! And contains 95 files! Also, question: I haven't had any patterns added to the list since I changed my "name" and "email" to be several hundred characters long. Is there some sort of invisible limit on that?
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 9:54 pm

Elithrion wrote:Ah, it exists! And contains 95 files! Also, question: I haven't had any patterns added to the list since I changed my "name" and "email" to be several hundred characters long. Is there some sort of invisible limit on that?
Hrm... there might be, actually. I'd change them to a reasonable limit while I test that ;)

And keep in mind that the script not only saves files that it *couldn't* send to the server, but also ones that it sent in no problem.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Census Program Idea

Post by Elithrion » June 22nd, 2009, 10:54 pm

Yeah, I figured out that it logs all files shortly after making the post, but you didn't see the edit that took place that time ;)

But, still, I don't understand why its generation count is off quite so much. Let's take your top ranking soup. It was logged at 21k generations, but verification took 4.5k off from that. At generation 16888, it's basically a mess dead centre and a number of gliders flying off in all directions, but quite a ways off from the mess already. And then apparently its death is not noticed for another 4000 generations? There should be a better-performing way >.>
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 22nd, 2009, 11:04 pm

Elithrion wrote:Yeah, I figured out that it logs all files shortly after making the post, but you didn't see the edit that took place that time ;)

But, still, I don't understand why its generation count is off quite so much. Let's take your top ranking soup. It was logged at 21k generations, but verification took 4.5k off from that. At generation 16888, it's basically a mess dead centre and a number of gliders flying off in all directions, but quite a ways off from the mess already. And then apparently its death is not noticed for another 4000 generations? There should be a better-performing way >.>
Yeah, I'll experiment with some different methods for the next version. I just wanted a "the pattern is done evolving" criterion that was fast for short-lived soup (since those are the vast majority), is general for any Life-like rule, but the trade-off is that it lags quite a bit for long-lived soup. Basically it computes the hash values within a square of side length 20 + (gencount/8), centred at (0,0) and waits for a repetition. Thus, if the pattern emits a glider anywhere near the end of its evolution, you have to wait for that glider to escape from that box before the lack of evolution is noticed. I suppose that could enforce some density condition as well to improve the check a bit, but I'd get a little nervous about other Life-like rules without thinking about it more first.

Edit: Also, the script may run forever (without noticing deadness) if you get a really high-period oscillator like the pentadecathlon. Sorry. This has been fixed for v1.01, which I'll upload when it has other more significant changes.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Census Program Idea

Post by Macbi » June 23rd, 2009, 4:51 am

I'm trying to direct Golly to newly installed python 2.6 but I keep running up against this:

Code: Select all

-bash: install_name_tool: command not found
Some quick goggleing tells me I need the developer tools for Mac, is there an easier way around this?

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: Census Program Idea

Post by DivusIulius » June 23rd, 2009, 7:17 am

But, still, I don't understand why its generation count is off quite so much. [...] There should be a better-performing way >.>
I suppose that could enforce some density condition as well to improve the check a bit, but I'd get a little nervous about other Life-like rules without thinking about it more first.
I know that WinLife32 has a neat autostop feature. The explanation at http://www.winlife32.com/tech-faq.htm could be of your interest:
How does the Autostop feature work?
The growth algorithm computes a signature for every generation, at negligible cost. This signature, which is based on the neighbor state for each live cell, is the same for any two patterns composed of the same objects (collections of contiguous cells). This means that moving objects such as gliders do not affect it. If two nearby generations have the same signature, then another cycle is grown. If the signatures match throughout the cycle, then the patterns themselves are compared (which is a much more expensive operation). Anything which is not common to the two generations is analysed to see if it is composed of known moving objects (typically gliders). If so then their trajectories are analysed to foresee possible interactions. Sometimes the only way to analyse them is to run the pattern until there is no possibility of interaction - that is why you sometimes see a pattern (particularly a random broth) grow for thousands of generations, then get a message saying it is not interesting from a much lower generation.
However, as far as I know, WinLife32 is not able to deduce when switch engines do stabilize. :wink:

User avatar
Nathaniel
Site Admin
Posts: 862
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Census Program Idea

Post by Nathaniel » June 23rd, 2009, 7:51 am

DivusIulius wrote:However, as far as I know, WinLife32 is not able to deduce when switch engines do stabilize. :wink:
Another worry I have with that is that it seems to be quite Life-specific (part of the algorithm works by checking know spaceships), while I would like to keep this as rule-independent as possible. I hadn't even really started trying to optimize it yet though in v1.00, so I'm sure we can do much better than has been done so far.

Also, I have a very rudimentary census script working in Python now, just so people are aware. Probably a week or more before it's anything I want to share/seriously try out though.

Post Reply