４点を参照する１次元セルオートマトン

セルオートマトン

SimCityの最新作が発売しますね．SimCity的なものを科学的に取り扱ったのがセルオートマトンである(CA)．CAとは，離散的な格子状のセルが値をそれぞれ持っているときに，近くのセルの値を使った簡単なルールによって，時間的に値を変化させていく計算モデルのことである．ライフゲームなんかが有名ですね．

Stephan Wolframが体系的に調べたのが１次元のCAだ．1次元のCAは，横軸をそれぞれのセルの位置，縦軸を時間に取った2次元の画像によって，時間発展を表すことができるから便利だ．彼が調べたのは，ある点とその両隣の点での３点での値を参照するものであった．その結果，興味深い現象が観察されたのだった．では，４点を参照した場合にはどうなるのだろう．気になったので調べてみた．

セルが0か1しか取らない場合，隣り合う４つのセルの組み合わせは次の16通りある．

それぞれに対応して，左中のセルの次のステップでの値が決定される．情報の伝播速度が方向によって異なり，対称性が悪くなって，やや気持ち悪いが仕方がない．

例えば，

　　　

この下の色の並びを２進数の数とみなして，10進数で表したものがWolfram codeである．上記の場合は，2進数で010001000011001であり，10進数では16921である．このルールをルール16921と呼ぶ．

可能なルールは，2^(2^4)=65536通り．Wolframの調べた基本CAでは，2^(2^3)=256通りのルールしかないので，それと比べると調べる量がかなり膨大だ．CAは二重累乗になっているから厄介だ．超指数爆発を起こすのだ．１秒１通りの絵を見ても，18.2時間かかる．ちょっと基本CAのように分類したりするのは，作業が膨大すぎて手作業ではちょっとできそうにない．計算機を用いても4点が限度だろうと思う．５点までできれば，２次元で上下左右方向すべてを見ていることになるから，面白いものが見れると思うのだが，難しいな．

計算コード

Mathematicaの使い方を知らないので，C++でコードを作りました．ソースコードは，
4CellAutomata.cpp
においておく．gccでコンパイルと動作確認を行なっている．

PBM形式の画像ファイルが出力される．256セル×86ステップの画像が65536枚で約2.7GBの容量になる．バイナリでの書き出しが上手くいかなかったのだ．画像だけ欲しいのであれば，一旦，PBMを出力後にImageMagickとかでGIFとかに変換すれば，かなり圧縮できる．ただ，それをするとポスト処理のための読み込みが面倒になってしまう．

ちなみに，ImageMagickでの一括変換はコマンドラインにて，

        $ mogrify -format gif *.pbm

である．


追記(2/22/2013)：
32ビット環境だとint型の最大値32767で，int型では全てのルールを表示できない．Wolfram Codeの評価をunsigned int型に変更した．
コマンドラインで，実行ファイルの後にwolfram codeを入力すると，そのルールで実行される．何も入力しなければ，ランダムにwolfram codeを選ぶ．

結果

初期条件は，１点のセルのみ■の値で，他のセルは□という条件で行った．

全部の図を貼れないし，確認も出来ないので，ランダムに選んで見つけた，興味深いものだけ紹介する．

全ての画像は，
4CA_Img00000-32767.7z (13.1MB)
4CA_Img32768-65535.7z (10.2MB)
にアップロードしておく．都合により２ファイルに分ける．また，圧縮率の高い7z形式で圧縮している．

rule 16921

rule 16830

rule 30030

rule 50044

rule 50092

rule 50118

rule 38236

rule 5050

rule 37926

rule 37880

キリがないので，このあたりで止めておく．３点参照のCAと大きく異なっていることは，現れるパターンが４点参照の方が多様であるということである．有機的なパターンが見られるようになった．また，定常な状態になるケースも，定常状態に落ち着くのに時間がかかる．また，規則的な模様であっても，複雑な模様である．また，左側は角度１の傾きの直線と角度２の傾きの直線の間の領域は，一部の情報しか伝わらないため，下のように特徴が色分けられることが多い．ただし，傾きは1/2の場合もかなりある．

要するに，ルールを複雑にすると，それ以上に現れる現象も複雑になってしまうということだ．

今後もまだするなら

正直，結果を眺めているだけでも飽きない．Wolframの著書"A New Kind of Science"もいろいろ試して遊んでみたというのがほとんどだ．シムシティ以上にハマってしまう危険だ．ただ，絵を眺めているだけじゃあ原理の深淵に潜っていかない．Wolframも基本CAを４つのクラスに分けて，分類したりしている．ただ，手作業で分類するのは，ちょっと不可能なので，計算機で機械的に分類できる方法を考えたい．

参考文献

Wolfram, S. (2002) A New Kind of Science.