- What is Game Of Life
- How does it work?
- Game of Life history
- Other rules in Life
- What are Cellular Automata?
- What are Cellular Automata good for?

Conway's Life (Game Of Life, GOL) is the most well known cellular automaton. It has been extensively explored, and a large number of extraordinary patterns have been found. Perhaps to call it a game is somewhat misleading. It's not a game like Doom or other games you would play with a joystick. Life is more of a simulation where you can alter the parameters but you cannot actually alter the outcome directly; that is done by the conditions of the simulation.

The game is played on a 2-dimensional grid. Each cell can be either "on" or "off". Each cell has eight neighbors, adjacent across the sides and corners of the square. The Life rule can be simply expressed (in terms of the way it affects a cell's behavior from one generation to the next) as follows:

- If a cell is off and has 3 living neighbors (out of 8), it will become alive in the next generation.
- If a cell is on and has 2 or 3 living neighbors, it survives; otherwise, it dies in the next generation.

A commonly used shorthand for this is 23/3 (or S23/B3), which signifies that a living cell survives if it has two live neighbors, and is born if it has three alive neighbors.

These specific rules were selected in 1970 by the mathematician J.H. Conway to guarantee that the cellular automaton is on the boundary between unbounded growth and decay into dullness. It was proven that its chaotic behavior is unpredictable and it could be used to build a universal Turing-machine and even a universal constructor. The contrast between the simplicity of this rule and the complexity of the behavior it produces is a constant source of wonder.

Note that each cell acts independently based on the old arrangement to produce a new one. The number of neighbors is counted from the old arrangement only. Therefore, if a dead cell has 3 neighbors, the cell will be alive in the next generation, even if those neighbors die.

You can read much more about the history of Cellular Automata here.

Let’s calculate some generations by hand. Consider the following starting pattern, where empty fields represent 'off' (dead) cells and red dots represent 'on' (living) cells:

In order to be able to apply Conway’s rules (Survival 2,3 / Birth 3) to the pattern we must calculate the counts of alive neighbors for each cell:

What will happen to living cells? Alive cells can survive when they have either 2 or 3 neighbors. Two central dots have exactly 2 living neighbors, so they will survive. Two other dots have only 1 neighbor; they will die of loneliness.

What will happen to empty cells? Four of them have exactly 3 neighbors; those four cells will become alive. The rest of empty cells will stay off - they have only 0, 1 or 2 neighbors.

So the next generation is as follows:

4 cells will survive (the ones with 3 neighbors). Two other cells have to die of crowd.

2 empty cells have 3 neighbors and will come alive. The rest will stay off.

So the third generation is:

And now? No cells have 3 neighbors, so no new cells will come alive. All alive cells have exactly 2 neighbors, so all of them will survive. We have reached a stable pattern (still life) that will not change in next generations.

You can read more about alternative Life rules in Other rules in Life.

John Horton Conway, a British mathematician at Gonville and Caius College, University of Cambridge, was playing around in the late 1960's with a few ideas for a simple cellular automaton. The first ideas for cellular automata were thought of by Ulam. John von Neumann used this idea to create complex cellular automata, which was able to produce non-trivial self-reproducing patterns. John von Neumann's machine has 29 states, however, so Conway was looking for something simple, yet interesting. More specifically, he defined the following 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 three possible ways:

- fading away completely (from overcrowding or from becoming too sparse),
- 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.

Conway and his graduate students played around with various rules, finally settling on the familiar "birth on 3 / survival on 2 or 3" rule. In those days (pre-1970), computers were very primitive, so most of the team's explorations were done with physical checker pieces. One of their greatest discoveries was the glider, which they found while trying to determine whether the R-pentomino was an infinite growth pattern.

The game was first published in the Scientific American in October 1970, in Martin Gardner's "Mathematical Games" column. A few other columns and articles appeared later, but there were more results than Scientific American could reasonably be expected to publish, so the LifeLine quarterly newsletter was invented, and it ran for 11 consecutive issues.

Not much more happened in the Life universe between 1974 and 1988. Then the appearance of more powerful computers, the availability of e-mail over the Internet, and ideas about search engines created something of a Cambrian explosion in the Life universe, which continues to this day.

Life is not limited to "23/3" rules. Other variations on the specific neighbor counts in the rules have been tried, but Conway's formulation seems to have generated more interest than all of the rest combined. Maybe that's partly due to self-generating popularity, and if Conway had specified other rules, probably those would be it.

Most alternative rules are not as simple, or let the universe die out too quickly, or create an exploding universe. Nevertheless many interesting alternatives to “23/3” were explored. Perhaps the most famous ones are HighLife "23/36" and Diamoeba "5678/35678".

MCell contains many built-in different Life rules. You can read about them in “Life" family.

Cellular automata can be seen as a generalization of Life. Cellular automata are not restricted to 2-dimensional 8-neighbours S/B rules - in different realizations the following items can be changed:

- The number of states per cell. In Life there are only two states – ‘on’ and ‘off’. Some Cellular Automata applications allow assigning more states, for example 8 or even 256. The states are usually represented as colors (see "Generations" family).
- The number of dimensions - especially popular are 1-dimensional rules (see "1D totalistic CA" family).
- The way cells are arranged. We can for instance play “Life” on a hexagonal lattice (see "Weighted Life" family, rule "Hexrule b2o").
- The neighborhood: in classic Life each cell has 8 neighbors. Other CAs consider 5 neighbors (von Neumann neighborhood, see "Neumann binary" family), 9 neighbors (8 neighbors + the cell itself, see "Vote for life" family, "Weighted Life" family), or even much more, not only those adjacent to the cell (see "Larger than Life" family, "Cyclic CA" family).
- The weight of neighbors: all cells are equal, but some can be more equal ;-) (see "Weighted Life" family)
- The operations performed on neighbors in order to evaluate the new state of the cell (see "Rules table" family, "Cyclic CA" family, "User DLLs" family).

MCell allows exploring Cellular Automata rules with all above extensions (see CA families in MCell).

Although the real Era of Cellular Automata is still expected to come, even today they have proven to be very useful. Some of best known applications of Cellular Automata are:

- image processing and image generation,
- simulations of biology,
- simulations of chemistry,
- simulations of physics,
- design of new computing hardware and algorithms,
- art.

Webmaster: Mirek Wojtowiczhttp://www.mirekw.com |
Europe http://www.mirwoj.opus.chelm.pl |

Last update: 07 Jan 2002