Game of Life, Part 2, Sparse Matrices

著者 Cleve Moler, September 10, 2012

2 ビュー (過去 30 日間) | 0 いいね | 2 コメント

The Game of Life, including the infinitely expanding universe, is a gorgeous application of MATLAB sparse matrices.

The Code
The Glider
Life Lexicon
Achim p144

The Code

The universe in the Game of Life is represented by a sparse matrix X that is mostly all zero. The only nonzero elements are ones for the live cells. Let's begin by describing the code that implements Conway's Rule:

A live cell with two live neighbors, or any cell with three live neighbors, is alive at the next step.

At any particular step in the evolution, X represents only a finite portion of the universe. If any cells get near the edge of this portion, we reallocate storage to accommodate the expanding population. This only involves adding more column pointers so it does not represent a significant amount of additional memory.

A basic operation is counting live neighbors. This involves an index vector p that avoids the edge elements.

%    m = size(X,1);
%    p = 2:m-1;

Here is the code that creates a sparse matrix N with elements between 0 and 8 giving the count of live neighbors.

%    N = sparse(m,m);
%    N(p,p) = X(p-1,p-1) + X(p,p-1) + X(p+1,p-1) + X(p-1,p) + ...
%       X(p-1,p+1) + X(p,p+1) + X(p+1,p+1) + X(p+1,p);

This is one of my all-time favorite MATLAB statements. With MATLAB matrix logical operations on sparse matrices, this is Conways Rule:

%    X = (X & (N == 2)) | (N == 3);

The Glider

Let's see how this works with the glider.

   X = sparse(7,7);
   X(3:5,3:5) = [0 1 0; 0 0 1; 1 1 1];
   disp('X')
   t = int2str(X); t(t=='0') = '.'; disp(t)

X
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  1  .  .  .
.  .  .  .  1  .  .
.  .  1  1  1  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .

Count how many of the eight neighbors are alive. We get a cloud of values around the glider providing a census of neighbors.

   m = size(X,1);
   p = 2:m-1;
   N = sparse(m,m);
   N(p,p) = X(p-1,p-1) + X(p,p-1) + X(p+1,p-1) + X(p-1,p) + ...
       X(p-1,p+1) + X(p,p+1) + X(p+1,p+1) + X(p+1,p);
   disp('N')
   t = int2str(N); t(t=='0') = '.'; disp(t)

N
.  .  .  .  .  .  .
.  .  1  1  1  .  .
.  .  1  1  2  1  .
.  1  3  5  3  2  .
.  1  1  3  2  2  .
.  1  2  3  2  1  .
.  .  .  .  .  .  .

Only the nose of the glider is alive and has two live neighbors.

   disp('X & (N == 2)')
   t = int2str(X & (N == 2)); t(t=='0') = '.'; disp(t)

X & (N == 2)
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  1  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .

Four other cells have three live neighbors

   disp('N == 3')
   t = int2str(N == 3); t(t=='0') = '.'; disp(t)

N == 3
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  1  .  1  .  .
.  .  .  1  .  .  .
.  .  .  1  .  .  .
.  .  .  .  .  .  .

"OR-ing" these last two matrices together with "|" gives the next orientation of the glider.

   disp('(X & (N == 2)) | (N == 3)')
   t = int2str((X & (N == 2)) | (N == 3)); t(t=='0') = '.'; disp(t)

(X & (N == 2)) | (N == 3)
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  .  .  .  .  .
.  .  1  .  1  .  .
.  .  .  1  1  .  .
.  .  .  1  .  .  .
.  .  .  .  .  .  .

Repeating this three more times moves the glider down and to the right one step.

Life Lexicon

Life Lexicon is a cultural treasure. It should be listed as a UNESCO World Heritage Site. The primary site is maintained by Stephen A. Silver. He has help from lots of other folks. I gave these two links in part one of the blog last week. Just go poke around. It's great fun.

Text version: <http://www.argentum.freeserve.co.uk/lex_home.htm>

Graphic version: <http://www.bitstorm.org/gameoflife/lexicon>

The lexicon has 866 entries. About half of them are of historical and computational complexity interest. Read them to learn the history of the Game of Life. For example, the starting population known as the "ark" takes 736692 steps to stabilize. Half of them, 447, are matrices that we can use as starting populations.

Achim p144

life_lex reads the text version of the lexicon and caches a local copy if one doesn't already exist. It then uses random entries as starting configurations. As just one example, we learn from the lexicon that the following population was found by Achim Flammenkamp, Dean Hickerson, and David Bell in 1994 and that its period is 144. We're showing every fourth step.