Game Of Life

According to Wikipedia, “The Game of Life [GoL], also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolu- tion is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.” The rules of this iconic game, which is ‘played’ on a 2-dimensional grid (or board) of square cells, are quite simple. Each cell can be either dead or alive, indicated as (e.g.) black and white, respectively. Given the conﬁguration of cells on the board (the pattern or current generation), the next generation is determined by applying the following transition rule to each cell:

An alive cell with two or three alive neighbors stays alive, simulating survival.
All other alive cells die, simulating under— and overpopulation.
A dead cell with three alive neighbors becomes alive, simulating reproduction.
All other dead cells stay dead.

The attractiveness of GoL stems from the complexity that can arise from applying these simple rules to a 2-dimensional pattern of 2-state cells. Patterns range from the simple 3X3-cell glider that has 5 alive and 3 dead cells and moves in a straight line by iterating through 4 states, to the 1714x1647-cell Turing machine. GoL is indeed "Turing complete and can simulate a universal constructor or any other Turing machine."

Despite their simplicity, cellular automata can exhibit such complex behavior that it led British computer scientist physicist, and businessman Stephen Wolfram to posit computation as an organizing principle of science (cf. his 2002 book A New Kind of Science) and to later even use cellular automata as the basis for a fundamental theory of physics (cf. his 2020 book A Project to Find the Fundamental Theory of Physics or the associated project site).

Many online and ofﬂine GoL implementations exist. Perhaps the quintessential one is Golly, which actually goes well beyond GoL in that it supports cellular automata with up to 256 states, multiple colors, different transition rules, and a variety of algorithms for implementing these rules. My motivation for writing yet another GoL app was not competing with or improving on existing ones — how could I ever presume to beat Golly’s Hashlife algorithm that computes 6,366,548,773,467,669,985,195,496,000 generations of a Turing machine in less than 30 seconds on an Intel Core Duo 2GHZ CPU? My motivation was twofold:

Explore how fast GoL can be when implemented in Visual C# in a straightforward manner, i.e., without the use of advanced algorithms. I started from an open source implementation written by Jon Skeet in 2008 to explore parallelism in C#. Speeding this up by decoupling board iterations from the user interface and using pointers in a few key places made the app fast enough for my next purpose:
Entertainment. While coding up the app was entertainment in and of itself, I wanted an ‘auto-play’ mode in which patterns randomly selected from a library are played back-to-back, so I can see ‘Game Of Life’ as art on the wall. The app has to run on an Intel® Compute Stick STK2m3W64CC that drives the screen, with pattern iteration visibly attractive, i.e., not extremely fast but also not exceedingly slow. The result is that the ‘c5linestretcher’ pattern depicted below evolves at up to 560 iterations per second (ips) with one pixel per cell on a 1900x1025 board. Likewise, a random 500x500-pixel pattern evolves at up to 170 ips. For comparison, these patterns evolve at up to 2,430 ips and up to 620 ips, respectively, on a 1500x950 board on my development machine (a Microsoft Surface Book 2).

As a final remark, while it is captivating to watch patterns evolve, I also ﬁnd it quite intriguing to follow the evolution of a screen full of random cells. While the ones I observed eventually all reached a steady state, a single remaining glider can ignite a big region of activity. Fascinating.

Screenshot