ライフゲーム

thumb|ペンタデカスロンと呼ばれる循環パターン（振動子）のひとつ（GIFアニメ）ライフゲーム (英語で単にとした場合、ハズブロが販売しているボードゲームと同名（日本では「人生ゲーム」）だが、これとは全く無関係である。これと区別するため、ライフゲームを、人生ゲームをとも呼ぶ。) は1970年にイギリスの数学者ジョン・ホートン・コンウェイ () が考案した数理モデルである。単純なルールから複雑な結果が生成され、パズルやミニスケープの要素を持っている。生命の誕生、進化、淘汰などのプロセスを連想させるパターンも存在し、シミュレーションゲームと分類される場合がある。

生物集団においては、過疎でも過密でも個体の生存に適さないという個体群生態学的な側面を背景に持つ。セル・オートマトンのもっともよく知られた例でもある。

概要我々が暮らす空間、さらには時間が連続的なものであるか、それとも非連続的なものであるのか、という問いはギリシア時代から思索の対象となってきた。セル・オートマトンはその問いに答えるものではないが、空間、時間が不連続であった場合、どのような世界が形成されるのかを示してくれる。

セル・オートマトンは、四角形などのセルによって分割された空間において、時間に最小単位が存在する場合の計算モデルである。1940年代にジョン・フォン・ノイマンとスタニスワフ・ウラムによって考案された。当時はコンピュータが発明された直後であり、セル・オートマトンの研究は、方眼紙と筆記具によるものである。フォン・ノイマンの関心は自己複製機械にあり、2次元セル・オートマトンによる自己複製機械の例を1952年に示している。

セル・オートマトンが研究者以外の興味をひくきっかけとなったのが、ライフゲームである。1970年10月の『サイエンティフィック・アメリカン』誌のマーチン・ガードナーのコラム上で紹介されたところ多くの反響を呼んだ。サイエンティフィック・アメリカン誌が読者からの手紙を中心とした記事を何度も組んだほどである。

ライフゲームの考案後すぐに、移動物体であるグライダーパターンと、長寿型のR-ペントミノパターンが発見された。当時は、このようなゲームの研究を目的として、コンピュータを利用できたのは限られた人々であったが、それらの人々の間にライフゲームは流行した。夜間あるいは未使用のコンピュータ上でライフゲームのプログラムが動かされることとなり、興味深いパターンが多数発見された。後にマイクロコンピュータの普及により、一定の人気を持つアプリケーションとして現在に至っている。

その後、セル・オートマトンの研究はライフゲームのような2次元のタイプではなく、1次元を中心に進んだ。1980年には、スティーブン・ウルフラムによって1次元セル・オートマトンの4分類が完成し、クリストファー・ラングトンによって「カオスの縁」と呼ばれる概念が確立した。3次元以上のセル・オートマトンも研究対象となっている。

ライフゲームのルールライフゲームでは初期状態のみでその後の状態が決定される。碁盤のような格子があり、一つの格子はセル（細胞）と呼ばれる。各セルには8つの近傍のセルがある (ムーア近傍) 。各セルには「生」と「死」の2つの状態があり、あるセルの次のステップ（世代）の状態は周囲の8つのセルの今の世代における状態により決定される。このため、光速 (セル・オートマトン) は、縦横及び斜め方向に、単位時間あたりセル1個である。

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

下に中央のセルにおける次のステップでの生死の例を示す。生きているセルは■、死んでいるセルは□で表す。 +ライフゲームの基本ルール誕生生存（維持）死（過疎）死（過密）ファイル:Game of life 3x3 cell arises.svgファイル:Game_of_life_block_with_border.svgファイル:Game of life 3x3 cell dies2.svgファイル:Game of life 3x3 cell dies1.svg

パターンの例ライフゲームでは世代を経ることで最終的に死滅する図形もある。

生き延びる場合の変化は4パターンに分類することができる。固定物体は世代が進んでも同じ場所で形が変わらないものを指す。振動子はある周期で同じ図形に戻るものを指す。移動物体は一定のパターンを繰り返しながら移動していくものを指す。繁殖型はマス目が無限であれば無限に増え続けるパターンである。

コンウェイは「生きたセルの数が無限に増えつづけるパターンはありうるか」という問題に50ドルの懸賞金をかけた。コンウェイ自身は、そのようなパターンとして「周期的だが次々にグライダーを打ち出すもの」や「移動しながら通過した後に破片を残すもの」の存在を予想し、前者を「グライダー銃」、後者を「シュシュポッポ列車」と呼んだ。1970年11月、らは、初めてグライダー銃の具体例を挙げて賞金を獲得した。後にシュシュポッポ列車の具体例も与えられている。繁殖型としては、移動しながらグライダーを打ち出す「宇宙の熊手」(space rake) と呼ばれるものや、四方に向かって成長する「マックス」と呼ばれるものなど、様々なパターンが見付かっている。

4つの分類における単純な例を以下に示す。

固定物体の例ブロック蜂の巣ボート船池ファイル:Game of life block with border.svgファイル:Game of life beehive.svgファイル:Game of life boat.svgファイル:Game of life 5x5 ship.svgファイル:Game of life 6x6 pond.svg

振動子の例（GIFアニメ）

周期が2で発生しやすい振動子には以下のようなものがある。ブリンカーヒキガエルビーコン時計ファイル:2-3 O1.gifファイル:2-3 unruhe.gifファイル:2g3 blinker.gifファイル:G3 unruhe.gif 周期が3以上のものでは、以下のようなものがある。パルサー八角形銀河ペンタデカスロンファイル:JdlV osc 3.225.gifファイル:JdlV osc 5.64.gifファイル:Oscilador8periodos.gifファイル:JdlV osc 15.144.gif

移動物体の例グライダー軽量級宇宙船中量級宇宙船重量級宇宙船ファイル:Game of life animated glider.gifファイル:Game of life animated LWSS.gifファイル:Animated Mwss.gifファイル:Animated Hwss.gif

繁殖型の例 +グライダー銃ファイル:Game of life glider gun.svg thumb|ゴスパーのグライダー銃。30世代毎にグライダーを打ち出す。 +シュシュポッポ列車

繁殖型の中には時間の2乗に比例した増加を示すパターンがありそれらは「ブリーダー」と呼ばれる。これもゴスパーにより発見された。

繁殖型には後にもっと単純なものが見つかっている。次の3つはいずれも、無限に増え続けるパターンに成長する初期配置である。1つ目のパターンは初期配置ではわずか10個のセルしか生きておらず（これが最少であることが証明されている）、2つ目のパターンは5×5に収まっている。3つ目のパターンはわずか1列である。（いずれも「スイッチ機関車」をベースとしたパターンになる。初期配置は小さいが、成長過程は単純ではない）

ファイル:Game of life infinite1.svgファイル:Game of life infinite2.svgファイル:Game of life infinite3.svg

成長過程が単純なものとしては、以下のようなシュシュポッポ列車がある。

このパターンは、後方にブリンカーを残してゆく（図では2列が既に現れている）。

長寿型の例非常に長い間変化を続ける長寿型（メトセラ）と呼ばれるパターンがある。「ダイハード」は130世代後に死滅するパターンであり、「どんぐり」(acorn) は13個のグライダーを生み出すのに5206世代かかるパターンである。ダイハードどんぐりファイル:Game of life diehard.svgファイル:Game of life methuselah.svg

バリエーションオリジナルのライフゲーム以外にも様々な新しいルールを考えることができる。

周囲に3つの隣人がいれば生命が誕生し、周囲に2つか3つの隣人がいれば生き残り、それ以外の場合では死ぬというルールである標準のライフゲームを23/3と表す。最初の数 (2,3) は生き残るために必要な数を表し、次の数 (3) は生命の誕生に必要な数を表す。従って16/6は、「1つあるいは6つの隣人がいれば生き残り、6つの隣人がいればセルが誕生する」ことを意味する。

バリエーションの中では、23/36が有名である。と呼ばれ、オリジナルのルールに加えて、6つの隣人がいれば誕生するというルールを付け加えたものである。また、一般的なライフゲームでうまくいかない点を研究するために、3-4Life (34/34) などの変則ルールが多数作られている。

また、「2次元平面とムーア近傍」以外の空間における、類似したルールによるセル・オートマトン、といったものも考えることができるいくつかの例がにある。。

ライフゲームを用いた計算機ライフゲームはチューリング完全であり、チューリングマシンと同等の計算能力を持つ。これは、ライフゲームのパターンで計算機を形成し、その上でプログラムを実行する事が可能である事を示している。

計算機を構成するために必要な要素として、グライダーなどのパターンの組み合わせでAND、OR、NOTなどの論理ゲートを構築できる。グライダーを利用することで他のオブジェクトとの相互作用を得られる。例えばブロックを近くに運んできたり遠くへ移動させたりすることができる。この移動機構はカウンタとして利用できる。

他にも様々な計算能力を持つパターンが発見されている。素数/乱数生成器や、ライフゲームを用いてライフゲームを計算する "Unit cell" などは、実際に動作する計算機としてのライフゲームの例である。

脚注

参考文献

ライフゲーム

Źródło i licencja