Conway's Game of Life

The Glider Gun (glider emitter, top) and pentadecatlon (glider absorber, bottom left)
The Game of Life, also known simply as Life, is a zero player game, one of the best-known example of a cellular automaton[1] It has been devised by the British mathematician John Horton Conway in 1970.

"Zero-player game" means that the game evolution is determined by its initial state, requiring no further input from players. One interacts with the Game of Life by creating an initial configuration and its evolution.

Rules

The universe of the Game of Life is an infinite two-dimensional grid of square cells, each of which can be in either live or dead state. Every cell interacts with its eight neighboring cells that are vertically, horizontally or diagonally adjacent. At each step, the following transitions occur:


  1. Any cell with fewer than two live neighbours dies, as if caused by underpopulation.
  2. Any cell with more than three live neighbours dies, as if by overcrowding.
  3. Any alive cell with two or three live neighbours lives on to the next generation.
  4. Any empty (or dead) cell with exactly three live neighbours becomes a live cell.

The changes are applied simultaneously over all grid. Cells contribute to the birth and death of other cells in the next generation even if they themselves die and will not make into that generation.


The R pentomino

Ever since its publication, Conway's Game of Life has attracted much interest because of the interesting ways in which the patterns can evolve. Life provides an example of self-organization, evolution and formogenesis. It is interesting for economists, mathematicians, philosophers, physicists, biologists and others to observe how complex patterns can emerge from the implementation of several simple rules.

Conway has experimented a lot, carefully choosing the rules to meet the follwing criteria:

  1. There should be no initial population that can grow without limit.
  2. There should be some populations that appear to grow without limit.
  3. There should be simple initial populations that evolve for a considerable period of time before:
    • Fading away (from overcrowding or from becoming too sparse), or
    • Settling into a stable configuration that remains unchanged, or
    • Entering an oscillating phase in which they endlessly repeat a cycle of two or more periods.

Examples of patterns

The earliest interesting patterns in the Game of Life were discovered even without the use of computers. The simplest static patterns ("still lives") and repeating patterns ("oscillators" — a superset of still lives) were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, physical game boards and the like. During this early research, Conway discovered that the F-pentomino (which he called the "R-pentomino") does not to stabilize in a small number of generations. Indeed, it takes 1103 generations to stabilize, by which time it has a population of 116. Pentomino fires six escaping gliders while evolving[2] (in fact, these were the first gliders ever discovered).[3] Many different types of patterns occur in the Game of Life, including still lives, oscillators, and patterns that capable to move across the board while oscillating ("spaceships"). Some frequently occurring examples are described in[4].

Block, beehive, load and boat (left to right). These colonies are stable.
The great majority of naturally occurring oscillators are period 2, like the blinker and the toad, but periods 4, 8, 14, 15, 30, and a few others have been seen on rare occasions.[5]
Tumbler, an oscillator with period 14.

F-pentomino belongs to the group of patterns called Methuselahs that evolve for long periods before stabilizing. "Diehard" is a pattern that completely dies after 130 generations, is likely the longest life duration for patterns with seven or fewer cells.[6]. Another known configuration, "acorn" takes 5206 generations to generate 633 cells including 13 escaped gliders.[7] Rules have been deliberately designed to prevent any obvious pattern to pattern can grow indefinitely. 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 keeps creating moving colonies that drift away, preventing overcrowding. A later discovered example of such colony is a "glider gun", which oscillates repeatedly shooting out a "glider" in every period. Another way of disproving the conjecture would be to construct a "puffer train", which moves itself but leaves behind a trail of persistent "smoke".[8].

The prize was won in November of the same year by a team led by Bill Gosper; the "Gosper glider gun" shown below produces its first glider on the 15th generation, and another glider every 30th generation from then on. This first glider gun is still the smallest one known:[9]

Smaller patterns were later found that also exhibit infinite growth. All three of the following patterns grow indefinitely: the first two create one "block-laying switch engine"[10] each, while the third creates two. The first has only 10 live cells (which has been proven to be minimal).[11] The second fits in a 5 × 5 square. The third is only one cell high.

Later discoveries included other "guns", which are stationary and shot out gliders or other spaceships; "puffers", which move along leaving behind a trail of debris; and "rakes", which move and emit spaceships.[12] Gosper also constructed the first pattern with an asymptotically optimal quadratic growth rate, called a "breeder", or "lobster", which moves over board leaving behind a trail of guns. As every gun then emits gliders, the colony grows with accelerating growth rate. However it does not grow with exponential rate, typical for real living forms, as the emitted gliders are not capable for self-reproduction. This remembers the final steps of formation of some specialised tissue in multicellular organism: gliders could be a red blood cells, for instance.

Gliders can interact with other colonies in interesting ways. 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 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.

Glider, once proposed as united logo of hackers of all kinds

Furthermore, a pattern can contain a collection of guns that fire gliders in such a way as 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.[13]


Algorithms

Early patterns with unknown futures such as the R-pentomino led programmers across the world to create programs to track the evolution of Life patterns. Most of the early algorithms are similar; they represented Life patterns as two dimensional arrays. Typically two arrays are used, one for the current and one for the future generation. 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 becomes the current array in the next iteration.


A variety of minor enhancements to this basic scheme are possible. 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.[14]

Two spaceships of different length demonstrate the toroidal model space (as ships departs to the right, it appears from the left

In principle, the Life field is infinite, but computers have finite memory. This leads to problems when the active area encroaches on the border of the array. 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. Dynamic storage allocation may also be used, creating ever-larger arrays to hold growing patterns.

Alternatively, the programmer may abandon the 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 fits into available memory. However counting live neighbours becomes a search operation, slowing down simulation speed. With more sophisticated data structures this problem can also be largely solved.

The [15] site specially focuses on that is know and that is still not known in the Game of Life. For instance, there are still no colonies known with the oscillation periods 19, 23 and some larger numbers, the biggest being 53. Colonies that oscillate with the longer periods are known. This site also describes many more complex questions.


Java applet with many preconfigured figures.

References

  1. 1  Martin Gardner. Scientific American
  2. 2  R-pentomino
  3. 3  Glider
  4. 4  Census Results in Conway's Game of Life
  5. 5  Most seen natural occurring ash objects in Game of Life
  6. 6  Diehard
  7. 7  New Methuselah Records
  8. 8  Puffer train
  9. 9  Gosper glider gun
  10. 10  Block-laying switch engine
  11. 11  Infinite Growth
  12. 12  Rake
  13. 13  Berlekamp E. R., Conway John Horton, Guy R.K.. Winning Ways for your Mathematical Plays
  14. 14  About my Conway's Game of Life Applet
  15. 15 http://entropymine.com/jason/life/status.html

See also

Acknowledgements

This web page reuses material from Wikipedia page http://en.wikipedia.org/wiki/Conway_game_of_life under the rights of CC-BY-SA license. As a result, the content of this page is and will stay available under the rights of this license regardless of restrictions that apply to other pages of this website.