Game of life
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 behaviours can be described by rules at these higher levels.
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. A JAVA based version is provided on this page.
The Game of Life was developed by John Conway in the late 1960s. PERSONAL ACCOUNT HERE.
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).
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.
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.