The Game of Life

A so called spaceship pattern in Conways Game of Life

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

A notable property of the special rule set used by Conway's "Game of Life" is it's Turing completeness. The Turing completeness is a property that describes that a programming language, a simulation or a logical system is in principle suitable to solve every computing problem. The programming of the "Game of Life" would be done with patterns, which then interact with each other in the simulation. LifeWiki has a large archive of such patterns for Game of Life. A selection of those is implemented in the applet shown below.

Because of the simplicity of the rule set, implementing Game of Life is a popular task for novice programmers. The source code of the "Game of Life" applet used here is written in Typescript and can be downloaded from GitHub. A description of the implementation of the Game of Life in Python can be found in another article on this website.

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 Neighborhoods

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.

Moore Neighborhood

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.

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 grid are connected to form a toroidal topology of the simulation domain

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

Still lifes are static structures that do not change over time.

Block

The block is the most common "still life". It consists of four cells that form a 2x2 block. A block is a so-called "eater". This means that it can destroy other patterns without being structurally damaged.

Beehive:

A "still life" consisting of 6 cells. The second most common still life.

Loaf:

A still life consisting of 7 cells. The third most common still life.

Oscillators

Oscillators are structures that repeat periodically over time, but maintain their position.

Spaceships

Spaceships are structures that move across the playing field of the "Game of Life".

Who was John Conway?

John Horton Conway (December 26, 1937 in Liverpool, UK; † April 11, 2020 in New Brunswick) was a British mathematician. He was working in the fields of finite groups, node theory, number theory, coding theory, combinatorial game theory and made many contributions to recreational mathematics.

Conway grew up in Liverpool. He spent the first part of his career at the University of Cambridge. He later moved to the University of Princeton in the USA, where he took over the chair from John von Neumann, which he held until the end of his career. For his work he received the Berwick Prize in 1971 and the Pólya Prize in 1987 from the Lonon Mathematical Society. In 1981 he became a fellow of the Royal Society. In 1992 he was elected to the American Academy of Arts and Sciences and in 2000 was awarded the Leroy P. Steele Prize by the American Mathematical Society.

One of his best-known works among non-mathematicians is the invention of the "Game of Life." Conway himself said in an interview with the YouTube channel Numberphile [7] that he did not find it to be particularly interesting. Therefore he did not understand the attention it generated. In his opinion, "Game of Life" overshadowed more important mathematical achievements. At times he hated being asked about it. Nevertheless in later years he also said it is something of which he was proud of.[7].

On April 11, 2020, Conway died of complications from a COVID-19 disiease.

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.

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

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.

Trivia / Eastereggs

• 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” An archived website with explanations of the Octa metapixel, Archive.org.
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