Chapter 7 Game of Life
One of the first cellular automata to be studied, and probably the most popular of all time, is a 2-D CA called “The Game of Life,” or GoL for short. It was developed by John H. Conway and popularized in 1970 in Martin Gardner’s column in Scientific American. See http://en.wikipedia.org/wiki/Conway_Game_of_Life.
The cells in GoL are arranged in a 2-D grid, either infinite in both directions or wrapped around. A grid wrapped in both directions is called a torus because it is topographically equivalent to the surface of a doughnut. See http://en.wikipedia.org/wiki/Torus.
This behavior is loosely analogous to real cell growth: cells that are isolated or overcrowded die; at moderate densities they flourish.
GoL is popular because:
7.1 Implementing Life
To implement GoL efficiently, we can take advantage of the multi-dimensional convolution function in SciPy. SciPy is a Python package that provides functions related to scientific computing. You can read about it at http://www.scipy.org/; if it is not already on your system, you might have to install it.
kernel = numpy.array([[1,1,1], [1,0,1], [1,1,1]])
represents a neighborhood with eight neighbors, all with weight 1.
Convolution computes the weighted sum of the neighbors for each element of the array. So this kernel computes the sum of the neighbors (not including the center element).
For example, if array represents a GoL grid with 1s for live cells and 0s for dead cells we can use convolution to compute the number of neighbors for each cell.
import scipy.ndimage neighbors = scipy.ndimage.filters.convolve(array, kernel)
import numpy import scipy.ndimage class Life(object): def __init__(self, n, mode='wrap'): self.n = n self.mode = mode self.array = numpy.random.random_integers(0, 1, (n, n)) self.weights = numpy.array([[1,1,1], [1,10,1], [1,1,1]]) def step(self): con = scipy.ndimage.filters.convolve(self.array, self.weights, mode=self.mode) boolean = (con==3) | (con==12) | (con==13) self.array = numpy.int8(boolean)
The attributes of the Life object are n, the number of rows and columns in the grid, mode, which controls the behaviors of the boundary cells, array, which represents the grid, and weights which is the kernel used to count the neighbors.
The weight of the center cell is 10, so the number of neighbors is 0-8 for dead cells and 10-18 for live cells.
In step, boolean is a boolean array with True for live cells; numpy.int8 converts it to integers.
import matplotlib matplotlib.use('TkAgg') import matplotlib.pyplot as pyplot class LifeViewer(object): def __init__(self, life, cmap=matplotlib.cm.gray_r): self.life = life self.cmap = cmap self.fig = pyplot.figure() pyplot.axis([0, life.n, 0, life.n]) pyplot.xticks() pyplot.yticks() self.pcolor = None self.update()
def update(self): if self.pcolor: self.pcolor.remove() a = self.life.array self.pcolor = pyplot.pcolor(a, cmap=self.cmap) self.fig.canvas.draw()
If there is already a plot, we have to remove it; then we create a new one and invoke draw to update the display.
To run the animation, we need two methods:
def animate(self, steps=10): self.steps = steps self.fig.canvas.manager.window.after(1000, self.animate_callback) pyplot.show() def animate_callback(self): for i in range(self.steps): self.life.step() self.update()
animate gets the animation started. It invokes pyplot.show,
which sets up the GUI and waits for user events, but first it has
to invoke window.after to set up a callback, so that
Download my implementation of GoL from thinkcomplex.com/Life.py.
Start the CA in a random state and run it until it stabilizes. What stable patterns can you identify?
7.2 Life patterns
People have spent embarrassing amounts of time finding and naming these patterns. If you search the web, you will find many collections.
From most initial conditions, GoL quickly reaches a stable state where the number of live cells is nearly constant (usually with a small amount of oscillation).
But there are a some simple starting conditions that take a long time to settle down and yield a surprising number of live cells. These patterns are called “Methuselahs” because they are so long-lived.
One of the simplest is the r-pentomino, which has only five cells in the shape of a “r,” hence the name. It runs for 1103 steps and yields 6 gliders, 8 blocks, 4 blinkers, 4 beehives, 1 boat, 1 ship, and 1 loaf. One of the longest-lived small patterns is rabbits, which starts with 9 live cells and takes 17 331 steps to stabilize.
Start with an r-pentomino as an initial condition and confirm that the results are consistent with the description above. You might have to adjust the size of the grid and the boundary behavior.
7.3 Conway’s conjecture
The existence of long-lived patterns brings us back to Conway’s original question: are there initial patterns that never stabilize? Conway thought not, but he described two kinds of pattern that would prove him wrong, a “gun” and a “puffer train.” A gun is a stable pattern that periodically produces a spaceship—as the stream of spaceships moves out from the source, the number of live cells grows indefinitely. A puffer train is a translating pattern that leaves live cells in its wake.
It turns out that both of these patterns exist. A team led by Bill Gosper discovered the first, a glider gun now called Gosper’s Gun. Gosper also discovered the first puffer train. You can find descriptions and animations of these patterns in several places on the Web.
There are many patterns of both types, but they are not easy to design or find. That is not a coincidence. Conway chose the rules of GoL so that his conjecture would not be obviously true or false. Of all the possible rules for a 2-D CA, most yield simple behavior; most initial conditions stabilize quickly or grow unboundedly. By avoiding uninteresting CAs, Conway was also avoiding Wolfram’s Class 1 and Class 2 behavior, and probably Class 3 as well.
If we believe Wolfram’s Principle of Computational Equivalence, we expect GoL to be in Class 4. And it is. The Game of Life was proved Turing complete in 1982 (and again, independently, in 1983). Since then several people have constructed GoL patterns that implement a Turing machine or another machine known to be Turing complete.
Many named patterns are available in portable file formats. Modify Life.py to parse one of these formats and initialize the grid.
Stable patterns in GoL are hard not to notice, especially the ones that move. It is natural to think of them as persistent entities, but remember that a CA is made of cells; there is no such thing as a toad or a loaf. Gliders and other spaceships are even less real because they are not even made up of the same cells over time. So these patterns are like constellations of stars. We perceive them because we are good at seeing patterns, or because we have active imaginations, but they are not real.
Well, not so fast. Many entities that we consider “real” are also persistent patterns of entities at a smaller scale. Hurricanes are just patterns of air flow, but we give them personal names. And people, like gliders, are not made up of the same cells over time. But even if you replace every cell in your body, we consider you the same person.
This is not a new observation—about 2500 years ago Heraclitus pointed out that you can’t step in the same river twice—but the entities that appear in the Game of Life are a useful test case for thinking about philosophical realism.
In the context of philosophy, realism is the view that entities in the world exist independent of human perception and conception. By “perception” I mean the information that we get from our senses, and by “conception” I mean the mental model we form of the world. For example, our vision systems perceive something like a 2-D projection of a scene, and our brains use that image to construct a 3-D model of the objects in the scene.
Scientific realism pertains to scientific theories and the entities they postulate. A theory postulates an entity if it is expressed in terms of the properties and behavior of the entity. For example, Mendelian genetics postulates a “gene” as a unit that controls a heritable characteristic. Eventually we discovered that genes are encoded in DNA, but for about 50 years, a gene was just a postulated entity. See http://en.wikipedia.org/wiki/Gene.
Again, I find it useful to state philosophical positions in a range of strengths, where SR1 is a weak form of scientific realism and SR4 is a strong form:
SR4 is so strong that it is probably untenable; by such a strict criterion, almost all current theories are known to be false. Most realists would accept something in the space between SR1 and SR3.
But SR1 is so weak that it verges on instrumentalism, which is the view that we can’t say whether a theory is true or false because we can’t know whether a theory corresponds to reality. Theories are instruments that we use for our purposes; a theory is useful, or not, to the degree that it is fit for its purpose.
To see whether you are comfortable with instrumentalism, consider the following statements:
“Entities in the Game of Life aren’t real; they are just patterns of cells that people have given cute names.”
“A hurricane is just a pattern of air flow, but it is a useful description because it allows us to make predictions and communicate about the weather.”
“Freudian entities like the Id and the Superego aren’t real, but they are useful tools for thinking and communicating about psychology (or at least some people think so).”
“Electrons are postulated entities in our best theories of electro-magnetism, but they aren’t real. We could construct other theories, without postulating electrons, that would be just as useful.”
“Many of the things in the world that we identify as objects are arbitrary collections like constellations. For example, a mushroom is just the fruiting body of a fungus, most of which grows underground as a barely-contiguous network of cells. We focus on mushrooms for practical reasons like visibility and edibility.”
“Some objects have sharp boundaries, but many are fuzzy. For example, which molecules are part of your body: Air in your lungs? Food in your stomach? Nutrients in your blood? Nutrients in a cell? Water in a cell? Structural parts of a cell? Hair? Dead skin? Dirt? Bacteria on your skin? Bacteria in your gut? Mitochondria? How many of those molecules do you include when you weigh yourself. Conceiving the world in terms of discrete objects is useful, but the entities we identify are not real.”
Give yourself one point for each statement you agree with. If you score 4 or more, you might be an instrumentalist!
If you are more comfortable with some of these statements than others, ask yourself why. What are the differences in these scenarios that influence your reaction? Can you make a principled distinction between them?
Read http://en.wikipedia.org/wiki/Instrumentalism and construct a sequence of statements that characterize instrumentalism in a range of strengths.
If you generalize the Turing machine to two dimensions, or add a read-write head to a 2-D CA, the result is a cellular automaton called a Turmite. It is named after a termite because of the way the read-write head moves, but spelled wrong as an homage to Alan Turing.
The rules are simple. During each time step, the ant checks the color of the cell is it on. If it is black, the ant turns to the right, changes the cell to white, and moves forward one space. If the cell is white, the ant turns left, changes the cell to black, and moves forward.
Given a simple world, a simple set of rules, and only one moving part, you might expect to see simple behavior—but you should know better by now. Starting with all white cells, Langton’s ant moves in a seemingly random pattern for more than 10 000 steps before it enters a cycle with a period of 104 steps. After each cycle, the ant is translated diagonally, so it leaves a trail called the “highway.”
If you start with multiple Turmites, they interact with each other in seemingly complex ways. If one Turmite is on the highway, another can follow it, overtake it, and cause it to reverse its pattern, moving back up the highway and leaving only white cells behind.
Like this book?
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.