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

1. セルオートマトン入門

 ここからはセルオートマトンという道具を使ってコンピュータシミュレーションをする。ここで「道具」というのは次のような意味だ。たとえば、気体の流れや電磁波の伝播などの物理現象は微分方程式(もっと言えば偏微分方程式)で記述されるから、コンピュータシミュレーションをしたければ微分方程式に基づいたモデルを作って計算すればよい。この場合、モデルを作るために微分方程式という「道具」を使うわけだ。社会現象ならたとえば「ゲーム理論」という道具を使うこともあるだろうし、ほかの道具を使うこともあるだろう。

 セルオートマトンはやはりモデルを作るための道具のひとつである。とても簡単でしかも応用範囲が広い。セルオートマトンを使うということは、なんでもかんでも非常に大胆に簡単なモデルにしてしまうということなのだが、逆に偏微分方程式の代わりにも使えるしゲーム理論の代わりにも使えるという便利なものでもある。もちろん、上手に使えばという但し書きはつくのだが。

 とにかく感じをつかんでもらうために、簡単な例で説明しよう。一番簡単な場合として、セルが一方向に並んだ1次元空間のセルオートマトンを考えよう。各セルとその状態に意味を与えることによって、なんらかの現象を表現するモデルを作る。たとえば、各セルにはなんらかの意味での"生物"が一匹住めるとする。セル自体の意味は、部屋でも小屋でも土地でも構わない。

 セルは、そこに生物が「いる(○)」か「いない(●)」かのふたつの状態になりうるとしよう。その場合、たとえば16個のセルを並べた空間全体の状態は、

などと表現できるわけだ。

 さて、これらのセルの変化を考えたい。たとえば、いったいどんな生物を想定しているのかはさておき、以下のような状況を考えたいとしよう。

 次の時刻(1秒後でも10秒後でもいいが)に個々のセルの状態が一斉に変化する。上で想定した状況では、その変化の仕方は、自分と両隣との計3個のセルが今どういう状態にあるかで決まってしまう。3個のセルには全部で2の3乗(=8)通りの状態が可能なので、それぞれの場合について、真ん中にあるセルの状態が次の時刻にYとNのいずれになるかを決めれば、変化の規則が完全に決まる。上の状況は
現在の3個の状態 ●●●●●○●○●●○○ ○●●○●○○○●○○○
次の時刻での真ん中のセルの状態  ● ● ● ○  ● ○ ○ ○

という規則を用意すれば、完全に表現できる。すると上のほうで例に挙げた16細胞空間の状態は(世界に端があるとなにかと面倒なので、空間の両端がくっついた環状の世界だとして) と変化する(自分で確かめてください)。ただし、残念ながら、この規則ではあまり面白いことは起きない

 今の例では、個々のセルの状態は「いる」「いない」のふたつだけで、次の時刻での状態を決めるのは自分を含めて3個のセルの状態だけである。このようなセルオートマトンは2状態3近傍CAと呼ばれる。

 さて、上では一次元空間で生物の「いる・いない」を考えた。セルオートマトンが シミュレーションの「道具」だという意味は、同様の2状態3近傍CAでも、違う規則を設定することにより、まったく別の現象のシミュレーションもできるということだ。
 たとえば、電光掲示板も一種のセルオートマトンとみなすことができる。 一色だけの電光掲示板なら、各セルの状態は「光っている(○)」と「消えている(●)」の2状態となる。「表示は必ず右へ移動する」という現象を記述したければ、規則としては
現在の3個の状態 ○○○○○●○●○○●● ●○○●○●●●○●●●
真ん中のセルの次の時刻での状態  ○ ○ ○ ○  ● ● ● ●

とすればよい。要するに、左隣のセルが○なら他のセルの状態にかかわらず次の時刻で真ん中のセルが○になるという規則である。

 この原理がわかってしまえば、セルがもっとたくさんの状態になれるモデルや、両隣だけではなくもっと遠くのセルが関与する規則へは、すぐさま拡張できる。 多色表示の電光掲示板なら、各セルのとりうる状態の種類は「色の数+1」である。当然、"+1"は消灯状態の分である。

2.簡単なプログラム

 2状態3近傍CAをとにかくプログラムにしよう。 規則は最初に説明した「いる・いない」のものを使うことにする。 まずは、煩雑だが素直なプログラムを書いてみる。 とりあえず、両端のセルの処理を省くために、両端は変化しないことにしよう。
 次のプログラムでは、各セルの状態を整数型配列 s[ ] に格納している。状態(s[ ] の内容)「いる」と「いない」は、それぞれ 0 と 1 という数で表わされるとする

#include<stdio.h>
#include<stdlib.h>
#define N 70
main(){
 int i,j,step,seed;
 int s[N], snew[N];
 int left,center,right;

 scanf("%d%d",&step, &seed);
 srandom(seed);

/* set initial random state */
 for(i=0; i<N; ++i)s[i]= random()%2;


 for(j=0; j<step; ++j){
  for(i=1; i< N-1; ++i){

   left = s[i-1];
   center = s[i];
   right = s[i+1];

   if(left == 0 && center == 0 && right ==0)snew[i] = 0;
   else if(left == 0 && center == 0 && right == 1)snew[i] = 0;
   else if(left == 0 && center == 1 && right == 0)snew[i] = 0;
   else if(left == 0 && center == 1 && right == 1)snew[i] = 1;
   else if(left == 1 && center == 0 && right == 0)snew[i] = 0;
   else if(left == 1 && center == 0 && right == 1)snew[i] = 1;
   else if(left == 1 && center == 1 && right == 0)snew[i] = 1;
   else if(left == 1 && center == 1 && right == 1)snew[i] = 1;
 }

  for(i=0; i<N; ++i)s[i]=snew[i];

  for(i=0; i<N ;++i){
    if(s[i]==0)printf(" ");
    else printf("#");}
  printf("\n");
  }
}
中ほどが煩雑だが、よく見れば上で決めた規則をそのままプログラムに したことがわかるだろう。セルの状態を更新する手順は以下の通りである。
  1. i番目のセルの状態 (s[i]) を決めるために、 両隣 (s[i-1]とs[i+1]) が必要なので、まずはそれら center, left, right という変数に代入しておく。
  2. center, left, right の値の組み合わせ には八通りの可能性があるので、そのうちでどのパターンかを一個ずつ判定する。
  3. 組み合わせがわかれば、規則に従って次の時刻での状態が決まるので、 それを snew[i] という新しい変数(配列)に代入する。
  4. すべてのセルについて snew の値が決まったら、その内容を s に代入すれば、 すべての s の内容が更新される
 その他、このプログラムでは
  1. システムの長さ(セルの総数)はN=70と定義(#define N 70)
  2. キーボードからステップ数と乱数の種を入力すると、計算を開始
  3. 最初の時刻でのセルの状態は乱数で決める(0または1をランダムに並べる)
  4. 1ステップごとにセルの状態を出力
となっている。

 右端と左端がぐるっとつながった円状のシステムとするには、 left, center, right に値を代入する部分を三つに場合わけする。 変更点だけ書くと
  for(i=0; i< N; ++i){
   if(i==0){
     left = s[N-1];
     center = s[0];
     right = s[1];}
   else if(i==N-1){
     left = s[N-2];
     center = s[N-1];
     right = s[0];}
   else {
     left = s[i-1];
     center = s[i];
     right = s[i+1];}
とでもすればよいだろう。要するに両端だけ特別扱いするわけだ。

 さて、上では規則をプログラム中に書き込んでいた(ifが八個並んでいる部分の 右端に書いた 0,0,0,1,0,1,1,1 が規則そのものである)。 別にこれでもいいのだが、いろいろな規則を試してみたいときなど、規則をいちいち プログラムに書き込んでコンパイルしなおすのも面倒といえば面倒だ。そこで、規則を キーボードから入力できるように変更してみる。
#include<stdio.h>
#define N 70
main(){
 int i,j,step,seed;
 int s[N], snew[N];
 int left,center,right;
 int rule[8];

 scanf("%d%d%d%d%d%d%d%d",&rule[0],&rule[1],&rule[2],&rule[3],&rule[4],&rule[5],&rule[6],&rule[7]);
 scanf("%d%d",&step, &seed);
 srandom(seed);

/* set initial random state */
 for(i=0; i<N; ++i)s[i]= random()%2;


 for(j=0; j<step; ++j){
  for(i=0; i< N; ++i){
   if(i==0){
     left = s[N-1];
     center = s[0];
     right = s[1];}
   else if(i==N-1){
     left = s[N-2];
     center = s[N-1];
     right = s[0];}
   else {
     left = s[i-1];
     center = s[i];
     right = s[i+1];}

   if(left == 0 && center == 0 && right ==0)snew[i] = rule[0];
   else if(left == 0 && center == 0 && right == 1)snew[i] = rule[1];
   else if(left == 0 && center == 1 && right == 0)snew[i] = rule[2];
   else if(left == 0 && center == 1 && right == 1)snew[i] = rule[3];
   else if(left == 1 && center == 0 && right == 0)snew[i] = rule[4];
   else if(left == 1 && center == 0 && right == 1)snew[i] = rule[5];
   else if(left == 1 && center == 1 && right == 0)snew[i] = rule[6];
   else if(left == 1 && center == 1 && right == 1)snew[i] = rule[7];
 }

  for(i=0; i<N; ++i)s[i]=snew[i];

  for(i=0; i<N ;++i){
    if(s[i]==0)printf(" ");
    else printf("#");}
  printf("\n");

  }
}

 ここでは新たな整数配列 rule[ ] を用意して、キーボードから入力した規則をそこへ 代入することにした。実行時に規則として八個の数字を入力する。続いてステップ数と乱数の種を入力すれば計算を開始する。なお、規則として入力する数字は 0 または 1 である。他の数をいれても動くかもしれないが、何をやっているかはわからない。

2B. もうちょっとスマートなプログラム

 上のプログラムは if が八個並ぶ部分が煩雑であるが、工夫するとはるかにスマートなプログラムを書くことができる。もっとも、無理にそうしなくてもいいので、ここは興味のある人だけ読めばいいです。興味がなければ、最後の「発展」にいってください。

#include<stdio.h>
#define N 70
main(){
 int i,j,step;
 int s[N], snew[N];
 int rule[8];

 scanf("%d%d%d%d%d%d%d%d",&rule[0],&rule[1],&rule[2],&rule[3],&rule[4],&rule[5],&rule[6],&rule[7]);
 scanf("%d",&step);

/* set initial random state */
 for(i=0; i<N; ++i)s[i]= random()%2;

 for(j=0; j<step; ++j){
  snew[0] = rule[s[N-1]*4+s[0]*2+s[1]];
  for(i=1; i< N-1; ++i){
    snew[i] = rule[s[i-1]*4+s[i]*2+s[i+1]];}
  snew[N-1] = rule[s[N-2]*4+s[N-1]*2+s[0]];

  for(i=0; i<N; ++i)s[i]=snew[i];

  for(i=0; i<N ;++i){
    if(s[i]==0)printf(" ");
    else printf("#");}
  printf("\n");
  }
}
  1. システムの長さ(セルの総数)はN=70と定義。上と同様、右端と左端がぐるっとつながった円状のシステムとする(周期的境界条件とよぶ)
  2. 各セルの状態を整数型配列s[ ]に格納している。状態は0または1という数で表わされるとする
  3. 状態変更規則は整数型配列rule[ ]に格納される。 これは実行時に端末から読み込む。
    rule[ ]の要素番号は、隣接する3セルの現在の状態を以下のように表す
    ruleの要素番号 01234567
    3セルの現在の状態 000001010011 100101110111

    実は3セルの状態を並べたものをひとつの二進数とみなすとき、その数が要素番号になっている。たとえば二進数の011を十進数になおすと3である

    状態変更規則は、これら8つの状態それぞれに対して、次の時刻に真ん中のマスが0または1のどちらの状態になるかを決めてやればよい。 たとえば、3マスの和が奇数なら真ん中のマスが1になり偶数なら0になるという規則にしたければ、
    ruleの要素番号 01234567
    真ん中のマスの次の時刻での状態 0110 1001

    とすればよい。なお、このとき、表の下段にある八つの数字の並びをやはり2進数だと みなすと105になるので、この規則はrule105と呼ばれる(Wolframの命名規則)
  4. 実行するステップ数stepを端末から入力

 ここまでが準備。以下、シミュレーション本体の実行部分を解説する。

  1. まず、初期状態の設定。
     for(i=0; i<N; ++i)s[i]=0;
     s[N/2]=1;
    
    ここでは、すべてのマスの状態をいったん0にしたのち、真ん中だけを1にしている。つまり、このプログラムでの初期状態は真ん中だけ1である。 ここはいろいろな変更が可能だろう。たとえば、すべてのマスの状態を乱数で決めたり、あるいは端末から初期状態を読み込めるようにするなどの工夫をしてみるとよい。

  2.  for(j=0; j<step; ++j){
    
    jを制御変数として、以下の{}内をstep回繰り返す

  3.   snew[0] = rule[s[N-1]*4+s[0]*2+s[1]];
    
    この行では、まず第0マスの状態を新しくする。第N-1マスの状態を4倍したものと第0マスの状態を2倍したものと第1マスの状態とを足したものは、つまり三つのマスの状態を2進数で表現したものとなる。新しい状態はその2進数を配列ruleの要素番号とすれば得られるので、それをsnew[]という配列の第0要素にいれておく。 ここで、いきなりs[0]にいれないのは、それをやってしまうとs[1]の状態を決めるときに変更されたs[0]を使うことになるからである。
  4.   for(i=1; i< N-1; ++i){
        snew[i] = rule[s[i-1]*4+s[i]*2+s[i+1]];}
      snew[N-1] = rule[s[N-2]*4+s[N-1]*2+s[0]];
    
    ここで、上と同じことを第1マスから第N-2マスについて繰り返し、最後に第N-1マスの状態を作る。第N-1マスについては周期的境界条件によって第0マスの状態も必要となる

  5.   for(i=0; i<N; ++i)s[i]=snew[i];
    
    すべてのマス目の新しい状態がsnewに書き込まれたので、それらをsにコピーする。 これで配列sの内容が更新された。

  6.   for(i=0; i<N ;++i){
        if(s[i]==0)printf(" ");
        else printf("#");}
      printf("\n");
    
    すべてのマスの状態を出力している。ここでは升目の状態に応じて、状態が0なら空白を出力し、1なら#記号を出力している。もちろん、別の記号を出力してもよいし、単にprintf("%d",s[i])でs[i]の値そのものを出力することもできる。全マス分のN個の記号を出力ののち改行。

発展

  1. 初期状態として、真ん中のセルだけが 1 で、他のすべてのセルが 0 であるような状態からスタートするように変更せよ
  2. "左右対称"な規則について、真ん中の1個が1である初期状態からスタートして、20ステップ後にもすべてが0にはなっていない規則をいろいろ見つけ、どんなパターンができるか調べよ
  3. 初期状態を端末から(あるいはリダイレクションを使ってファイルから)読み込めるように変更せよ
  4. 1を車と見立て(0は空白)、各ステップで車が右に1マスだけ進むシミュレーションの規則を考えて、実行せよ。ただし、右隣が空いていれば進むが、右隣がつまっているときは、空くまで待つとする

次へ