The Game Of Life Part I

Most of the work of John Horton Conway, a distinguished mathematician at the University of Cambridge, has been in pure mathematics. For instance, in 1967 he discovered a new group—some call it "Conway's constellation"—that includes all but two of the then known sporadic groups. (They are called "sporadic" because they fail to fit any classification scheme.) It is a breakthrough that has had exciting repercussions in both group theory and number theory. It ties in closely with an earlier discovery by John Leech of an extremely dense packing of unit spheres in a space of 24 dimensions where each sphere touches 196,560 others. As Conway has remarked, "There is a lot of room up there."

In addition to such serious work Conway also enjoys recreational mathematics. Although he is highly productive in this field, he seldom publishes his discoveries. One exception was his paper on "Mrs. Perkins' Quilt," a dissection problem discussed in my Mathematical Carnival. Another was sprouts, a topological pencil-and-paper game invented by Conway and M. S. Paterson. It is also the topic of a chapter in the same book.

In this chapter we consider Conway's most famous brainchild, a fantastic solitaire pastime he calls "Life." Because of its analogies with the rise, fall and alterations of a society of living organisms, it belongs to a growing class of what are called "simulation games"—games that resemble real-life processes. To play Life without a computer you need a fairly large checkerboard and a plentiful supply of flat counters of two colors. (Small checkers or poker chips do nicely.) An Oriental "go" board can be used if you can find flat counters small enough to fit within its cells. (Go stones are awkward to use because they are not flat.) It is possible to work with pencil and graph paper but it is much easier, particularly for beginners, to use counters and a board.

The basic idea is to start with a simple configuration of counters (organisms), one to a cell, then observe how it changes as you apply Conway's "genetic laws" for births, deaths and survivals. Conway chose his rules carefully, after a long period of experimentation, to meet three desiderata:

(1) There should be no initial pattern for which there is a simple proof that the population can grow without limit.

(2) There should be initial patterns that apparently do grow without limit.

(3) 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.

In brief, the rules should be such as to make the behavior of the population both interesting and unpredictable.

Conway's genetic laws are delightfully simple. First note that each cell of the checkerboard (assumed to be an infinite plane) has eight neighboring cells, four adjacent orthogonally, four adjacent diagonally. The rules are:

(1) Survivals. Every counter with two or three neighboring counters survives for the next generation.

(2) Deaths. Each counter with four or more neighbors dies (is removed) from overpopulation. Every counter with one neighbor or none dies from isolation.

(3) Births. Each empty cell adjacent to exactly three neighbors—no more, no fewer—is a birth cell. A counter is placed on it at the next move.

It is important to understand that all births and deaths occur simultaneously. Together they constitute a single generation or, as we shall usually call it, a "tick" in the complete "life history" of the initial configuration. Conway recommends the following procedure for making the moves:

(1) Start with a pattern consisting of black counters.

(2) Locate all counters that will die. Identify them by putting a black counter on top of each.

(3) Locate all vacant cells where births will occur. Put a white counter on each birth cell.

(4) After the pattern has been checked and double-checked to make sure no mistakes have been made, remove all the dead counters (piles of two) and replace all newborn white organisms with black counters.

You will now have the first generation in the life history of your initial pattern. The same procedure is repeated to produce subsequent generations. It should be clear why counters of two colors are needed. Because births and deaths occur simultaneously, newborn counters play no role in causing other deaths or births. It is essential, therefore, to be able to distinguish them from live counters of the previous generation while you check the pattern to be sure no errors have been made. Mistakes are very easy to make, particularly when first playing the game. After playing it for a while you will gradually make fewer mistakes, but even experienced players must exercise great care in checking every new generation before removing the dead counters and replacing newborn white counters with black.

You will find the population constantly undergoing unusual, sometimes beautiful and always unexpected change. In a few cases the society eventually dies out (all counters vanishing), although this may not happen until after a great many generations. Most starting patterns either reach stable figures—Conway calls them "still lifes"—that cannot change or patterns that oscillate forever. Patterns with no initial symmetry tend to become symmetrical. Once this happens the symmetry cannot be lost, although it may increase in richness.

Conway originally conjectured that no pattern can grow without limit. Put another way, any configuration with a finite number of counters cannot grow beyond a finite upper limit to the number of counters on the field. This is probably the deepest and most difficult question posed by the game. Conway offered a prize of $50 to the first person who could prove or disprove the conjecture before the end of 1970. One way to disprove it would be to discover patterns that keep adding counters to the field: A "gun" (a configuration that repeatedly shoots out moving objects such as the "glider," to be explained below) or a "puffer train" (a configuration that moves but leaves behind a trail of "smoke"). The results of the contest for Conway's prize are discussed in the next chapter.

Let us see what happens to a variety of simple patterns.

A single organism or any pair of counters, wherever placed, will obviously vanish on the first tick.

A beginning pattern of three adjacent counters also dies immediately unless at least one counter has two neighbors. Figure 126 shows the five triplets that do not fade on the first tick.

o 1 •• • n i h block blinker dies' dies 'dies . * . 'jfm. \

stable 'peri0d b lAbLt TWQ

The fate of five triplets in "life"

(Their orientation is of course irrelevant.) The first three [a, b, c] vanish on the second tick. In connection with c it is worth noting that a single diagonal chain of counters, however long, loses its end counters on each tick until the chain finally disappears. The speed a chess king moves in any direction is called by Conway (for reasons to be made clear later) the "speed of light." We say, therefore, that a diagonal chain decays at each end with the speed of light.

Pattern d becomes a stable "block" (two-by-two square) on the second tick. Pattern e is the simplest of what are called "flip-flops" (oscillating figures of period 2). It alternates between horizontal and vertical rows of three. Conway calls it a "blinker."

Figure 127 shows the life histories of the five tetrominoes (four rookwise-connected counters). The square [a] is, as we have seen, a still-life figure. Tetrominoes b and c reach a stable figure, called a "beehive," on the second tick. Beehives are frequently produced patterns. Tetromino d becomes a beehive on the third tick. Tetromino e is the most interesting of the lot. After nine ticks it becomes four isolated blinkers, a flip-flop called "traffic lights." It too is a common configuration. Figure 128 shows 12 common forms of still life.

The reader may enjoy experimenting with the 12 pentomi-noes (all possible patterns of five rookwise-connected counters) to see what happens to each. He will find that five vanish before the fifth tick, two quickly reach a stable loaf, and four in bed

.BLOCK

beehive ' beehive

beehive [

traffic lights

The life histories of the five tetrominoes

loaf

pond

0 0

Post a comment