セルオートマトンでシミュレーションをしよう(3)

3. Game of Life (1)

セルオートマトンの中でもっとも有名なGame of Life（ライフ・ゲーム）のプログラムを書いてみよう。 これは２次元９近傍ＣＡの一種である。なお、Game of Lifeの解説とシミュレータの完成品を 置いたホームページは「関連コンテンツへのリンク」から辿れる。

プログラムの詳細

1. 盤面は横NXセル、縦NYセルの長方形
2. １次元ＣＡと同様に、各セルの状態を記憶する整数配列 s と状態変更のための整数配列 snew を用意する。ただし、今回はどちらも２次元配列とする。つまり、横にx番目、縦にy番目のセルの状態は s[x][y] に格納される。
3. 各セルのとりうる２状態を0と1とする。
4. 初期状態はすべてのセルにランダムに0か1をわりあてるものとする
5. 状態変更の規則は二次元配列 rule[state][sum] にあらかじめ記憶させておく。具体的には整数変数 state に状態を決めるべきセルの現在の状態（0または1）、整数変数 sum にその周囲８セルに含まれる1の総数（0から8）を与えると、そのときの配列要素 rule[state][sum] が新しいセルの状態（0または1）になるように rule の要素を決めておく。つまり、配列の中身は下表のようにする。

   	sum = 0	1	2	3	4	5	6	7	8
   state = 1	0	0	1	1	0	0	0	0	0
   state = 0	0	0	0	1	0	0	0	0	0

   ruleが用意できれば（sumは既に計算されているものとして）

   state=s[x][y]; snew[x][y]=rule[state][sum];

   とするだけで s[x][y] の新しい状態が snew[x][y] に格納される。
6. ２次元盤面の左端と右端がつながり、上端と下端がつながった「周期的境界条件」を採用することにする。 問題は各セルについて周囲８個のセルにある1の総数を計算する部分である。 すなおにプログラムを書こうとすれば、どのセルの周囲を足しているかによって場合分けしなくてはならない。中心のセルの位置は

   (1)上左隅(2)上右隅(3)下左隅(4)下右隅(5)上辺（隅以外）(6)下辺（隅以外）(7)左辺（隅以外）(8)右辺（隅以外）(9)辺以外

   の９通りに分類できるから、たとえばその部分のプログラムは

   if(y==0){ if(x==0){ sum=s[NX-1][NY-1]+s[0][NY-1]+s[1][NY-1]+s[NX-1][0]+s[1][0]+s[NX-1][1]+s[0][1]+s[1][1];} else if(x==NX-1){ sum=s[NX-2][NY-1]+s[NX-1][NY-1]+s[0][NY-1]+s[NX-2][NY-1]+s[0][NY-1]+s[NX-2][1]+s[NX-1][1]+s[0][1];} else{ sum=s[x-1][NY-1]+s[x][NY-1]+s[x+1][NY-1]+s[x-1][NY-1]+s[x+1][NY-1]+s[x-1][1]+s[x][1]+s[x+1][1];} } else if(y==NY-1){ if(x==0){ sum=s[NX-1][NY-2]+s[0][NY-2]+s[1][NY-2]+s[NX-1][NY-1]+s[1][NY-1]+s[NX-1][0]+s[0][0]+s[1][0];} else if(x==NX-1){ sum=s[NX-2][NY-2]+s[NX-1][NY-2]+s[0][NY-2]+s[NX-2][NY-1]+s[0][NY-1]+s[NX-2][0]+s[NX-1][0]+s[0][0];} else{ sum=s[x-1][NY-2]+s[x][NY-2]+s[x+1][NY-2]+s[x-1][NY-1]+s[x+1][NY-1]+s[x-1][0]+s[x][0]+s[x+1][0];} } else{ if(x==0){ sum=s[NX-1][y-1]+s[0][y-1]+s[1][y-1]+s[NX-1][y]+s[1][y]+s[NX-1][y+1]+s[0][y+1]+s[1][y+1];} else if(x==NX-1){ sum=s[NX-2][y-1]+s[NX-1][y-1]+s[0][y-1]+s[NX-2][y]+s[0][y]+s[NX-2][y+1]+s[NX-1][y+1]+s[0][y+1];} else{ sum=s[x-1][y-1]+s[x][y-1]+s[x+1][y-1]+s[x-1][y]+s[x+1][y]+s[x-1][y+1]+s[x][y+1]+s[x+1][y+1];} }

   とでもすればできる。これで、s[x][y] の周囲８個のセルにある1の総数が整数変数 sum に格納される。場合分けをもう少しスマートにしたり、足し算のしかたを工夫したりという改良の余地はあるが、基本は上のようなプログラムである。

   しかし、これではプログラムが長たらしくなってしまい、間違いも起こりやすい（計算速度の上でも損なのだが、プログラミング初心者は計算速度や効率について気にしないほうがよい。むしろ、プログラムが読みにくくなり間違いが起こりやすいことのほうが問題）。 ここでは、少々トリッキーだが、以下のような方法を採用しよう

   盤面を縦横とも２マスずつ大きくする。つまり、配列 s の大きさを NX×NY ではなく、(NX+2)×(NY+2) とする。 これを本来の盤面の上下左右にそれぞれ１列ずつ余分のマス目がついているものとし、そこには反対端の列の状態をコピーしておく。たとえば、NX=NY=4の場合は下図のようにする。

   (15)	(12)	(13)	(14)	(15)	(12)
   (3)	0	1	2	3	(0)
   (7)	4	5	6	7	(4)
   (11)	8	9	10	11	(8)
   (15)	12	13	14	15	(12)
   (3)	(0)	(1)	(2)	(3)	(0)

   ここで、0から15までが本来の盤面であり、"かっこ"で囲んだ数字のセルには本来の盤面の該当するセルの内容がコピーされる。 このように端のセルのコピーを反対側に用意しておけば、0から15までのどのセルも盤の端ではなくなるので、セルの分類をせずに周囲８セルの和を計算することができる。すべてのセルについて状態を変更したら、最後に端のコピーを作ればよい。

プログラム例（計算部分）

#include<stdio.h>
#include<stdlib.h>
#define NX 30
#define NY 10
main()
{ 
  int s[NX+2][NY+2], snew[NX+2][NY+2];
  int rule[2][9];
  int x,y,i;
  int step,rseed;
  int state,sum;

/* set rule */
  for(i=0;i<9;++i)rule[0][i]=rule[1][i]=0;
  rule[0][3]=1;
  rule[1][2]=rule[1][3]=1;

/* input step and rseed */
  scanf("%d%d",&step,&rseed);
  srandom(rseed);

/* set random initial state */
  for(y=1;y<NY+1;++y){
   for(x=1;x<NX+1;++x)s[x][y]=random()%2;
  }
/* transfer boundary */
  for(x=1;x<NX+1;++x){
   s[x][0] = s[x][NY];
   s[x][NY+1] = s[x][1];
  }
  for(y=0;y<NY+2;++y){
   s[0][y] = s[NX][y];
   s[NX+1][y] = s[1][y];
  }

  for(i=0; i<step; ++i){
/* start one step */
     for(y=1;y<NY+1;++y){
      for(x=1;x<NX+1;++x){
/* one cell*/
        state=s[x][y];
        sum=s[x-1][y-1]+s[x-1][y]+s[x-1][y+1]
           +s[x][y-1]+s[x][y+1]
           +s[x+1][y-1]+s[x+1][y]+s[x+1][y+1];
        snew[x][y]=rule[state][sum];
     }}
/* transfer snew[][]  to s[][] */
     for(y=1;y<NY+1;++y){
      for(x=1;x<NX+1;++x)s[x][y] = snew[x][y];
     }
/* transfer boundary */
     for(x=1;x<NX+1;++x){
      s[x][0] = s[x][NY];
      s[x][NY+1] = s[x][1];
     }
     for(y=0;y<NY+2;++y){
      s[0][y] = s[NX][y];
      s[NX+1][y] = s[1][y];
     }

/* display one step */
 printf("-----------------------------------------------\n");
  for(y=1;y<NY+1;++y){
   for(x=1;x<NX+1;++x){
    {if(s[x][y]==1) printf("o");
      else printf(" ");}
    }
   printf("\n");
  }

}
}

1. ターミナルからステップ数 step と乱数の初期値 rseed の値を入力する。どちらも整数変数
2. 初期状態を作るための乱数だが、特によい乱数でなくてもいいので、Ｃ言語標準の random() を使った。srandom(rseed) はその初期化をするもので、変数 rseed には適当な整数値を与える。srandomは一度実行すればよく、以後 random() を実行するたびに新しい整数乱数が発生される。randomを使うために最初の部分に

   #include<stdlib.h>

   を追加する。 全セルにランダムに状態を割り当てるのが以下の部分

   /* set random initial state */ for(y=1;y<NY+1;++y){ for(x=1;x<NX+1;++x)s[x][y]=random()%2; }

   random()%2で0または1がランダムに生成される。境界の処理のため、本来の盤面は横(x)が1からNXまで、縦(y)が1からNYまでであることに注意。
3. 盤面の状態ができたら、端を反対側にコピーする。以下がその部分

   /* transfer boundary */ for(x=1;x<NX+1;++x){ s[x][0] = s[x][NY]; s[x][NY+1] = s[x][1]; } for(y=0;y<NY+2;++y){ s[0][y] = s[NX][y]; s[NX+1][y] = s[1][y]; }

   ループの範囲に注意すること。xについては1からNXまでだが、yについては0からNY+1までのループとなっている。理由を考えてみよ。
4. 境界の処理を工夫したので、各セルについての計算は

   /* one cell */ state=s[x][y]; sum=s[x-1][y-1]+s[x-1][y]+s[x-1][y+1] +s[x][y-1]+s[x][y+1] +s[x+1][y-1]+s[x+1][y]+s[x+1][y+1]; snew[x][y]=rule[state][sum];

   と非常に簡単化された。if文を並べて９通りに分類したものと比較してみれば、その違いは歴然だろう。これをすべてのセルについて行なうと、新しい状態がsnewに格納される。
5. snew にすべてのセルの状態が格納されたら、それをsに書き戻す。

   /* transfer snew[][] to s[][] */ for(y=1;y<NY+1;++y){ for(x=1;x<NX+1;++x)s[x][y] = snew[x][y]; }

6. 最後に上でやったのと同様にして、端のセルの状態を反対側にコピーすれば1ステップが完了である