Conway's Game Of Life

In 1970 the British Mathematician John Conway created his "Game of Life" -- a set of rules that mimics the chaotic yet patterned growth of a colony of biological organisms. The "game" takes place on a two-dimensional grid consisting of "living" and "dead" cells, and the rules to step from generation to generation are simple:

  • Overpopulation: if a living cell is surrounded by more than three living cells, it dies.
  • Stasis: if a living cell is surrounded by two or three living cells, it survives.
  • Underpopulation: if a living cell is surrounded by fewer than two living cells, it dies.
  • Reproduction: if a dead cell is surrounded by exactly three cells, it becomes a live cell.

By enforcing these rules in sequential steps, beautiful and unexpected patterns can appear.

We shall experiment with the Game of Life in the following lines. Start importing the usual packages.

In [1]:
import numpy as np
import matplotlib.pyplot as plt
%pylab inline

Populating the interactive namespace from numpy and matplotlib

Exercise 1. Our first task is to define a function which implements one step of the game, using loops and conditionals to fulfill the above rules.

The input is a boolean matrix indicating where a living cell is present (True) or not (False), for instance

In [2]:
np.random.seed(0)
X = np.zeros((30, 40), dtype=bool)
r = np.random.random((10, 20))
X[10:20, 10:30] = (r > 0.75)

plt.imshow(X, cmap=plt.cm.binary, interpolation='nearest');

Thus, we have to visit each element (cell) of the matrix and check which of the above rules is satisfied (examining the $3\times 3$ square centered at the cell), and set the new state of the cell.

For cells in the boundary, we suppose that the neighbors which lie outside of the rectangle are those of the opposite boundary. For instance, the neighbors of $X[0,10]$ are: $$X[29,9], X[29,10],X[29,11], X[0,9], X[0,11], X[1,9], X[1,10], X[1,11].$$ Observe that $X[29,\cdot]$ is also indexed as $X[-1,\cdot ]$.

Define this function as life_step_1(X). The output must be a matrix of the same shape with the new state of the cells.

For the above example we get (you don't need to create a library, for the moment, just do it directly in a script)

In [3]:
import libGameOfLife

newX = libGameOfLife.life_step_1(X)
plt.imshow(newX, cmap=plt.cm.binary, interpolation='nearest');

Exercise 2. In this exercise, we continue the above script by incorporating a time-loop. We define the number of steps (40, in this example), and keep actualizing the cells state, X, with the function life_step_1(X) inside the time loop. Show in a figure the evolution of the state. To do this, apart from plt.imshow you should use plt.pause(0.001) inside the loop.

The sequence you get should be similar (but not the same, since the seed is random) to

In [4]:
# Animation tool borrowed from https://github.com/jakevdp/JSAnimation
libGameOfLife.life_animation_ori(X, dpi=10, frames=40, mode='once')
Out[4]:


Once Loop Reflect

One of the main advantages of Numpy is the speed in matrix manipulation. Use the following function to replace life_step_1(X):

In [5]:
def life_step_2(X):
    """Game of life step using scipy tools"""
    from scipy.signal import convolve2d
    nbrs_count = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X
    return (nbrs_count == 3) | (X & (nbrs_count == 2))    
    # | and & are for bitwise "or" and "and" (used for arrays)
    # returns True if nbrs_count = 3 or (X[i,j] = 1 and nbrs_count = 2)

Exercise 3.

  • Check that both functions give the same result by using np.max(np.abs(X1-X2)), where X1 and X2 are the outputs of life_step_1(X) and life_step_2(X), for a same input X.
  • Compare the execution times of the time loop that we obtain using both functions (comment the lines with plt.imshow and plt.pause, since rendering graphics slows down the code). To do this, use the package timeit as follows
In [6]:
import timeit

tic=timeit.default_timer()
for i in range(0,1000):
    i += 1                       # replace with your statements
toc=timeit.default_timer()
print "time=%f" % (toc - tic )         

time=0.000434
In [7]:
time1 = libGameOfLife.execution_time(X, life_step = libGameOfLife.life_step_1, time_steps = 40)
time2 = libGameOfLife.execution_time(X, life_step = libGameOfLife.life_step_2, time_steps = 40)
print time1, time2

0.476269960403 0.00340604782104

Exercise 4. Finally, write an script containing the function life_step_2(X), life_animation (download here) and use it on the data given below. Check your results with those showed below.

Static Configurations

Several static configurations are known: some of the smallest static units are shown here. We'll generate a few frames just to show that they are in fact static.

In [8]:
X = np.zeros((6, 21))
X[2:4, 1:3] = 1
X[1:4, 5:9] = [[0, 1, 1, 0],
               [1, 0, 0, 1],
               [0, 1, 1, 0]]
X[1:5, 11:15] = [[0, 1, 1, 0],
                 [1, 0, 0, 1],
                 [0, 1, 0, 1],
                 [0, 0, 1, 0]]
X[1:4, 17:20] = [[1, 1, 0],
                 [1, 0, 1],
                 [0, 1, 0]]

libGameOfLife.life_animation_ori(X, dpi=5, frames=3)
Out[8]:


Once Loop Reflect

Some simple oscillators (The "Blinker" and the "Toad")

An oscillator is a pattern that returns to its initial configuration after some number of steps. The static patterns shown above could be thought of as oscillators with a period of one. Here are two commonly-seen period-two oscillators:

In [9]:
blinker = [1, 1, 1]
toad = [[1, 1, 1, 0],
        [0, 1, 1, 1]]

X = np.zeros((6, 11))
X[2, 1:4] = blinker
X[2:4, 6:10] = toad
libGameOfLife.life_animation_ori(X, dpi=5, frames=4)
Out[9]:


Once Loop Reflect

Another Oscillator: The "Pulsar"

More complicated oscillators exist. Here's a period-three oscillator known as "The Pulsar", which displays some appealing symmetry.

In [10]:
X = np.zeros((17, 17))
X[2, 4:7] = 1
X[4:7, 7] = 1
X += X.T
X += X[:, ::-1]
X += X[::-1, :]
libGameOfLife.life_animation_ori(X, frames=6)
Out[10]:


Once Loop Reflect

The "Glider"

There are other classes of object which oscillate, but also move while oscillating. One of the earliest seen is the "Glider", which after 4 steps returns to its initial configuration, but shifted by one cell in both the x and y direction. This is a configuration that often emerges from random starting points.

In [11]:
glider = [[1, 0, 0],
          [0, 1, 1],
          [1, 1, 0]]
X = np.zeros((8, 8))
X[:3, :3] = glider
libGameOfLife.life_animation_ori(X, dpi=5, frames=32, interval=100)
Out[11]:


Once Loop Reflect

Unbounded Growth

An early question posed about the Game of Life was whether any configurations exist which result in asymptotically unbounded growth. It was quickly found that the answer was yes. Though it wasn't the first discovered, the following is one of the most compact configurations which display unbounded growth.

In [12]:
unbounded = [[1, 1, 1, 0, 1],
             [1, 0, 0, 0, 0],
             [0, 0, 0, 1, 1],
             [0, 1, 1, 0, 1],
             [1, 0, 1, 0, 1]]
X = np.zeros((30, 40))
X[15:20, 18:23] = unbounded
libGameOfLife.life_animation_ori(X, dpi=10, frames=100, interval=200, mode='once')
Out[12]:


Once Loop Reflect

The "Gosper Glider Gun"

The earliest known instance of unbounded growth is the "Glider Gun" discovered by Bill Gosper. It is an oscillating pattern that creates an infinite series of gliders.

In [13]:
glider_gun =\
[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]

X = np.zeros((50, 70))
X[1:10,1:37] = glider_gun

libGameOfLife.life_animation_ori(X, dpi=15, frames=180, interval=50, mode='once')
Out[13]:


Once Loop Reflect

Going Further

Despite (or perhaps because of) its simplicity, the Game of Life has inspired an entire community of people who study its properties. It has influenced fields as diverse as mathematics, computer science, biology, epidemiology, and sociology.

This interest has led to the discovery of configurations with some very surprising properties.

Incredibly, it has even been shown that a Universal Turing Machine can be created within the rules of the game of life. That is, a computer which can compute game of life steps could, in theory, use this process to compute just about anything!

Here are another few patterns you might try embedding in a game board, to see what will happen.

In [14]:
diehard = [[0, 0, 0, 0, 0, 0, 1, 0],
           [1, 1, 0, 0, 0, 0, 0, 0],
           [0, 1, 0, 0, 0, 1, 1, 1]]

boat = [[1, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]

r_pentomino = [[0, 1, 1],
               [1, 1, 0],
               [0, 1, 0]]

beacon = [[0, 0, 1, 1],
          [0, 0, 1, 1],
          [1, 1, 0, 0],
          [1, 1, 0, 0]]

acorn = [[0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 1, 0, 0, 0],
         [1, 1, 0, 0, 1, 1, 1]]

spaceship = [[0, 0, 1, 1, 0],
             [1, 1, 0, 1, 1],
             [1, 1, 1, 1, 0],
             [0, 1, 1, 0, 0]]

block_switch_engine = [[0, 0, 0, 0, 0, 0, 1, 0],
                       [0, 0, 0, 0, 1, 0, 1, 1],
                       [0, 0, 0, 0, 1, 0, 1, 0],
                       [0, 0, 0, 0, 1, 0, 0, 0],
                       [0, 0, 1, 0, 0, 0, 0, 0],
                       [1, 0, 1, 0, 0, 0, 0, 0]]

References