Here’s a video introduction to the Game of Life
Historically, one of the pioneers of computer science John von Neumann was interested in finding machines which could reproduce themselves. He developed an abstraction allowing him to mathematically model his work on a computational grid. A mathematician John Conway took up and simplified his work publishing the idea in Scientific American in 1970 as the Game of Life.
The Game of Life is a cellular automaton. Cellular automaton are discrete models consisting of a regular grid of cells each with a finite number of states. Each cell has a neighborhood defined relative to it. An initial time state t=0 is defined by assigning every cell a state. Then, the system is evolved via a rule or function that determines the new state as a function of its current state and the states of the cells in its neighborhood and is then considered to be at time t=1. The simplest sort of rule doesn’t change over time and is globally applied to the grid, but more general types of cellular automata can have a stochastic or asynchronous nature.
Particularly the Game of Life‘s rule is of the sort which doesn’t change over time and is globally applied to the grid. It can be stated as follows (for a 2D grid, with 8 neighbors of each cell) :
- Underpopulation: a live cell with fewer than 2 live neighbors dies
- Stasis: a live cell with 2-3 live neighbors lives
- Overcrowding: a cell with more than 3 live neighbors dies
- Reproduction: a dead cell with exactly 3 live neighbors becomes a live cell
Despite its name containing “Life”, The Game of Life has no sentient players; in game theory that is known as a “Zero-player game.” Rather, the evolution of the Game is determined completely by its initial state. The initial assignment of live or dead to every cell at t=0 plus the rule above complete determines the evolution. Because of the neighbor constraint, there is a maximum speed 1 cell per timestep, at which information can travel. The Game of Life, despite such a simple ruleset, is itself a universal cellular automaton, it can emulate any universal system including other cellular automata and Turing machines.
Here are some simple examples
figure taken from Martin Gardner
The Game can produce interesting behavior: patterns which are static, which oscillate, which move across the grid with a defined pattern.
figure from J.S. Hallinan
Even more interesting patterns exist. Patterns exist which exhibit infinite growth. A pattern designed by A. Wade in 2010 exists which creates a copy of itself and destroys its parent. In 2013 D. Green built the first replicator which copies itself and its instruction set. There exist patterns Garden of Eden patterns which have no parent patterns. It is not known if there exist patterns which have a parent pattern but no grandparent pattern. If you find such a pattern in your research let us know!
The Game of Life is an excellent programming exercise for beginners to the field and also can be used as a great introduction to parallel programming. You can see it in action online and I recommend writing your own too. It can be extended, with the appropriate definition of the grid and what neighborhood consists of, to dimensions other than 2. Exploring these extensions are part of the fun of implementing the Game yourself.