Game of Life

  • The game of life (GOL) is a two state discrete cellular automaton.
  • Like so much of computing the origins of cellular automata can be traced back to John von Neumann (and a colleague, not as well known, Stanislaw Ulam) working at the Los Alamos National Laboratory in the 1940s.
  • Von Neumann was working on the problem of self-replicating systems, or if you like 'one robot building another robot'. His compiled lecture notes are available here and make fascinating reading.
  • Ulam was the one who suggested using a discrete system for creating a reductionist model of self-replication.
  • GOL was devised by John Conway and is sometimes known as Conway's Game of Life but it was popularised by the hugely influential Martin Gardener in 1970.
  • Ever since its publication GOL has attracted interest, because it provides example of emergence, self-replication and self-organization from very simple rules.

Rules for the simple 1d cellular automata exercise

  1. If a cell is alive in one generation, it will be dead in the next ie each cell has a lifespan of one iteration.
  2. If a cell is dead but has one and only one live neighbour, it will come alive in the next generation ie new lives are born if no overcrowding.

The code that generated this figure can be found here and click here for an explanation of how the code is built.

Rules for the 2D version

Game of Life plays out on an infinite two-dimensional orthogonal grid of cells, each of which is in one of two possible states, alive or dead (black = alive, white = dead). Every cell interacts with its eight neighbours. At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.