Section 2 - The Game of Life

3A.2.1 The Game of Life

When I was just out of high school, I read an article about a mathematical game called life. It was invented by a mathematician, John Horton Conway. Life was not a game in the sense of Xbox 360 or Wii. It was played by oneself in the spirit of solitaire. One began with a large piece of graph paper and placed some marks or stones in a few of the squares to create an initial pattern or seed. After that, the rules of life determined what happened next. One referred to Conway's rules carefully examining each cell of the seed to figure out whether it survived, died or was reborn into the next generation. Thus, a series of generations resulted, each one arising by applying life's rules to the prior generation. Conway's initial research demonstrated that there were certain seeds that caused things to get boring fast (the entire board became empty, i.e., all white/dead), while others generated interesting repetitive graphics: blinkers and gliders. He even offered a $50 prize to anyone who could prove or disprove that there was no finite initial condition that would grow without limit as the generations passed. Fifty bucks!

Life's playing field, called the universe, is a two-dimensional grid of square cells, each of which is in one of two possible states, alive (black or 1) or dead (white or 0). Every cell interacts with its eight neighbors to determine whether it and its neighbors will survive to the next generation. The rules are applied to all cells simultaneously in one generation, and when all the survivors are computed, the old pattern is removed and replaced by survivors (and children) of the next generation. The rules are simple:

1. Any live cell with two or three live neighbors lives on to the next generation (ideal life support).
2. Conversely, if it has zero, one or four-or-more live neighbors, it dies (death from loneliness or overcrowding).
3. Any dead cell with exactly three live neighbors becomes a live cell (birth).

Here are some examples taken from Martin Gardner's 1970 Scientific American article about life.

	generations			ultimate result
	0 (seed)	1	2
a				dies
b				dies
c				dies
d				block (stable)
e				blinker (period 2)

Today, we can animate gifs to see how the generations evolve. Here is the blinker, example e, above:

Here is an example of a glider - a pattern that moves diagonally, forever. Notice that every four generations, the pattern has moved itself one step diagonally to the lower-right:

And about that $50 prize? Within a year a mathematician, Bill Gosper, found a seed that resulted in a bullet being ejected every 30 generations, thus growing without bound. It is called Gosper's Glider Gun:

3A.2.2 The Significance of Life

In case you think that the behavior of the game of life is nothing more than a primitive animation, reminiscent of early and clunky video games, you have not yet gotten the point. These cute movies are not something that a graphic designer and animator put together. They are the direct result of a few simple rules and a seed -- and nothing more. In the case of life, the rules are symbolic of a few crude observations that biologists have made about populations: If things get either too crowded or too barren, individuals tend to die. If they are in the sweet middle ground, they tend to survive. And there is usually a special condition that creates birth. (Lest you think that the three neighbors needed to generate a new live cell is wrong -- that it should be two -- don't forget that no one said that the three neighbors are the parents. Conway's rule only says that, in general, it is more likely that a child will result when there are three individuals in close proximity. And indeed, maybe this is true. If you randomly group individuals into twos, you are less likely to get the ingredients for procreation than if you group them into threes. Jests aside, what we are saying is that there is an ideal condition that will result in a new member of the group, and this condition is slightly narrower than the condition for survival of an existing member.)

Computational digital modeling of complex natural behavior turns out to be very common in research and industry. Life represents a simple and easily visualized example of this operation, but not the only, nor even the first, one. Why it captured the imagination of intellectuals and mathematical enthusiasts when it was introduced while other computational inventions were confined to the specialists in the field probably had to do with a combination of things. It had a simple name, it was easy to explain, it roughly represented population dynamics and human behavior and it was popularized in a magazine that was read by a larger, lay population (Scientific American). Also, let's not forget that Conway offered fifty bucks to anyone who could settle an assertion about it.

The game of life was one of many theoretical inventions which can be traced back to Alan Turing and John von Neumann, two of the founding fathers of modern theory of computation in the 1940s. Variously called "self-replicating systems" or "cellular automata" (CA), the field studies how individual building blocks like the binary cells of life and a simple rule-set can generate larger, more complex structures that have properties that neither the cells themselves, nor the inventor of their rules could have anticipated.

CA (I'll start using the abbreviation for cellular automata from here out) are mathematical models characterized by the requirement that time and space are discrete quantities that can take on only a finite number of values. This may seem like an unrealistic model of the "obviously" continuous the universe in which we live, but ever since Max Planck's initial work that spawned quantum physics over 100 years ago, there has been increasing evidence that at the smallest levels, such assumptions may be correct.

The developer of the popular visualization software Mathematica, Stephan Wolfram, advanced the field of CA in the 1980s and '90s demonstrating that there were both highly ordered and impossibly chaotic systems that could emerge from elementary CA models. More recently, Melanie Mitchell is among many researchers who have added significantly to the body of knowledge in CA. We'll use her elegant rule description in our example of 1-dimensional CA, coming up next.

There are many fields which are closely related to CA but which each have a unique emphasis and application. You can do a search on these areas by Googling phrases like genetic algorithms, emergence and artificial life. A somewhat more distant cousin, but one that has some overlap with CA is that of artificial intelligence, especially the sub-field of artificial neural networks.

The applications of CA and its related fields are varied. They include:

• Simulation of biological systems
• The design of massively parallel computers
• Graphic design in the visual and performing arts
• Pattern recognition
• Machine intelligence
• Modeling phenomena such as
  • the dispersal patterns of forest fires
  • occurrence of certain crime patterns in urban areas
  • competition between species
  • plankton growth
  • animal behavior

Soon, we will actually write a program that has all the characteristics of these more complex CA algorithms yet is surprisingly simple, especially when formulated in the context of OOP. Before doing so, we'll need to acquire some new programming tools: binary number representations and bit-wise operators.