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.