Hacker News Reader

Comment by galaxyLogic | Hacker News Reader

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

Reply on news.ycombinator.com