3 ms·

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

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.

rezmason 5y ago
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=macrocell https://rezmason.github.io/wireworld-player/?engine=macrocel...
eesmith 5y ago
"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.
- galaxyLogic 5y ago
  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?
  - woodrush 5y ago
    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_automaton) 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-space-and-t/184406478 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!
    - galaxyLogic 5y ago
      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. ?
      - woodrush 5y ago
        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.
        galaxyLogic 5y ago
        Cool
ngcc_hk 5y ago
Fpga ?

rezmason 5y ago

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=macrocell https://rezmason.github.io/wireworld-player/?engine=macrocel...

eesmith 5y ago

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

galaxyLogic 5y ago
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?
- woodrush 5y ago
  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_automaton) 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-space-and-t/184406478 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!
  - galaxyLogic 5y ago
    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. ?
    - woodrush 5y ago
      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.
      - galaxyLogic 5y ago
        Cool

ngcc_hk 5y ago

Fpga ?