ライフゲームは、2次元のセル・オートマトンのひとつで、英国の数学者ジョン・H・コンウェイによって考案された規則によるものである。1970年にマーティン・ガードナーが紹介するや否や、当時のハッカーらが熱狂し、さまざまなパターンが発見された。特に、有限のパターンから無限に成長するパターンが存在するか否かは発表時未解決で、懸賞問題であった。ゲームとはいっても、一人ゲームどころか、初期状態を決める以外はプレーヤーを全く必要としない珍しい「ゼロ人ゲーム」(無理矢理にゲームとして分類するならば)である。
概要
ライフゲームは、無限に広がる2次元の格子のマス目で展開される(囲碁のように格子点でもよいのだが、普通はマス目とする)。マス目には2状態があり、片方は生物がいない状態、もう片方は生物がいる状態である。生物がいないのが基本状態であり、初期状態において有限個の「生物がいる」状態のマスがあるのに対して、残りの無限個のマスは「生物がいない」状態とするのが普通である。以下、生物がいる状態を「黒」、生物がいない状態を「白」とする。マス目の状態は、離散的な単位時間ごとに全て一斉に変化する。あるマスが、次の単位時間にどの状態になるかは、そのマスの、今の単位時間における状態と、上下左右の周囲8個のマス(ムーア近傍)の状態のみから決まる。その規則は、
- そのマスが黒なら、周囲8マスのうち2マスか3マスが黒ならそのマスは黒のまま(「生存」)
- そのマスが白なら、周囲8マスのうち3マスが黒ならそのマスも黒にする(「誕生」)
- それ以外の場合、そのマスは何色でも(白でも黒でも)白にしておく(元が黒だった場合は、「死亡」)
である。実際に時間を進めると初期状態で黒が多すぎても少なすぎでもすぐに自明な定常的なループに入ってしまうが、適度な密度のパターンには数千単位時間ほど、粘菌のように変化するものもある。最初に発見された自明でない無限に増殖するパターンは、ハッカーのゴスパーらにより発見された「グライダー銃」である(自明な無限増殖パターンとしては、無限の長さの棒状のパターンがある。これは初期状態が有限ではない)。生存と死亡のパラメータをいじってみると、無限増殖するパターンが簡単には存在しないよう、微妙なところ(後にクリストファー・ラングトンにより「カオスの縁」(かおすのふち、Edge of Chaos)と命名された)にうまく設定されたルールであることがよくわかる。
万能チューリング機械を構成することが可能であるので、計算理論的にはチューリング完全である。
やってみたい
- JavaScript ライフゲーム
AKIYAMA Kouhei氏が公開しているお手軽なライフゲーム環境。JavaScript製なので、3DS等でも動作する。
http://misohena.jp/art/js_lifegame/
http://zekitokaihatu.esy.es/niconico/lifegame/lifegame.htm ミラー。ダウンロード版もあり。
- Golly
数万ピクセル級の大規模な状態を扱うことができる本格的な実行環境。プリセットも豊富で、ライフゲーム以外のセルオートマトンの実行も可能。
関連動画
関連? 動画
文献
関連項目
- 12
- 0pt