Game of Life
| Eugene M. Izhikevich et al. (2015), Scholarpedia, 10(6):1816. | doi:10.4249/scholarpedia.1816 | revision #150735 [link to/cite this article] |
The Game of Life (sometimes known simply as Life) is an example of a cellular automaton and a zero-player game. It takes place on an infinite two-dimensional grid in which cells can be ‘on’ (alive) or ‘off’ (dead), and is defined by a set of rules that jointly determine the state of a cell given the state of its neighbours. Following specification of an initial configuration, patterns evolve over time across the grid requiring no further user input (thus ‘zero-player’). First popularized in 1970 in the Scientific American (Gardner, 1970), the Game of Life has attracted lasting appeal among both scientific and amateur communities. One reason for its appeal is that it is very simple to program, yet at the same time it appears to exemplify emergent and self-organized behaviour. Even though its (simple) rules are specified at the level of individual cells, one sees entities at coarse-grained ‘higher’ levels of description, whose behaviors are better described by rules at these higher levels.
Contents |
Rules
In its standard format, the Game of Life unfolds on an infinite two-dimensional grid composed of cells each of which is either ‘on/alive’ or ‘off/dead’. The game takes place in discrete time, with the state of each cell at time t determined by its own state and the states of its eight immediate neighbours at t-1 (the Moore neighbourhood of radius 1), according to the following simple rules:
- Any ‘on’ cell (at time t-1) with fewer than two ‘on’ neighbours (at t -1) transitions to an ‘off’ state at time t.
- Any ‘on’ cell (t -1) with two or three ‘on’ neighbours (t -1) remains ‘on’ at time t.
- Any ‘on’ cell (t -1) with more than three ‘on’ neighbours (t -1) transitions to an ‘off’ state at time t
- And ‘off’ cell (t -1) with exactly three ‘on’ neighbours (t -1) transitions to an ‘on’ state at time t.
These rules can be thought to represent basic processes of life and death, motivating the name ‘Game of Life’. Rule 1 represents ‘death by under-population’; rule 2 represents ‘sustainable life’; rule 3 represents ‘death by over-population’, and rule 4 represents ‘birth’. The initial state of the game is the ‘seed’ and all cells are updated simultaneously. Time steps are sometimes called ‘generations’.
The Game of Life rules were carefully chosen by Conway to satisfy three simple criteria (Gardner, 1970):
- There should be no initial pattern [configuration] for which there is a simple proof that the population can grow without limit.
- There should be initial patterns that apparently do grow without limit.
- There should be simple initial patterns that grow and change over some time, before coming to end in three possible ways: fading away completely (from overcrowding or becoming too sparse); settling into a stable pattern that remains unchanged thereafter, or entering an oscillating phase in which they repeat an endless cycle of two or more periods.
The Game of Life generates what Wolfram has called ‘class 4’ cellular automata behaviour; that is, behaviour which is neither completely random nor completely repetitive (Wolfram, 2002). The basic Game of Life is very easy to implement in almost any computer language.
History
The Game of Life was first published in the Martin Gardner’s column in October 1970 issue of Scientific American, resulting in the greatest number of letters from readers at that time.
While John Conway was an undergraduate at Cambridge University, he would write letters to Martin Gardner on various mathematical games. Sometimes, Martin would use the letters in his Scientific American column on mathematical puzzles.
While at Cambridge, John Conway used to play various games using Go board with his friends during teatime. Being bored with real games, like “five in a line”, John tried to invent new games.
The book “Automata Studies” (Ashby, 1956) and the cellular automata of Von Neumann motivated John Conway to look for set of rules that would result in interesting dynamics.
Earlier version: 3-state system
After 18 months or so of trying to discover rules for a 2-state system (live or dead), John gave up and switched to 3-state system: off, A and B. A friend of John Conway, Martin Huxley, referred to A and B as being “actresses” and “bishops”, as in the famous at that time stories with a secondary meaning that is a bit suggestive (but deceitful).
The most popular set of rules was the following:
- Birth rule: 3 people needed to give birth; they have to be of mixed sexes; the sex of the child is the weaker sex (2A+B would give a birth to a B)
- Overcrowding rule: If you have 4 or more neighbors, you die.
- Sexual frustration rule: if you do not touch anybody of the opposite sex – you die.
There were many variations on the rules, leading to the perpetual fight: If the birth rule is too strong – everything expands. If the death rules are too strong – everything dies. It turned out to be quite hard to balance the rules.
Game of Life using Go stones
It took about 18 months of teatime (and coffee time) to come up with good set of rules resulting in configurations that do not tend to explode or die out too soon.
A best way to experiment was to use Go boards with Go stones. Some cheap Go sets have flat stones, which are perfect for experimentation. The configuration at time t is set in white Go stones. John would put a black stone when there is a birth. If anybody is going to die, John would put a little shell on top. To step to the configuration at time t+1, John would remove any stones with shells, then see what is the color of the majority, and flip the other color. This would work, except for the time when there is a huge massacre and most of organisms should. John would say “shell a living” and put the shells on the survivors.
Discovery of the glider
John and his friends always had in mind that they might simulate a computer with the Game of Life. However, it was not obvious until they found a glider. This was the moment that John realized that he got the right set of rules.
Keeping track of Go stone configuration was a daunting and a bit annoying task, especially when the configuration has blinkers. John needed a “blinker watcher” and he recruited his friend, Richard K. Guy, who visited him at Cambridge. Richard was responsible for watching not only blinkers, but anything else that is small and changes periodically.
One day, Richard said to John “my blinker is walking”. John suspected that there might have been moving configurations and he referred to them as “space ships”; the glider was the first such “space ship”.
In hope to discover more interesting configurations, John went through an overdrive and crashed the gliders in every possible way -- 40 different ways. To find a glider generator, John Conway announced a prize - $50. To make sure he does not miss anything else interesting, he offered the prize to anybody who would find an initial configuration whose population goes to infinity. The prize was won by the MIT group who discovered the glider gun.
Within a few weeks after the discovery of the glider, John had proven that Game of Life is equivalent to the universal Turing machine.
Game of Life vs. Life Game
John Conway often refers to the Game of Life as “Life Game”. This is to avoid the confusion with “Game of Life” owned by Parker Brothers (who also own the “Monopoly Game”).
We got first PDP machine in Cambridge, and we watch the game on screen without Go boards.
Patterns
Since its inception there has been considerable interest in discovering novel patterns within the Game of Life. Patterns can be categorized according to the complexity of their behaviour, from simple unchanging ‘still lives’ to emulations of universal Turing machines (see below). Here are some examples of some Game of Life patterns at the simple end of the scale:
- Still life: a stable pattern in which no changes follow the initial configuration.
- Oscillator: Patterns that change but repeat themselves after a particular number of iterations (period). The example below shows a blinker, which is a period-2 oscillator.
- R-Pentomino: A pentomino is a pattern with five connected cells, with connections along edges (not diagonals). The R-pentomino was studied extensively by Conway, as the only pentomino that does not end quickly; it does however stabilize after 1103 iterations.
- Glider: The glider is a very important pattern within the Game of Life, furnishing an early example of ‘emergence’. As the game evolves, a glider will move across the environment as a persistent entity.
- Glider gun: Another very important pattern; the first example of a pattern that grows indefinitely. As the name suggests, glider guns generate a continuous stream of glider objects.
- Puffer train: A puffer train also produces objects, but unlike a glider gun it does so while moving.
Patterns within the Game of Life can be much more complex than illustrated in the above examples, and can even be organized in ways that perform functional operations. Streams of gliders (and other moving objects, generally known as ‘spaceships’) can be considered as signals which have causal effects on other patterns with which they interact. These interactions can be organized to furnish basic computational procedures such as logic gates (AND, OR, NOT) as well as simple memory counters. These properties imply that the Game of Life is theoretically equivalent to a ‘Universal Turing Machine’; that is, it is ‘Turing complete’ (Berkelamp, Conway, & Guy, 1982). Turing completeness means that, absent any constraints of memory or time, the Game of Life has unlimited computational power. More recently, Universal Turing Machines have been implemented in practice in Game of Life environments (Rendell, 2000, see FIGURE). Another recent development, the ‘Gemini’ pattern, reaches back to John Von Neumann’s early interest in self-replicating automata (see http://conwaylife.com/forums/viewtopic.php?f=2&t=399&start=0). Gemini is a self-constructing pattern which creates a copy of itself while destroying its parent (over the course of 34 million iterations).
The exploration of novel Game of Life patterns has been supported by dedicated software which accelerates the computations needed to follow large populations over millions or billions of iterations (e.g., the ‘Golly’ environment, available at http://golly.sourceforge.net). A growing community of enthusiasts has developed around this and other software platforms, continually extending the boundaries of Life patterns. Subjects discussed within this community include such topics as ‘stable pseudo-Heisenburp device and other P1 wiring projects’ (http://b3s23life.blogspot.com).
Variations
Recalling that the original Game of Life rules were chosen very carefully, there remain a large variety of alternative rule sets defining similar games, at least some of which also have interesting properties supporting apparently emergent behaviour. There is now a nomenclature differentiating different varieties of Game of Life cellular automata. The original game is referred to as B3/S23 because a cell is born (B) if it has exactly three neighbours, and stays alive (S) if it has two or three neighbours. The automaton B36/S23 defines what has been called ‘High Life’, which is known for having frequently occurring replicators (see http://www.tip.net.au/~dbell/). Among the very many possible Games of Life, only a very few seem able to generate rich (emergent, self-organized) behaviour. The challenge of determining a priori (i.e., without instantiation) whether a given rule set will lead to rich behaviour remains an open challenge.
Implications: Emergence, self-organization, autopoeisis, and the physics of information
Emergence and self-organization are controversial topics within the science of complexity. Both appear to be exemplified by the Game of Life. Emergence is colloquially taken to mean that the whole is (somehow) greater than the sum of the parts. This concept can be cashed out in several ways (Bedau, 2003). At one extreme, so-called ‘nominal’ emergence refers to a property that can pertain to a collection of items that by definition cannot pertain to the components themselves; for example, a circle is nominally emergent from the points which make it up. At the other extreme, ‘strong emergence’ refers to a global property which in principle cannot be accounted for by interactions among the constituent parts. Concrete examples of strong emergence are hard to come by: conscious experience is one frequently suggested possibility, though this may reflect simply equating one difficult-to-understand concept with another (Seth, 2010). The Game of Life rather exemplifies so-called ‘weak emergence’, according to which global properties result from interactions among the parts but in ways which are difficult (or maybe impossible) for an external observer to understand, except by explicitly simulating these interactions. Thus, in the Game of Life, global entities such as gliders, puffer trains and other such wonders arise from the interaction of simple components behaving according to well-defined rules. Extending this notion, a recent study has examined how some Game of Life configurations can give rise to an ever-growing variety of novel local interaction patterns (Gotts, 2009).
Self-organization and emergence are closely related concepts. Self-organization is usually defined as the spontaneous formation of spatiotemporal patterns without external guidance. More specifically, one may attribute self-organization to a system on the basis that (i) it exhibits (at least weakly) emergent behaviour and (ii) it does so without any explicit external input, given an initial configuration. On these criteria, the Game of Life is a good example of both emergence and self-organization.
Beer (2004) has considered glider patterns within the Game of Life from the perspective of autopoeisis. Autopoeisis is a fundamental concept in the biology of cognition; an autopoeitic (literally, self-producing) system is a network of component-producing processes with the property that the interactions between the components generate the very same network of processes that produced them, as well as constituting a distinct entity (a ‘unity’) (Maturana and Varela, 1973). The biological cell is a canonical example of autopoeisis; its components underlie processes (supported by external energy and material flow) which continually regenerate the components in a structure that defines itself against the surrounding medium. In a similar way, a glider pattern can be considered as a ‘coherent localized pattern of spatiotemporal activity in the Life universe that continuously reconstitutes itself’ (Beer, 2004, p.311). The analogy is complicated, since one may query whether states in the Game of Life can really be thought of as components, whether the glider pattern really possesses a boundary that generates and constrains it, and so on.
Emergence, self-organization, and autopoeisis are important concepts applicable to a broad range of systems, biological and non-biological. By providing concrete examples of these phenomena, the Game of Life serves a useful purpose. However, some people take its implications to be considerably more far-reaching. These implications are based on the notion that information has equivalent ontological status to mass, charge, and the like; the so-called ‘it from bit doctrine’ (Wheeler, 1990). Following this line of thought, one can consider that interactions among emergent objects within cellular automata (including of course the Game of Life) are equivalent to interactions among physical objects. (One implication of taking this view would be that gliders could more reasonably be thought of as autopoeitic.) At the limit, one can think of the Game of Life as demonstrating the plausibility of an information-based physics as a fundamental description of reality, with computation as a fundamental physical principle. One does not however need to accept these provocative notions in order to appreciate the many insights into emergence and self-organization, and the simple joys of discovery, offered by the Game of Life.
References
Ashby, W. R. (1956). Automata studies (Vol. 267). C. E. Shannon, & J. McCarthy (Eds.). Princeton, NJ: Princeton University Press.
Beer, R.D. (2004). Autopoeisis and cognition in the Game of Life. Artificial Life 10:309-326.
Bedau, M. (1997). Weak emergence. Philosophical Perspectives, 11:375–399.
Berkelamp, E.R., Conway, J.H., and Guy, R.K. (1982). Winning ways for your mathematical plays, Vol. 2. New York: Academic Press.
Gardner, M. (1970). Mathematical Games: The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American
Gardner, M. (1983). Wheels, life, and other mathematical amusements. New York: W.H. Freeman.
Gotts, N.M. (2009). Ramifying feedback networks, cross-scale interactions, and emergent quasi-individuals in Conway’s Game of Life. Artificial Life 15:351-375.
Rendell, P. (2000) Turing universality of the Game of Life. In Collision Based Computing, ed. A. Adamatzky, Springer-Verlag, pp.513-538. See also http://rendell-attic.org/gol/fullutm/index.htm
Seth, A.K. (2010). Measuring emergence and autonomy via Granger causality. Artificial Life 16:179-196
Wheeler, J.A. (1990) Information, physics, quantum: The search for links. In Complexity, Entropy, and the Physics of Information, ed. W. Zurek; Addison-Wesley, Redwood City.
Wolfram, S. (2002) A new kind of science. Wolfram Media Inc.
