Speeding up life

 Exploring ideas for speeding up the computation of Conway's game of life.

Conway's game of life is a zero player game devised by the late John Conway in 1970. It is the first widely publicised example of the emergence of lifelike "creatures" from simple laws. The game is played on an infinite grid, where each cell of the grid can either be alive or dead. The following rules then define how the game is played going forward:

1. Any live cell with two or three live neighbours survives.
2. Any dead cell with three live neighbours becomes a live cell.
3. All other live cells die in the next generation. Similarly, all other dead cells stay dead.

Following these simple laws and given some live cells to start, strange patterns emerge. Creatures seem to crawl across the grid, other objects oscillate in peculiar ways. 

The natural implementation and indeed the one that is used in most implementations is a boolean array in which each element of the array represents a single square on the board. I thought, given that each square is only a single bit, that you could optimize the implementation storing each cell as one bit of a word.

I thought about if you could calculate lots of the squares at a time by manipulating the integer representation of arrays of the bits. Using 32-bit integers, in theory, means we could represent 32 squares per number. However, in the implementation I’ve come up with, we need to use some additional bits per cell so that we can add the total number of neighbours. 

For the explanation, I'm going to be using the following notation, the use of bitshifts is faster in a lot of machines because as opposed to the multiplication of two numbers, multiplying a number by a power of two, when the number is represented in binary, just requires moving the digits of the number left or right a certain number of places. Similar to multiplying or dividing by 10 in denary is easy.

At first, I thought that this sum would require 5 bits per cell to be represented but it turns out this can be compressed down to 4 so that we can fit more in and not have any spare in implementations where we can use unsigned integers.

Introducing the bit based representation

Rather than the trivial implementation of the board as a n*n boolean array, we will instead represent the board as an n*4n/w integer array.

Here we represent w/4 cells per word. Where w is the size of the word. In 32-bit integer implementation, this is 32/4 or 8. This gives each cell 4 bits of the integer to work with.

The rightmost bit indicates if the cell was alive in the last step.

The next 3 bits represent the sum of all the cells adjacent.
Because the total number of adjacent cells can sum to 8 which would require 4 bits of space, the last of the bits is first xor’ed with the 3rd bit before being added. This means if we already have more than 4 live neighbours this last cell isn’t counted. This is fine as the cell has already been overcrowded. Adding to this overcrowded nature doesn’t affect its future state and allows us to keep the number of bits down.

We then have a 3-bit “sum” of the neighbours and a bit representing if the cell was alive or dead before.

If the number of neighbours is 3 the cell will be alive.

If the number of neighbours is 2 and the cell was alive it remains alive.

Otherwise, the cell is dead.

This means we can use the following conditioning to set the future bit:

Now it took me a while to work out how to do this inside the integer.

I wasn’t sure given the 8 bit integer

A,b,c,d,e,f,g,h

How I could do either an and or an or on adjacent elements.

Then I realised that if I want to take A and AND it to B:

This will be the case for each 4 bit series. The new x will have some garbled bits in between for c and d of each 4 bit but that doesn’t really matter here. 

This allows us to implement the algorithm.

What I have tried to represent here, perhaps attempting to be too concise, is the operations which lead to the cells in the middle of 3 rows. In the following, I have shown how the x values (subscripted by j in the formula above) are arranged.

The circled squares are highlighting the bits which represent the aliveness of that cell. The other bits allowing space for the sum.

You can hopefully see that by shifting the rows 3 right, 5 left and 1 left that, each of the 8 neighbours can be aligned above the least significant sum bit (To the left of the bit representing the cells liveness).

This technique is used by most of the advanced implementations of Conway's game of life. Another technique which is much faster to run but requires a very large amount of memory is hashlife.

I started looking into this because of another optimisation that I had thought about, whereby the groups of cells are broken into blocks so that if a block remains stationary or becomes locked in oscillations, the future of that block no longer needs to be calculated until a neighbouring block has a change of state.

There are some other aspects of this which I hope to discuss in a future post such as representing the space in a way which isn't limited and plotting the position of gliders into the future.