In a previous post, we explored generating the grid-neighborhoods of an element in a NumPy array. The punch line of that work was grid_nD, shown below.
import numpy as np
import matplotlib.pyplot as plt
import time
from IPython import display
%matplotlib inline
from numpy.lib.stride_tricks import as_strided
def grid_nD(arr):
assert all(_len>2 for _len in arr.shape)
nDims = len(arr.shape)
newShape = [_len-2 for _len in arr.shape]
newShape.extend([3] * nDims)
newStrides = arr.strides + arr.strides
return as_strided(arr, shape=newShape, strides=newStrides)
Using grid_nD, coding the game of life becomes really, really easy. Given the neighborhood around a cell, we can simply make use of two lookup tables: (1) the rules to use if the center cell is alive and (2) the rules to use if the center cell is dead. Normally, the Game of Life is implemented with these rules encoded as if-then-else or case statements. Instead, we’re going to use np.where which allows us to specify an array of boolean values (true/false, 1/0, alive/dead) and then pick from a "true/1/alive" value or a "false/0/dead" value.
We’ll create a table of the living values and a table of the dead values in two separate NumPy arrays. For a given number of neighbors, we can lookup the state of the center cell for the next time point.
Recall the rules for a currently living cell:
- If I’m alive and I have fewer than two alive neighors, I die of loneliness.
- If I’m alive and I have two or three alive neighbors, I live.
- If I’m alive and I have more than three alive neighbors, I die of starvation.
And for a currently dead cell:
- If I’m dead and I have three (exactly) live neighbors, I become alive by spontaneous combustion.
# index is number of neighbors alive
ruleOfLifeAlive = np.zeros(8+1, np.uint8) # default all to dead
ruleOfLifeAlive[[2,3]] = 1 # alive stays alive <=> 2 or 3 neighbors
print "ruleOfLifeAlive:", ruleOfLifeAlive
ruleOfLifeDead = np.zeros(8+1, np.uint8) # default all to dead
ruleOfLifeDead[3] = 1 # dead switches to living <=> 3 neighbors
print " ruleOfLifeDead:", ruleOfLifeDead
So, for example a live cell with three neighbors looks up ruleOfLifeAlive[3] which has the value 1, so it stays living. Another dead cell, with five living neighbors looks up ruleOfLifeDead[5] and we get the value 0: it stays dead.
The Game of Life
We’re now ready to implement the Game of Life. We only pull one non-obvious trick. We don’t want to have a "special case" for the cells on the boarder: we want to count the neighbors by summing up a neighborhood (which can do easily with our grid_nD and a NumPy np.sum call) and subtracting the center cell value. We do that in line 25 below. With a sequence of axes, np.sum(array, axes) adds up over multiple axes. For a 2D array, it is the two inner-most axes that pop out from the grid_nD call. We can count from inside-out with -1, -2.
To prevent the need for "special" (partial) neighborhoods around the boarder, we simply embed our Game of Life board inside of a slightly larger board with 0s surrounding our main board. NumPy is able to do this in a clever way that makes the inner (main) board a "view" into the outer board so we don’t have to duplicate memory.
One other pure Python piece you may not have seen is the use of slice. When we write arr[1:3, 4:10], the : character tells the Python interpreter to create a slice object. We can also manually create them. For 1:3, the slice call looks like slice(1,3). For 4:10, the call looks like slice(1,4). These are very useful if you have to programmatically develop the slice (instead of typing in fixed values and/or a fixed number of slices). If you are unsure of the use-case ofr this, consider what would happen if (1) in one run of a program, you needed 5 dimensions of slicing and (2) in another run of the program, you need only 3 dimensions of slicing. And, extending that, you wanted that program to work in arbitrary dimensions.
def imshow_helper(board, sleepSeconds=0.5):
''' helper method to display a board for short time interval
being lazy and using the MATLAB style API '''
plt.imshow(board, cmap="binary", interpolation="none")
plt.axis('off')
display.display(plt.gcf())
display.clear_output(wait=True)
time.sleep(sleepSeconds)
class GameOfLife(object):
def __init__(self, board_size=(10,10)):
full_size = tuple(i+2 for i in board_size)
self.full = np.zeros(full_size, dtype=np.uint8)
nd_slice = (slice(1, -1),) * len(board_size)
# self.board = self.full[1:-1,1:-1,...]
self.board = self.full[nd_slice]
self.ndims = len(self.board.shape)
def run_board(self, N_ITERS = 10):
imshow_helper(self.board)
for i in range(N_ITERS):
neighborhoods = grid_nD(self.full)
# shape = (10,10) --> (-1, -2)
sumOver = tuple(-(i+1) for i in xrange(self.ndims))
neighborCt = np.sum(neighborhoods, sumOver) - self.board
self.board[:] = np.where(self.board,
ruleOfLifeAlive[neighborCt],
ruleOfLifeDead[neighborCt])
imshow_helper(self.board)
One Quick Board
Here’s one quick board with a square in the lower right. First we look at the raw NumPy array (just the inner array, ignoring the outer array that stores the extra zeros)
gol = GameOfLife()
gol.board[5:8,5:8] = 1
print gol.board
And here’s what that array looks like when we interpret it as an image:
plt.imshow(gol.board, cmap="binary", interpolation="none")
plt.axis('off');
And Some 2D Boards
Here are a few simple boards (starting configurations) and a few named boards from https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Examples_of_patterns
gol = GameOfLife()
gol.board[4:7, 5] = 1
gol.run_board(10)
gol = GameOfLife()
gol.board[4:6, 4:6] = 1
gol.board[6:8, 6:8] = 1
gol.run_board(10)
gol = GameOfLife((11,11))
gol.board[4,5] = 1
gol.board[5, 4:7] = 1
gol.board[6,5] = 1
gol.run_board(10)
gol = GameOfLife((11,11))
gol.board[4,6] = 1
gol.board[4:7,5] = 1
gol.board[5,4] = 1
plt.imshow(gol.board, cmap="binary", interpolation="none")
gol.run_board(10)
gol = GameOfLife((11,11))
gol.board[1,7] = 1
gol.board[2,1:3] = 1
gol.board[3,2] = 1
gol.board[3, 6:9] = 1
plt.imshow(gol.board, cmap="binary", interpolation="none")
gol.run_board(50)
Additional Resources
You can grab a copy of this notebook.
Even better, you can view it using nbviewer.
License
Unless otherwise noted, the contents of this notebook are under the following license. The code in the notebook should be considered part of the text (i.e., licensed and treated as as follows).
DrsFenner.org Blog And Notebooks by Mark and Barbara Fenner is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.< br/>Permissions beyond the scope of this license may be available at drsfenner.org/blog/about-and-contacts.
Additional Resources
You can grab a copy of this notebook.
Even better, you can view it using nbviewer.
License
Unless otherwise noted, the contents of this notebook are under the following license. The code in the notebook should be considered part of the text (i.e., licensed and treated as as follows).
DrsFenner.org Blog And Notebooks by Mark and Barbara Fenner is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Permissions beyond the scope of this license may be available at drsfenner.org/blog/about-and-contacts.