ハッシュライフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ハッシュライフライフゲームや関連するセル・オートマトンで、与えられた初期状態から遠い未来の状態を計算するためのメモ化アルゴリズムであり、オートマトンの各セルの一ステップを計算するアルゴリズムに比べて、非常に高速に計算することが可能である。初出は1980年代初期で、その頃ゼロックスパロアルト研究所の研究に参加していたビル・ゴスパーによる。オリジナルのハッシュライフはシンボリックスLISPマシンでFlavorsというLISP拡張を用いて実装された。

ハッシュライフ[編集]

ハッシュライフはライフゲームのバリエーションの多くで現れる多量の時間的・空間的な冗長性を活用する。例えば、ライフゲームではある領域内の生きているセルの最大密度は1/2に過ぎず、一見してランダムに見える多くのパターンは単純な固定型や振動型の集まりに収束する。

データ構造[編集]

多くの場合、フィールドは理論上無限の広さを持つ格子として扱われ、パターンは原点の近くに置かれる。フィールドは四分木によって表現される。一辺が2k個のセルからなる22k個のセルの正方形の領域に対して、木の深さkで、中心にある2k-1x2k-1個のセルの正方形の領域の2k-2ステップ先の状態をハッシュテーブルに保持する。例えば、4x4の領域に対しては中心2x2の領域の一ステップ先の状態を保持し、8x8の領域に対しては中心4x4の領域の二ステップ先の状態を保持する。

ハッシュ法[編集]

四分木は明らかに他の単純なデータ構造(例えば、ビット行列)よりも計算のオーバーヘッドが膨大になるが、様々な最適化が可能である。名前が示す通り、四分木のノードを保持するためにハッシュテーブルが使われる。木の中の多くのサブパターンは互いに同一であることが多い。例えばあるパターンは同じ宇宙船のコピーを多く含んでいるかもしれないし、何もない領域がただ広く集まっているということすらある。これらのサブパターンのコピーは全てハッシュ関数によってハッシュテーブルの同じ場所に記録することができるので、同じサブパターンのコピーは同じハッシュテーブルのエントリを使って記録できる。しかも、コピーごとに計算する他のライフゲームの計算アルゴリズムとは違い、同じサブパターンについては一度だけ計算すれば良い。

このことは計算資源の大幅な節約につながる。例えば、ブリーダーやスペースフィラーは多項式の速さで生きているセルが増加するパターンだが、ハッシュライフを使うことで対数の空間と時間で計算することができる。

超高速化とキャッシュ[編集]

四分木の異なるノードを異なる速さで展開していくことによって、多くのパターンでさらなる高速化を達成できる。例えば、深さ(k+1)のノードに対する状態の計算を深さkのノードに比べて二倍先のステップまで実行する。グライダー銃のように、密度の低いパターンや繰り返しの多いパターンの場合はこの工夫によって劇的に高速化され、より大きなパターンをより先のステップまでより高速に、時には指数関数の速さで計算できるようになる。この性質を最大限引き出すには、過去に出現したサブパターンもキャッシュする必要がある。

ゴスパー自身のhlifeプログラムのように、ハッシュライフの実装の中には、異なるパターンは異なる速さで実行されるものがある。そのような実装は大抵コマンドラインから実行するようになっていて、状態のリアルタイムな画面表示を持たず、単に初期状態から指定したステップまでを計算する。しかしGollyのような最近のプログラムでは、ハッシュライフに基づく計算エンジンを持ちながらGUIを実現している。

ハッシュライフのプログラムは概ね次のようなパターンで動作する。最初のうちはハッシュ関数の計算や四分木の構築にかかる一定のオーバーヘッドのために他のアルゴリズムより遅い。その後、十分なデータが集まったら、劇的に、時には爆発的ともいえるほどの加速度で速くなる。

欠点[編集]

メモ化されたコードの多くに当てはまることとして、ハッシュライフは他のアルゴリズムと比べて極めて多くのメモリを使う。特にエントロピーの多い中規模のパターンや四分木のノードの境界に上手く配置されないサブパターンを含む場合(例:2のべき乗のサイズ)には顕著になる。キャッシュは不安定な要素である。これらのパターンに対しては計算時間も他のアルゴリズムより大きくなってしまう。数あるライフゲームシミュレータの中でもGollyはオプションでハッシュライフと従来のアルゴリズムを切り替えることができる。

ハッシュライフは他のアルゴリズムと比べて実装が非常に難しい。例えば、不要になったノードをキャッシュから削除する専用のガベージコレクタが必要である。

参考文献[編集]

  • "Exploiting Regularities in Large Cellular Spaces", Bill Gosper. 1984, pp. 75-80 from Volume 10 of Physica D. Nonlinear Phenomena

関連項目[編集]

外部リンク[編集]