Variations on the Game of Life

The Game of Life is perhaps the most well-known example of cellular automata. Originally developed by John Conway, the Game of Life has been the subject of countless studies and exists in multiple variations.

A "Glider Gun" in the Game of Life

Cellular Automata - Models that consist of a grid of "cells"--each of which can be in different "states". The cells each obey defined rules and change states over time according to those rules.

The Game of Life has simple rules that give rise to complex patterns.

Life is played on an infinite grid of square cells--each of which can be living or dead. The grid is initialized to some pattern and then the universe proceeds through timesteps, or generations, according to the rules.

Each cell has 8 neighboring cells surrounding it. The states of these neighbors determine whether the cell will be alive or dead in the next generation.

A dead cell with exactly 3 living neighbors comes to life in the next generation.

A live cell with exactly 2 or 3 living neighbors stays alive in the next generation.

A live cell with less than 2 living neighbors dies of loneliness.

A live cell with more than 3 living neighbors dies of overcrowding.

The Game of Life has been used as a programming exercise in the CS 106X class at Stanford, and it has been said (somewhat humorously) that since 1970 more computer time world-wide has been devoted to the Game of Life than any other single activity.
Indeed, while it is quite possible to carry out the Game of Life by using large quantities of graph paper, it is much faster and more feasible to evaluate and display the results of each timestep with the aid of a computer program. Many patterns and quirks that exist in the Game of Life can be easily discovered simply by experimenting with random starting seeds and watching as a computer simulates the evolution of the game.

As larger and more complex patterns in the Game of Life began to be simulated, it became desirable to optimize computer programs in order to efficiently process large Life grids. Hashlife is one optimization strategy that has been used for this purpose.

The emergence of complex behavior--sometimes chaotic and other times seemingly orderly--from the simple rules set out by the Game of Life has notable implications in many fields:

"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."
--Wikipedia article on Conway's Game of Life

Static patterns, such as this "block", remain the same forever unless disturbed externally.

Static Patterns

Repeating patterns, such as this 2-state "blinker", cycle between 2 or more states.

Repeating Patterns

"Spaceships" such as the basic "glider" shown here are patterns that travel across the grid in a particular direction in a regular manner. Some spaceships, called "puffers", emit blocks as they travel. Others, known as "rakes", create other spaceships in their wake.

Spaceships

The "glider gun" shown here produces spaceships indefinitely at a regular rate.

Glider Gun

The Wikipedia article on the Game of Life notes:
"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 that acts like a finite state machine connected to two counters."

Although it may seem a bit convoluted, this idea became the basis for the construction of a Turing Machine within the Game of Life. The details of this construction are available at Paul Rendell's site here.

Just as spectacular as the concept of a Turing Machine being built in the Game of Life is the "17c/45 Caterpillar spaceship"--a gigantic pattern involving over 10 million cells that travels across the universe. More information on the 17c/45 Caterpillar is available here and here.

Read about variations on the Game of Life

Timm[ie] Wong, September 2008