Hashlife

Hashlife is an algorithm for computing the long-term fate of a given starting configuration in various Life rules. The algorithm was invented by Bill Gosper in the early 1980s while he was engaged in research at the Xerox Palo Alto research center. Hashlife was originally implemented on Symbolics Lisp machines with the aid of the Flavors extension.

Hashlife

Hashlife is designed to exploit large amounts of spatial and temporal redundancy in most Life rules. For example, in Conway's Life, the maximum density of live cells in a region is only 1/2, and many seemingly random patterns end up as collections of simple still lifes and oscillators.

Representation

The field is typically treated as a theoretically infinite grid, with the pattern in question centered near the origin. A quadtree is used to represent the field. An update operation takes the square of 2^2"k" cells, 2^"k" on a side, at the "k"th level of the tree, and computes the next generation of the 2^"k"-1-by-2^"k"-1 square of cells in the center.

Hashing

While a quadtree trivially has far more overhead than other simpler representations (such as using a matrix of bits), it allows for various optimizations. As the name suggests, it uses hash tables to store the nodes of the quadtree. Many subpatterns in the tree are usually identical to each other; for example the pattern being studied may contain many copies of the same spaceship, or even large swathes of empty space. These subpatterns will all hash to the same position in the hash table, and thus many copies of the same subpattern can be stored using the same hash table entry. In addition, these subpatterns only need to be evaluated once, not once per copy as in other Life algorithms.

This itself leads to significant improvements in resource requirements; for example a generation of the various breeders and spacefillers, which grow at polynomial speeds, can be evaluated in Hashlife using logarithmic space and time.

uperspeed and caching

A further speedup for many patterns can be further achieved by evolving different nodes at different speeds. For example, one could compute twice the number of generations forward for a node at the ("k"+1)-th level compared to one at the "k"th. For sparse or repetitive patterns such as the classical glider gun, this can result in tremendous speedups, paradoxically allowing one to compute "bigger" patterns at "higher" generations "faster", sometimes exponentially. To take full advantage of this feature, subpatterns from past generations should be saved as well.

Since different patterns are allowed to run at different speeds, some implementations, like Gosper's own hlife program, do not have an interactive display, but simply compute a preset end result for a starting pattern, usually run from the command line. More recent programs such as Golly, however, have a graphical interface that can be driven by a Hashlife-based engine.

The typical behavior of a Hashlife program on a conducive pattern is as follows: first the algorithm runs slower compared to other algorithms because of the constant overhead associated with hashing and building the tree; but later, enough data will be gathered and its speed will increase tremendously - the rapid increase in speed is often described as "exploding".

Drawbacks

Hashlife can consume significantly more memory than other algorithms, especially on moderate-sized patterns with a lot of entropy, or which contain subpatterns poorly aligned to the bounds of the quadtree nodes (ie. power-of-two sizes); the cache is a vulnerable component. It can also consume more time than other algorithms on these patterns. Golly, among other Life simulators, have options for toggling between Hashlife and conventional algorithms.

Hashlife is also significantly more complex to implement. For example, it needs a dedicated garbage collector to remove unused nodes from the cache. While an amateur programmer might be able to write a simple Life player over an afternoon, few Hashlife implementations exist.

ee also

* Conway's Game of Life
* Optimization
* Functional data structures, of which the hashed quadtree is one

References

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

External links

* [http://www.ericweisstein.com/encyclopedias/life/HashLife.html HashLife from Eric Weisstein's Treasure Trove of Life]
* [http://tomas.rokicki.com/hlife/ Tomas Rokicki's implementation of hashlife]
** [http://golly.sourceforge.net/ Golly] -(cross-platform Windows/Linux/Mac successor program)
* [http://www.argentum.freeserve.co.uk/lex_h.htm#hashlife Entry] in the [http://www.argentum.freeserve.co.uk/lex_home.htm Life Lexicon]
* [http://www.ddj.com/dept/ai/184406478 Explanation of the algorithm] from Dr Dobb's Journal