ハッシュライフ
一般に、ライフゲームの(理論上の)フィールドは無限に広い格子である。扱いやすさなどのために、多くの場合、その格子点に縦横に整数で付番し、原点すなわち (0, 0) の近くに有限個の「生存」セルによるパターンがあるものとし、残りの無限の部分を無限個の非生存のセルとする。以上は理論的な観点からの話だが、実装では、生存しているセルがある付近を十分にカバーできる情報があれば良い。
ハッシュライフでは、1辺が2の冪乗個のセルの正方形の領域を、縦横それぞれ2等分する四分木構造の再帰でフィールドを表現する。この時、その範囲内のフィールドの状態にもとづくハッシュ値をキーにしたハッシュテーブルを併用し、全く同じ状態のフィールドであれば、四分木構造における部分木を共有する(すなわち、実際には木ではなくDAGとなっている)。このようなハッシュ(ハッシュテーブル)を利用した効率化を図るものであることから、その名がある。
一般的なライフゲームのアプリケーションソフトのエンジンとして利用するには、全盤面の1世代後を得る手続きも実装する必要もあるが、少々煩雑な部分があるのでここでは省略する。以下で述べる高速化についても、概要のみとする。
ここで、木の深さ0で一辺が1セルとする。
↑ それをしない場合、極端に効率が悪いため現実的ではない手法となってしまう。
↑ ライフゲームでは、グライダー銃の発見などでも知られる。
↑ Zebra stripes などのパターンの場合に最大になる。
↑ 原文献を参照するのも良いが、Dr Dobb's Journal の解説記事 An Algorithm for Compressing Space and Time がわかりやすい。
↑ なぜ効率的に計算できるのかはここでは説明しない。外部にある詳細な解説か、実装を読むこと。
↑ マックス (ライフゲーム) のようなパターンのこと。