Time until stability versus torus size

For general discussion about Conway's Game of Life.
Post Reply
User avatar
SeanBP
Posts: 33
Joined: December 2nd, 2014, 12:49 am

Time until stability versus torus size

Post by SeanBP » December 3rd, 2014, 10:40 pm

Although the field for the Game of Life is infinite in theory, many programs use a torus when running it. It is easy to see that the larger the grid size is, the longer it will take for a random fill to become stable. I wanted to see if there was a relationship to describe this, so I built a code in java that would give me a set of data points.

The code runs the Game of Life, finds when it repeats itself, and gets the number of ticks it took to get to that point. It then repeats this several times and returns the average. Here are the results for each torus size up until 100 cells^2.
S6izgot.png
S6izgot.png (25.18 KiB) Viewed 101 times
So, is there a mathematical relationship that can describe this? Well, partially. While the graph eventually evens out to the equation t=24.35s-320, the first 27 points are very odd. Each one increases, but not to any simple equation I could find (I could use equations with powers of 6+, but by then it's just connecting the dots). Knowing with 100% certainty that the first two points are (0,0) and (1,0.5) make it difficult to find a best curve fit that includes most of the data. This segment of somewhat sporadic data might not follow the trend because of certain patterns that can not form in those sizes. However, feel free to run the code yourself using a higher "accuracy" (tests per torus size) to find a pattern I could not. For the first 10, I used an accuracy of 1000000 tests per torus size, and the rest at 1000 tests per torus size.

You might also notice that the points become slightly more chaotic near the end, but this is to be expected. The larger the size, the game has a wider range of possibilities it can take. This, however, does not break from the best fit line. Because there are a similar amount of points above the best fit line as there are below it, we can still say that it follows the pattern. All that we would have to do fix the graph is to run those points at a higher accuracy.

Pattern or not, this code can predict how long it will take for a random fill inside a torus to become stable. The code (in java) can be found here: https://gist.github.com/SeanBP/fb600e7375c6209002ba

I hope you found this interesting. I would like to hear your possible explanations for these first few odd data points, and perhaps some of you can run the code on a much higher accuracy than what my computer can take.
Last edited by SeanBP on March 22nd, 2015, 3:06 pm, edited 1 time in total.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Time until stability versus torus size

Post by HartmutHolzwart » December 8th, 2014, 4:24 pm

Is there any specific reason why the mean settlement time should go linearly with grid size? Do we recognize the constant factor??

How about grids with a fixed aspect of the sides? How does the relation change then?

Hartmut

User avatar
SeanBP
Posts: 33
Joined: December 2nd, 2014, 12:49 am

Re: Time until stability versus torus size

Post by SeanBP » December 8th, 2014, 7:21 pm

HartmutHolzwart wrote:Is there any specific reason why the mean settlement time should go linearly with grid size? Do we recognize the constant factor??

How about grids with a fixed aspect of the sides? How does the relation change then?

Hartmut
I was actually surprised to find out that it was linear, I expected it to be a bit more complicated. So no, we don't know what the common factor is.

You mean if the grid is surrounded by dead cells? It will become stable quicker, but I dislike testing those kind of grids. Different patterns form around the edges, and since the perimeter increases with every grid size, these patterns will rise with the perimeter. So in addition to testing the regular rules for the game of life, we would also be testing unrelated patterns that increase in frequency with every grid size.
Last edited by SeanBP on July 1st, 2015, 11:28 am, edited 1 time in total.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Time until stability versus torus size

Post by HartmutHolzwart » December 9th, 2014, 4:36 pm

No! I was thinken of rectangular tori with fixed aspect of the sides.

I would think that teh time to settle would rather be a function of the size of the torus in terms of number of cells than in terms of side length.

So I would be very interested how the graph would change for an aspect of 1.5 : 1, i.e. 3x2, 6x4, 9x6, ...

Still linear with the same slope or a different slope?

Is the linear trend really sustainable with bigger grids? If yes, why?

Very interesting in any case!

User avatar
SeanBP
Posts: 33
Joined: December 2nd, 2014, 12:49 am

Re: Time until stability versus torus size

Post by SeanBP » December 9th, 2014, 4:44 pm

Oh, I see what you mean. I think a thinner grid would yield a quicker decay time, or a shallower slope.
Last edited by SeanBP on March 22nd, 2015, 3:08 pm, edited 1 time in total.

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Time until stability versus torus size

Post by Extrementhusiast » December 15th, 2014, 8:08 pm

That graph looks very much like a hyperbola.
I Like My Heisenburps! (and others)

User avatar
SeanBP
Posts: 33
Joined: December 2nd, 2014, 12:49 am

Re: Time until stability versus torus size

Post by SeanBP » December 19th, 2014, 9:23 pm

Extrementhusiast wrote:That graph looks very much like a hyperbola.
It does from that graph, but when you zoom in on the first few points, it's too chaotic. Maybe, I could be proven wrong.

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Time until stability versus torus size

Post by Hunting » November 11th, 2020, 8:19 am

Hello. Can you do a similar experiment for LeapLife? In July I made several statistic scripts for LeapLife. I figured that it is very similar to CGoL in several respects, for example, its optimal soup density is also 37.5%.

Post Reply