ハッシュライフ
ハッシュライフはライフゲームないし類似したセル・オートマトンで、繰り返しパターンなどがある場合を効率的に表現したり、全盤面について1世代ずつ計算を繰り返すのではなく、影響範囲をうまく利用することで効率よく未来の状態を計算することが可能な手法である。「ハッシュ」の名の通り、ハッシュテーブルを利用した部分構造の共有が前提[1]だが、さらにメモ化を利用すれば、1世代ごとの計算の繰り返しに比べて、非常に高速に未来の世代を得ることも可能となる。初出は1980年代初期で、その頃ゼロックスパロアルト研究所の研究に参加していたビル・ゴスパーによる[2]。ゴスパーによる実装には、シンボリックスのLISPマシンと、FlavorsというLISPのオブジェクト指向拡張が用いられた。
ハッシュライフ
[編集]ハッシュライフはライフゲームのバリエーションの多くで現れる多量の時間的・空間的な冗長性を活用する。例えば、ライフゲームではある程度の広さの内側で、長期的に生きていられるセルの密度は最大でも1/2[3]であり、通常はもっと疎である。一見してランダムに見える多くのパターンは単純な固定型や振動型の集まりに収束する。
データ構造
[編集]一般に、ライフゲームの（理論上の）フィールドは無限に広い格子である。扱いやすさなどのために、多くの場合、その格子点に縦横に整数で付番し、原点すなわち (0, 0) の近くに有限個の「生存」セルによるパターンがあるものとし、残りの無限の部分を無限個の非生存のセルとする。以上は理論的な観点からの話だが、実装では、生存しているセルがある付近を十分にカバーできる情報があれば良い。
ハッシュライフでは、1辺が2の冪乗個のセルの正方形の領域を、縦横それぞれ2等分する四分木構造の再帰でフィールドを表現する。この時、その範囲内のフィールドの状態にもとづくハッシュ値をキーにしたハッシュテーブルを併用し、全く同じ状態のフィールドであれば、四分木構造における部分木を共有する（すなわち、実際には木ではなくDAGとなっている）。このようなハッシュ（ハッシュテーブル）を利用した効率化を図るものであることから、その名がある。
一般的なライフゲームのアプリケーションソフトのエンジンとして利用するには、全盤面の1世代後を得る手続きも実装する必要もあるが、少々煩雑な部分があるのでここでは省略する[4]。以下で述べる高速化についても、概要のみとする。
ここで、木の深さ0で一辺が1セルとする。規則的で再帰的な四分木構造により、深さ1では一辺が2セルの正方形、深さ2では一辺が4セル……というようにして、深さkの木は一辺が2k個のセルからなる22k個のセルの正方形をあらわしている（前述のように具体的にはDAGで実装する）。周辺との干渉があるから、「その領域全体の未来の状態」のメモ化は不可能である。1辺が4セルの時、その中央の2x2の領域の1世代先の状態については確定的なのでメモ化できる。そして、8x8の領域に対しては中心4x4の領域の2世代先の状態、16x16の領域に対しては中心8x8の領域の4世代先の状態というように、倍々で、より未来の世代のメモ化が可能であり、また、効率的に計算することもできる[5]というのが急所である。一般に、木の深さkで、中心にある2k-1x2k-1個のセルの正方形の領域の2k-2世代先をメモ化できる。この「メモ」の範囲とその未来の世代は、ライフゲームの「光速」によって、その世代における結果は確定的であることから、うまく機能するということが言える。ハッシュライフの著しい利点として、このメモ化の利用により、例えば動作が数万世代を超えるような巨大なパターンについて、何世代もスキップさせつつ、その後の結果のみを迅速に得ることができる。
ハッシュ法
[編集]四分木は明らかに他の単純なデータ構造（例えば、ビットの行列）よりも、ライフゲームの計算のために必要なデータ処理量は局所的には多いが、様々な最適化が可能である。名前が示す通り、内容が同一なノードを共有するためにハッシュテーブルが使われる。木の中の多くのサブパターンは互いに同一であることが多い。例えばあるパターンは同じ宇宙船のコピーを多く含んでいるかもしれないし、何もない領域がただ広く集まっているということすらある。これらのサブパターンのコピーについて、同じパターンであればキーとして使用するハッシュ値が同一となるようにハッシュ関数を設計し、ハッシュテーブルを利用するのである。また、コピーごとに計算する他のライフゲームの計算アルゴリズムとは違い、同じサブパターンについては一度だけ計算すれば良いようにできる（前述のように、それが表現している盤面全体について、その未来をメモ化することはできないが）。
このことは計算機資源の大幅な節約につながる。例えば、ブリーダーやスペースフィラー[6]は二次的に生きているセルが増加する（quadratic growth）パターンだが、ハッシュライフを使うことで対数の空間と時間で計算することができる。
超高速化とキャッシュ
[編集]ゴスパー自身のhlifeプログラムのように、ハッシュライフの実装の中には、異なるパターンは異なる速さで実行されるものがある。そのような実装の多くはインタフェースとして、コマンドだけを持っていて画面表示のようなインタラクティビティを持たず、単に初期状態から指定した世代までを計算する。一方で多くはないが、Gollyに代表される、ハッシュライフに基づく計算エンジンとそれを活用した高速化機能を持ちつつ、同時にインタラクティビティも実現しているものもある。
効率的に実装されたハッシュライフのプログラムは概ね次のようなパターンで動作する。最初のうちはハッシュ関数の計算や四分木の構築にかかる一定のオーバーヘッドのために他のアルゴリズムより遅い。その後、十分なデータが集まったら、劇的に、時には爆発的ともいえるほどの加速度で速くなる。試すにはGollyで、Bヘプトミノによるシュシュポッポ列車を、エンジンをハッシュライフに指定して Hyperspeed オプションをオンにして動かしてみるとよい。
欠点
[編集]メモ化という技法一般に言えることではあるが、ハッシュライフは他のアルゴリズムと比べて極めて多くのメモリを使う。またライフゲームにおける特性としては、特にエントロピーの多い中規模のパターンや四分木のノードの境界に上手く配置されないサブパターンを含む場合（すなわち、2のべき乗のサイズよりちょっと大きいような）には顕著になる。また、キャッシュは不安定な要素でもある。これらのパターンに対しては計算時間も他のアルゴリズムより大きくなってしまう。数あるライフゲームアプリケーションの中でもGollyはオプションでハッシュライフと従来のアルゴリズムを切り替えることができる。
以上の説明では触れていないが、その実装の詳細においては入り組んでいて多少に難しい点がある。また、メモリの利用量の多さが動作を極端に遅くしているようであれば、最近使われていない保存データを破棄する、というような機能なども、比較的実装が面倒な部類の機能のひとつと言えると思われるが、実用的な実装には必要である。
参考文献
[編集]- "Exploiting Regularities in Large Cellular Spaces", Bill Gosper. 1984, pp. 75-80 from Volume 10 of Physica D. Nonlinear Phenomena
注
[編集]- ^ それをしない場合、極端に効率が悪いため現実的ではない手法となってしまう。
- ^ ライフゲームでは、グライダー銃の発見などでも知られる。
- ^ Zebra stripes などのパターンの場合に最大になる。
- ^ 原文献を参照するのも良いが、Dr Dobb's Journal の解説記事 An Algorithm for Compressing Space and Time がわかりやすい。
- ^ なぜ効率的に計算できるのかはここでは説明しない。外部にある詳細な解説か、実装を読むこと。
- ^ マックス (ライフゲーム) のようなパターンのこと。