HashLife

HashLife is an algorithm created by Bill Gosper in 1984 for simulating the Game of Life. It is designed to take advantage of the considerable amount of repetitive behaviour in many large patterns of interest.[1]

The 6,366,548,773,467,669,985,195,496,000th (6 octillionth) generation of Paul Rendell's Turing machine, computed in less than 30 seconds on an Intel Core Duo 2GHz CPU using HashLife in Golly.

Roughly speaking, the idea of the algorithm is to store subpatterns in a hash table so that the results of their evolution don't have to be recomputed if they arise again at another place or time: 2N+1×2N+1 tiles are run 2N-1 ticks into the future, and the 2N×2N centers are stored and re-used without recalculating them, whenever the same large hashtiles show up again. This works because information cannot travel faster than the speed of light in Conway's Game of Life and other rules of range 1: it is impossible for anything outside of the large tile to affect the center area in that amount of time.[2]

This does, however, mean that complex patterns can require substantial amounts of memory. HashLife provides a means of evolving repetitive patterns millions (or even billions or trillions) of generations further than normal Life algorithms such as QuickLife can manage in a reasonable amount of time. It is not, generally, suitable for showing a continuous display of the evolution of a pattern, because it works asynchronously — at any given moment it will usually have evolved different parts of the pattern through different numbers of generations. Nonetheless, some Life simulation programs do have a HashLife mode, the most well-known example being Golly.

More detail on the quadtree data structure that underlies the HashLife algorithm and Golly's associated macrocell format can be found in Tomas Rokicki's 2006 article in Dr. Dobb's Journal.[3]

HashLife can be used for any outer-totalistic Life-like cellular automaton using the Moore or von Neumann neighbourhoods; increasing the size of the base hashtiles allows it to be adapted to the larger neighborhoods of Larger than Life rules.

References
  1. R. Wm. Gosper, Exploiting Regularities in Large Cellular Spaces. Physica 10D (1984) 75-80.
  2. Dave Greene (July 11, 2017). "Re: Larger than Life". ConwayLife.com forums. Retrieved on July 11, 2017.
  3. Tomas Rokicki (April 1, 2006). "An Algorithm for Compressing Time and Space". Dr. Dobb's Journal. Retrieved on July 11, 2017. (archived from the original on July 19, 2012)
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.