The Game of Life vs. Convolutions

Conway’s Game of Life is a self-contained simulation game that evolves “living” cells over multiple generations according to four easy rules.

Game of Life in RGB

While the game is trivially implemented by sequentially evaluating the rules for every cell on the board, a rather beautiful highly parallelizable solution exists that uses 3×3 kernel convolutions and some clever observations. In the following, we will explore that algorithm and see a GPU-accelerated implementation of it in Rust using the ArrayFire library. At its core, it will look like this:

Recap: The rules to the game.

The game state is evolved over multiple generations. Each cell has two distinct states: Alive (1) or dead (0). A cell also has a 3×3 Moore neighborhood of eight neighbors from the top left (north-west) to the bottom right (south-east).

A cell’s 8-connected Moore neighborhood.

Starting from a randomly initialized board, a single evolution is performed by applying these steps:

1. Any living cell with fewer than two neighbors dies out due to underpopulation.
2. Any living cell with two or three living neighbors lives on to the next generation due to its stable environment.
3. Any living cell with more than three live neighbors dies due to overpopulation.
4. Any dead cell with exactly three living neighbors becomes alive due to reproduction.

Rules of Conway’s Game of Life, taken from here.

In repeatedly applying these steps, the game may either converge to a steady state, cycle between two states or continue to change infinitely.

Simplifying the rules

After transferring the rules to pseudo-code, it looks somewhat like this:

From here, we can make some observations:

1. If a cell has less than two neighbors, the result will always be 0 regardless of the cell’s current value; this is due to the Under-population rule.
2. If the cell has exactly three neighbors, the result will always be 1 regardless of the cell’s current value; this is due to both the Stable Environment and Reproduction rules.
3. We do need to check for exactly two neighbors to ensure a cell keeps surviving (1) according to the Stable Environment rule: Note that with exactly two neighbors no new cell is born, so the outcome depends on the cell’s current state.
4. More than three neighbors always cause a cell to be 0 regardless of the cell’s current value; this is due to the Overpopulation rule.

This allows us to ignore a couple of tests for the cell’s previous value; in pseudo code:

When we ignore the cell’s current value for a moment, we can see the following pattern:

Upon closer inspection however, we see that both lines are simply the negation of each other:

As a consequence of that, only the Stable Environment and Overcrowding rules are required to determine the entire state progression. The missing piece being, of course, the current state of the cell:

• As we know from observation 2 and the Overpopulation rule, a cell will always exist if there are exactly three neighbors. We’ll call this the must_exist condition; it is additive (i.e. we “add life” to a cell).
• From observation 3 and the Stable Environment rule, a cell only continues to exist if it existed before. We’ll call this the can_exist condition; it is multiplicative (i.e. we “zero out” dead cells).

Mathematically, we can now express the resulting state as simply a multiplication and addition:

How do we get the number of neighbors of the cell? This is where a 2D convolution enters the stage: Convolving the board with the 8-neighborhood kernel shown below simply sums up all living cells (valued 1) around the center, which itself is ignored.

An 8-neighborhood kernel.

The result of that operation is therefore a direct measurement of the neighborhood size. All we need to do then is to compare that value against our thresholds of two and three as established above — and that’s it. If you want a nice refresher on how convolutions work particularly in image processing, head over to to the excellent post Image Kernels explained visually.

Putting it together in Rust and ArrayFire

As just explained, we want to determine the neighborhood size using a 2-dimensional convolution with the neighborhood kernel via convolve2. To specify our kernel in ArrayFire we use a 3×3×1×1 dimensionality, which reads approximately as height, width, number of channels and a “batch” dimension we can safely ignore here. When used against a multi-channel input such as an RGB image, this format will process each color channel independently of the others, as shown in the image in this post’s header.

Due to GPU requirements we cannot operate on a binary image directly and instead use a 32-bit floating point array. As a consequence, the addition used by our update will eventually send the cell values outside their allowed range. To mitigate that, we introduce the method clamp_range that limits the value range to the range 0..1 using ArrayFire’s clamp function:

Finally, we update the state using the method you already know by comparing counts exactly using ArrayFire’s eq function:

With that, Conway’s Game of Life runs on your GPU.

An Artist’s impression of Conway thinking about GPU acceleration of cellular automata.

As usual, you can find the entire code on GitHub.

GitHub - sunsided/rust-arrayfire-experiments: Toying around with ArrayFire in Rust

Take care, stay safe and have fun!