Conway's Game of Life

From Wikipedia, the free encyclopedia

Gosper's Glider Gun creating "gliders".

The Game of 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.

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.

1 Rules
2 Origins
3 Iteration
4 Examples of patterns
5 Algorithms
6 Variations on Life
7 See also
8 External links
- 8.1 Patterns and pattern collections
- 8.2 Life program links

[edit] Rules

The universe of the Game of Life is an infinite two-dimensional square grid of square cells, each of which is in exactly one of two possible states, live or dead. Cells interact with their eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following effects occur:

Any live cell with fewer than two live neighbours dies, as if by loneliness.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any live cell with two or three live neighbours lives, unchanged, to the next generation.
Any dead cell with exactly three live neighbours comes to life.

The initial pattern constitutes the first generation of the system. The second generation is created by applying the above rules simultaneously to every cell in the first generation -- births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. The rules continue to be applied repeatedly to create further generations.

[edit] 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 Cartesian grid. Conway tried to simplify von Neumann's ideas and eventually succeeded. By coupling his previous success with Leech's problem in group theory with his interest in von Neumann's ideas concerning self-replicating machines, Conway devised the Game of Life.

It made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column. 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, it has attracted much interest because of the surprising ways 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.

Life has a number of recognised patterns which emerge from particular starting positions. Soon after publication, several interesting patterns were discovered, including the ever-evolving R-pentomino (more commonly known as "F-pentomino" outside the game), the self-propelling "glider", and various "guns" which generate an endless stream of new patterns, all of which led to increased interest in the game. Its popularity was helped by the fact that it came 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 aficionados 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 into the mid-1980s; 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:

There should be no initial pattern for which there is a simple proof that the population can grow without limit.
There should be initial patterns that apparently do grow without limit.
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:
1. Fading away completely (from overcrowding or from becoming too sparse); or
2. 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.

[edit] Iteration

From an initial pattern of living cells on the grid, observers will find, as the generations tick by, the population constantly undergoing unusual and always unexpected, change. The patterns that form from the simple rules may be considered a form of beauty. In a few cases the society eventually dies out, with all living cells vanishing, although this may not happen until after a great many generations. Most initial patterns either reach stable figures - Conway calls them "still lifes" - that cannot change or patterns that oscillate forever. Patterns with no initial symmetry tend to become symmetrical. Once this happens the symmetry cannot be lost, although it may increase in richness.

Conway originally conjectured that no pattern can grow without a limit. Thus, any configuration with a finite number of counters cannot grow beyond a finite upper limit to the number of counters on the field. This was probably the deepest and most difficult question posed by the game at the time. Conway offered a prize of $50 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 initial configuration (shown below) grows into such a gun, emitting the first glider on the 40th generation. The gun emits a new glider every 30th generation from then on.

[edit] Examples of patterns

The evolution and movement of a "glider".

There are all sorts of different patterns that occur in the Game of Life, including static patterns ("still lifes"), repeating patterns ("oscillators" - a superset of still lifes), and patterns that translate themselves across the board ("spaceships"). The simplest examples of these three classes are shown below, with live cells shown in black, and dead cells shown in white.


Block	Boat	Blinker	Toad	Glider	LWSS

The "block" and "boat" are still lifes, the "blinker" and "toad" are oscillators, and the "glider" and "lightweight spaceship" ("LWSS") are spaceships which steadily march their way across the grid as time goes on. Patterns called "Methuselahs" can evolve for long periods before repeating. "Diehard" is a pattern that eventually disappears after 130 generations, or steps. "Acorn" takes 5206 generations to generate 13 gliders then stabilizes as many oscillators.


Diehard	Acorn

In the game's original appearance in "Mathematical Games", Conway offered a cash prize for any patterns that grew indefinitely. The first of these was found by Bill Gosper in November 1970. They include "guns", which are stationary and shoot out gliders or other spaceships; "puffers", which move along leaving behind a trail of debris; and "rakes", which move and emit spaceships. Gosper also later discovered a pattern with a quadratic growth rate, called a "breeder", which worked by leaving behind a trail of guns. Since then, various complicated constructions have been made, including glider logic gates, an adder, a prime number generator, and a unit cell which emulates the Game of Life at a much larger scale and slower pace. The first glider gun discovered is still the smallest one known:

Gosper Glider Gun

Simpler patterns were later found that also have infinite growth. All three of the following patterns have infinite growth. The first two create one blocklaying switch engine each, while the third creates two. The first has only 10 live cells (which has been proven to be minimal). The second fits in a 5 x 5 square. The third is only 1 cell high:

It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in just the right way, 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 which 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 as powerful as any computer with unlimited memory: it is Turing complete. Furthermore, a pattern can contain a collection of guns that combine to construct new objects, including copies of the original pattern. A "universal constructor" can be built which contains a Turing complete computer, and which can build many types of complex objects, including more copies of itself. Descriptions of these constructions are given in Winning Ways by Conway, Elwyn Berlekamp and Richard Guy.

[edit] Algorithms

The earliest results in the Game of Life were obtained 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, physical game boards, for instance 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 neighbors 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 neighbors 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. 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 neighbors 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.

[edit] Variations on Life

Since Life's original inception, new rules have been developed. The standard Game of Life, in which a cell is "born" if it has exactly 3 neighbors, stays alive if it has 2 or 3 alive neighbors, and dies otherwise, is symbolized as "23/3". The first number, or list of numbers, is what is required for a cell to continue. The second set is the requirement for birth. Hence "16/6" means "a cell is born if there are 6 neighbours, and lives on if there are either 1 or 6 neighbours". HighLife is therefore 23/36, because having 6 neighbors, in addition to the original game's 23/3 rule, causes a birth. HighLife is best-known for its replicators. Additional variations on Life exist, although the vast majority of these universes are either too chaotic or desolate.

Additional variations have been designed by modifying other elements of the universe. 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 Hex 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 q states (where q ≥ 2). Taking q = 2 results in a cellular automaton whose rules are equivalent to Conway's. In this q-state Life one may find 'gliders', etc., as in Conway's Life, although they occur more rarely.

Other patterns, relating to fractals and fractal systems may also be observed in certain Life-like variations - e.g. the automaton 12/1 generates four very close approximations to the Sierpinski Triangle when applied to a single live cell.

[edit] See also

The Hacker Emblem is derived from Conway's Game of Life.

[edit] External links

Wikimedia Commons has media related to:

Game of Life

O'Connor, John J., and Edmund F. Robertson. "Conway's Game of Life". MacTutor History of Mathematics archive. (Some text, such as the rules, were taken from a Life version coded in Microsoft Visual Basic. The author of the software is unknown.)
Life Lexicon -- An interesting lexicon concerning the terminology of "Life".
Game of Life News - a blog reporting on recent developments in the Game of Life
Conway's Game of Life - Al Hensel
Eric Weisstein's Treasure Trove of the Life C.A. - a site by Dr. Eric Weisstein containing many descriptions and animations of Life patterns
Wonders of Math - The Game of Life - math.com
Patterns, Programs, and Links for Conway's Game of Life - Paul Callahan
Game of Life Information - H. Koenig
Information on the Game of Life - older site from H. Koenig
Jason’s Life Page
Stephen Silver's Life Page
David I. Bell's home page - Spaceship articles, programs and special pattern collections
Gabriel Nivasch's Game of Life page
Andrzej Okrasinski Game of Life website
Achim's Game of Life Page
LIFEPAGE - Robert T. Wainwright
Cellular Automata FAQ - Conway's Game of Life - Tim Tyler
The Unit Life Cell - David Bell
Lifegame The game of life as a battle between two opponents

The Internet Life Joining up the strict rules of the Game of Life with the chaotic randomness of internet visitors in order to create the visualisation of the internet activity.