HashLife – A memoized algorithm for Conway's Game of Life and cellular automata | Hacker News Reader

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

en.wikipedia.org

80 pointsnikolay12 comments

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.

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.

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://conwaylife.com/wiki/OTCA_metapixel

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-spac...

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

You can click the tiny printer icon above the title to display the entire article as a single page.

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.drdob...

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.

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

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.

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

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?

Reply on news.ycombinator.com