Conway's Game of Life

An Introduction to Cellular Automata

The Game of Life

The Game of Life is a cellular automaton devised by the british mathematician John Horton Conway in 1970. It was popularised by Martin Gardner in his October 1970 column of "Mathematical Games" in the "Scientific American" magazine [6]. The article garnered more response than any other of his previous articles in the magazine, including Gardners famous article on Hexaflexagons.

(Patterns Courtesy of LifeWiki)

What is a Cellular Automaton?

A Cellular automaton is a discrete model that consists of a regular grid of cells wherein each cell is in a finite state. The inital state of the cellular automate is selected by assigning a state to each cell. The simulation then progresses in discreet time steps. The state of a cell at timestep t depends only on the state of nearby cells at timestep t-1 and a set of rules specific to the automate.

Cell Neighboorhoods

The cells which have an influence on the state of the automate are called neighborhood. There are two commonly used types of neighborhoods: The Moore Neighborhood and the Van Neumann Neighborhood. The Moore neighborhood contains all neighboring cells even if they share only a cornerpoint with a cell whilst the Van Neumann Neighborhood contains only cells that share an edge with a cell.

Van Neumann Neighborhood and Moore Neighborhood
Image: Left Moore Neighborhood of the cell C. Right: Van Neumann Neighborhood.

Rules of the Game of Life

In the Game of Life each grid cell can have either one of two states: dead or alive. The Game of Life is controlled by four simple rules which are applied to each grid cell in the simulation domain:

  • A live cell dies if it has fewer than two live neighbors.
  • A live cell with two or three live neighbors lives on to the next generation.
  • A live cell with more than three live neighbors dies.
  • A dead cell will be brought back to live if it has exactly three live neighbors.
Rules of the Game of Life

Boundary Conditions

Cellular automata often use a toroidal topology of the simulation domain. This means that opposing edges of the grid are connected. The rightmost column is the neighbor of the leftmost column and the topmost row is the neighbor of the bottommost row and vice versa. This allows the unrestricted transfer of state information across the boundaries.

Opposing Edges of the Simulation domain are Connected
Image: Different boundary conditions of the Game Of Life; Left: Opposing edges of the grid are connected to form a toroidal topology of the simulation domain; Right: Cells beyond the grid boundary are always treated as if they were dead.

Another type of boundary condition treats nonexisting cells as if they all had the same state. In the Game of Life this would mean that nonexisting cells are treated as if they were dead (as opposed to the second state "alive"). The advantage of this boundary condition in the Game of Life is that it prevents gliders from wrapping around the edges of the simulation domain. This will prevent the destruction of a glider gun by the gliders it produces (see text below below for details about what gliders are).

Pattern Examples

Patterns will appear in a typical run of the Game of Life. Some patterns are static, others are oscillating or are moving across the screen. Some Patterns may even produce other patterns. The following tables give an overview on commonly appearing patterns in the Game of Life.

Still Lifes
Block:
The Block is the most common still life. It consists of four cells forming a 2x2 block. The block is a so called eater. This means it can destroy other patterns without suffering lasting damage to itself.
Beehive:
The beehive is a still life consisting of 6 cells. It is the second most common still life.
Loaf:
The loaf is a 7 cell still life. It is the third most common still life.
Oscillators
Blinker:
The smallest and most common oscillator.
Toad:
The Toad is a period 2 oscillator. It is the second most common naturally occuring oscillator.
Beacon:
The third most common naturally occuring oscillator. It is composed of two diagonally touching blocks.
Spaceships
The Glider:
The glider is a pattern that is moving diagonally across the screen. It is the smallest, most common, and first-discovered spaceship.
Lightweight spaceship (LWSS):
This is an oscillating object that is moving orthogonally across the screen. It is the smallest orthogonally moving spaceship.
Weekender:
This is an orthogonal spaceship that is slightly larger than the previous patterns.

Inventing the Game of Life

John Conway gave an interesting interview on the youtube channel Numberphile [1] where he provided insight on the origins of the Game of Life. If you are interested what the terraforming of Mars has to do with the game of life I highly recommend watching it.

External Content: Video courtesy of Youtube / Numberphile

Video: John Horton Conway in an interview with the youtube channel Numberphile .

Recent developments

Being devised in 1970 the Game of Life is a thing from the early years of computing. If you listened to John Conways interview you may have noticed him mentioning that the Game of Life was investigated on paper in the early years. With the advent of home computers it gained in popularity and is now something most people who start programming will come across earlier or later. It's like the "Hello World" of graphics programming. What makes the game of life fascinating is the simplicity of its rules and the complexity of the patterns the result from this simple set of rules. The following sections will discuss some of the more recent findings of the community evolving around the "Game of Life".

The OCTA metapixel

In the interview with Numberphile John Conway mentioned that the Game of Life could be used for arbitrary computation. If you ask yourself what this means and how this is supposed to look like you should have a look at the following Video demonstrating the implementation of Game of Life in Game of Life.

External Content: Video courtesy of Youtube / Phillip Bradbury

Video: "Life in Life" by Phillip Bradbury [3]. Created with the life simulator Golly using the OCTA metapixel

The basic building block of this simulation is the OCTA metapixel [3]. This is a 2048 x 2048 Unit cell designed by Brice Due in the year 2006. A unit cell is a construct in a cellular automaton that is capable of simulating another cellular automate possibly itself. There are other Unit cells like the P5760 unit Life cell devised earlier but the OCTA metapixel is unique in its resemblence of an actual cell. As far as i'm concerned this is close to black magic and a beautiful thing to watch.

Smooth Life

Smooth Life is the extension of the Game of Life to a continuous domain. It is using floating point values instead of integers. The SmoothLife rules were created by Stephan Rafler [5]. The video shown below was created by Tim Hutton with SmoothLife. A more extensive collection of SmoothLife videos can be found on the SmoothLife Video Channel.

External Content: Video courtesy of Youtube / Tim Hutton

Video: SmoothLife shows many of the well known structures from the Game of Life such as Gliders in a stunningly beautiful visualization that is looking like microbial life forms. (Video © 2012; Tim Hutton)

Trivia

  • If you google "Conways Game Of Life" you will see the game of life running on the upper right corner of the results page

References

  1. “Inventing Game of Life - Numberphile.” Youtube, Interview with John Conway on the youtube channel numberphile, Web.
  2. “Life in Life.” Youtube, Channel of Phillip Bradbury, Web.
  3. “OTCAmetapixel - How does is work” A website with explanations of the Octa metapixel, Web.
  4. “OTCA metapixel” Article at LifeWiki explaining the OCTA metapixel, Web.
  5. “Generalization of Conway's "Game of Life" to a continuous domain - SmoothLife” Stephan Rafler, 2011
  6. The fantastic combinations of John Conway's new solitaire game "life"", Scientific American 223, Pages 120-123, Martin Gardner, October 1970
  7. Game of Life, Scholarpedia, Eugene M. Izhikevich, Dr. John H. Conway, Anil Seth, 2015-06-12, Webpage
back     

You might also like: