Previous Up Next

This HTML version of Think Complexity, 2nd Edition is provided for convenience, but it is not the best format of the book. In particular, some of the symbols are not rendered correctly.

You might prefer to read the PDF version.

Chapter 6  Game of Life

In this chapter we consider two-dimensional cellular automatons, especially John Conway’s Game of Life (GoL). Like some of the 1-D CAs in the previous chapter, GoL follows simple rules and produces surprisingly complicated behavior. And like Wolfram’s Rule 110, GoL turns out to be universal; that is, it can compute any computable function, at least in theory.

Complex behavior in GoL raises issues in the philosophy of science, particularly related to scientific realism and instrumentalism. I discuss these issues and suggest additional reading.

At the end of the chapter, I demonstrate ways to implement GoL efficiently in Python.

The code for this chapter is in chap06.ipynb in the repository for this book. More information about working with the code is in Section ??.

6.1  Conway’s GoL

One of the first cellular automatons 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.

Each cell has two states—live and dead—and 8 neighbors—north, south, east, west, and the four diagonals. This set of neighbors is sometimes called a “Moore neighborhood”.

Like the 1-D CAs in the previous chapters, the Game of Life evolves over time according to rules, which are like simple laws of physics.

In GoL, the next state of each cell depends on its current state and its number of live neighbors. If a cell is alive, it survives if it has 2 or 3 neighbors and dies otherwise. If a cell is dead, it stays dead unless it has exactly 3 neighbors.

The following table summarizes the rules:

CurrentNumber ofNext
stateneighborsstate
live2–3live
live0–1, 4–8dead
dead3live
dead0–2, 4–8dead

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:

  • There are simple initial conditions that yield surprisingly complex behavior.

  • There are many interesting stable patterns: some oscillate (with various periods) and some move like the spaceships in Wolfram’s Rule 110 CA.
  • And like Rule 110, GoL is Turing complete.

  • Another factor that generated interest was Conway’s conjecture—that there is no initial condition that yields unbounded growth in the number of live cells—and the $50 bounty he offered to anyone who could prove or disprove it.

  • Finally, the increasing availability of computers made it possible to automate the computation and display the results graphically.

6.2  Life patterns


Figure 6.1: A stable pattern called a beehive.


Figure 6.2: An oscillator called a toad.


Figure 6.3: A spaceship called a glider.

If you run GoL from a random starting state, a number of stable patterns are likely to appear. Over time, people have identified these patterns and given them names.

For example, Figure ?? shows a stable pattern called a “beehive”. Every cell in the beehive has 2 or 3 neighbors, so they all survive, and none of the dead cells adjacent to the beehive has 3 neighbors, so no new cells are born.

Other patterns “oscillate”; that is, they change over time but eventually return to their starting configuration (provided they don’t collide with another pattern). For example, Figure ?? shows a pattern called a “toad”, which is an oscillator that alternates between two states. The “period” of this oscillator is 2.

Finally, some patterns oscillate and return to the starting configuration, but shifted in space. Because these patterns seem to move, they are called “spaceships”.

Figure ?? shows a spaceship called a “glider”. After a period of 4 steps, the glider is back in the starting configuration, shifted one unit down and to the right.

Depending on the starting orientation, gliders can move along any of the four diagonals. There are other spaceships that move horizontally and vertically.

People have spent embarrassing amounts of time finding and naming these patterns. If you search the web, you will find many collections.

6.3  Conway’s conjecture

From most initial conditions, GoL quickly reaches a stable state where the number of live cells is nearly constant (possibly with some oscillation).


Figure 6.4: Starting and final configurations of the r-pentomino.

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, roughly in the shape of the letter “r”. Figure ?? shows the initial configuration of the r-pentomino and the final configuration after 1103 steps.

This configuration is “final” in the sense that all remaining patterns are either stable, oscillators, or gliders that will never collide with another pattern. In total, the r-pentomino yields 6 gliders, 8 blocks, 4 blinkers, 4 beehives, 1 boat, 1 ship, and 1 loaf.


Figure 6.5: Gosper’s glider gun, which produces a stream of gliders.

The existence of long-lived patterns prompted Conway to wonder if there are initial patterns that never stabilize. He conjectured that there were 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, which is shown in Figure ??. Gosper also discovered the first puffer train.

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 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.

6.4  Realism

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.

Right?

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, theories about electromagnetism are expressed in terms of electrical and magnetic fields. Some theories about economics are expressed in terms of supply, demand, and market forces. And theories about biology are expressed in terms of genes.

But are these entities real? That is, do they exist in the world independent of us and our theories?

Again, I find it useful to state philosophical positions in a range of strengths; here are four statements of scientific realism with increasing strength:

SR1:
Scientific theories are true or false to the degree that they approximate reality, but no theory is exactly true. Some postulated entities may be real, but there is no principled way to say which ones.
SR2:
As science advances, our theories become better approximations of reality. At least some postulated entities are known to be real.
SR3:
Some theories are exactly true; others are approximately true. Entities postulated by true theories, and some entities in approximate theories, are real.
SR4:
A theory is true if it describes reality correctly, and false otherwise. The entities postulated by true theories are real; others are not.

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.

6.5  Instrumentalism

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).”

“Electric and magnetic fields are postulated entities in our best theories of electromagnetism, but they aren’t real. We could construct other theories, without postulating fields, 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?

For more on instrumentalism, see http://en.wikipedia.org/wiki/Instrumentalism.

6.6  Implementing Life

The exercises at the end of this chapter ask you to experiment with and modify the Game of Life, and implement other 2-D cellular automata. This section explains my implementation of GoL, which you can use as a starting place for your experiments.

To represent the state of the cells, I use a NumPy array with type uint8, which is an 8-bit unsigned integer. As an example, the following line creates a 10 by 10 array initialized with random values of 0 and 1.

a = np.random.randint(2, size=(10, 10)).astype(np.uint8)

There are a few ways we can compute the GoL rules. The simplest is to use for loops to iterate through the rows and columns of the array:

b = np.zeros_like(a) rows, cols = a.shape for i in range(1, rows-1): for j in range(1, cols-1): state = a[i, j] neighbors = a[i-1:i+2, j-1:j+2] k = np.sum(neighbors) - state if state: if k==2 or k==3: b[i, j] = 1 else: if k == 3: b[i, j] = 1

Initially, b is an array of zeros with the same size as a. Each time through the loop, state is the condition of the center cell and neighbors is the 3x3 neighborhood. k is the number of live neighbors (not including the center cell). The nested if statements evaluate the GoL rules and turn on cells in b accordingly.

This implementation is a straightforward translation of the rules, but it is verbose and slow. We can do better using cross-correlation, as we saw in Section ??. There, we used np.correlate to compute a 1-D correlation. Now, to perform 2-D correlation, we’ll use correlate2d from scipy.signal, a SciPy module that provides functions related to signal processing:

from scipy.signal import correlate2d kernel = np.array([[1, 1, 1], [1, 0, 1], [1, 1, 1]]) c = correlate2d(a, kernel, mode='same')

What we called a “window” in the context of 1-D correlation is called a “kernel” in the context of 2-D correlation, but the idea is the same: correlate2d multiplies the kernel and the array to select a neighborhood, then adds up the result. This kernel selects the 8 neighbors that surround the center cell.

correlate2d applies the kernel to each location in the array. With mode='same', the result has the same size as a.

Now we can use logical operators to compute the rules:

b = (c==3) | (c==2) & a b = b.astype(np.uint8)

The first line computes a boolean array with True where there should be a live cell and False elsewhere. Then astype converts the boolean array to an array of integers.

This version is faster, and probably good enough, but we can simplify it slightly by modifying the kernel:

kernel = np.array([[1, 1, 1], [1,10, 1], [1, 1, 1]]) c = correlate2d(a, kernel, mode='same') b = (c==3) | (c==12) | (c==13) b = b.astype(np.uint8)

This version of the kernel includes the center cell and gives it a weight of 10. If the center cell is 0, the result is between 0 and 8; if the center cell is 1, the result is between 10 and 18. Using this kernel, we can simplify the logical operations, selecting only cells with the values 3, 12, and 13.

That might not seem like a big improvement, but it allows one more simplification: with this kernel, we can use a table to look up cell values, as we did in Section ??.

table = np.zeros(20, dtype=np.uint8) table[[3, 12, 13]] = 1 c = correlate2d(a, kernel, mode='same') b = table[c]

table has zeros everywhere except locations 3, 12, and 13. When we use c as an index into table, NumPy performs element-wise lookup; that is, it takes each value from c, looks it up in table, and puts the result into b.

This version is faster and more concise than the others; the only drawback is that it takes more explaining.

Life.py, which is included in the repository for this book, provides a Life class that encapsulates this implementation of the rules. If you run Life.py, you should see an animation of a “puffer train”, which is a spaceship that leaves a trail of detritus in its wake.

6.7  Exercises

Exercise 1  

The code for this chapter is in the Jupyter notebook chap06.ipynb in the repository for this book. Open this notebook, read the code, and run the cells. You can use this notebook to work on the exercises in this chapter. My solutions are in chap06soln.ipynb.

Exercise 2  

Start GoL in a random state and run it until it stabilizes. What stable patterns can you identify?

Exercise 3  

Many named patterns are available in portable file formats. Modify Life.py to parse one of these formats and initialize the grid.

Exercise 4  

One of the longest-lived small patterns is “rabbits”, which starts with 9 live cells and takes 17 331 steps to stabilize. You can get the initial configuration in various formats from http://www.conwaylife.com/wiki/Rabbits. Load this configuration and run it.

Exercise 5  

In my implementation, the Life class is based on a parent class called Cell2D, and LifeViewer is based on Cell2DViewer. You can use these base classes to implement other 2-D cellular automatons.

For example, one variation of GoL, called “Highlife”, has the same rules as GoL, plus one additional rule: a dead cell with 6 neighbors comes to life.

Write a class named Highlife that inherits from Cell2D and implements this version of the rules. Also write a class named HighlifeViewer that inherits from Cell2DViewer and try different ways to visualize the results. As a simple example, use a different color map.

One of the more interesting patterns in Highlife is the replicator. Use add_cells to initialize Highlife with a replicator and see what it does.

Exercise 6  

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 most famous Turmite is Langton’s Ant, discovered by Chris Langton in 1986. See http://en.wikipedia.org/wiki/Langton_ant.

The ant is a read-write head with four states, which you can think of as facing north, south, east or west. The cells have two states, black and white.

The rules are simple. During each time step, the ant checks the color of the cell it is on. If 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”.

Write an implementation of Langton’s Ant.

Are you using one of our books in a class?

We'd like to know about it. Please consider filling out this short survey.


Think DSP

Think Java

Think Bayes

Think Python 2e

Think Stats 2e

Think Complexity


Previous Up Next