### 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:

- Any live cell with two or three live neighbours survives.
- Any dead cell with three live neighbours becomes a live cell.
- 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**

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.

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.

## Comments

## Post a Comment