Conway's Game of Life

The Game of Life, also known as Conway's Game of Life (sometimes abbreviated as CGoL) or simply Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.[1] It is a zero-player game,[2] meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves in discrete time steps called generations. There is no limit to the number of generations (computational resources permitting) nor is there a win condition.

The Game of Life is played on an infinite square grid, with each cell being in one of two states: live or dead. Cells in configurations called patterns evolve over generations according to the number of live and dead cells in their Moore neighborhood, that is, the eight cells in their immediate proximity.

Patterns can be grouped into different types, such as still lifes, oscillators, and spaceships.

The Game of Life was first simulated manually, with computerized simulations arriving soon afterwards. Nowadays, more modern programs such as Golly are used. These programs often do not store cells as two-dimensional arrays, instead using algorithms such as Hashlife which represent patterns as a tree structure.

The Game of Life has spawned a number of other cellular automata, known as Life-like cellular automata. Examples include Highlife and Seeds. Other variations may include more than two states or use a non-square grid.

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours (its Moore neighborhood), which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

This makes it described by the rulestring B3/S23,[nb 1] where the numbers before the slash signify conditions for dead cells becoming alive, and the ones after it signifying survival conditions for cells that are already alive.[4]: 5

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, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick.{{cite web|title=NaiveLife Emulated: A reading-order simulation of Life|url=https://conwaylife.com/forums/viewtopic.php?f=11&t=4523&p=128919|website=ConwayLife.com|access-date=29 November 2021|language=en|date=24 May 2020}}</ref><ref>{{cite web|last1=Goucher|first1=Adam|title=Re: Thread For Your Accidental Discoveries|url=https://conwaylife.com/forums/viewtopic.php?f=2&t=279&p=13168#p13168|website=ConwayLife.com|access-date=29 November 2021|language=en|archive-date=29 November 2021|archive-url=https://web.archive.org/web/20211129154301/https://www.conwaylife.com/forums/viewtopic.php?f=2&t=279&p=13168#p13168|url-status=live}}</ref> because it is a common beginners' mistake among people attempting to program Conway's Game of Life.<ref>{{cite web|author1=((Ian07))|title=Re: Strange spaceship that is supposed to be impossible and infinite cell spread|url=https://conwaylife.com/forums/viewtopic.php?f=9&t=4288&p=88701#p88701|archive-date=29 November 2021|archive-url=https://web.archive.org/web/20211129164454/https://conwaylife.com/forums/viewtopic.php?f=9&t=4288&p=88701#p88701|website=ConwayLife.com|access-date=29 November 2021|language=en|quote=''I'm pretty sure this is because you've accidentally created an implementation of what's sometimes known as NaiveLife (as it's a common mistake made by many people coding CGoL for the first time): ''}}</ref>"},"2":{"wt":"group="nb""}},"i":0}}]}'>[nb 2] Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

In the editable widget below, one of the patterns discovered by Conway, the I-heptomino can be simulated.

Cellular automata have their origins in the work of Stanisław Ulam and John von Neumann in the 1940s. Development continued through the 1950s and 1960s when, in 1968, John Horton Conway began doing experiments with a variety of different two-dimensional cellular automaton rules. Conway's initial goal was to define an interesting and unpredictable cellular automaton. According to Martin Gardner, Conway experimented with different rules, aiming for a ruleset that would allow for patterns to "apparently" grow without limit, while keeping it difficult to prove that any given pattern would do so. Moreover, some "simple initial patterns" should "grow and change for a considerable period of time" before settling into a static configuration or a repeating loop.[1] Conway later wrote that the basic motivation for Life was to create a "universal" cellular automaton.[8][better source needed]

The game made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column, which was based on personal conversations with Conway. Theoretically, the Game of Life has the power of a universal Turing machine: anything that can be computed algorithmically can be computed within the Game of Life.[9][2] Gardner wrote, "Because of Life's analogies with the rise, fall, and alterations of a society of living organisms, it belongs to a growing class of what are called 'simulation games' (games that resemble real-life processes)."[1]

The popularity of the Game of Life was helped by its coming into being at the same time as increasingly inexpensive computer access. The game could be run for hours on these machines, which would otherwise have remained unused at night. In this respect, it foreshadowed the later popularity of computer-generated fractals. For many, the Game of Life was simply a programming challenge: a fun way to use otherwise wasted CPU cycles. It developed a cult following through the 1970s and beyond; current developments have gone so far as to create theoretic emulations of computer systems within the confines of a Game of Life board.[10]

Many different types of patterns occur in the Game of Life, which are classified according to their behaviour. Common pattern types include still lifes, which do not change from one generation to the next; oscillators, which return to their initial state after a finite number of generations; and spaceships, which translate themselves across the grid.[4]: 4, 6

The earliest interesting patterns in the Game of Life were discovered without the use of computers. The simplest still lifes and oscillators were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, and physical game boards, such as those used in Go. During this early research, Conway discovered that the R-pentomino failed to stabilize in a small number of generations. In fact, it takes 1103 generations to stabilize, by which time it has a population of 116 and has generated six escaping gliders; these were the first spaceships ever discovered.[11]

Frequently occurring[12][13] examples (in that they emerge frequently from a random starting configuration of cells called soups[4]: 5 ) of the three aforementioned pattern types are shown below, with live cells shown in black and dead cells in white. Period refers to the number of ticks a pattern must iterate through before returning to its initial configuration.

The pulsar[14] is the most common period-3 oscillator.[15] The great majority of naturally occurring oscillators have a period of 2, like the blinker and the toad, but oscillators of all periods are known to exist,[16][17] and oscillators of periods 4, 8, 14, 15, 30, and a few others have been seen to arise from random initial conditions.[18] Patterns which evolve for long periods before stabilizing are called methuselahs, the first-discovered of which was the R-pentomino. Diehard is a pattern that disappears after 130 generations. Starting patterns of eight or more cells can be made to die after an arbitrarily long time.[19] Acorn takes 5,206 generations to generate 633 cells, including 13 escaped gliders.[20]

Conway originally conjectured that no pattern can grow indefinitely—i.e. that for any initial configuration with a finite number of living cells, the population cannot grow beyond some finite upper limit. In the game's original appearance in "Mathematical Games", Conway offered a prize of fifty dollars (equivalent to $415 in 2025) to the first person who could prove or disprove the conjecture before the end of 1970. The prize was won in November by a team from the Massachusetts Institute of Technology, led by Bill Gosper; the "Gosper glider gun" produces its first glider on the 15th generation, and another glider every 30th generation from then on. For many years, this glider gun was the smallest one known.[21] In 2015, a gun called the "Simkin glider gun", which releases a glider every 120th generation, was discovered that has fewer live cells but which is spread out across a larger bounding box at its extremities.[22]

Smaller patterns were later found that also exhibit infinite growth. All three of the patterns shown below grow indefinitely. The first two create a single block-laying switch engine: a configuration that leaves behind two-by-two still life blocks as it translates itself across the game's universe. The third configuration creates two such patterns. The first has only ten live cells, which has been proven to be minimal.[23] The second fits in a five-by-five square, and the third is only one cell high.

Later discoveries included other guns, which are stationary, and which produce gliders or other spaceships; puffer trains, which move along leaving behind a trail of debris; and rakes, which move and emit spaceships.[24] Gosper also constructed the first pattern with an asymptotically optimal quadratic growth rate, called a breeder, which worked by leaving behind a trail of guns.[25]

It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in a specific position, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This sliding block memory can be used to simulate a counter. It is possible to construct logic gates such as AND, OR, and NOT using gliders. It is possible to build a pattern that acts like a finite-state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete.[9][2] In fact, several different programmable computer architectures[26][27] have been implemented in the Game of Life, including a pattern that simulates Tetris.[28]

Until the 2010s, all known spaceships could only move orthogonally or diagonally. Spaceships which move neither orthogonally nor diagonally are commonly referred to as oblique spaceships.[29] On May 18, 2010, Andrew J. Wade announced the first oblique spaceship, dubbed "Gemini", that creates a copy of itself on (5,1) further while destroying its parent.[30] This pattern replicates in 34 million generations, and uses an instruction tape made of gliders oscillating between two stable configurations made of Chapman–Greene construction arms. These, in turn, create new copies of the pattern, and destroy the previous copy. In December 2015, diagonal versions of the Gemini were built.[31]

A more specific case is a knightship, a spaceship that moves two squares left for every one square it moves down (like a knight in chess), whose existence had been predicted by Elwyn Berlekamp since 1982. The first elementary knightship, Sir Robin, was discovered in 2018 by Adam P. Gou