Hashlife

Hashlife is a memoized algorithm for computing the long-term fate of a given starting configuration in Conway's Game of Life and related cellular automata, much more quickly than would be possible using alternative algorithms that simulate each time step of each cell of the automaton.

Hashlife was originally implemented on Symbolics Lisp machines with the aid of the Flavors extension.

Hashlife is designed to exploit large amounts of spatial and temporal redundancy in most Life rules.

Hashlife does however not depend on patterns remaining in the same position; it is more about exploiting that large patterns tend to have subpatterns that appear in several places, possibly at different times.

The field is typically treated as a theoretically infinite grid, with the pattern in question centered near the origin.

A node at the kth level of the tree represents a square of 22k cells, 2k on a side, by referencing the four k–1 level nodes that represent the four

The root node has to be at a high enough level that all live cells are found within the square it represents.

While a quadtree naively seems to require far more overhead than simpler representations (such as using a matrix of bits), it allows for various optimizations.

A hash table, or more generally any kind of associative array, may be used to map square contents to an already existing node representing those contents, so that one through the technique of hash consing may avoid creating a duplicate node representing those contents.

If this is applied consistently then it is sufficient to hash the four pointers to component nodes, as a bottom–up hashing of the square contents would always find those four nodes at the level below.

square centered at the same point determine the next timestep contents of the

cells in both the horizontal and vertical directions, so even in the case of still life it would likely not be among the level k nodes that combine into the

Practically, computing the next timestep contents is a recursive operation that bottom–up populates the cache field of each level k node with a level k–1 node representing the contents of the updated center

Sharing of nodes can bring a significant speed-up to this operation, since the work required is proportional to the number of nodes, not to the number of cells as in a simpler representation.

If nodes are being shared between quadtrees representing different timesteps, then only those nodes which were newly created during the previous timestep will need to have a cached value computed at all.

For example the pattern being studied may contain many copies of the same spaceship, and often large swathes of empty space.

Each instance of these subpatterns will hash to the same quadtree node, and thus only need to be stored once.

In addition, these subpatterns only need to be evaluated once, not once per copy as in other Life algorithms.

For sparse or repetitive patterns such as the classical glider gun, this can result in tremendous speedups, allowing one to compute bigger patterns at higher generations faster, sometimes exponentially.

A generation of the various breeders and spacefillers, which grow at polynomial speeds, can be evaluated in Hashlife using logarithmic space and time.

Since subpatterns of different sizes are effectively run at different speeds, some implementations, like Gosper's own hlife program, do not have an interactive display; they simply advance the starting pattern a given number of steps, and are usually run from the command line.

More recent programs such as Golly, however, have a graphical interface that can drive 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".

Like many memoized codes, 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 (i.e. power-of-two sizes); the cache is a vulnerable component.

Golly, among other Life simulators, has options for toggling between Hashlife and conventional algorithms.

For example, it needs a dedicated garbage collector to remove unused nodes from the cache.

Due to being designed for processing generally predictable patterns, chaotic and explosive rules generally operate much more poorly under Hashlife than they would under other implementations.