Conway's Game of Life

Conway's Game of Life, also known as the Game of Life or simply Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is the best-known example of a cellular automaton.

Conway's Game of Life
View animated image
Rulestring 23/3
B3/S23
Rule integer 6152
Character Chaotic
Black/white reversal B0123478/S01234678

The "game" is actually a zero-player game, meaning that its evolution is determined by its initial state, needing no input from human players. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.

Rules

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. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbours dies (referred to as underpopulation or exposure[1]).
  2. Any live cell with more than three live neighbours dies (referred to as overpopulation or overcrowding).
  3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
  4. Any dead cell with exactly three live neighbours will come to life.

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 happen 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 one before.) The rules continue to be applied repeatedly to create further generations.

Origins

Conway was interested in a problem presented in the 1940s by renowned mathematician John von Neumann, who tried to find a hypothetical machine that could build copies of itself and succeeded when he found a mathematical model for such a machine with very complicated rules on a rectangular grid. The Game of Life emerged as Conway's successful attempt to simplify von Neumann's ideas. The game made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column, under the title of The fantastic combinations of John Conway's new solitaire game "life". From a theoretical point of view, it is interesting because it has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life. Gardner wrote:

The game made Conway instantly famous, but it also opened up a whole new field of mathematical research, the field of cellular automata ... 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)

Ever since its publication, Conway's Game of Life has attracted much interest because of the surprising ways in which the patterns can evolve. Life is an example of emergence and self-organization. It is interesting for physicists, biologists, economists, mathematicians, philosophers, generative scientists and others to observe the way that complex patterns can emerge from the implementation of very simple rules. The game can also serve as a didactic analogy, used to convey the somewhat counterintuitive notion that "design" and "organization" can spontaneously emerge in the absence of a designer. For example, philosopher and cognitive scientist Daniel C. Dennett has used the analog of Conway's Life "universe" extensively to illustrate the possible evolution of complex philosophical constructs, such as consciousness and free will, from the relatively simple set of deterministic physical laws governing our own universe.[2][3][4]

The popularity of Conway's Life was helped by its coming into being just in time for a new generation of inexpensive minicomputers which were being released into the market, meaning that the game could be run for hours on these machines which were otherwise unused at night. In this respect it foreshadowed the later popularity of computer-generated fractals. For many, Life was simply a programming challenge; a fun way to waste CPU cycles. For some, however, Life had more philosophical connotations. 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 Life board.

Conway chose his rules carefully, after considerable experimentation, to meet three criteria:

  1. There should be no initial pattern for which there is a simple proof that the population can grow without limit.
  2. There should be initial patterns that apparently do grow without limit.
  3. There should be simple initial patterns that grow and change for a considerable period of time before coming to an end in the following possible ways:
    • Fading away completely (from overcrowding or from becoming too sparse); or
    • Settling into a stable configuration that remains unchanged thereafter, or entering an oscillating phase in which they repeat an endless cycle of two or more periods.

Patterns
Main article: Patterns

Many different types of patterns occur in the Game of Life, including static patterns ("still lives"), repeating patterns ("oscillators" – a superset of still lives), and patterns that translate themselves across the board ("spaceships"). Common examples of these three classes are shown below, with live cells shown in black, and dead cells shown in white.

Gosper glider gun

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 $50 prize to the first person who could prove or disprove the conjecture before the end of 1970. One way to disprove it would be to discover patterns that keep adding counters to the field: a "gun", which would be a configuration that repeatedly shoots out moving objects such as the "glider", or a "puffer train", which would be a configuration that moves but leaves behind a trail of persistent "smoke".

The prize was won in November of the same year by a team from the Massachusetts Institute of Technology, led by Bill Gosper; the "Gosper glider gun" shown to the right produces its first glider on the 15th generation, and another glider every 30th generation from then on. This first glider gun still has a smaller bounding box than any other known gun, and among single-barrelled guns shares the record for lowest population with the Simkin glider gun.

Later discoveries included other guns, puffers, and "rakes", which move and emit spaceships. Gosper also constructed the first pattern with an asymptotically optimal quadratic growth rate, called a "breeder", or "lobster", which worked by leaving behind a trail of guns.

Iteration

From a random initial pattern of living cells on the grid, observers will find the population constantly changing as the generations tick by. The patterns that emerge from the simple rules may be considered a form of beauty. Small isolated subpatterns with no initial symmetry tend to become symmetrical. Once this happens the symmetry may increase in richness, but it cannot be lost unless a nearby subpattern comes close enough to disturb it. In a very few cases the society eventually dies out, with all living cells vanishing, though this may not happen for a great many generations. Most initial patterns eventually "burn out", producing either stable figures or patterns that oscillate forever between two or more states (known as ash); many also produce one or more gliders or spaceships that travel indefinitely away from the initial location.

Algorithms
R-pentomino

The earliest results in the Game of Life were obtained without the use of computers. The simplest still-lives and oscillators were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, physical game boards (such as Go) and the like. During this early research, Conway discovered that the R-pentomino failed to stabilize in a small number of generations.

These discoveries inspired computer programmers over the world to write programs to track the evolution of Life patterns. Most of the early algorithms were similar. They represented Life patterns as two-dimensional arrays in computer memory. Typically two arrays are used, one to hold the current generation and one in which to calculate its successor. Often 0 and 1 represent dead and live cells, respectively. A double loop considers each element of the current array in turn, counting the live neighbours of each cell to decide whether the corresponding element of the successor array should be 0 or 1. The successor array is displayed. For the next iteration the arrays swap roles so that the successor array in the last iteration becomes the current array in the next iteration.

A variety of minor enhancements to this basic scheme are possible, and there are many ways to save unnecessary computation. A cell that did not change at the last time step, and none of whose neighbours changed, is guaranteed not to change at the current time step as well, so a program that keeps track of which areas are active can save time by not updating the inactive zones.

In principle, the Life field is infinite, but computers have finite memory, and usually array sizes must be declared in advance. This leads to problems when the active area encroaches on the border of the array. Programmers have used several strategies to address these problems. The simplest strategy is simply to assume that every cell outside the array is dead. This is easy to program, but leads to inaccurate results when the active area crosses the boundary. A more sophisticated trick is to consider the left and right edges of the field to be stitched together, and the top and bottom edges also, yielding a toroidal array. The result is that active areas that move across a field edge reappear at the opposite edge. Inaccuracy can still result if the pattern grows too large, but at least there are no pathological edge effects. Techniques of dynamic storage allocation may also be used, creating ever-larger arrays to hold growing patterns.

Alternatively, the programmer may abandon the notion of representing the Life field with a 2-dimensional array, and use a different data structure, like a vector of coordinate pairs representing live cells. This approach allows the pattern to move about the field unhindered, as long as the population does not exceed the size of the live-coordinate array. The drawback is that counting live neighbours becomes a search operation, slowing down simulation speed. With more sophisticated data structures this problem can also be largely solved.

For exploring large patterns at great time depths, sophisticated algorithms like Hashlife may be useful.

There is also a method for implementation of the Game of Life using arbitrary asynchronous updates but still exacting emulating the behaviour of the synchronous game, also applicable to other cellular automata.[5]

Variations on Life
Main article: Life-like cellular automaton

Since Life's original inception, new rules have been developed based on similar ideas. The standard Game of Life, in which a cell is "born" if it has exactly 3 neighbours, stays alive if it has 2 or 3 living neighbours, and dies otherwise, is symbolised as "B3/S23". The first set of numbers, indicated by "B" for birth, is the list of numbers of neighbours a dead cell can have in order to be born in the next generation. The second set, indicated by "S" for survival, is what is required for a living cell to continue. Hence "B6/S16" means "a cell is born if there are 6 neighbours, and lives on if there are either 1 or 6 neighbours". HighLife is B36/S23, because having 6 neighbours, in addition to the original game's B3/S23 rule, causes a birth. HighLife is best known for its replicators.

This can be further generalized to non-totalistic rules, which consider the positions of living cells in a given cell's neighbourhood rather than merely the number of them when determining birth and survival. Some well known non-totalistic variations on Life are tlife and Snowflakes, the former itself having many variants of interest. Additional variations on Life exist, although the vast majority of these universes are either too chaotic or desolate to warrant extensive exploration.

Other popular types of cellular automata include Generations rules such as Brian's Brain in which cells "age" over time rather than dying immediately, and Larger than Life rules such as Bugs which feature larger neighbourhoods to be considered. Some variations modify the geometry of the universe as well as the rule. The above variations can be thought of as 2D Square, because the world is two-dimensional and laid out in a square grid. 3D Square and 1D Square variations have been developed, as have 2D Hexagonal variations where the grid is hexagonal or triangular instead of square.

Conway's rules may also be generalized so that instead of two states (live and dead) there are three or more. State transitions are then determined either by a weighting system or by a table specifying separate transition rules for each state; for example, Mirek's Cellebration's multi-coloured "Rules Table" and "Weighted Life" rule families each include sample rules equivalent to Conway's Life.

Patterns relating to fractals and fractal systems may also be observed in certain Life-like variations. For example, the automaton 12/1 generates four very close approximations to the Sierpiński triangle when applied to a single live cell.

Immigration is a variation that is the same as the Game of Life, except that there are two ON states (often expressed as two different colours). Whenever a new cell is born, it takes on the ON state that is the majority in the three cells that gave it birth. This feature can be used to examine interactions between spaceships and other objects within the game. Another similar variation, called QuadLife, involves four different ON states. When a new cell is born from three different ON neighbours, it takes on the fourth value, and otherwise like Immigration it takes the majority value. Except for the variation among ON cells, both of these variations act identically to Life.

gollark: Hmm. PotatOS is not, in fact, security™ in this instance.
gollark: I can ship SHA256 inline (i.e. copypaste into source code) as it's only 3KB to protect against *accidental* tampering, but ECC is a giant 30KB library.
gollark: I should probably deal with this.
gollark: Hmm. Troubling.
gollark: Maybe it should just not require verification if there's no ECC library installed yet? But I feel like that could be exploited.

References
  1. "Exposure". The Life Lexicon. Stephen Silver.
  2. Dennett, D.C. (1991). Consciousness Explained. Boston: Back Bay Books. ISBN 0316180661
  3. Dennett, D.C. (1995). Darwin's Dangerous Idea: Evolution and the Meanings of Life. New York: Simon & Schuster. ISBN 068482471X
  4. Dennett, D.C. (2003). Freedom Evolves. New York: Penguin Books. ISBN 0142003840
  5. Nehaniv, Chrystopher L. (2002), "Self-Reproduction in Asynchronous Cellular Automata", 2002 NASA/DoD Conference on Evolvable Hardware (July 15-18, 2002, Alexandria, Virginia, USA), IEEE Computer Society Press, pp. 201-209
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.