ライフゲーム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

再選考	この項目について、秀逸な記事の再選考にて秀逸の可否について議論されています。

ライフゲーム(Conway's Game of Life)は1970年にイギリスの数学者ジョン・ホートン・コンウェイ (John Horton Conway) によって考案された生命の誕生、進化、淘汰などのプロセスを再現したシミュレーションゲームである。

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

なお、ライフゲームはボードゲームの人生ゲームとは全く違うものである。英語ではいずれも"The Game of Life"であり紛らわしい。そのため、ライフゲームは"Conway's Game of Life"、人生ゲームは"Hasbro's Game of Life"として区別される。（Hasbro(ハスブロ)は人生ゲームを発売しているメーカー。）

目次 1 概要 2 ライフゲームのルール 3 パターンの例 3.1 固定型の例 3.2 振動型の例 3.3 移動型の例 3.4 繁殖型の例 3.5 長寿型の例 4 バリエーション 5 脚注 6 関連項目 7 参考文献 8 外部リンク

[編集] 概要

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

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

セル・オートマトンが研究者以外の興味をひくきっかけとなったのが、ライフゲームである。1970年10月の『サイエンティフィック・アメリカン』誌のマーチン・ガードナーのコラム上で紹介されたところ多くの反響を呼んだ。サイエンティフィック・アメリカン誌が読者からの手紙を中心とした記事を何度も組んだほどである。興味深いことにライフゲームは万能チューリングマシンであることが証明されている^[1]。これは、ライフゲームは計算機で実行可能な全てのアルゴリズムを作ることができるということを表している。

この『サイエンティフィック・アメリカン』誌の出版後すぐに、グライダーパターンとR-ペントミノパターンが発見された。これらの興味深いパターンの発見やコンピュータの普及によってライフゲームは流行した。夜間あるいは未使用のコンピュータ上でライフゲームのプログラムが動かされることとなり、興味深いパターンが多数発見された。

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

[編集] ライフゲームのルール

ライフゲームは「0人ゲーム」である。通常のゲームではプレイヤーの操作でその後の状態が変化していくが、ライフゲームでは初期状態のみでその後の状態が決定されるからである。碁盤のような格子があり、一つの格子はセルと呼ばれる。各セルは8つのセルと接している。各セルには「生」と「死」の2つの状態があり、あるセルの次のステップ（世代）の状態は周囲の8つのセルの今の世代における状態により決定される。

セルの生死は次のルールに従う。基本的な考えは「過疎状態でも過密状態でも生き残ることはできない」というものである。

誕生 

死んでいるセルの周囲に3つの生きているセルがあれば次の世代では生きる（誕生する）。

維持 

生きているセルの周囲に2つか3つの生きているセルがあれば次の世代でも生き残る。

死亡 

上以外の場合には次の世代では死ぬ。

下に次のステップでの生死の例を示す。生きているセルは黒、死んでいるセルは白で表す。

維持（生）	誕生	死	死

[編集] パターンの例

ライフゲームでは世代を経ることで最終的に死滅する図形が多い。

生き延びる場合の変化は4パターン（固定型、振動型、移動型、繁殖型）に分類することができる。

• 固定型は世代が進んでも同じ場所で形が変わらないものを指す。
• 振動型はある周期で同じ図形に戻るものを指す。
• 移動型は一定のパターンを繰り返しながら移動していくものを指す。グライダーと呼ばれるものが有名である。
• 繁殖型はマス目が無限であれば無限に増え続けるパターンである。

コンウェイは「無限にセルの数が増えつづけるパターンはありうるか」という問題に懸賞金をかけた。この問題は、1970年11月にゴスパー (Bill Gosper) により解かれた。それは30世代毎にグライダーを打ち出す「グライダー・ガン」と呼ばれるパターンであった。繁殖型には他にも、本体が通過した後に破片を残していく「汽車ポッポ」 (puffers) や、宇宙船が集まって移動しながらグライダーを発射していく「宇宙編隊」と呼ばれるものを含め様々なパターンが見つかっている。

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

[編集] 固定型の例

ブロック	蜂の巣	ボート	船	池
■■ ■■	□■□ ■□■ ■□■ □■□	□■□ ■□■ □■■	■■□ ■□■ □■■	□■■□ ■□□■ ■□□■ □■■□

[編集] 振動型の例

ブリンカー	ヒキガエル	ビーコン	時計
□■□ □■□ □■□	□□■□ ■□□■ ■□□■ □■□□	□□■■ □□■■ ■■□□ ■■□□	□□■□ ■□■□ □■□■ □■□□
↑ ↓	↑ ↓	↑ ↓	↑ ↓
□□□ ■■■ □□□	□□□□ □■■■ ■■■□ □□□□	□□■■ □□□■ ■□□□ ■■□□	□■□□ □□■■ ■■□□ □□■□

[編集] 移動型の例

グライダー	軽量級宇宙船	中量級宇宙船	重量級宇宙船
□■□ ■□□ ■■■	□■□□■ ■□□□□ ■□□□■ ■■■■□	□□□■□□ □■□□□■ ■□□□□□ ■□□□□■ ■■■■■□	□□□■■□□ □■□□□□■ ■□□□□□□ ■□□□□□■ ■■■■■■□

[編集] 繁殖型の例

グライダー・ガン (gliderguns)
□□□□□□□□□□□□□□□□□□□□□□□□■□□□□□□□□□□□ □□□□□□□□□□□□□□□□□□□□□□■□■□□□□□□□□□□□ □□□□□□□□□□□□■■□□□□□□■■□□□□□□□□□□□□■■ □□□□□□□□□□□■□□□■□□□□■■□□□□□□□□□□□□■■ ■■□□□□□□□□■□□□□□■□□□■■□□□□□□□□□□□□□□ ■■□□□□□□□□■□□□■□■■□□□□■□■□□□□□□□□□□□ □□□□□□□□□□■□□□□□■□□□□□□□■□□□□□□□□□□□ □□□□□□□□□□□■□□□■□□□□□□□□□□□□□□□□□□□□ □□□□□□□□□□□□■■□□□□□□□□□□□□□□□□□□□□□□

汽車ポッポ (puffers)
□□□■□ □□□□■ ■□□□■ □■■■■ □□□□□ □□□□□ □□□□□ ■□□□□ □■■□□ □□■□□ □□■□□ □■□□□ □□□□□ □□□□□ □□□■□ □□□□■ ■□□□■ □■■■■

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

繁殖型には後にもっと単純なものが見つかっている。次の3つはいずれも無限に増え続けるパターンである。 1つ目のパターンは初期配置ではわずか10個のセルしか生きておらず（これが最少であることが証明されている）、2つ目のパターンは5×5に収まっている。3つ目のパターンはわずか1列である。

□□□□□□■□ □□□□■□■■ □□□□■□■□ □□□□■□□□ □□■□□□□□ ■□■□□□□□

■■■□■ ■□□□□ □□□■■ □■■□■ ■□■□■

■■■■■■■■□■■■■■□□□■■■□□□□□□■■■■■■■□■■■■■

非常に長い間変化を続ける長寿型（メトセラ）と呼ばれるパターンがある。「ダイハード」は130世代後に死滅するパターンであり、「ドングリ」 (acorn) は13個のグライダーを生み出すのに5206世代かかるパターンである。

[編集] 長寿型の例

ダイハード	ドングリ
□□□□□□■□ ■■□□□□□□ □■□□□■■■	□■□□□□□ □□□■□□□ ■■□□■■■

グライダーを利用することで他のオブジェクトとの相互作用を得ることができる。例えばタイミングよくいくつかのグライダーを打ち出すことでブロックを近くに運んできたり遠くへ移動させたりすることができる。この移動機構はカウンターをシミュレートしていると考えることができる。また、グライダーなどのパターンの組み合わせでAND、OR、NOTゲートを構築することができる。 現在に至るまで他にも様々な性質を持つパターンが発見されていて、グライダー・ガンによる論理ゲート以外にも、素数生成器や大規模でゆっくりとした速度でライフゲームをエミュレートするunit cellなどがあげられる。

ライフゲームのパターンはチューリング完全であり、ライフゲームはチューリングマシンと同等の計算能力を持つことが示されている。この計算能力は昨今のコンピュータと同等であり、つまりライフゲームはパターンで表現されたプログラムを実行するコンピュータであると言うことができる。

[編集] バリエーション

オリジナルのライフゲーム以外にも様々な新しいルールを考えることができる。周囲に3つの隣人がいれば生命が誕生し、周囲に2つか3つの隣人がいれば生き残りそれ以外の場合では死ぬというルールである標準のライフゲームを23/3と表す。最初の数 (2,3) は生き残るために必要な数を表し、次の数 (3) は生命の誕生に必要な数を表す。従って16/6は、「6つの隣人がいればセルが誕生し、1つあるいは6つの隣人がいれば生き残る」ことを意味する。 バリエーションの中では、23/36が有名である。HighLifeと呼ばれ、オリジナルのルールに加えて、6つの隣人がいれば誕生するというルールを付け加えたものである。

[編集] 脚注

1. ^ ウィリアム・パウンドストーン著／有澤誠訳、『ライフゲイムの宇宙』、日本評論社、1990年、ISBN 4535781745

[編集] 関連項目

• 人工生命
• セル・オートマトン
• カオス理論

[編集] 参考文献

• Gardner, M. "Mathematical games", 1970 Scientific American, 223 October, 120-123.
• Gardner, M. "Mathematical games", 1971 Scientific American, 224 February, 112-117.
• 『エントロピーと秩序—熱力学第二法則への招待』、日経サイエンス社、ISBN 4532520142
• 『コンピューターレクリエーションIV　遊びの展開』、日本経済新聞社、ISBN 4532511135
• 『神になる科学者たち　21世紀科学文明の危機』、日本経済新聞社、 ISBN 9784532147983

[編集] 外部リンク

• Life Lexicon（英語）
• Eric Weisstein's Treasure Trove of the Life C.A.（英語）
• Vector: ライフゲーム（Windows上で動作するライフゲームのプログラムがある）
• Windows版ライフゲームシミュレータ
• Golly（オープンソースのライフゲームシミュレータ、例が豊富）
• ライフゲーム入門 for Mac OS X