2010年7月13日火曜日

2次元セルオートマトンとエントロピー

このブログ記事をはてなブックマークに追加

2状態の2次元セルオートマトン(Cellular Automaton)をActionScript 3.0 (AS3)で作ってみた。2次元セルオートマトンで最も有名なのはライフゲーム(Conway's Game of Life)だろう。プログラムでは初期ルールをライフゲームとしている。初めにC++で書こうと思ったのだけど、Web上でグラフィカルに操作できないとつまらないと思い、AS3でFlashとして作成しwonderflに登録することにした。ついでに時間的なエントロピー変化を視覚的に認識できたら面白そうだと思ったので、それについても実装した。

今回、セルオートマトンのコードを書こうと思ったのはTCO Marathon Round 2の問題として出されたからだ。2次元セルオートマトンのサイズと初期配置、それにルールが与えられ、指定した世代で生存セルが最大になるように初期配置を変更しろという問題だ。そして、問題を解くために色々と調べているうちにセルオートマトンが面白く感じられたのでブログ記事にしてみた。とは言っても今回のコードはコンテストのような特別なチューンなどはしていない。ビット配列や剰余テーブルなどは使っているがどちらかというと読みやすさを優先させている。

作成したプログラムを以下に示す。



1-9 : ルール設定 - セルの周りの生存セル数(0-8)に対応 : '.' 死亡, '&' 変化, '+' 誕生, '=' 維持 SPACE : 一時停止 ENTER : リセット V : メッセージ表示/非表示 Z : 初期生存セルの割合を減少 X : 初期生存セルの割合を増加

最初に実行されるルールはライフゲームだ。つまり、セルの回りに2つの生存セルがあった場合、そのセルは現状「維持」となり、3つの生存セルがあればそこに生存セルが「誕生」する。生存セルが1つ以下か4つ以上の場合は死亡セルとなる。また、上端と下端、右端と左端は繋がっていて周期境界条件となっている。現在のルール設定はFlash画面の左下に[..=+.....]と表示される。[]内の9つの文字はそれぞれ左から順に、セルの回りに生存セルがない場合、1つある場合、2つある場合、…周りがすべて生存セル(8つ)の場合を表していて、. は「死亡」(死亡セルとなる)、+ は「誕生」(生存セルとなる)、= は「維持」(現在のセルのまま)、& は「変化」(死亡セルであれば生存セルとなり、生存セルであれば死亡セルとなる)となっている。ルールの変更はキーボードの1~9キーに対応しており、キーを押す毎に、.&+= と変化していく。

ルールの右隣にある数値は初期状態の生存セルの割合で、その右隣の数値は現在の生存セルの割合を示している。初期状態の生存セルの割合はXキーで増加、Zキーで減少させることができる。また、一番上に書かれているFPSは1秒間に表示されるフレーム数を示し、Nは現在の生存セル数、Hはエントロピーを示す。

ここでエントロピーについての説明をしておく。時間的なエントロピーHについては下記の情報エントロピーの式を用いた。


1世代におけるセルの変化は0→0、0→1、1→0、1→1の4通りあり、それらの確率Pkからエントロピーを求めている。またlogの底を4とすることでHを0~1にスケールしている(参考: 2次元セルオートマトンの相転移と結晶化)。

表示されるセルの色は生存セル数が多いほど赤く、少ないほど青く表示される。また、背景色はエントロピーに比例しており、エントロピーが高いほど明るい緑となり、低いほど暗くなる。

以下にいくつかのルールによる変化を例示する。

ルール [..=+.....] / 初期生存セルの割合 0.3

これはライフゲームのルールであり、初期生存セル数の割合は0.3としている。最初は生存セル数が多くエントロピーが高いので背景は比較的明るい緑となっているが、徐々に生存セル数およびエントロピーが減ってきて暗くなってきている。5万ほどいた生存セルも1万を切るぐらいに減ってしまい、活動しているセルも縮小していることが分かる。


ルール [..=++....] / 初期生存セルの割合 0.9

これはライフゲームのルールに周りが4つのセルで「誕生」するルールを加えたものだ。初期生存セル数の割合を0.9と高くして最初にほとんどのセルを死滅させている(周りの生存セル数が高いと次の世代で「死亡」するため)。これにより非常に少ない生存セルから始めることができる。このルールではほんの僅かに残った生存セルからでも驚異的な再生力を示し、最終的にはすべてに生存セルが生息し、エントロピーは0.98以上と非常に高い値を示す。


ルール [..=+====.] / 初期生存セルの割合 0.1

これは現状維持の性質を非常に強く持ったルールで、初期生存セル数の割合を0.1から始めるとスピードは遅いが侵食するように生存セルが繁殖していき、最終的には全体の75%ほどを生存セルで占める。動きはほとんど見られないのでエントロピーは0.4ほどであるが、生存セル数が多いので画面は赤くなる。


この他にも[..+=.....] 0.9[..=+=....] 0.9[..=+&....] 0.9なども面白いので試してみて欲しい。セルの繁殖する様は、実際の細胞増殖を顕微鏡で眺めているかのようであり、とても興味深い。

1 コメント:

匿名 さんのコメント...

一風変わったセルオートマトンです
http://www7b.biglobe.ne.jp/~gca/