Cellular Automata

What is Game Of Life

Conway's Life (Game of Life, GOL) is the most well-known cellular automaton. It has been extensively explored, leading to the discovery of numerous extraordinary patterns. Perhaps calling it a "game" is somewhat misleading. It's not a game like "Doom" or other video games one might play with a joystick. Life is more of a simulation where you can alter the initial parameters but cannot directly influence the outcome; the conditions of the simulation dictate that.

The game is played on a two-dimensional grid where each cell can be either "on" or "off." Each cell has eight neighbors, adjacent horizontally, vertically, or diagonally. The Life rules, which determine a cell’s state from one generation to the next, can be simply expressed as follows:

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

These specific rules were selected in 1970 by mathematician J.H. Conway to ensure that the cellular automaton sits on the boundary between unbounded growth and decay into dullness. It has been proven that its chaotic behavior is unpredictable, making it capable of simulating a universal Turing machine and even a universal constructor. The contrast between the simplicity of these rules and the complexity they produce continues to be a constant source of wonder.

Each cell acts independently based on the previous arrangement to produce a new one. The number of neighbors is counted from the previous arrangement only. Therefore, if a dead cell has three living neighbors, the cell will become alive in the next generation, even if those neighbors subsequently die.

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

How does it work?

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:

exp01_00

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:

exp01_01

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:

exp01_02

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:

exp01_03

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.

Game of Life history

John Horton Conway, a British mathematician at Gonville and Caius College, University of Cambridge, was experimenting in the late 1960s with a few ideas for a simple cellular automaton. The initial concept of cellular automata was first proposed by Ulam. John von Neumann utilized this concept to create complex cellular automata capable of producing non-trivial self-reproducing patterns. However, von Neumann's machine had 29 states, so Conway sought something simpler yet intriguing. He defined the following criteria:

Conway and his graduate students experimented with various rules, eventually settling on the familiar "birth on 3 / survival on 2 or 3" rule. In those days (pre-1970), computers were limited, so most of the team's explorations were done using 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 Scientific American in October 1970, in Martin Gardner's "Mathematical Games" column. Several other columns and articles followed, but there were more results than Scientific American could reasonably publish. Consequently, the LifeLine quarterly newsletter was created and ran for 11 consecutive issues.

Not much more happened in the Life universe between 1974 and 1988. However, the advent of more powerful computers, the availability of email over the Internet, and ideas about search engines led to a "Cambrian explosion" in the Life universe, which continues to this day.

Other rules in Life

Life is not limited to the "23/3" rules. Other variations on the specific neighbor counts in the rules have been tried, but Conway's formulation has generated more interest than all the rest combined. Perhaps this is partly due to its self-generating popularity, and had Conway specified other rules, they might have become the most popular instead.

Most alternative rules are either more complex, cause the universe to die out quickly, or result in an exploding universe. Nevertheless, many interesting alternatives to "23/3" have been explored. Perhaps the most famous ones are HighLife "23/36" and Diamoeba "5678/35678".

MCell contains many built-in alternative Life rules.

What are Cellular Automata?

Cellular automata (CA) can be seen as a generalization of Life. They are not restricted to the 2-dimensional, 8-neighbor S/B rules. In different implementations, the following elements can vary:

MCell allows exploring CA rules with nearly all these extensions.

What are Cellular Automata good for?

Cellular Automata have proven to be very useful in a wide range of applications. Some of the best-known ones are:

Biological and Ecological Modeling

One of the prominent uses is in modeling biological systems like population dynamics, spread of diseases, and ecological interactions3. For instance, CA can simulate how a forest fire spreads through a grid representing a forest.

Physics and Material Science

CA models are used to simulate physical processes such as crystal growth, diffusion, and material deformation. The simplicity of CAs makes them highly effective in modeling complex behaviors from simple, local rules.

Cryptography

Certain cryptographic algorithms, like the S-box in the Keccak hash function (SHA-3), utilize Cellular Automata for creating complex patterns that are hard to reverse engineer.

Computer Graphics and Art

Artists and developers use CA to generate intricate patterns and designs. The famous Conway's Game of Life is at the heart of many visual and algorithmic art pieces.

Urban Planning and Geography

Urban planners use CA to simulate various scenarios of city growth and infrastructure development. It helps in visualizing and predicting the evolution of urban landscapes based on simple rules.

Random Number Generation

CA can generate pseudo-random sequences that are used in simulations, cryptographic applications, and procedural content generation in video games.

Traffic Flow Simulation

Another fascinating use is in modeling traffic patterns and flows. CA helps in understanding and optimizing traffic light configurations and predicting congestion hotspots.

Artificial Life and Evolutionary Computation

In research, CA is used to study artificial life forms and evolutionary algorithms. They provide insights into how simple rules can lead to complex, emergent behaviors over time.