HashLife: Difference between revisions
Disambiguation |
No edit summary |
||
| (20 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
'''HashLife''' is an algorithm created by [[Bill Gosper]] for simulating the [[ | [[File:Turing Machine in Golly.png|thumb|379px|right|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]].]] | ||
'''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 [[pattern]]s of interest.<ref>R. Wm. Gosper, ''Exploiting Regularities in Large Cellular Spaces''. Physica '''10D''' (1984) 75-80.</ref> | |||
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 | 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: 2<sup>N+1</sup>×2<sup>N+1</sup> tiles are run 2<sup>N-1</sup> ticks into the future, and the 2<sup>N</sup>×2<sup>N</sup> 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.<ref name="dvgrn20170711" /> | ||
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''.<ref name="trokicki20060401" /> | ||
{{ | |||
{{LinkLexicon|lex_h.htm#hashlife}} | HashLife can be used for any [[outer-totalistic]] [[Life-like cellular automaton]] using the [[Moore neighbourhood|Moore]] or [[von Neumann neighbourhood]]s; increasing the size of the base hashtiles allows it to be adapted to the larger neighborhoods of [[Larger than Life]] rules,<ref>https://conwaylife.com/forums/viewtopic.php?p=47655#p47655</ref> though Golly hosts no such implementation. | ||
== References == | |||
<references> | |||
<ref name="dvgrn20170711">{{cite web | |||
|url = https://conwaylife.com/forums/viewtopic.php?p=46376#p46376 | |||
|title = Re: Larger than Life | |||
|author = Dave Greene | |||
|date = July 11, 2017 | |||
|accessdate = July 11, 2017 | |||
|work = ConwayLife.com forums | |||
}}</ref> | |||
<ref name="trokicki20060401">{{cite web | |||
|url = https://web.archive.org/web/20120719224016/http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 | |||
|title = An Algorithm for Compressing Time and Space | |||
|author = Tomas Rokicki | |||
|date = April 1, 2006 | |||
|accessdate = July 11, 2017 | |||
|work = Dr. Dobb's Journal | |||
}} (archived from the original on July 19, 2012)</ref> | |||
</references> | |||
== External links == | |||
* {{LinkLexicon|lex_h.htm#hashlife}} | |||
* {{LinkGollyHelp|filename=Algorithms/HashLife.html}} | |||
* {{LinkWikipedia|Hashlife}} | |||
{{GollyNavbox}} | |||
[[Category:Algorithms]] | |||
Latest revision as of 18:32, 2 September 2025
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]
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,[4] though Golly hosts no such implementation.
References
- ↑ R. Wm. Gosper, Exploiting Regularities in Large Cellular Spaces. Physica 10D (1984) 75-80.
- ↑ Dave Greene (July 11, 2017). "Re: Larger than Life". ConwayLife.com forums. Retrieved on July 11, 2017.
- ↑ 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)
- ↑ https://conwaylife.com/forums/viewtopic.php?p=47655#p47655
External links
- HashLife at the Life Lexicon
- HashLife at Golly's online help
- HashLife at Wikipedia
| ||||||||||||||||||||