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. The algorithm was first described 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 is designed to exploit large amounts of spatial and temporal redundancy in most Life rules. For example, in Conway's Life, many seemingly random patterns end up as collections of simple still lifes and oscillators.

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. Given a square of 2^2k cells, 2^k on a side, at the kth level of the tree, the hash table stores the 2^k-1-by-2^k-1 square of cells in the center, 2^k-2 generations in the future. For example, for a 4x4 square it stores the 2x2 center, one generation forward; and for an 8x8 square it stores the 4x4 center, two generations forward.

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.

...
Wikipedia