Ok, on my old computer (I think it was a Packard Bell, with Windows 3.1), there was this one game. I can’t remember what it was called, but it involved a grid where you could make each box blue, red, or blank. It followed certain rules, such as “Any box surrounded by three of a particular color will become that color” and “Any box surrounded by more than 5 boxes or less than 2 boxes will ‘die.’” It was an amazing little game. You could set up boxes that bloomed into starbursts when you hit start, or ones that formed a kind of “rocket” that moved in a line across the grid.
Does anyone know what this game is? And is there any place I can find it online? I’d love to toy with it again, but I can’t for the life of me remember what it was called…
It is a slightly more sophisticated variant of John Conway’s The Game of Life, first proposed in 1945. The original game only involves one type of block vs. empty blocks.
I dabbled with the exact software implementation that you mention, and am therefore quite confident in my response.
There is also a two-player version played on a 5 x 5 grid. I wrote a Windows implementation for it in C++, if anyone is interested. In my version, you play versus the computer.
As others have pointed out, it’s Conway’s “Game of Life”. To take it out of the realm of a simple “game”, I feel the need to point out that it is a classic example of a complex system. At some point, it was proven that the game of life is Turing complete, meaning that it is as powerful as any other Turing machine. Also, it is an example of automata, which are more fully covered in Stephen Wolfram’s tome <u>A New Kind of Science</u>.
For those of us that have never delved too far into the algorithm - how on earth do you get around the circularity of it when you’re implementing said algorithm? It would seem to me that to calculate some cell A’s future, you need to know about the neighbouring cells B,C,D…but those cells are dependent upon A. Does this mean that every implementation is ‘heuristic’ rather than analytic?
No, it’s purely algorithmic. The program takes each cell and examines the eight adjacent cells and stores the cell’s fate in another array. Once the grid is completely scanned, the program examines the second array and marks each cell on the game grid accordingly.
Ah, I believe it goes in stages. So the program examines the everything, decides on the state of each cell for the next generation, set 'em all, and then starts again.
So A, B, C and D’s state in the second generation depend on their state in the previous, they’re not changed sequentially.
QED and SpaceDog - you are both right - I should have thought this through more carefully. Somehow I had got it twisted in my mind that a cell’s destiny depends on the future state of its neighbouring cells, which of course is false: it only depends on their present state. Therefore, it’s not a “hard” problem to calculate the next state, but a simple one, since we are dealing with a static board. For the same reasons, I was afraid that the next patern on the board would depend in which order your algorithm processes the cells, but this is also clearly untrue.
It is not exactly Conway’s game of Life, but it is what is called a cellular automaton. Conway’s game involves only on or off and the rules are as follows (where an adjacent cell means any of the 8 cells horizontally, vertically, or diagonally adjacent);
A cell that is empty in one generation, but is adjacent to exactly 3 live cells is live in the next.
A cell that is live in one generation, but is adjacent to either 2 or 3 live cells is live in the next.
All other cells are empty in the next generation.
Conway proved (with the help of literally thousands of hackers who used untold millions of 1960s dollars worth of computer time) that with these simple rules, then you could simulate a self-reproducing universal Turing machine on a sufficiently large plane. Actually the rules are not quite complete on a finite board since they do not specify what happens at the edge. Most people substitute a torus for the plane, since there are no edges. Other possibilities: Klein bottle, projective plane. I think Conway imagived an infinite plane or one large enough to avoid edge effects as long as necessary.
The game described is somewhat different and the differences could have major effects.
)