Simulating Experiences: Excursions in Programming

"The Game of Life"

Mathematica in Education
Vol.2 No.4
(October 1993)

by
Richard J. Gaylord
Department of Materials Science
University of Illinois at Urbana-Champaign
gaylord@ux1.cso.uiuc.edu

Introduction

I have previously discussed one-dimensional cellular automata [Gaylord,
1993] and a two-dimensional cellular automaton known as the sandpile model
[Gaylord, 1992]. Now I want to look at the most famous 2D CA, the Game of
Life, created by the British mathematician John Conway.

A variety of Game of Life programs encompassing different programming
styles, in order of increasing speed and elegance (the two often go
together), will be described and compared.

The Game of Life

The Game of Life is played on a square lattice with reflecting boundary
conditions. The configuration of the game board is a Boolean matrix so that
lattice sites have values of either zero or one. At each time step in the
evolution of the CA, all of the sites of the game board are simultaneously
updated by applying rules to the neighborhoods of each site (a neighborhood
consists of the site and its nearest-neighbor (nn) sites). The life & death
rules (where a living site is a site with value one and a dead site is a
site with value zero) are:

any site with three living nn sites stays alive or is born.
a living site with two living nn sites remains alive.  
all other sites either remain dead or die.

The game proceeds until the system stops evolving, defined by two
successive game board generations with the same configuration, or until a
specified number of time steps have occurred.

A Functional Style Program

The first 'Life' algorithm is a modified version of the program in the
Life.m package that comes with Mathematica (the changes include the use of
an extinction condition and the deletion of graphics).

lifeGameMa[s_Integer,  t_Integer] := 
  Module[{initconfig,  bc,  rule,  update},
         initconfig = Table[Random[Integer], {s}, {s}] ;
         bc = Join[{Last[#]}, #, {First[#]}]& ;
         rule[lis_] :=  
                    Module[{k},
                          k = Count[lis, 1, {2}] ;
                          If[(lis[[2, 2]] == 1 && k == 4) || k == 3,
1, 0]
                                ] ;
         update[lis_] := 
            Map[rule, Partition[bc[Map[bc,  lis]], {3, 3},  {1,
1}], { 2}];
         evolution = FixedPointList[update, initconfig, t]
         ]

I'll walk through the program and explain its various components (this is
easier to do with programs written in a functional style than with
procedural style code).

The initial setup of the game board is given by a random Boolean matrix of
0's and 1's.

initconfig = Table[Random[Integer], {s}, {s}]

(note: various patterns, such as still lifes, blinkers, gliders, and
oscillators, can also be introduced into the initial configuration. These
life forms display some interesting behaviors that have been explored in
the Game of Life literature)

To update a site on the board, the neighborhood of the site is examined.
The neighborhood of a site located in the interior of the board consists of
the eight nn sites lying north, northeast, east, southeast, south,
southwest, west and northwest of the site and is easily constructed.  The
neighborhood of a site lying on one of the borders of the board is a bit
more complicated to construct because it contains sites on the opposing
borders. A non-corner site located in the first row (column) of the board
has the corresponding site in the last row (column) as a nn site and a
corner site has the two sites in the opposing corner as two of its nn
sites. 

The neighborhoods of all of the sites on both the  interior and the borders
of the game board are created in a single two-step operation. 
(1) the 's by s' gameboard is enlarged to an '(s+2) by (s+2)'  lattice by
placing a copy of the first row after the last row, a copy of the last row
before the first row, a copy of the first column after the last column and
a copy of the last column before the first column. This is done with the
anonymous function

bc = [{Last[#]}, #, {First[#]}]&

which is first applied to each of the rows in initconfig (to create the
additional columns)

Map[bc, initconfig]

and then to the result (to create the additional rows)

bc[Map[bc, initconfig]

(2) the enlarged matrix is tesselated into '3 by 3' matrices (each matrix
is the neighborhood of a site) with overlapping elements.

Partition[bc[Map[bc, initconfig]], {3, 3}, {1, 1}]

To perform the update of a site, a rule is defined which encompasses the
life & death criteria in a conditional function.

rule[lis_] := 
              Module[{k},
                      k = Count[lis, 1, {2}] ;
                      If[(lis[[2, 2]] == 1 && k == 4) || k == 3, 1, 0]
                       ]

This rule function is employed as an argument in another function which
maps rule onto the list of neighborhoods

update[lis_] := 
       Map[rule, Partition[bc[Map[bc, lis]], {3, 3}, {1, 1}], {2}]

Finally, the evolution of the game board proceeds until either the game
board stops changing or a specified number of time steps have occurred.

evolution = FixedPointList[update, initconfig, t]

While this program is nice-looking functional code, it can be improved (as
can most code).

lifeGameTess[s_Integer, t_Integer] := 
	Module[
	   {mask = {{2,2,2}, {2,1,2}, {2,2,2}}, initconfig, bc, update},
			initconfig = Table[Random[Integer],{s},{s}] ;
		  bc = Join[{Last[#]}, #, {First[#]}]& ;
			
			update[lis_] := 
         Map[(mask # /. List -> Plus)&, 
             Partition[bc[Map[bc, lis]], {3, 3}, {1, 1}], {2}] /. 
                                           Thread[{5, 6, 7,  _Integer} ->
{1, 1, 1, 0}];
      
      evolution = FixedPointList[update, initconfig, t]
			       ]

lifeGameTess differs from lifeGameMa in the definition of the update function. 

The operation of the anonymous function (mask # /. List -> Plus)& can be
illustrated using a single neighborhood

{{1, 0, 0}, {0, 1, 0}, {1, 1, 1}}

Multiplying this by the value of mask

{{2, 2, 2}, {2, 1, 2}, {2, 2, 2}} {{1, 0, 0}, {0, 1, 0}, {1, 1, 1}}

and applying the transformation rule, List -> Plus, to the result

% /. List -> Plus

returns an integer.  If the anonymous function is applied to each of the
possible neighborhood configurations, an integer is returned that depends
only on the total number of living nn sites and on whether the center site
is alive. These integer values are given in the following table.

nbrhdvals = 
   Table[ Print["i = " , i,",  ",  "j = ", j,",  ", "(i + 2 j) = ", "",
        i + 2 j],  
  {i, 0, 1}, {j, 0, 8}];

I need to explain the basis for constructing this table. In the table, j
gives the number of living nn sites and i = 1 for a living center site and
i = 0 for a dead center site. Mathematically, when (mask # /. List ->
Plus)& is applied to a neighborhood, the center site is weighted by a
factor one (giving1 1  or 0 1) and its nn sites are each weighted by a
factor two (giving 0 2, 1 2, 2 2, 3 2, 4 2, 5 2, 6 2, 7 2, or 8 2) and the
weighted values are added to give one of the 18 values above. Of these
eighteen values, 5, 6 and 7 are pro-life, according to the life & death
rules:
"living sites with two living nn sites remain alive" corresponds to 
(2 2) + (1 1) = 5.    
"any site with three living nn sites stays alive or is born" corresponds to
(3 2) + (0 1) = 6 and (3 2) + (1 1) = 7.

Mapping (mask # /. List -> Plus)& onto the the list of site neighborhoods
returns a list of the integer values for the neighborhoods of the sites.
The updated values of the sites can be determined by applying a set of
transformation rules to the list of computed neighborhood values

Thread[{5, 6, 7,  _Integer} -> {1, 1, 1, 0}]

which changes the values of 5, 6 and 7 to 1 and changes all other integer
values to 0.

While these changes are aesthetically pleasing (to some) they don't
increase the efficiency of the program very much. One thing that would be
expected to increase the speed of the program substantially, would be to
work with game board as a whole rather than deconstructing it to form
neighborhoods to perform the updating and then reassembling the game board
afterwards.

An APL Style Program

The letters in the name APL stand for "A Programming Language" but they
could also be taken to stand for "Array Processing Language". While APL is
not a functional language (there is a functional dialect of APL, known as
J), it does have one important feature in common with functional languages;
its ability to manipulate entire data structures, such as lists. This
capability has been called "the power of large values". It is also present
in Mathematica and it allows us to follow the functional programming dictum
to "deal with data structures as wholes rather then tear them apart and
rebuild them again".

If I create eight different matrices by various rotations of the entire
game board matrix, multiple each rotated matrix by two and add all of them
to the original matrix,

2 (RotateRight[mat] + RotateLeft[mat] + Map[RotateRight, mat] +  
    Map[RotateLeft, mat] + Map[RotateRight, RotateRight[mat]] +
    Map[RotateLeft, RotateRight[mat]] + 
    Map[RotateRight, RotateLeft[mat]] +
    Map[RotateLeft, RotateLeft[mat]]) + mat 

The elements of the resulting matrix are precisely the integer values for
the neighborhoods of the sites.

This method can be used to write yet another version of the Game of Life
program.

lifeGameRot[s_Integer, t_Integer] := 
		Module[{initconfig, ngbrs, rule},
			  initconfig = Table[Random[Integer],{s},{s}] ;
			  ngbrs[mat_]:= 
			               RotateRight[mat]+ 
			               RotateLeft[mat]+
                     Map[RotateRight,mat]+ 
                     Map[RotateLeft,mat]+
                     Map[RotateRight,RotateRight[mat]]+
                     Map[RotateLeft,RotateRight[mat]]+
                     Map[RotateRight,RotateLeft[mat]]+ 
                    Map[RotateLeft,RotateLeft[mat]];
			 evolution = 
		    FixedPointList[
		        ((#+2 ngbrs[#]) /. 
		 Thread[{5, 6, 7, _Integer} -> {1, 1, 1, 0}])&,  initconfig, t]
]

The anonymous function

((#+2 ngbrs[#]) /. Thread[{5, 6, 7, _Integer} -> {1, 1, 1, 0}])&

returns the same result, albeit via a different path, as the update
functions in the previous two programs.

A timing comparision of the lifeGameMa, lifeGameTess and lifeGameRot
programs indicates that the APL style program is at least four times faster
than the functional style programs. While this is gratifying, there remains
one other modification that can be made to squeeze out a bit more speed.

A Rule-Based Style Program

The use of rules takes advantage of the fact that fundamentally,
Mathematica is a rule-based programming language which evaluates
expressions by term-rewriting pattern-matched expressions. By an
appropriate use of rules (using as many as are needed and no more), the
speed of execution can be increased. 

For the Game of Life, various sets of updating rules with differing degrees
of specificity can be written. 

For example,, a rule could be written for each  possible neighborhood (eg.,
update[{{0, 1, 0},{0, 1, 0}, {0, 0, 0}}] := 0) but this approach would
result in 2^9 = 512 rules which would be much too many. 

The life and death rules can be expressedwith  a minimal number of rules by
simply using the exact formulation of the life & death rules (in which
there are two pro-life rules and one rule for all of the remaining
neighborhood patterns).

update[1, 2] := 1;
update[_, 3] := 1;
update[_, _] := 0;

where the first argument of update is the value of the center site of a
neighborhood and the second argument is the number of living nn sites (note
that by using this two-argument rule, we avoid the need to calculate the
integer value of a neighborhood).

Using this rule set in the APL style program eliminates the need to use
transformation rules and gives us the following rather compact,
elegant-looking program (note that the update function is given the
Listable Attribute so that it is automatically mapped onto a list it is
applied to).

lifeGameRule[s_, t_]:=
    Module[{initconfig, ngbrs, update},
        initconfig = Table[Random[Integer],{s},{s}] ;
        ngbrs[mat_]:= 
                     RotateRight[mat]+
                     RotateLeft[mat]+
                     Map[RotateRight,mat]+
                     Map[RotateLeft,mat]+
                     Map[RotateRight,RotateRight[mat]]+
                     Map[RotateLeft,RotateRight[mat]]+
                     Map[RotateRight,RotateLeft[mat]]+
                     Map[RotateLeft,RotateLeft[mat]];
        update[1, 2] := 1;
        update[_, 3] := 1;
        update[_, _] := 0;
        Attributes[update] = Listable;
       
       evolution = FixedPointList[update[#, ngbrs[#]]&, initconfig, t]
          ]

Program Graphics

The graphics code in the program in the Life.m package creates a
three-dimensional graphic. While using 3D graphics to display a 2D CA is
analagous to using 2D graphics to display a 1D CA [Gaylord, 1993], I find
it to be unhelpful for visualizing the Game of Life evolution process and
so I use the following graphics.

Map[
    (Show[Graphics[RasterArray[Reverse[
		 evolution[[#]]/.{1->RGBColor[0,1,0], 0->RGBColor[1,0,1]}]]]])&,                                                           
   Range[Length[evolution]]]

Playing the Game of Life

The Game of Life is most interesting to watch when persistent patterns, or
life forms, occur during the evolution process. Below is a slightly
modified version of the program that can be used to seed life forms.  In
the program, the game board set-up consists of all zero's and patterns are
introduced onto the gameboard via the variable,  lifeform. The graphics are
displayed in a single GraphicsArray as well as in successive animation
frames.

(* s = size of lattice
   t = number of iterations
   n = partition parameter for GraphicsArray
*)

lifeGame[s_Integer, t_Integer, lifeform_List, n_]:=
    Module[{initconfig, ngbrs, update},
       initconfig = Table[0,{s},{s}] ;
       initconfig = ReplacePart[initconfig, 1, lifeform];
       ngbrs[mat_]:= 
                     RotateRight[mat]+
                     RotateLeft[mat]+
                     Map[RotateRight,mat]+
                     Map[RotateLeft,mat]+
                     Map[RotateRight,RotateRight[mat]]+
                     Map[RotateLeft,RotateRight[mat]]+
                     Map[RotateRight,RotateLeft[mat]]+
                     Map[RotateLeft,RotateLeft[mat]];
       update[1, 2] := 1;
       update[_, 3] := 1;
       update[_, _] := 0;
       Attributes[update] = Listable;
       evolution = FixedPointList[update[#, ngbrs[#]]&, initconfig, t];
       animation = Map[(Show[Graphics[RasterArray[
              Reverse[evolution[[#]] /. 
			     {1->RGBColor[0,1,0], 0->RGBColor[1,0,1]}]]]])&,
                                                                 
Range[Length[evolution]]];
    Show[GraphicsArray[Partition[animation, n]]];                 
]

Gliders

A pattern of considerable interest is known as the glider

glider[x_, y_] := {{x, y}, {x+1, y}, {x+2, y}, {x+2, y+1}, {x+1, y+2}}

Introducing one glider lifeform into the Game of Life,

lifeGame[30, 24, glider[25, 15], 5]

Honeyfarms

Another interesting life form is the honeyfarm:

honeyfarm[x_, y_] := 
   {{x, y}, {x, y+1}, {x, y+2}, {x, y+3}, {x, y+4}, {x, y+5}, {x,y+6}};

Here we introduce one honeyfarm function into the Game of Life:

lifeGame[25, 15, honeyfarm[10, 10], 4];

The graphics indicate that after fourteen generations, the honey farm life form appears and the board stops evolving.

Conclusion

We might comment on the use of biological terms in the description of the Game of Life. These terms were originally meant in a metaphorical rather than literal sense since the model was viewed as being too abstract to represent a natural system. Recently however, the Game of Life has been proposed as a realistic model of a co-evolutionary process in an ecosystem. Moreover, the new field of artificial life (which commonly creates cellular automata and investigates their reproductive behaviors) has extended the use of terms from the biological realm to the digital world, making their earlier use in the Game of Life seem prescient. While the use of biological terms for computer-generated patterns is certainly a case of anthropomorphism, there's no reason to discriminate against entities simply because they consist of one's and zero's.

References

Wolfram, Stephen. 1984. "Computer Software in Science and Mathematics", Scientific American, 251(Sept.), pp. 188-203
Gaylord, Richard J. 1993. " One-Dimensional Cellular Automata", Mathematica in Education, 2(x), pp. 21-26 .
Gaylord, Richard J. 1992. " Catastrophes in Complex Systems", Mathematica in Education, 2(x), pp. 19-22 .

Things to come:

In the next column, we will look at a model that is of great interest in statistical physics, the Ising model which is used to model systems of interacting bodies (the model has also been used to discuss imitative behavior in biological and sociological systems). We will discuss both a probabilistic and a deterministic cellular automaton implementation of the model.