Problem: Simulating the Game of Life¶

In 1970, mathematician John H. Conway proposed a simulation that he called the Game of Life. Martin Gardner wrote an column about Life in the October 1970 issue of Scientific American that brought widespread attention to the Game of Life. It’s not what most people think of as a game; there are no players and there’s no way to win or lose the game. Instead, Life is more like a model or simulation in which you can play and experiment.

Life takes place on a two-dimensional grid of square cells. Each square cell can be either alive or dead (full or empty).

The simulation is carried out at fixed time steps; every time step, all the cells on the grid can switch from dead to alive, or alive to dead, depending on four simple rules that only depend on a given cell’s eight immediate neighbours. Let’s take the cell x in the diagram, whose neighbours have been numbered 1 through 8 in the diagram.

1. Birth: if exactly three of its neighbours are alive, the cell will become alive at the next step.

If the cell is already alive:

1. Survival: if the cell has two or three live neighbours, the cell remains alive.

Otherwise, the cell will die:

1. Death by loneliness: if the cell has only zero or one live neighbours, the cell will become dead at the next step.
2. Death by overcrowding: if the cell alive and has more than three live neighbours, the cell also dies.

These rules are simple and readily understandable, but they lead to surprisingly complex behaviour. (The general term for a simulation carried out on a grid of cells and following some simple rules is a cellular automaton.) For example, here are some patterns that occur after starting with five live cells in a row.

This pattern ends up in a cycle that repeats itself endlessly. Researchers in Life have coined many terms for different types of pattern, and this one is called an oscillator. The wiki at ConwayLife.com <http://www.conwaylife.com/wiki/Main_Page> describes many such terms. For example, oscillators go through a cycle of states and return to their initial state; still life patterns are stable and don’t change over time at all; spaceships return to their initial configuration but in a different position, and therefore the pattern moves through the grid.

Approach¶

It’s possible to work out Life patterns using pencil and paper, but obviously this is boring for large or long-lived patterns, and there’s also the risk of error. Computer implementations of Life were written soon after Conway described it.

A basic implementation is straightforward: store the state of the board, and loop over every cell to determine its new state. To be correct, the code has to record new states in a copy of the board’s data structure and not update the original board as it’s scanned.

Solution¶

This implementation of Life uses the `turtle` graphics to draw the board. Keystrokes are used to control the program; hit ‘R’ to fill the board with a random pattern, and then ‘S’ to step through one generation at a time.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235``` ```#!/usr/bin/env python3 # life.py -- A turtle-based version of Conway's Game of Life. # # An empty board will be displayed, and the following commands are available: # E : Erase the board # R : Fill the board randomly # S : Step for a single generation # C : Update continuously until a key is struck # Q : Quit # Cursor keys : Move the cursor around the board # Space or Enter : Toggle the contents of the cursor's position # import sys import turtle import random CELL_SIZE = 10 # Measured in pixels class LifeBoard: """Encapsulates a Life board Attributes: xsize, ysize : horizontal and vertical size of the board state : set containing (x,y) coordinates for live cells. Methods: display(update_board) -- Display the state of the board on-screen. erase() -- clear the entire board makeRandom() -- fill the board randomly set(x,y) -- set the given cell to Live; doesn't refresh the screen toggle(x,y) -- change the given cell from live to dead, or vice versa, and refresh the screen display """ def __init__(self, xsize, ysize): """Create a new LifeBoard instance. scr -- curses screen object to use for display char -- character used to render live cells (default: '*') """ self.state = set() self.xsize, self.ysize = xsize, ysize def is_legal(self, x, y): "Returns true if the x,y coordinates are legal for this board." return (0 <= x < self.xsize) and (0 <= y < self.ysize) def set(self, x, y): """Set a cell to the live state.""" if not self.is_legal(x, y): raise ValueError("Coordinates {}, {} out of range 0..{}, 0..{}".format( x, y, self.xsize, self.ysize)) key = (x, y) self.state.add(key) def makeRandom(self): "Fill the board with a random pattern" self.erase() for i in range(0, self.xsize): for j in range(0, self.ysize): if random.random() > 0.5: self.set(i, j) def toggle(self, x, y): """Toggle a cell's state between live and dead.""" if not self.is_legal(x, y): raise ValueError("Coordinates {}, {} out of range 0..{}, 0..{}".format( x, y, self.xsize, self.ysize)) key = (x, y) if key in self.state: self.state.remove(key) else: self.state.add(key) def erase(self): """Clear the entire board.""" self.state.clear() def step(self): "Compute one generation, updating the display." d = set() for i in range(self.xsize): x_range = range( max(0, i-1), min(self.xsize, i+2) ) for j in range(self.ysize): s = 0 live = ((i,j) in self.state) for yp in range( max(0, j-1), min(self.ysize, j+2) ): for xp in x_range: if (xp, yp) in self.state: s += 1 # Subtract the central cell's value; it doesn't count. s -= live ##print(d) ##print(i, j, s, live) if s == 3: # Birth d.add((i,j)) elif s == 2 and live: # Survival d.add((i,j)) elif live: # Death pass self.state = d # # Display-related methods # def draw(self, x, y): "Update the cell (x,y) on the display." turtle.penup() key = (x, y) if key in self.state: turtle.setpos(x*CELL_SIZE, y*CELL_SIZE) turtle.color('black') turtle.pendown() turtle.setheading(0) turtle.begin_fill() for i in range(4): turtle.forward(CELL_SIZE-1) turtle.left(90) turtle.end_fill() def display(self): """Draw the whole board""" turtle.clear() for i in range(self.xsize): for j in range(self.ysize): self.draw(i, j) turtle.update() def display_help_window(): from turtle import TK root = TK.Tk() frame = TK.Frame() canvas = TK.Canvas(root, width=300, height=200, bg="white") canvas.pack() help_screen = turtle.TurtleScreen(canvas) help_t = turtle.RawTurtle(help_screen) help_t.penup() help_t.hideturtle() help_t.speed('fastest') width, height = help_screen.screensize() line_height = 20 y = height // 2 - 30 for s in ("Click on cells to make them alive or dead.", "Keyboard commands:", " E)rase the board", " R)andom fill", " S)tep once or", " C)ontinuously -- use 'S' to resume stepping", " Q)uit"): help_t.setpos(-(width / 2), y) help_t.write(s, font=('sans-serif', 14, 'normal')) y -= line_height def main(): display_help_window() scr = turtle.Screen() turtle.mode('standard') xsize, ysize = scr.screensize() turtle.setworldcoordinates(0, 0, xsize, ysize) turtle.hideturtle() turtle.speed('fastest') turtle.tracer(0, 0) turtle.penup() board = LifeBoard(xsize // CELL_SIZE, 1 + ysize // CELL_SIZE) # Set up mouse bindings def toggle(x, y): cell_x = x // CELL_SIZE cell_y = y // CELL_SIZE if board.is_legal(cell_x, cell_y): board.toggle(cell_x, cell_y) board.display() turtle.onscreenclick(turtle.listen) turtle.onscreenclick(toggle) board.makeRandom() board.display() # Set up key bindings def erase(): board.erase() board.display() turtle.onkey(erase, 'e') def makeRandom(): board.makeRandom() board.display() turtle.onkey(makeRandom, 'r') turtle.onkey(sys.exit, 'q') # Set up keys for performing generation steps, either one-at-a-time or not. continuous = False def step_once(): nonlocal continuous continuous = False perform_step() def step_continuous(): nonlocal continuous continuous = True perform_step() def perform_step(): board.step() board.display() # In continuous mode, we set a timer to display another generation # after 25 millisenconds. if continuous: turtle.ontimer(perform_step, 25) turtle.onkey(step_once, 's') turtle.onkey(step_continuous, 'c') # Enter the Tk main loop turtle.listen() turtle.mainloop() if __name__ == '__main__': main() ```

Code Discussion¶

The `LifeBoard` class has a `state` attribute that’s a set of (X,Y) tuples that contain live cells. The coordinate values can vary between 0 and an upper limit specified by the `xsize` and `ysize` attributes.

The `step()` method computes a single Life generation. It loops over the entire board, and for each cell the code counts the number of live cells surrounding it. A new set is used to record the cells that are live in the new generation, and after the whole board has been scanned, the new set replaces the existing `state`.

The size of the `state` set is therefore proportional to the number of live cells at any given time. Another approach would be just to have an N x N array representing the board, which would require a fixed amount of memory.

If there are only a few live cells on a large board, most of the time will be spent scanning empty areas of the board where we know nothing is going to happen. Cells never come alive spontaneously, without any live neighbours. Therefore, one minor optimization is to record the minimum and maximum coordinates of live cells, and then limit the scanning accordingly. An entirely different approach called Hashlife represents the board as a quadtree, a 2-dimensional tree structure, and relies on large Life patterns often containing many copies of similar structures. (See the references for an explanation of Hashlife.)

Lessons Learned¶

Part of what makes Life so fascinating is that it’s easy to ask questions and then try to answer them. For example, if you start with a straight line of N cells, which values of N produce interesting patterns? What if you make squares, or two lines of cells? This leads to asking more theoretical questions: are there Life patterns that can make copies of themselves? How fast can a spaceship move? You can get an idea of the complexity hiding inside Life by exploring some of the references for this section.

You may wonder if there’s anything special about the rules that Conway chose for Life. For example, what if live cells survived when they had four neighbours instead of dying? You can easily experiment with different rules by modifying the `life.py` program. Mirek Wojtowicz has written a list of alternate rules at http://www.mirekw.com/ca/rullex_life.html and comments on the different properties of the resulting simulations.

People have also created many other cellular automata that change other aspects such as:

• having the world be a 3-dimensional grid of cubes or a 1-dimensional line of cells instead of a 2-dimensional grid.
• use a triangular or hexagonal grid instead of a square one.
• have multiple colours for live cells; a newborn cell’s can either be the majority colour of its neighbours, or
• have the cells containing decimal values between 0 and 1, instead of restricting values to only 0 and 1.

Fairly soon after Life was invented, Conway proved that there existed Life patterns that were equivalent to a Turing Machine and therefore could carry out any computable function. In April 2000, Paul Rendell actually constructed a Life pattern that behaved like a Turing machine.

References¶

Relevant web pages, books, with an annotation about why it’s notable or worthwhile.

http://www.math.com/students/wonders/life/life.html
An introductory article by Paul Callahan. The web page includes a Java applet that’s similar to our Python application.
http://www.nytimes.com/1993/10/12/science/scientist-at-work-john-h-conway-at-home-in-the-elusive-world-of-mathematics.html
A New York Times profile of mathematician John H. Conway, who invented Life.
http://www.ibiblio.org/lifepatterns/october1970.html
A copy of Martin Gardner’s 1970 Scientific American article that started it all.
http://home.interserv.com/~mniemiec/lifeterm.htm
A glossary of Life terminology.
http://www.conwaylife.com/wiki/
LifeWiki contains over a thousand Wiki articles about Life, including definitions of terms and descriptions of various patterns.
http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478
An April 2006 article by Tomas G. Rokicki that explains the HashLife algorithm and implements it in Java.