Yet Another Game Of Life

The famous Game of Life, devised by mathematician John Conway about four decades ago, is the best-known example of a cellular automaton. It has probably been coded up in every possible computer language about a million times by now, as evidenced by this plethora of examples. I was introduced to the rules of the game already 15 years ago during my first year in college, and became immediately fascinated by the complexity and beauty of some of the emerging patterns. At that time I implemented it in C, and soon forgot about it. This is already a very good reason to revisit the game, its rules, and to show animations produced with matplotlib in python. Let’s go!

Rules of Conway’s game of life

As per Wikipedia, the universe of the Game of Life is an infinite two-dimensional grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Yet another python implementation of Life

Our python implementation will use a two-dimensional numpy array to store the grid representing the universe, with values 1 for live and 0 for dead cells. We will code a init function for the initialization of the grid and a evolve routine for the evolution of the universe. A very simple way of initializing the grid to random values, allowing for variable grid dimensions, is as follows: 

def init_universe(rows, cols):
    grid = np.zeros([rows, cols])
    for i in range(rows):
        for j in range(cols):
            grid[i][j] = round(random.random())
    return grid

random_universe
An example of a random universe created with the init_universe(rows, cols) function with 600 cells distributed in 20 rows and 30 columns can be seen in the figure on the right. The call to generate the figure, with black cells representing live (or 1) states, is as follows:

grid = init_universe(20,30)
ax = plt.axes()
ax.matshow(grid,cmap=cm.binary)
ax.set_axis_off()

Now, for the evolution logic, let us code a function that takes a universe as input, together with the parameters that regulate its evolution, and outputs the new universe after one iteration. The classical rules of the game of life set the parameters for overcrowding, under-population and reproduction as 3, 2, 3, respectively. In our implementation, we create a padding around the original universe, which allows us to define the neighbors in an easy way without having to worry whether a particular cell is at the border or not. At every position i,j we compute the sum of all cells in positions [i-1, i, i+1] \times [j-1, j, j+1] and then we subtract the center point at i,j. Then we apply the evolution logic: cells die when underpopulated or overcrowded, and new cells are born when the reproduction condition (3 alive neighbors) is fulfilled:

def evolve(grid, pars):
    overcrowd, underpop, reproduction = pars
    rows, cols = grid.shape
    newgrid = np.zeros([rows, cols])
    neighbors = np.zeros([rows,cols])
    # Auxiliary padded grid
    padboard = np.zeros([rows+2, cols+2])
    padboard[:-2,:-2] = grid
    # Compute neighbours and newgrid
    for i in range(rows):
        for j in range(cols):
            neighbors[i][j] += sum([padboard[a][b] for a in [i-1, i, i+1] \
                                    for b in [j-1, j, j+1]])
            neighbors[i][j] -= padboard[i][j]
            # Evolution logic
            newgrid[i][j] = grid[i][j]
            if grid[i][j] and \
               (neighbors[i][j] > overcrowd or neighbors[i][j] < underpop):
                newgrid[i][j] = 0
            elif not grid[i][j] and neighbors[i][j] == reproduction:
                newgrid[i][j] = 1
    return newgrid

Note that in the above code we make use of a wonderful property of arrays in python, namely that the last element of an array arr can be referenced either as arr[len(arr)-1] or as arr[-1]. Thus, we create a padboard with 2 columns and 2 rows more than the dimensions of the grid. If n is the number of rows of the grid, the padboard has n+2 rows, which range from 0 to n+1, or, equivalently, from -1 to n!

Visualization of Life and creation of mp4 videos with matplotlib

For the visualization of the evolution of our random universe we could create a series of png plots and stitch them together to produce an animated gif. However, matplotlib also offers the possibility of generating animations and saving them directly in mp4 format. The code that follows is based on this very useful tutorial, which contains instructions to embed matplotlib animations directly in the ipython notebook.

pars = 3, 2, 3
rows, cols = 20, 20
fig = plt.figure()
ax = plt.axes()
im = ax.matshow(init_universe(rows,cols),cmap=cm.binary)
ax.set_axis_off()

def init():
    im.set_data(init_universe(rows, cols))

def animate(i):
    a = im.get_array()
    a = evolve(a, pars)
    im.set_array(a)
    return [im]

In the code above, we have set the parameters for the evolution as described by the original logic of the game, and we initialize a matplotlib figure using the matshow directive. We also need the functions init and animate; the latter updates the content of the plot with evolved iterations of the universe. The matplotlib call to produce an animation and save it in mp4 format is then simply:

anim = animation.FuncAnimation(fig, animate, init_func=init, frames=100, blit=True)

anim.save('animation_random.mp4', fps=10) # fps = FramesPerSecond

A random initialization gives rise to the following animation, which ends in a configuration with 3 stable patterns (block, blinker and a diamond-shaped structure that settles to a blinker in 8 steps) after approximately 50 iterations.

While a random initialization often gives rise to interesting universes, there is a vast body of research devoted to classifying particular configurations that are known to evolve in a specific fashion (oscillators, stable figures, moving patterns…). A quick google search illustrates this point and leads to many resources for the interested reader. For starters, let us code up the initialization function of a “pulsar”, a type of oscillator with a 3-iteration period. 

def init_universe_pulsar():
    grid = zeros([15, 15])
    line = zeros(15)
    line[3:6] = 1
    line[9:12] = 1
    for ind in [1,6,8,13]:
        grid[ind] = line
        grid[:,ind] = line
    return grid

To generate and save this universe, we need to modify the function init used to produce the matplotlib animation and replace the call to init_universe(rows, cols) with init_universe_pulsar(). The resulting evolution can be seen in the following video:

An interesting kind of universes are those that resemble spacecrafts. There are many of them, as a visit to this page shows. Other configurations resemble guns that emit gliders forever. By far the most famous one is the Cosper glider gun, which can be generated using the following initialization function:

def init_universe_glider_gun():
    glider_gun = 38*'0' + 25*'0'+'1'+12*'0' + 23*'0'+'101'+12*'0' +\
             13*'0'+'11'+6*'0'+'11'+12*'0'+'11'+'0' +\
             12*'0'+'1'+3*'0'+'1'+4*'0'+'11'+12*'0'+'11'+'0' +\
             '0'+'11'+8*'0'+'1'+5*'0'+'100011'+15*'0' +\
             '0'+'11'+8*'0'+'1'+'000'+'1011'+4*'0'+'101'+12*'0' +\
             11*'0'+'1000001'+7*'0'+'1'+12*'0' +\
             12*'0'+'10001'+21*'0' + 13*'0'+'11'+23*'0' + 38*'0' +\
             19*38*'0'
    grid = np.array([float(g) for g in glider_gun]).reshape(30,38)
    return grid

Once started, this glider gun evolves emitting gliders indefinitely, which move across the grid at -45 degrees and exit the universe bounding box through the bottom right corner. Bill Gosper discovered this first glider gun, which is so far the smallest one ever found, in 1970 and got 50 dollars from Conway for that. The discovery of the glider gun eventually led to the proof that Conway’s Game of Life could function as a Turing machine. A video of the Gosper glider gun in action can be seen below.

Here is a very nice visualization of yet another type of configuration in Life, the so-called “puffers”, patterns that move like a spaceship but leave debris behind as they evolve.

Table-top data experiment take-away message

Conway’s game of life is a zero-player game, with evolution completely determined by its initial state, consisting on live and dead cells on a two-dimensional grid. The state of each cell varies with each iteration according to the number of populated neighbors in the adjacent cells. The game, devised in 1970, opened up a whole new area of mathematical research, the field of cellular automata, and belongs to a growing class of what are called “simulation games”. Implementing the evolution algorithm behind the game in any programming language is a classical exercise in many CS schools, is always a lot of fun, and allows to explore the huge variety of configurations that give rise to strangely addictive evolution patterns.

Post a comment