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]

Today I’m “officially” announcing the Online Life-Like CA Soup Search, though some of the folks over at the ConwayLife.com forums have been helping me test it out for a couple of weeks now.

As I mentioned in this post, one way to learn about the general behaviour of Conway’s Game of Life (or any other Life-like cellular automaton) is to generate random patterns and see what stable patterns they typically evolve into (if any). If you’ve played around with Conway’s Game of Life, then you more than likely are very familiar with blocks, blinkers, beehives, loaves, and maybe even pulsars, simply as a result of drawing random gibberish on the grid and letting it evolve. This is exactly the idea behind the Online Life-Like CA Soup Search, just on a larger scale — what if we had lots of people’s computers drawing random gibberish on Life grids, letting them evolve, and storing the resulting patterns in a communal database?

This method of collecting patterns in Life is known as a census, and to my knowledge it has been carried out on a relatively large scale twice in the past; once by Achim Flammenkamp (results here), and once by Andrej Okrasinski (results linked in the first paragraph here). As we would expect, the block is by far the most common still life, and the blinker is by far the most common oscillator. If we scroll down a bit, we see that the pulsar is the fourth most common oscillator (which is reasonably surprising, given its size). Scrolling much past that, we get into the interesting stuff — objects that no reasonable person has ever seen from drawing random stuff and seeing what it evolves into, simply because they occur so infrequently.

So why bother doing another census if two rather large-scale censuses (censi?) have already been carried out? My reasons are threefold:

1. There has never (to my knowledge) been a census of any other Life-like cellular automata conducted. The Online Life-Like CA Soup Search is completely general in that it can conduct a census of any Life-like rule (assuming that rule is stable, of course). Censuses have already been started for five other rules, including 2×2, Day & Night, HighLife, and Move. Because some of these other rules have been studied relatively little, this is an easy way of discovering new yet fundamental patterns in them. For example, it didn’t take long for the soup search script to uncover a c/8 line puffer in the 2×2 (B36/S125) rule; the very first known pattern that exhibits infinite growth in 2×2!
   

   Line puffer in 2x2

2. Previous soup searches were limited in that they only looked for very specific types of objects — usually still lifes and oscillators (though Achim Flammenkamp did a search for spaceships and puffers that can be viewed here). The Online Life-Like CA Soup Search searches for still lifes, oscillators, spaceships and puffers all at once, and even gets pseudo objects (such as the bi-block) as well.
3. Multiple users can run the script and contribute to the results simultaneously. Rather than just having one person run a script that they themself wrote, the Online Life-Like CA Soup Search works by having users download a script and that script uploads results to the central database. This obviously provides a huge speed-up, and allows the census to continuously improve and expand.

So what are you waiting for? Visit the Online Life-Like CA Soup Search, download the script, and put your computer’s CPU cycles to good use!

Census results 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:

1. 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%.
2. 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]

No. No it does not.

Update [June 14, 2011]: Entering “Conway’s Game of Life” into Wolfram Alpha now does provide you with information about the game. I suppose that means that it officially lives up to the hype.

In Conway’s Game of Life, a lake is a pattern that is a simple closed loop made up of diagonally-adjacent dominoes. It is a fact that lakes are always still lifes and that their number of cells is always a multiple of eight, but no one seems to have calculated the number of distinct (ie. not the same under rotation or reflection) lakes that exist on 8n cells; possibly because it’s not a particularly interesting problem (blasphemy!) or possibly because it’s a rather difficult problem (or most likely a combination of the two).

Indeed, computing an explicit formula for the number of lakes on 8n cells seems to be nigh intractable (although some people disagree). In place of an explicit formula I have simply gone the computer science route and coded a little C program to do the counting. The program’s running time is somewhere in the area of O(4ⁿ) since it basically brute-forces the solution by noting that lakes are in 1-1 correspondence with walks on a 2D lattice that have three properties: 1) they turn 90 degrees after each step of length one, 2) they eventually return to the starting position, and 3) they never cross a grid point that they’d previously visited (except on the last step when they return to the start).

The sequence (as far as I have computed it) of the number of lakes on 8n cells for n = 1, 2, 3, … is 1, 0, 1, 1, 4, 7, 31, 98, 446, 1894, 9049, 43151 … (Sloane’s A156228). The C source code is provided below in case you’re interested.

Download:

• C source code (zip file): numLakes.zip (1.48kB)
• C source code (plaintext): numLakes.txt

The two smallest lakes, pond and lake 2:

Sometime around the start of December I was reminded of Conway’s Game of Life – a mathematical “game” that I was first introduced to in my grade 12 programming class. Unfortunately for me and my research, I found the game much more interesting this time around and have proceeded to spend almost the entire last month dedicated to it.

It started out innocently enough; I thought that a webpage that uses the canvas tag to run the Game of Life would be the perfect way to hammer home what I was talking about in this post. It turns out that the game gets quite computationally intensive for even moderately-sized patterns however, so although the tool was functional, it chugged. What would be the solution to this problem? Write the tool in a pre-compiled programming language like Java, of course.

There are several Java implementations of the game freely available on the internet, but at this point I wanted to make an online tool that does a bit more than just evolve patterns; I wanted also to be able to upload, save, and download pattern files from the tool, something that is quite impossible from a Java applet. Also, because building interfaces for Java applets is a bit of a chore, most of the pre-existing Java applets implementing the game are a bit hard to look at. All of these problems can be solved via a bit of server-side ASP and some Java-to-javascript communication, fortunately (something I will post about separately later).

The end result? Well, I don’t really know yet, but here’s the beta 0.2.0 result:

The Java applet that runs the game itself is based on Alan Hensel’s brilliantly fast Java staggerstep algorithm, with some added file manipulation functionality and a dynamic online database of patterns. The applet is still very much a work in progress and there are quite a few known bugs, but it works well enough for now.

The real star of the website for now is the LifeWiki, which I’m hoping will fill a huge gap on the internet that I was rather shocked to find – even though there are many great homepages with bits and pieces of information about the game scattered across the internet, there really is no central resource that catalogues everything about the game; LifeWiki will hopefully fill that gap. I have started it off with some 150 articles and uploaded as many images, but I’m hoping that I can draw a few other Life enthusiasts to the wiki to help expand it so as to ease some of the burden.

Anyway, that’s about all I have to say for now about the website; I’ll likely make another post or two in the reasonably near future with coding tips/tricks based on my experience making the tool and site in general. Until then, I present to you my favourite pattern for the Game of Life, the Canada goose:

PS. Happy birthday to me!