Conway's Game of Life¶

with IPython Blocks!

Conway's Game of Life is a common program used in CS education. It involves a two-dimensional grid of square cells, all of which are in one of two states: alive or dead. The system then evolves to a new generation at each timestep, based on a few simple rules:

A live cell with two or three live neighbors survives to the next generation
A live cell with any other number of live neighbors (0, 1, > 3) dies
A dead cell with exactly three live neighbors comes alive in the next generation

Let's get started with a simple system, illustrated with IPython Blocks

In [1]:

from IPython.display import display, clear_output
from ipythonblocks import BlockGrid

Dead cells will be illustrated by empty white space, and live ones as black blocks

In [2]:

DEAD = (255,) * 3
ALIVE = (0,) * 3

We will start with a simple 3x4 grid

In [3]:

COLS = 3
ROWS = 4
cell_grid = BlockGrid(COLS, ROWS, fill=DEAD)

And some simple functions for turning cells on/off, and checking whether they are alive

In [4]:

def live(cell):
    """bring the cell to life"""
    cell.rgb = ALIVE

def die(cell):
    """kill the cell"""
    cell.rgb = DEAD

def is_alive(cell):
    """is the cell alive?"""
    return cell.rgb == ALIVE

Let's start with a few live cells on our small grid

In [5]:

cell = cell_grid[2,1]
live(cell)

live(cell_grid[1,2])
live(cell_grid[1,0])
live(cell_grid[3,0])
live(cell_grid[0,1])
live(cell_grid[0,2])
cell_grid

Out[5]:

Now let's define a function that, for a given cell at $(row,col)$ , gives us the neighbors

In [6]:

def get_neighbors(cell, grid):
    """Get all eight neighboring cells"""
    r = cell.row
    c = cell.col
    neighbors = [
        grid[r-1, c-1],
        grid[r-1, c],
        grid[r-1, c+1],
        grid[r+1, c-1],
        grid[r+1, c],
        grid[r+1, c+1],
        grid[r, c-1],
        grid[r, c+1]
    ]
    return neighbors

So the neighbors of our cell at $(2,1)$ are

In [7]:

for neighbor in get_neighbors(cell, cell_grid):
    print neighbor

Block [1, 0]
Color: (0, 0, 0)
Block [1, 1]
Color: (255, 255, 255)
Block [1, 2]
Color: (0, 0, 0)
Block [3, 0]
Color: (0, 0, 0)
Block [3, 1]
Color: (255, 255, 255)
Block [3, 2]
Color: (255, 255, 255)
Block [2, 0]
Color: (255, 255, 255)
Block [2, 2]
Color: (255, 255, 255)

but we need to be careful, because we don't want to be indexing outside the grid

In [8]:

get_neighbors(cell_grid[2,2], cell_grid)

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-8-b5d6d74a6b57> in <module>()
----> 1 get_neighbors(cell_grid[2,2], cell_grid)

<ipython-input-6-3543a099ce81> in get_neighbors(cell, grid)
      6         grid[r-1, c-1],
      7         grid[r-1, c],
----> 8         grid[r-1, c+1],
      9         grid[r+1, c-1],
     10         grid[r+1, c],

/Users/minrk/dev/py/ipythonblocks/ipythonblocks/ipythonblocks.pyc in __getitem__(self, index)
    415 
    416         elif ind_cat == _SINGLE_ITEM:
--> 417             block = self._grid[index[0]][index[1]]
    418             block._row, block._col = index
    419             return block

IndexError: list index out of range

So here's a more careful version that checks boundaries, so that we don't get IndexErrors

In [9]:

def get_neighbors(cell, grid):
    """Get the neighboring cells, excluding any that might be out of bounds"""
    neighbors = []
    row = cell.row
    col = cell.col
    for r in range(row-1, row+2):
        if r < 0:
            continue
        elif r >= grid.height:
            continue
        
        for c in range(col-1, col+2):
            if c < 0:
                continue
            elif c >= grid.width:
                continue
            elif r == row and c == col:
                continue
            else:
                neighbors.append(grid[r,c])

    return neighbors

In [11]:

print cell
print "has neighbors:"

for neighbor in get_neighbors(cell, cell_grid):
    print neighbor

Block [2, 1]
Color: (0, 0, 0)
has neighbors:
Block [1, 0]
Color: (0, 0, 0)
Block [1, 1]
Color: (255, 255, 255)
Block [1, 2]
Color: (0, 0, 0)
Block [2, 0]
Color: (255, 255, 255)
Block [2, 2]
Color: (255, 255, 255)
Block [3, 0]
Color: (0, 0, 0)
Block [3, 1]
Color: (255, 255, 255)
Block [3, 2]
Color: (255, 255, 255)

Visualizing neighbors¶

Let's pick some colors for the five possible numbers of living neighbors:

0 - black (certain death)
1 - gray (same condition as black, but not as severe)
2 - blue (will survive if already alive)
3 - cyan (will live, even if not alive now)
4 - red (too many! can't survive!)

In [12]:

colors = [
    (0,) * 3,
    (55,) * 3,
    (0,0,255),
    (0,255,255),
    (255,0,0)
    ]

_max_color = len(colors)-1
def color(n):
    return colors[min(n, _max_color)]
colors

Out[12]:

[(0, 0, 0), (55, 55, 55), (0, 0, 255), (0, 255, 255), (255, 0, 0)]

And define a function for counting the living neighbors

In [13]:

def count_living_neighbors(cell, grid):
    neighbors = get_neighbors(cell, grid)
    count = 0
    for neighbor in neighbors:
        if is_alive(neighbor):
            count += 1
    return count

In [14]:

count_living_neighbors(cell, cell_grid)

Out[14]:

We can visualize the environment with another grid, colored by the number of living neighbors for each cell.

In [15]:

def new_grid_like(grid):
    return BlockGrid(grid.width, grid.height,
            lines_on=grid.lines_on,
            block_size=grid.block_size,
    )

In [16]:

neighbor_grid = new_grid_like(cell_grid)
for cell in cell_grid:
    n = count_living_neighbors(cell, cell_grid)
    neighbor_grid[cell.row, cell.col].rgb = colors[min(n,4)]

print "The Grid:"
display(cell_grid)
print "Neighbors:"
display(neighbor_grid)

The Grid:

Neighbors:

So we see that cell $(1,1)$ is surrounded by too much to survive, and cell $(2,0)$ is in such good condition, that it will be alive, regardless of whether there is a live cell there currently, and cells $(0,0), (0,2), (2,2), (3,1)$ can all support life if it is already present.

The remaining cells do not have enough surrounding life to sustain their own life.

Evolving the Grid¶

Now that we have a grid of the neighbor counts, we can determine what the next generation of the cell grid should be, by following the Rules of the Game.

Recall:

If a cell is alive and has two or three living neighbors, it will survive.
If a cell has exactly three living neighbors, it will come to life.
If a cell has zero, one, or four living neighbors, it will die.

So we define a function that gives us the next state for a single cell, by counting its living neighbors

In [17]:

def next_cell_state(cell, cell_grid):
    """The next state for a given cell, according to Conway's Game of Life"""
    living_neighbors = count_living_neighbors(cell, cell_grid)
    if living_neighbors == 3:
        return ALIVE
    elif living_neighbors == 2 and is_alive(cell):
        return ALIVE
    else:
        return DEAD

And use that function to generate the grid for the next generation of cells

In [19]:

def next_generation(cell_grid):
    """Return a new grid with the next state of an existing grid"""
    next_gen = new_grid_like(cell_grid)
    for cell in cell_grid:
        next_gen[cell.row, cell.col] = next_cell_state(cell, cell_grid)
    return next_gen

To demonstrate this, we can generate a large random grid

In [20]:

import random
def random_grid(rows, cols, fraction=0.5, block_size=20):
    """Construct a random grid of a given size.
    
    fraction determines the starting population.
    """
    grid = BlockGrid(rows, cols, fill=DEAD, block_size=block_size)
    for cell in grid:
        if random.random() < fraction:
            live(cell)
    return grid

And, for use later, a function to check whether two grids differ. We can use this to stop a simulation after it reaches steady state. It will not catch cycles!

In [21]:

def grid_changed(first, second):
    """Did the grid change?"""
    for a,b in zip(first, second):
        if a.rgb != b.rgb:
            return True
    return False

Generate a random $32x32$ grid with $60\%$ population.

In [22]:

cell_grid = random_grid(32, 32, 0.6)
cell_grid

Out[22]:

And now we can animate the evolution of a Game, by displaying the current state, evolving the state, and waiting a second before displaying the new state in its place.

We check whether the grid has changed, so that we stop the simulation when it has stabilized.

In [23]:

present = cell_grid

for generation in range(100):
    clear_output()
    display(present)
    future = next_generation(present)
    if not grid_changed(present, future):
        break
    present = future
    time.sleep(1)

print "Reached steady state in %i generations" % generation

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-23-82f4c37a2ce2> in <module>()
      8         break
      9     present = future
---> 10     time.sleep(1)
     11 
     12 print "Reached steady state in %i generations" % generation

KeyboardInterrupt:

Conway's Diff of Life¶

Now we can define a 'diff' for the grid. This is a new grid of the same shape, but highlighting the changes between to generations. Each cell that does not change is displayed the same, but where a cell dies from one generation to the next will be red, and where a new cell is born will be cyan.

In [24]:

def grid_diff(before, after):
    """Compute a new grid showing the difference between to grids"""
    diff = new_grid_like(before)
    for A, B, D in zip(before, after, diff):
        if A.rgb == B.rgb:
            # no change, store the value itself
            D.rgb = A.rgb
        elif is_alive(B):
            # Cyan for birth
            D.rgb = (0,255,255)
        else:
            # Red for death
            D.rgb = (255,0,0)
    return diff
            

In [25]:

cell_grid = random_grid(64, 64, block_size=10)

In [26]:

present = cell_grid
future = next_generation(present)
display(grid_diff(present, future))

We update our evolution procedure to display the diff in between each generation

In [31]:

present = cell_grid

step = 1.0

for generation in range(100):
    clear_output()
    display(present)
    future = next_generation(present)
    if not grid_changed(present, future):
        break
    time.sleep(step)
    clear_output()
    display(grid_diff(present, future))
    time.sleep(0.75 * step)
    present = future

print "Reached steady state in %i generations" % generation

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-31-4a8f8c750f06> in <module>()
     12     clear_output()
     13     display(grid_diff(present, future))
---> 14     time.sleep(0.75 * step)
     15     present = future
     16 

KeyboardInterrupt: