Longevity in Conway's Game of Life Revisited
A couple of weeks ago, I posted some intuition that suggested that, in Conway’s Game of Life, the longest-lived patterns should on average be those with density right around 37.5%. To test this hypothesis, I wrote a simple Golly Python script that generated random 20×20 patterns of varying densities and checked how long it took for them to stabilize. One noticeable problem cropped up, however: patterns with density around 90% tended to live for an extremely long time due to edge effects that caused the pattern to explode out of the original 20×20 box initially, even though they would almost entirely die off within the box.
The solution to the given problem is to emulate the Game of Life not on an infinite planar grid, but rather on a toroidal grid; that is, we fix our 20×20 universe and treat the top row as if it borders the bottom row and the left row as if it borders the right row. Running the simulation in this set-up results in data that matches our intuition more closely:
The results are based on 13592 random patterns of each density 1%, 2%, 3%, …, 99%. As with the previous graph, we notice that the lifespan plateaus in the 25% – 50% range, providing evidence that our intuition for a maximum at 37.5% is probably well-founded. Also, at the request of Elithrion in the comments on the previous post, I have included the median plot for the lifespans this time as well, though the median seems to behave pretty similarly to the average (it’s just more or less uniformly 25% smaller). As we would expect, the average lifespan in the toroidal universe set-up is much lower than the average lifespan in the infinite planar grid set-up, because expanding patterns have nowhere to go. The longest-lived pattern that was found on the torus had a lifespan of 2169 (and an initial density of 30%), whereas the longest-lived pattern that was found on the infinite plane (over significantly fewer trials, I might add) was 14042.
While I’m presenting results, how about we take a look at the final population of patterns of various starting densities?
The behaviour is almost identical to that of the average/median lifespan. The one cool thing is that, in addition to the plateau centred at ~37.5%, here we see that the median final population peaks with a value of 13 at an initial density of 38%. Nevermind the fact that this is almost certainly a statistical anomaly — it helps support my original hypothesis, and if the popular news media has taught me anything, it’s that randomly picking out things like that and claiming that they are significant is always mathematically sound.
Downloads:
- Lifespan and final population raw data [.zip of an Excel spreadsheet — 2.99MB]
- Torus lifespan script [.zip of a Golly Python script]
Speaking of statistical anomalies, I’ve noticed that in the raw data you supply, when a 99% density trial has a life span of 2, the 98% trial with the same trial number also does. I haven’t had a chance to look at the script, but it happens far to consistently to be chance.
@Macbi – You’re quite right — there was a bug in the script! I have updated the script so that it is bug-free now, but here’s what the problem was:
The script checks for stability by storing hashes of each generation and checks for hash collisions. When a hash collision is found, it marks the pattern as stable and records the generation number of the generation that it collided with. Unfortunately, the script was not properly clearing out the hash list after each new pattern was generated (this is what is fixed now). Thus, if a pattern ever stabilized with an empty field in generation 2 at 98%, that generation 2 would also get marked down for 99%, even though it almost surely stabilized at generation 1.
The good news is that this problem would only ever come up if two consecutive patterns stabilized to the exact same pattern, which almost always would be the empty field, meaning the middle densities (i.e., the interesting ones) were unaffected by the bug. I ran the bug-free script for 1000 trials just to make sure that the resulting graphs look pretty much the same as the ones included with this post, and they do.
Good catch!