Back To Life

The "Game of Life" is John Conway's simulation of cellular automata. I won't describe how it works here. You can easily can find a lot of information about it if you'll do a web search. You can find several excellent simulators as well.

What is important to know is that it takes a lot of computer horsepower to perform the simulation. A reasonably sized grid can easily bring even the fastest computer to its knees. The difference between a naive implementation and a good one can be orders of magnitude in performance so it is well worthwhile to spend the effort to discover better methods.

This effort isn't just a curious way to pass the time. Cellular automata have been shown to be Turing-complete. They can in theory compute anything that is computable. They can mimic any other machine and they can even self-replicate. Many processes, including simulations of neural networks and semantic networks, are simular or even identical in design. A better life simulator could easily yield a better neural network simulator. This work is important and the chasm separating it from being an intellectual novelty and making it practical is bridged only by better performance.

In 1992, Michael Abrash hosted a competition to build the fastest life simulator for a 386 PC. My program was fortunate enough to share first place. Since then I've been thinking about ways to make it even faster. These web pages document my thoughts along the way. I recommend reading them one step at a time and pausing to think about the problems before I discuss how I solved them. It will give you a better understanding of the problem plus you may even come up with better solutions than I found!

1. Describing the problem

2. The first insight

3. The second insight

4. The third insight and success!

5. More gems are revealed

6. Another insight, another solution

7. Like a ton of bricks!

8. Final thoughts

Back to David's home page