Sep 20, 2016

Game of Life by Conway: Beyond a Game

September 20, 2016 - We would have played many mathematical games for fun. However, one game—Life, designed by John Horton Conway—stands out from the rest. The most interesting thing about this game? It's a zero-player game! This game is built on simple rules which simulate unpredictable patterns. The reason it is more than just a game is that it explains (or at least makes us think about) the evolution of life and space, and has practical applications for today's industries.

Background:
John von Neumann, a great mathematician of 20th century, contributed to multiple fields of science, including Astrophysics, Game Theory, Economics/Behavioral Economics, Shockwave, Hydrodynamics, Weather Control, Atomic Energy, Computer Technology, and Theory of Automata.

Conway, before he created Life, studied Von Neumann's Theory of Automata, in which Von Neumann discusses colonizing the planet Mars. According to Von Neumann's theory, humans, in advance of colonization, send machines to Mars that will smelt iron oxide to separate iron and oxygen. And, using the available iron and other metals, these machines are capable of creating a copies of themselves. (The idea is similar to that of DNA—e.g., replication, transcription, and translation—in humans.)

Von Neumann considered Mars as a plane object and imagined a machine with 29 squares, with each square performing different functions with different states. Conway simplified this idea, refining the rules laid out by Von Neumann to create the wonderful mathematical game Life (popularly known as “The Game Of Life").

In this game, Conway considered only two states: Alive and Dead—quite unlike Von Neumann's 29-state machines. To be precise, Von Neumann's machine was very well designed, but Conway's wasn't!

Game of Life:
Conway's game was first published in Scientific American in October, 1970, and went on to become one of the most popular reads of that time. Because the game resembles the rise, fall, and alternations of a society of living organisms, it is categorized as a simulation game. This game was initially played using small checkers or poker chips and a go board. Later, it was programmed on 1970's computers known as PDPs (programmed data processors). Today, the game is so advanced that we have many different patterns.

Initial assumption of the game should be that, it will be played on an infinite plane. Each cell in the board or plane has eight neighboring cells, four adjacent orthogonally, four adjacent diagonally. Below are Conway's delightfully simple rules:

  1. Survival: Every cell with two or three similar neighbors will survive for the next generation.
  2. Death: Each cell with four neighbors will die because of overpopulation; each cell with one or zero neighbor will die from isolation.
  3. Births: Each empty cell adjacent to exactly three neighbors cells will give birth to a new cell.

It is important to note that all births and deaths occur simultaneously, because of which a population will constantly undergo changes that create different—and very often beautiful—patterns.

Let us see some simple triplet patterns that get generated initially.

Image 1. Image showing triplet patterns (“The Fantastic combination of John Conway's new solitaire game life", Martin Gardner, Scientific American, 1970)

In the above figure, “A" and “B" patterns die in the third move. The pattern “C," which is a single diagonal chain of counters, loses its end-counters on each move until the chain finally disappears (Conway refers to this as “Speed of Light"). Pattern “D" becomes a stable block, while “E" will become a blinking oscillator due to its flip-flop property. In each step of this pattern, two cells die, the middle cell stays alive, and two new cells are born to give orientation as shown above. This pattern is also known as “Period."

The above picture illustrates triplets. Let us consider tetrominoes (four cells) and see what patterns are produced in the below figure.

Image 2. Image showing tetrominoes patterns (“The Fantastic combination of John Conway's new solitaire game life", Martin Gardner, Scientific American, 1970)

The above figure illustrates five tetrominoes where pattern “A" is a still-life figure. Pattern “B" and “C" both become the stable figure called “Beehive"; “D" also becomes a beehive on the third move. Interestingly, the pattern “E" initially becomes an isolated blinker, but then, after nine moves, becomes four isolated blinkers—a pattern called “Traffic Light."

Let us go one step further and consider a five-cell initial population. At each step, two cells will die and two new ones be born. After four steps the original population will reappear, but move diagonally down and across the plane. This pattern continues to move in the same direction forever. Eventually, it will disappear from our view, but it will continue to exist in the infinite plane. This pattern is called “Glider."

Image 3. Image showing Glider pattern (“Game of Life", Cleve Moler, 2011)

The game becomes even more interesting when we think beyond these static patterns. Computer programs can make this game dynamic, and enable us to watch the evolution of larger populations. One such pattern is “Glider Gun," developed by Bill Gosper in 1970.

In Glider Gun, a portion of the cell population between the two static blocks oscillates back and forth, and, at every 30 steps, a glider emerges. This leads to a huge number of gliders that fly out of the view but exist in the infinite plane.

Image 4. Image showing Glider Gun (“Game of Life", Cleve Moler, 2011)

Over the years the game advanced and now has numerous patterns.

There are hundreds of programs (Python R, C, Java, etc.) that can develop various patterns of Life.

Many ideas originally developed in Conway's game have found interesting applications in others fields, such as creating sound patterns using a Musical Instrument Digital Interface (MDMI)—that is, creating music. The game has been used as a basis for explaining diverse phenomena, from astronomical events to the evolution and survival of various cells, species, and organisms. It's no wonder, given the extent of these applications, that many consider Life much more than a simple mathematical game.

Jayanth Babu MN is part of the Genpact Chief Science Office protégé program. Jayanth Babu MN was supervised by Pradyumna S. Upadrashta, Chief Science Officer, Analytics & Research, for this blog