ライフゲーム

ライフゲームとは

ライフゲーム（Conway's Game of Life）は、1970年にイギリスの数学者ジョン・ホートン・コンウェイによって考案された、シンプルなルールで複雑な挙動を示す数理モデルです。このモデルは、細胞のようなものが格子状に配置された空間で、それぞれの生死が周囲の細胞の状態によって決定されるという、非常にシンプルなルールに基づいています。

ライフゲームは、その単純さにもかかわらず、非常に多様なパターンや現象を生み出すことで知られています。生命の誕生、進化、淘汰といったプロセスを連想させることから、シミュレーションゲームとして分類されることもあります。また、セル・オートマトンの中でも最も有名な例の一つとして、研究対象となることも多いです。

セル・オートマトンの背景

ライフゲームを理解する上で、セル・オートマトンという概念を知っておくことは重要です。セル・オートマトンは、空間と時間が離散的な場合に、どのような世界が形成されるのかを示す計算モデルです。このモデルは、1940年代にジョン・フォン・ノイマンとスタニスワフ・ウラムによって提唱されました。当時、コンピュータが発明されたばかりで、研究は主に方眼紙と筆記具を用いて行われていました。

セル・オートマトンの研究は、フォン・ノイマンが自己複製機械に関心を持っていたことから始まりました。1952年には、2次元セル・オートマトンによる自己複製機械の例が示されました。そして、1970年にライフゲームが発表され、その面白さが一般の人々の間にも広まりました。

ライフゲームの歴史

ライフゲームは、1970年10月に「サイエンティフィック・アメリカン」誌のマーチン・ガードナーのコラムで紹介されたことがきっかけで、大きな反響を呼びました。読者からの手紙が殺到し、何度も記事が組まれたほどでした。

ライフゲームの発表後すぐに、移動物体であるグライダーパターンや、長寿型のR-ペントミノパターンが発見されました。当時はコンピュータが利用できる人が限られていたため、主に夜間や未使用のコンピュータでプログラムが動かされ、多くの興味深いパターンが発見されました。その後、マイクロコンピュータの普及とともに、ライフゲームは人気のあるアプリケーションとして定着しました。

セル・オートマトンの研究は、ライフゲームのような2次元のものから、1次元へと進みました。1980年には、スティーブン・ウルフラムによって1次元セル・オートマトンの4分類が完成し、クリストファー・ラングトンによって「カオスの縁」という概念が確立しました。現在では、3次元以上のセル・オートマトンも研究対象となっています。

ライフゲームのルール

ライフゲームのルールは非常にシンプルです。碁盤のような格子状の空間があり、各マスは「セル」と呼ばれます。各セルは「生」か「死」のいずれかの状態を持ち、次の世代の状態は周囲8つのセルの状態によって決定されます。

具体的なルールは以下の通りです。

誕生: 死んでいるセルに隣接する生きているセルがちょうど3つあれば、次の世代で誕生します。
生存: 生きているセルに隣接する生きているセルが2つか3つならば、次の世代でも生存します。
過疎: 生きているセルに隣接する生きているセルが1つ以下ならば、過疎により死滅します。
過密: 生きているセルに隣接する生きているセルが4つ以上ならば、過密により死滅します。

このシンプルなルールに基づいて、複雑なパターンが生成されます。

パターンの例

ライフゲームでは、世代を経るにつれて死滅するパターンもあれば、生き残るパターンもあります。生き残るパターンは、以下の4つに分類することができます。

固定物体: 世代が進んでも形が変わらず、同じ場所に留まるパターンです。
振動子: 一定の周期で同じ形に戻るパターンです。
移動物体: 一定のパターンを繰り返しながら移動するパターンです。
繁殖型: マス目が無限であれば、無限に増え続けるパターンです。

コンウェイは、生きたセルの数が無限に増え続けるパターンがあるかどうかという問題に懸賞金をかけました。そして、グライダーを次々と打ち出す「グライダー銃」や、移動しながら跡を残す「シュシュポッポ列車」などが発見され、懸賞金が贈られました。

繁殖型には、「宇宙の熊手」や「マックス」といった、複雑な成長パターンを持つものも存在します。これらのパターンは、ライフゲームの奥深さを示しています。

長寿型の例

ライフゲームには、非常に長い間変化を続ける長寿型（メトセラ）と呼ばれるパターンも存在します。「ダイハード」は130世代後に死滅するパターンであり、「どんぐり」は13個のグライダーを生成するのに5206世代もかかるパターンです。これらのパターンは、ライフゲームの複雑さを象徴しています。

バリエーション

ライフゲームには、オリジナルのルール以外にも様々なバリエーションが存在します。標準のライフゲームは「23/3」と表され、最初の2つの数字は生き残るために必要な隣人の数を、次の数字は誕生に必要な隣人の数を表します。例えば、「16/6」は、1つまたは6つの隣人がいれば生き残り、6つの隣人がいればセルが誕生することを意味します。

有名なバリエーションには、「HighLife」と呼ばれる「23/36」があります。これは、オリジナルのルールに加えて、6つの隣人がいれば誕生するというルールを追加したものです。他にも、3-4Life (34/34) など、変則的なルールを持つものが多数作られています。また、2次元平面とムーア近傍以外の空間で、類似したルールによるセル・オートマトンも研究されています。

ライフゲームを用いた計算機

ライフゲームはチューリング完全であり、チューリングマシンと同等の計算能力を持つことが知られています。これは、ライフゲームのパターンを使って計算機を構成し、プログラムを実行できることを意味します。

計算機を構成するためには、グライダーなどのパターンを組み合わせてAND、OR、NOTといった論理ゲートを作成します。グライダーを利用することで、他のオブジェクトと相互作用させることができ、例えばブロックを移動させたり、カウンタとして利用したりすることも可能です。

素数や乱数を生成するパターンや、ライフゲーム上でライフゲームを計算する「Unit cell」など、実際に動作する計算機の例も存在します。

まとめ

ライフゲームは、単純なルールから驚くほど複雑な現象を生み出す、非常に魅力的な数理モデルです。その普遍的な性質と奥深さから、数学やコンピュータ科学だけでなく、様々な分野で研究されています。ライフゲームを通して、複雑な現象の本質を理解し、新たな発見につなげることができるかもしれません。

もう一度検索