3 ms·

HashLife – A memoized algorithm for Conway's Game of Life and cellular automata

80 points by nikolay 3y ago

kfogel 3y ago
There are algorithms where I think "Sure, with enough time and attention given to the problem, I might have thought of that." And then there are algorithms where I think "Oh, wow. That came from another planet. I would never have come up with that myself." This one is definitely in the latter category.
- Retr0id 3y ago
  Agreed. Further, for most algorithms, I can read a high-level description of it and go "ohhh, I get it now", and go away and implement it myself without further information. HashLife is not one of those algorithms! While I grok the concept of it, I'm pretty lost on how I'd turn that into functional code. I'm sure I could figure it out with enough further reading, though.
codeflo 3y ago
The Wikipedia article skips an important trick on how to arrange the quadtree nodes to make this work. This link is better: http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...
- johngossman 3y ago
  Yeah, I implemented this in 2010 and the Dr. Dobbs article was essential. I even had the original C code and couldn’t figure it out without this article.
- Aardwolf 3y ago
  It starts very good, but does this article have multiple pages? Clicking 2 or Next at the bottom shows "something went wrong. Please contact an administrator". Tried in firefox and chrome on android
  - codeflo 3y ago
    There was a second page when I posted it, but then it stopped working. Sorry. This archive link is also semi-broken, but at least seems to have the complete article text on page 1: https://web.archive.org/web/20120719224016/https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 https://web.archive.org/web/20120719224016/https://www.drdob...
  - nyankosensei 3y ago
    You can click the tiny printer icon above the title to display the entire article as a single page.
- deleted 3y ago
  [deleted]
deleted 3y ago
[deleted]
OscarCunningham 3y ago
An interesting consequence of the HashLife algorithm is that when people design patterns in Conway's Game of Life they sometimes try to tailor them to the algorithm. The rule of thumb is that any repeated components should be laid out with spacings that are powers of two, and the period of any oscillations should be a power of two.
nikolay 3y ago
Here's a great explanation and implementation: https://johnhw.github.io/hashlife/index.md.html https://johnhw.github.io/hashlife/index.md.html
deleted 3y ago
[deleted]
turtleyacht 3y ago
Current AI is like memoized probability, then? Optimizations across a gigantic word cloud. Suppose someone puts on a canvas one instance or snapshot of an intermediate representation of the board. If it is contained in the "path" of a future HashLife, what would it mean?
lioeters 3y ago
This person used HashLife and OTCA metapixel (+ magic/genius) to create an infinite canvas of life within life. https://blog.oimo.io/2023/04/10/life-universe-en/ https://blog.oimo.io/2023/04/10/life-universe-en/ https://conwaylife.com/wiki/OTCA_metapixel https://conwaylife.com/wiki/OTCA_metapixel
natessilva 3y ago
I had a lot of fun a few years ago playing with this algorithm. I ended up with a little site that has life in life and some fun zooming and panning gestures on mobile. https://github.com/natessilva/gol https://github.com/natessilva/gol

80 points by nikolay 3y ago

There are algorithms where I think "Sure, with enough time and attention given to the problem, I might have thought of that." And then there are algorithms where I think "Oh, wow. That came from another planet. I would never have come up with that myself." This one is definitely in the latter category.

Retr0id 3y ago
Agreed. Further, for most algorithms, I can read a high-level description of it and go "ohhh, I get it now", and go away and implement it myself without further information. HashLife is not one of those algorithms! While I grok the concept of it, I'm pretty lost on how I'd turn that into functional code. I'm sure I could figure it out with enough further reading, though.

codeflo 3y ago

The Wikipedia article skips an important trick on how to arrange the quadtree nodes to make this work. This link is better: http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...

johngossman 3y ago
Yeah, I implemented this in 2010 and the Dr. Dobbs article was essential. I even had the original C code and couldn’t figure it out without this article.
Aardwolf 3y ago
It starts very good, but does this article have multiple pages? Clicking 2 or Next at the bottom shows "something went wrong. Please contact an administrator". Tried in firefox and chrome on android
- codeflo 3y ago
  There was a second page when I posted it, but then it stopped working. Sorry. This archive link is also semi-broken, but at least seems to have the complete article text on page 1: https://web.archive.org/web/20120719224016/https://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 https://web.archive.org/web/20120719224016/https://www.drdob...
- nyankosensei 3y ago
  You can click the tiny printer icon above the title to display the entire article as a single page.
deleted 3y ago
[deleted]

deleted 3y ago

[deleted]

OscarCunningham 3y ago

An interesting consequence of the HashLife algorithm is that when people design patterns in Conway's Game of Life they sometimes try to tailor them to the algorithm. The rule of thumb is that any repeated components should be laid out with spacings that are powers of two, and the period of any oscillations should be a power of two.

nikolay 3y ago

Here's a great explanation and implementation: https://johnhw.github.io/hashlife/index.md.html https://johnhw.github.io/hashlife/index.md.html

deleted 3y ago

[deleted]

turtleyacht 3y ago

Current AI is like memoized probability, then? Optimizations across a gigantic word cloud. Suppose someone puts on a canvas one instance or snapshot of an intermediate representation of the board. If it is contained in the "path" of a future HashLife, what would it mean?

lioeters 3y ago

This person used HashLife and OTCA metapixel (+ magic/genius) to create an infinite canvas of life within life. https://blog.oimo.io/2023/04/10/life-universe-en/ https://blog.oimo.io/2023/04/10/life-universe-en/ https://conwaylife.com/wiki/OTCA_metapixel https://conwaylife.com/wiki/OTCA_metapixel

natessilva 3y ago

I had a lot of fun a few years ago playing with this algorithm. I ended up with a little site that has life in life and some fun zooming and panning gestures on mobile. https://github.com/natessilva/gol https://github.com/natessilva/gol