http://blog.regehr.org/archives/546
John Regehr, an associate professor of computer science at the University of Utah, writes about two algorithmic optimizations for Conway's Game of Life, and speculates on the implications for self-aware entities in simulations.
Hashlife is a clever optimization that treats the Life grid as a hierarchy of quadtrees. By observing that the maximum speed of signal propagation in a Life configuration is one cell per step, it becomes possible to evolve squares of the Life grid multiple steps into the future using hash codes. Hashlife is amazing to watch: it starts out slow but as the hashtable fills up, it suddenly “explodes” into exponential progress. I recommend Golly. Hashlife is one of my
... (read more)
Thanks for writing such a comprehensive explanation!