Hacker News Reader

Comment by galaxyLogic | Hacker News Reader

Special-purpose hardware for cellular automata would not evaluate it "step-by-step" either, but in parallel. Every cell could evaluate its next state independently of others.

We could think of some kind of version of RAM where each 'cell' would implement this behavior.

Perhaps similar optimizations like HashLife could be developed for such special purpose hardware as well.

View on HN

I implemented Hashlife for a different CA rule set earlier this year.

Hashlife's data structure is a quad tree embedded in a hash table. Most Hashlife instances only spend a few short moments simulating cellular automata at the "ground level"— the real work involves combining the future of the children of a quad tree node into the future of the node. That might be optimizable, but it feels extremely application-specific.

Edit: shameless, shameless plug: https://rezmason.github.io/wireworld-player/?engine=macrocel...

"evaluate its next state" is what I meant by "step-by-step".

There could certainly be a dedicated hardware implementation of HashLife. It would not be based on the idea "cells are almost bits", nor would it be faster than a direct CPU implementation of Lisp.

But isn't the idea of Game of Life to evaluate all its states, all the steps, step by step?

Or is HashLife doing something like "Calculating state N + 100 without having to calculate all states in between?

Hi, I'm the author of this project. HashLife actually does just that, by memoizing and reusing past occurrences and outcomes of the same pattern. Since one cell can only interact with its 8 neighbors in one timestep, there is a limit to the distance that a fixed-size pattern can interfere with in a fixed amount of time, analogous to the speed of light in physics. (It is in fact called the speed of light for cellular automatons as well, as described in https://en.wikipedia.org/wiki/Speed_of_light_(cellular_autom... .) Therefore, by remembering the outcomes of a certain pattern in a certain timeframe, you can jump to that amount of time in one step by using the memoized pattern. More details are explained in this article: https://www.drdobbs.com/jvm/an-algorithm-for-compressing-spa...

By the way, with all the passion for Lisp, simple but Turing-complete systems, and programming that I put into this project, I'm very happy that other people have enjoyed it too. Thanks to everyone for checking it out!

Very interesting project. What I don't quite get is if you can calculate the state after 100 steps in one go what would make you select exactly100? Why not select 1007 or 10 million etc. ?

Thanks! That would be since the skippable timestep width is bounded by the size of the size of the patterns that you've memorized. Say we have a square pattern of size W. The outcome of this pattern within this region in 1 timestep is completely determined by its surrounding square region of size W+2c, with c as the speed of light (pixels per timestep), since patterns beyond that can never interfere with it unless its interference travels beyond the speed of light. For two timesteps the surrounding region would be of size W+4c, since more pixels can interfere with it within that amount of time. Therefore, If you memorize a pattern of size W+4c, you can predict the outcome of the inner square of size N after 2 timesteps, or the inner square of size W+2c after 1 timestep, etc. This sets an upper bound to the number of timesteps you can skip, depending on the sizes of the patterns that you have memorized. So if you've memorized a pattern of size W+200c, you can predict the outcome of the inner square of size c after 100 timesteps, but predicting the 101st timestep would require information of a region beyond the memorized pattern.

Cool

Fpga ?

Reply on news.ycombinator.com