Conway’s Game of Life

One of the early examples of cellular automata to be popularized was John Conway’s ‘Game of Life’. You start with an infinite two-dimensional grid of cells, each of which is in one of two states: ‘dead’ or ‘alive’. (In practice, this is usually implemented by coloring the dead pixels black and the live ones white, or vice versa.) Each cell has eight neighboring cells — the four orthogonally adjacent cells and the four diagonally adjacent cells. Based on the initial position of the live and dead cells, the arrangement ‘evolves’ according to a set of simple rules:

  1. Any live cell with fewer than two live neighbors dies (underpopulation).
  2. Any live cell with exactly two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies (overpopulation).
  4. Any dead cell with exactly three live neighbours becomes a live cell (reproduction).

The ‘game’ was invented in 1970 and has been extensively analyzed and explored. Here’s a quick demonstration that I coded in my pattern formation course, taught by Prof. Ted Kim. The initial setup is an R-pentomino, which expands rapidly.

I also made a few modifications as an exploration. One of the major implementation concerns are boundary conditions — although the game in theory is played on an infinite grid, computers work with a finite amount of memory. One solution is to treat the boundary as a dead zone. Another is to use a ‘wrap-around’ effect, essentially mapping the grid to the fundamental polygon of a torus. I decided to try out a more exotic concept, mapping the grid to the fundamental polygon of the real projective plane. In addition, I relaxed the ‘birth’ rules to include having only two live neighbors. Here are the results.

My classmates are also producing interesting content, which you can view on our course blog.