math.com
Home    |    Teacher    |    Parents    |    Glossary    |    About Us
Homework Help Practice Ask An Expert Calculators & Tools Games Store
Email this page to a friend Email this page to a friend
More Wonders
· Fractals
· Spirograph
· Conway's Game of Life
· Roman Numeral Calculator
· Chaos
· Knots
· Mazes
· Tessellations
· Oragami
· Lissajous Lab

 
Resources
· Cool Tools
· Formulas & Tables
· References
· Test Preparation
· Study Tips
· Wonders of Math
 
Search
Custom Search



Math Jobs


  

What is the Game of Life?
by Paul Callahan
The Game of Life (or simply Life) is not a game in the conventional sense. There are no players, and no winning or losing. Once the "pieces" are placed in the starting position, the rules determine everything that happens later. Nevertheless, Life is full of surprises! In most cases, it is impossible to look at a starting position (or pattern) and see what will happen in the future. The only way to find out is to follow the rules of the game.
Play Life Now!


[no button]

Draw a pattern on the grid and click "Go".

Applet help

Applet by
Alan Hensel

Rules of the Game of Life
Life is played on a grid of square cells--like a chess board but extending infinitely in every direction. A cell can be live or dead. A live cell is shown by putting a marker on its square. A dead cell is shown by leaving the square empty. Each cell in the grid has a neighborhood consisting of the eight cells in every direction including diagonals.

To apply one step of the rules, we count the number of live neighbors for each cell. What happens next depends on this number.

  • A dead cell with exactly three live neighbors becomes a live cell (birth).
  • A live cell with two or three live neighbors stays alive (survival).
  • In all other cases, a cell dies or remains dead (overcrowding or loneliness).

Note: The number of live neighbors is always based on the cells before the rule was applied. In other words, we must first find all of the cells that change before changing any of them. Sounds like a job for a computer!

Background
Life was invented by the mathematician John Conway in 1970. He choose the rules carefully after trying many other possibilities, some of which caused the cells to die too fast and others which caused too many cells to be born. Life balances these tendencies, making it hard to tell whether a pattern will die out completely, form a stable population, or grow forever.

Life is just one example of a cellular automaton, which is any system in which rules are applied to cells and their neighbors in a regular grid.

There has been much recent interest in cellular automata, a field of mathematical research. Life is one of the simplest cellular automata to have been studied, but many others have been invented, often to simulate systems in the real world.

In addition to the original rules, Life can be played on other kinds of grids with more complex patterns. There are rules for playing on hexagons arranged in a honeycomb pattern, and games where cells can have more than two states (imagine live cells with different colors).

Life is probably the most often programmed computer game in existence. There are many different variations and information on the web. (See the Paul Callahan's home page for more information.)

 

Who is John Conway?

John Conway is a professor of Finite Mathematics at Princeton University.

A current profile in Scientific American magazine.


Dr. John Conway

A list of books, articles and web pages about Life and other work of John Conway.

John Conway first played Life by hand on a board for the game of Go, using the Go pieces for live cells. His early discoveries were publicized by Martin Gardner in a series of Scientific American columns.

Other games invented by John Conway.

 

Why is Life So Interesting?
Life is one of the simplest examples of what is sometimes called "emergent complexity" or "self-organizing systems." This subject area has captured the attention of scientists and mathematicians in diverse fields. It is the study of how elaborate patterns and behaviors can emerge from very simple rules. It helps us understand, for example, how the petals on a rose or the stripes on a zebra can arise from a tissue of living cells growing together. It can even help us understand the diversity of life that has evolved on earth.
Artistic Life

People have created all kinds of patterns in Life. Some are works of art!

[no button]
[no button]
[no button]

Use the Open button on the applet to see more of these patterns.

In Life, as in nature, we observe many fascinating phenomena. Nature, however, is complicated and we aren't sure of all the rules. The game of Life lets us observe a system where we know all the rules. Just like we can study simple animals (like worms) to discover things about more complex animals (like humans), people can study the game of Life to learn about patterns and behaviors in more complex systems.

The rules described above are all that's needed to discover anything there is to know about Life, and we'll see that this includes a great deal. Unlike most computer games, the rules themselves create the patterns, rather than programmers creating a complex set of game situations.

Life Patterns
A good way to get started in Life is to try out different patterns and see what happens. Even completely random starting patterns rapidly turn into Life objects recognizable to anyone with a little experience. In this section, we follow a simple-looking pattern called the R-pentomino. It starts out with just five cells, but gets complicated very fast. We can see many of the early discoveries in Life just by running this one pattern in the applet. (click Go to start the pattern, see Applet Help to single-step and other control features)

 
[no button]

The R-pentomino is the first pattern Conway found that defied his attempts to simulate by hand. In fact, the pattern eventually becomes "stable" or easy to predict, but this does not happen until 1103 steps have passed. Some of the earliest computer programs for Life were written to determine the fate of this small pattern. This was a challenging problem for many computers of that time, but a modern PC can run the complete sequence of steps many times in one second. Even the applet can run this pattern very fast, but you should slow it down enough to watch it carefully. Try drawing your own patterns on the grid to see what happens. (Applet help)

What Kinds of Objects Emerge in Life?

Still Life Objects
Some of the most common objects in Life remain the same from step to step. No live cells die and no new cells are born. Conway, who is fond of making puns, called this kind of object a "still life." You can observe several of these objects by running the R-pentomino in the applet. For an object to be a still life, every live cell most have 2 or 3 live neighbors, and every dead cell may have any number of neighbors except 3.

The most common still life is called the block. It is simply a 2x2 square of live cells:

You will see it appear many times as you run the R-pentomino. Every live cell has exactly three neighbors, but no dead cell has more than two neighbors.

Some other still lifes you will see are:
beehive
boat
ship
loaf

Look for these in the applet, and try to understand why these objects remain the same. You can design still lifes by hand, and it makes an interesting puzzle. Some people with a lot of experience are good at designing still lifes, but usually computer search is used to find new ones. All still lifes of up to 20 live cells have been enumerated this way.

Oscillators
Oscillators are objects that change from step to step, but eventually repeat themselves. The simplest kind are period-2 oscillators, or those that repeat themselves after two steps. The most common is the blinker, which consists of three cells:

You will see a lot of these when you watch the R-pentomino.

Another common period-2 oscillator is the toad:

You can see this one in the R-pentomino, but you have to watch carefully! After 737 steps, a toad briefly appears at the far right of the pattern. It is destroyed by a nearby explosion after just 14 steps.

Gliders
If you've been following the R-pentomino in the applet, you've probably noticed that some of the objects are moving. This was one of the most exciting early discoveries in Life. These common moving patterns, called gliders, consist of just 5 cells:

 
[no button]

(Click Go to start the pattern) Follow this pattern along for four steps in the applet. Or, to really understand what's going on, apply the rules by hand as Conway did. You will see that after four steps, it looks just like it did when it started. The only difference is that it is shifted along a diagonal. Repeat this process, and you have a moving Life object, which in general we call a spaceship. Remember, the rules said nothing about movement; moving patterns just appear. This is a simple but convincing demonstration of emergent complexity.

The Queen Bee Shuttle
A very important pattern makes a brief appearance after running the R-pentomino for 774 steps:

It doesn't last long in these stormy surroundings, but you can enter it into the applet by itself and watch what it does. First it moves to the right, but after a few steps, it produces the still life called a beehive and turns back to the left. Then it produces another beehive to its left and turns right again. Conway called this pattern the queen bee shuttle for this reason. Unfortunately, the next time around, it crashes into the first beehive it created. But we can get rid of unwanted beehives using a block:

If you run this in the applet, you will see that the beehive goes away but the block remains. By putting a block on either side of the queen bee, we can cause it to shuttle back and forth indefinitely. This is a period-30 oscillator, since the shuttle moves for 15 steps in each direction. Later, we will see how this pattern was used to answer an important question about Life.

Other Interesting Objects
There are some early discoveries that do not show up in the R-pentomino, but which sometimes show up from random starting states.

The orthogonal spaceships move left, right, up, or down instead of on diagonals like gliders. These are much less common than gliders, but very important in certain kinds of patterns. They come in three sizes:
light weight
medium weight
heavy weight
Finally, here are some simple starting patterns that develop into oscillators. A row of 10 live cells becomes the period-15 oscillator called the pentadecathlon:

The following pattern becomes a very pretty period-3 oscillator called the pulsar:

Do All Patterns Stabilize Eventually?
We say a pattern has stabilized when it becomes obvious that the population has stopped growing. For example, we say the R-pentomino stabilizes at step 1103 because at this point it consists of just gliders and oscillators, and it is clear that the gliders will never collide with each other or with any oscillators. It was observed early on in the study of Life that random starting states all seem to stabilize eventually. Conway offered a prize for any example of patterns that grow forever. Conway's prize was collected soon after its announcement, when two different ways were discovered for designing a pattern that grows forever.

The first of these patterns is the period-30 glider gun, which is based on the interaction of two queen bee shuttles. Where these shuttles collide, instead of producing beehives, they produce a new glider. This glider moves away in time for the process to repeat itself 30 steps later.
[no button] (click Go to start the pattern)

Another kind of pattern that grows forever is called a puffer. Unlike the glider gun, which remains stationary and produces moving objects, puffers move while producing objects, which may be either moving or stationary. Here is one of the simplest, and earliest puffers.
[no button] (click Go to start the pattern)

In recent years, many new puffers and guns have been discovered or invented.

Finally, here's a pattern, called the spacefiller, that grows as fast as the rules of Life can allow. It is not at all like the kinds of Life patterns that result from random starting states, and would never have been discovered without the aid of a computer search. It's a very recent discovery compared to the patterns described above, and was not known until 1993.
[no button] (click Go to start the pattern)

How Complex Can Life Get?
A computer can be built inside the Life "universe". Space does not permit a detailed description, but you can find much more information in some of the references given at the bottom. Briefly, streams of gliders and spaceships can be used to send information just as electrical signals are used to send information in a physical computer. These streams of gliders can react in a way to perform all of the logical functions on which a modern computer is based. It would be very impractical to build a computer this way, but given a large enough Life pattern and enough time, we could run any program that runs on a computer. Several interesting special-purpose computers have been constructed as Life, including one that outputs the prime numbers.

A universal constructor can even be built. This is a pattern that can take a blueprint for some other Life pattern (or its own) and build that pattern. No one has built this yet, since it would be very large, but it has been shown to be possible. This means that Life patterns could exist that reproduce themselves. They could even modify their blueprints just as living things combine and mutate their genes. Who can say what would develop in a large enough universe of reproducing Life patterns?

What is Life Good For?
Studying the patterns of Life can result in discoveries in other areas of math and science.

The behavior of cells or animals can be better understood using simple rules. Behavior that seems intelligent, such as we see in ant colonies might just be simple rules that we don't understand yet. Take a look at this simulation of termites piling up woodchips. (click here) There are only 2 rules in this system, and yet, a seemingly "intelligent" pattern emerges. What does this say about the nature of intelligence?

Traffic problems might be solved by analyzing them with the mathematical tools learned from these types of simulations. (Unjamming Traffic with Computers)

Computer viruses are also examples of cellular automata. Finding the cure for computer viruses could be hidden in the patterns of this simple game.

Human diseases might be cured if we could better understand why cells live and die.

Exploring the galaxies would be easier if machines could be invented that could build themselves. Imagine sending a probe to Mars that could build a copy of itself. Although this is theoretically possible, it hasn't been invented yet!

Is Life Alive?
Would living creatures evolve in a sufficiently large Life universe if we waited long enough? We can see that Life, simple as it is to describe, exhibits much of the complexity of our own universe. It is intriguing to ask what would happen in an infinitely large Life space seeded with random patterns. It seems that likely that complexity would emerge beyond what we can see when we watch Life on a computer. Even in our own universe, there is a huge difference between what we know about natural history and what we can observe on a human time frame.

On the other hand, Life has only two dimensions, unlike our own universe, and that is a severe limitation. There are other properties of Life -- the tendency to stabilize locally into oscillators -- that may make it an unlikely place for living things to develop. The answer to this question remains unknown, but Life illustrates at a simplified level the kinds of evolutionary forces that we witness in our own universe.

Bibliography
Berlekamp, Conway, and Guy: Winning Ways (for your Mathematical Plays), Volume 2, (c)1982. ISBN 0-12-091152-3.
Gardner, Martin: Wheels, Life, and Other Mathematical Amusements, (c)1983. ISBN 0-7167-1589-9.
Poundstone, William: The Recursive Universe, (c)1985. ISBN 0-688-03975-8.

About the Authors
Paul Callahan - text
Paul's Page of Conway's Life Miscellany - Patterns, how to create your own pattern files, and links to other Life pages.

Alan Hensel - applet
Alan Hensel's page - more about the applet and more patterns.

Other Wonders of Math

  Fractals Chaos Tessellations
Spirograph Knots Origami
Conway's Game of Life Mazes Lissajous Lab
Roman Numeral Calculator

Applet Help

[no button]
This button will launch the applet with a pattern. You can run the pattern by clicking the Go button. To create your own pattern, click the Clear button and you can draw on the grid to create a pattern, or select one of the pre-set patterns by clicking the Open button. Click Go to start.

Buttons

Open Opens a list of patterns to start from.
Go (Stop) Click to start, take a step, or stop Game of Life.
Step Control
Forever (+1, -1)
Forever setting will cause Game to step through patterns. +1 allows you to see a step at a time. Click Go to advance to the next step. -1 takes one step back.
Clear Clears the grid.
Speed Sets how fast the pattern is generated in frames per second. You can also set it to skip generations. Click Go to start pattern again.
Options Allows you to change How-Far to skip. This will show up in the Step Control drop down list.
Zoom 5 is the closest you can zoom in, use this for small patterns. 0 is the farthest you can zoom out to see large patterns.
Quit Close the applet window.
Generation Counter The number at the far right is the number of generations the pattern has gone through.

Troubleshooting

I don't see anything! You need an up-to-date browser to run this Java program. Click here to find out how to get one.

 

  
 
 
  

 
Contact us | Advertising & Sponsorship | Partnership | Link to us

© 2000-2005 Math.com. All rights reserved.     Legal Notices.     Please read our Privacy Policy.