ハッシュライフ

Hashlifeは、コンウェイのライフゲームや関連するセルオートマトンにおける特定の初期構成の長期的な運命を計算するためのメモ化された アルゴリズムです。オートマトンの各セルの各時間ステップをシミュレートする他のアルゴリズムを使用する場合よりもはるかに高速です。このアルゴリズムは、 1980 年代初頭に、ゼロックス パロアルト研究所で研究に従事していたBill Gosperによって初めて説明されました。Hashlife は、当初Flavors拡張機能を利用してSymbolics Lisp マシンに実装されました。

Hashlife は、ほとんどの Life ルールにおける大量の空間的および時間的冗長性を活用するように設計されています。たとえば、Conway の Lifeでは、一見ランダムなパターンの多くが、単純な静物画と発振器の集合として現れます。ただし、Hashlife はパターンが同じ位置に留まることを前提としていません。むしろ、大きなパターンには、場合によっては異なる時間に複数の場所に現れるサブパターンがある傾向があることを利用することに重点を置いています。

通常、フィールドは理論的には無限のグリッドとして扱われ、問題のパターンは原点付近に集中します。フィールドを表すために、四分木(ノードを共有) が使用されます。ツリーのk番目のレベルのノードは、レベルkの正方形の 4 つの象限を表す 4 つのk –1 レベル ノードを参照することにより、1 辺が2 ^{kの 2 2 k}セルの正方形を表します。たとえば、レベル 3 のノードは 8×8 の正方形を表し、これは 4 つの 4×4 の正方形に分解されます。明示的なセルの内容はレベル 0 にのみ保存されます。ルート ノードは、それが表す正方形内のすべてのライブ セルが見つかる程度に高いレベルにある必要があります。 ${\displaystyle 2^{k-1}\times 2^{k-1}}$

単純に考えると、4 分木はより単純な表現 (ビットの行列を使用するなど) よりもはるかに多くのオーバーヘッドを必要とするように見えますが、さまざまな最適化が可能です。各セルは生きているか死んでいるかのどちらかであるため、レベル 0 のノードには 2 つの可能性しかありません。そのため、ノードを親間で共有できる場合、合計で 2 つ以上のレベル 0 ノードを持つ必要はありません。同様に、2×2 の正方形の 4 つのセルは異なる組み合わせしか示せないため、レベル 1 のノードもその数だけ必要ありません。レベルが高くなると、可能なk番目のレベルの正方形の数は に伴って増えますが、特定の実行で発生する異なるk番目のレベルの正方形の数ははるかに少なく、同じ正方形の内容が複数の場所に現れることも非常によくあります。4 分木 (これは木というよりは有向非巡回グラフ) でノードを最大限に共有するには、同じ内容のすべての正方形を表すために 1 つのノードのみを使用します。 ${\displaystyle 2^{4}=16}$${\displaystyle 2^{2^{k}\cdot 2^{k}}=2^{2^{2k}}}$

ハッシュ テーブル、またはより一般的にはあらゆる種類の連想配列を使用して、スクエアの内容を、その内容を表す既存のノードにマッピングすることができます。これにより、ハッシュ コンシングの手法によって、その内容を表す重複ノードの作成を回避できます。これを一貫して適用すると、スクエアの内容をボトムアップでハッシュすると、常にその下のレベルでその 4 つのノードが見つかるため、コンポーネント ノードへの 4 つのポインターをハッシュするだけで十分です。上位レベルのノードに対するいくつかの操作は、それらのノードの内容を明示的に生成せずに実行でき、代わりに一定数下のレベルのノードへのポインターを操作するだけで十分であることがわかります。

クアッドツリーを拡張して、ノード内でそのノードのコンテンツの更新結果をキャッシュすることもできます。正方形には、その正方形全体の次のタイムステップのコンテンツを決定するのに十分な情報がありませんが、同じポイントを中心とする正方形のコンテンツによって、正方形の次のタイムステップのコンテンツが決まります。次のタイムステップのこのレベルkノードは、水平方向と垂直方向の両方でセルによってオフセットされるため、静物画の場合でも、正方形に結合するレベルkノードの中には含まれない可能性がありますが、レベルk –1では、正方形は再び同じ位置にあり、変更されていない場合は共有されます。 ${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle 2^{k+1}\times 2^{k+1}}$${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle 2^{k-1}}$${\displaystyle 2^{k+1}\times 2^{k+1}}$

実際には、次のタイムステップの内容を計算することは、各レベルkノードのキャッシュ フィールドに、更新された中央の正方形の内容を表すレベルk –1 ノードをボトムアップで入力する再帰操作です。ノードを共有すると、この操作の速度が大幅に向上します。これは、必要な作業が、より単純な表現の場合のようにセルの数に比例するのではなく、ノードの数に比例するためです。異なるタイムステップを表すクワッドツリー間でノードが共有されている場合、前のタイムステップで新しく作成されたノードに対してのみ、キャッシュされた値を計算する必要があります。 ${\displaystyle 2^{k-1}\times 2^{k-1}}$

Superspeed はさらに進んで、正方形の内容が実際には次のタイムステップの中央の正方形の内容を決定するという観察を利用します。レベルkノードに 1 ステップ先のコンテンツ用にレベルk –1 ノードをキャッシュさせる代わりに、ステップ先のコンテンツ用に 1 つキャッシュさせることができます。レベルkの更新はレベルk –1の更新から計算され、レベルk –1 にはタイムステップを進めるための結果がキャッシュされているため、レベルk –1で 2 ラウンド進めるだけで、レベルkでステップを進めるのに十分です。 ${\displaystyle 2^{k+1}\times 2^{k+1}}$${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle 2^{k-1}}$${\displaystyle 2^{k-2}}$${\displaystyle 2^{k-3}}$${\displaystyle 2^{k-2}}$

最悪の場合、レベルk –1 の 2 ラウンドはレベルk –2の 4 ラウンドを実行しなければならず、その結果レベルk –3の 8 ラウンドが必要になるなどですが、実際にはツリー内の多くのサブパターンは互いに同一であり、再帰のほとんどのブランチは短いです。たとえば、調査対象のパターンには、同じ宇宙船のコピーが多数含まれている場合があり、多くの場合、大きな空き領域があります。これらのサブパターンの各インスタンスは同じ四分木ノードにハッシュされるため、一度だけ保存する必要があります。さらに、これらのサブパターンは、他の Life アルゴリズムのようにコピーごとに 1 回ではなく、一度だけ評価する必要があります。

古典的なグライダーガンのようなまばらなパターンや反復的なパターンの場合、これにより大幅なスピードアップが実現し、より大きなパターンをより高い世代でより速く、時には指数関数的に計算できるようになります。多項式速度で成長するさまざまなブリーダーとスペースフィラーの世代は、対数空間と時間を使用して Hashlife で評価できます。

異なるサイズのサブパターンは実際には異なる速度で実行されるため、Gosper 自身の hlife プログラムなどの一部の実装には対話型ディスプレイがありません。これらの実装は、開始パターンを指定されたステップ数だけ進めるだけで、通常はコマンド ラインから実行されます。ただし、 Gollyなどの最近のプログラムには、Hashlife ベースのエンジンを操作できるグラフィカル インターフェイスがあります。

誘導パターンにおける Hashlife プログラムの典型的な動作は次のとおりです。最初はハッシュとツリーの構築に関連する一定のオーバーヘッドのため、アルゴリズムは他のアルゴリズムに比べて遅く実行されます。しかし、後で十分なデータが収集され、速度が大幅に向上します。速度の急激な増加は、しばしば「爆発的」と表現されます。

多くのメモ化されたコードと同様に、Hashlife は、特にエントロピーの多い中規模のパターンや、四分木ノードの境界に適切に配置されていないサブパターン (つまり、2 の累乗サイズ) を含むパターンでは、他のアルゴリズムよりも大幅に多くのメモリを消費する可能性があります。キャッシュは脆弱なコンポーネントです。また、これらのパターンでは、他のアルゴリズムよりも多くの時間を消費する可能性があります。他の Life シミュレータの中でも、 Gollyには、Hashlife と従来のアルゴリズムを切り替えるオプションがあります。

Hashlife の実装もかなり複雑です。たとえば、未使用のノードをキャッシュから削除するには 専用のガベージ コレクターが必要です。

一般的に予測可能なパターンを処理するように設計されているため、混沌とした爆発的なルールは、他の実装よりもHashlifeでは一般的にはるかにうまく機能しません。^[1]

• 純粋に関数的なデータ構造。ハッシュ四分木はその1つである。
• ハッシュコンシングは、Hashlife の元の実装で使用された主要な戦略でした。

• ゴスパー、ビル (1984)。「大きな細胞空間における規則性の活用」。Physica D . 10 (1–2)。エルゼビア: 75–80。doi : 10.1016/0167-2789(84)90251-3。

• エリック・ワイスタインの「Treasure Trove of Life」からのハッシュライフ
• Tomas Rokicki による hashlife の実装
• 人生用語集への登録
• ドブ博士のジャーナルからのアルゴリズムの説明
• ゴスパーのアルゴリズム（Has​​hlife）の説明 オリジナルからアーカイブ