Longest-Lived Soup Density in Conway's Game of Life
In Conway’s Game of Life, a simple way to learn about the general dynamics of the game are to study what happens to soup – patterns made up of a random assortment of ON and OFF cells. Two particularly interesting questions that we can ask are “What types of stable patterns arise most frequently from soup?” and “How long does soup generally last before stabilizing?” I will focus on the latter question for today’s post, as the former has become the bud of a more ambitious project that I will announce in the near future.
The question of how long soup generally lasts before stabilizing is quite vague, because there are two important considerations that we have not specified:
- How dense should the soup be? Clearly soup with ON density of 5% will survive only a fraction as long as soup with ON density of 50%.
- How large of a region of soup should we let evolve? Smaller regions will stabilize much more quickly than large regions, and infinite regions will likely never stabilize(?), not to mention we can’t effectively simulate an infinite field of random cells.
For #2, I will choose the region to be of size 20×20. This decision is pretty arbitrary, but part of the reason I chose such a small size is as a desire to make this script kill two birds with one stone; any particularly long-lived patterns of this size that are discovered can likely be considered methuselahs, while larger patterns can not.
For #1, we might naively expect that patterns will live longest if they have density 37.5%, since cells are born if and only if they have exactly three ON neighbours (out of a possible eight = 37.5%). To test this theory, I created a Golly script that creates regions of varying density and checks how long it takes for them to stabilize. The following graph shows the average lifespan of 20×20 patterns with densities ranging from 1% to 99%, based on 5000 generated patterns for each percentage point.
Indeed, it looks like the longest-lived density estimate of 37.5% isn’t too far off. The true maximum in this set-up might actually be slightly higher, but that is most likely caused by the same thing that is causing the hump centered at 90%: edge effects. Roughly speaking, because we are simulating a finite region of soup on an infinite grid (as opposed to on a toroidal universe), patterns of higher density will tend to expand out very quickly in their first few generations, giving them longer lifespans in general than they would have on a toroidal universe. Alas, Golly doesn’t support toroidal universes, so the toroidal lifespan results will have to wait for another day.
Update [July 8, 2009]: I have attached to the end of this post the Python script used to generate these results.
Update [July 11, 2009]: See this post, which deals with the “more ambitious project” that I mentioned.
Update [July 19, 2009]: See this post, which deals with soup longevity on a torus.
Downloads:
- Methuselah 14042 – A methuselah with lifespan 14042 found during the search [.zip of an RLE file]
- Methuselah Search Script [.zip of a Golly Python script]
- Soup Density Data [Excel spreadsheet — 26.0kB]
Ah, you sort of took my request! Although I think more extensive data would be nice – median density seems like it might be a bit more representative than average, and maximum density would be nice to have for the actual search (although that might need checks for outliers). Of course, it’s not unlikely that the graphs for those would just mirror the average one, but then again there’s a decent chance they would not (in particular, I expect that they would differ with regards to the 90% hump at least), and that would be interesting too.
Actually, (apologies for the double-post) could you send me the source for this? I’m curious to tweak it a little – I want to see if I can make it vary probabilities cell-by-cell and either come up with a more efficient generation mechanism this way (I imagine that having a few clumps separated by some white space will yield higher maximums than a uniform distribution, for example), or see if I can tweak it to evolve towards methuselahs (by having it continuously adjust the probabilities towards whatever gets the best results). Admittedly the latter option is unlikely due to high sensitivity of the generations to the exact starting conditions, but it would be awesome if it worked (and the former option could work if it doesn’t) 😀
@Elithrion – Haha yeah, I actually had already written the script and started the computations when you made the suggestion. Great minds think alike, I guess 😉
You make a good point about the median vs. mean thing – I’ll definitely create median data if/when I post the results of the toroidal version of this script.
And I completely meant to attach the source code to this post (as I try to do with all my coding posts), but I forgot and it unfortunately is sitting on a harddrive halfway around the world right now. I’ll update the post to include the source code in two weeks time 😉
Also, just as an FYI in case you’re curious – I tried something semi-similar to what you described about trying to create methuselahs based on observing past long-lived patterns and evolving the density used. Instead I tried things like taking the top half of one methuselah (possibly modified by one or two cells) and the bottom half of another methuselah (also possibly mutated a bit) and checked whether that was long-lived. It was basically a standard cross-breed and mutate genetic algorithm, but unfortunately it yielded results that were no better than a uniformly random search, due to the high volatility of methuselahs. Silly Life.
Hey 🙂 just saw this post off Google. Is it true that infinite sized Game of Life grids never equilibriate? I’ve never seen a theorem to that effect. Is it known?
@Julian – There certainly infinite-sized GoL grids that stabilize – just put an infinite number of still lifes at various positions in the plane. If you mean whether or not a random infinite GoL grid never stabilizes with high probability, then the answer is not 100% clear to me. I would naively expect that almost all infinite grids never stabilize, but I also don’t know of a theorem to that effect.
You could do a simple sketch proof I suppose by noting that almost all random infinite grids will contain (your favourite methuselah with lifespan x) somewhere, so the whole thing must have lifespan at least x. Since x was arbitrary, the total lifespan is larger than any finite number.