See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/228713112

A new candidate rule for the game of two-dimensional life

Article in Complex Systems · January 1996

CITATIONS READS

16 439

1 author:

Jean-Claude Heudin
Artificial-Creature.com
69 PUBLICATIONS 205 CITATIONS

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

PhD Thesis work: Fault Tolerance on real-time large-scale MIMD computers - The Evolutionary Approach View project

ANGELIA View project

All content following this page was uploaded by Jean-Claude Heudin on 12 March 2014.

The user has requested enhancement of the downloaded file.

Complex Systems 10 (1996) 367–381

A New Candidate Rule for the Game of

Two-dimensional Life

Jean-Claude Heudin∗
International Institute of Multimedia,
Pôle Universitaire Léonard de Vinci,
92916 Paris La Défense, France

Abstract. This paper introduces a new candidate rule for a game of

two-dimensional Life “worthy of the name.” The cellular automaton
is defined in a formal sense and presented using qualitative and quan-
titative approaches. Various natural stable and oscillating patterns,
including a propagating glider, are described.

1. Introduction
The two-dimensional cellular automaton (CA) Life, originally described in
[6, 7], has been presented in a large number of publications. It shows complex
dynamics [14] and has been proven capable of supporting universal compu-
tation [5]. According to several authors [13, 14], Life seems to be an ex-
ception in the huge space of possible two-dimensional transition rules. Few
variants have been mentioned [5, 14] but never clearly identified or care-
fully described.1 Therefore, most authors have concluded that Life is in fact
unique.
The most recent variation on this theme has been a series of articles
by Carter Bays [1–4]. Bays has expanded Life into three dimensions and
proposed a general definition for the set of possible rules [1]. Each rule can
be written in the form Eb EhFb Fh where Eb is the minimum number of living
neighbor cells that must touch a currently living cell in order to guarantee
that it will remain alive in the next generation. Fb is the minimum number
touching a currently dead cell in order that it will come to life in the next
generation and Eh and Fh are the corresponding upper limits. These rules are
called the “environment” and “fertility” rules. According to this notation,
Conway’s Life would be written “Life 2333,” that is Eb = 2, Eh = 3, Fb = 3,
and Fh = 3.
Electronic mail address: Jean-Claude.Heudin@devinci.fr.
∗

A good place to see what is widely available is the Usenet interest groups on CA:
1

comp.theory.cell-automata and cellular-automata@buphy.bu.edu.

c 1996 Complex Systems Publications, Inc.

!
368 Jean-Claude Heudin

While performing a systematic study of two-dimensional Life CA [10],

another rule candidate for a game of Life worthy of the name has been
discovered. This rule, called Life 1133, satisfies the following two criteria
defined in [4].

1. Primordial soup experiments must exhibit bounded growth. This means

than an initial random “blob” must eventually stabilize and cannot
grow without limit.
2. A glider must exist and occur “naturally,” that is, it must be discover-
able by repeatedly performing primordial soup experiments.

The first criterion is satisfied since all primordial soup experiments we

have performed shrunk and stabilized or disappeared, as we show in section 2.
The second criterion is also satisfied since we have discovered a propagating
glider that occurs naturally. The glider is described in section 3 along with
other natural structures of Life 1133.

2. Qualitative and quantitative analysis

2.1 Experimental environment
We have based our experiments on a toroı̈dal universe, consisting of a 64×64×
64 lattice with a finite-state automaton at each lattice site. Each primordial
soup experiment was initialized randomly to a 50 percent density of living
cells (Figure 1). Such disordered configurations are typical members of the
set of all possible configurations and, therefore, patterns generated from them
are typical of those obtained with any initial state. Thus, the presence of
structures in these patterns is an indication of self-organization in the CA
[16].

Figure 1: A sample random initialization.

A New Candidate Rule for the Game of Two-dimensional Life 369

At each generation we have recorded the distribution of fired rules for

a deeper understanding of the dynamical properties of the system. In this
framework, we have written the Life rules using the following (equivalent)
definition.
Let St be the state of an arbitrary cell at generation t, and Nt the num-
ber of its living neighbors. Then, the general Life transition rule can be
defined by:
if (Nt ≥ Fb )&(Nt ≤ Fh) → St+1 = 1, (R1)
else if (Nt ≥ Eb)&(Nt ≤ Eh) → St+1 = St , (R2)
else St+1 = 0. (R3)
That is, for Life 1133:
if Nt = 3 → St+1 = 1, (R1)
else if Nt = 1 → St+1 = St , (R2)
else St+1 = 0. (R3)

2.2 Qualitative results

The global behavior of Life 1133 looks like that of Life 2333, but with shorter
transients. For almost all initial disordered configurations, the density de-
creases rapidly and tends to an equilibrium limit. In all cases, most sites are
seen to “die” after a small finite time. However, stable or periodic patterns
which persist for an infinite time are generally formed and, in a few cases,
propagating structures have emerged. Section 3 describes more carefully
some of these natural structures.
Figure 2 gives an example of a typical configuration of Life 1133 after
a few time steps. Figure 3 shows a typical ending configuration with both

Figure 2: A typical configuration of Life 1133 after a few generations.

370 Jean-Claude Heudin

Figure 3: A typical ending configuration showing both stable and

period 2 patterns (top is generation n and bottom is generation n+1).

stable and period 2 oscillators. In most cases this kind of pattern occurs
before generation 50, to be compared with the very long transients of Life
2333 (generally more than 1000 generations in the same conditions).

2.3 Fired rules distribution

Before proceeding further, we should examine the distribution of fired rules

for Life 1133 and compare it to that of LIFE 2333. Figure 4 gives results for
the first 100 generations for both CA. Summing up our results, we obtain
the given plots. For all experiments performed, most “alive” cells die from
overpopulation or isolation (R3) and the systems rapidly stabilize with the
ordering R3 > R2 > R1.
A New Candidate Rule for the Game of Two-dimensional Life 371

Figure 4: A comparison of the rule dynamics for Life 1133 (top curves)
and Life 2333 (bottom curves).

Our convention for the transition rule emphasizes the role of R2 acting
as a “memory rule” which significantly influences the dynamical behavior of
both CA. All experiments have revealed the same ordering of rules, that is,
R3 > R2 > R1 with R1 &= 0, which seems to be a property of Life Class IV
CA, as already mentioned in a previous study [9].

2.4 Mean field approximation

The mean field theory describes how CA act on probability measures [8].
According to this theory, we note with x the probability that a cell is alive and
372 Jean-Claude Heudin

Figure 5: Mean field probability curves for Life 2333 and Life 1133.

with 1 − x the probability that it is dead. If we assume that the probability

for a cell to be in a given state is uncorrelated with the states of other cells,
then the probability for a block is just the product of the probabilities of the
cells in the block.
Thus, for Life 2333, we obtain the following mean field equation:

y = C83 · x3 · (1 − x)6 + C82 · x3 · (1 − x)6 + C83 · x4 · (1 − x)5 ,

that is,

y = 84 · x3 · (1 − x)6 + 56 · x4 · (1 − x)5 .

With the same conditions, the mean field equation for Life 1133 is:

y = C83 · x3 · (1 − x)6 + C83 · x4 · (1 − x)5 + C81 · x2 · (1 − x)7 ,

that is,

y = 56 · x3 · (1 − x)6 + 56 · x4 · (1 − x)5 + 8 · x2 · (1 − x)7 .

Figure 5 shows a graph of these two probability curves together with the
diagonal line of unchanged probability. Both curves cross the diagonal at
slightly more than tangency and are quadratic at the origin.

2.5 Lambda value

There has been a growing feeling that Wolfram’s classification is a scale
measuring the distribution of periodic cycles in CA with class IV forming
a transition region between class II (short periods and lengths) and class
III (chaotic regime). In this framework, Cristopher Langton proposed a
parametrization scheme on the CA rule space based on the λ parameter [11].
A New Candidate Rule for the Game of Two-dimensional Life 373

Figure 6: A selection of stable structures.

Figure 7: A selection of period 2 oscillators.

According to the definition of λ, Life 1133 is characterized by a value in the

same vicinity:
λ2333 = 0.273438 and λ1133 = 0.234375.
This would suggest the correctness of the λ parametrization. However,
we have also found class I (e.g., Life 2255), class II (e.g., Life 6633) and class
III (e.g., Life 1233) CA in the same vicinity [10]. As first observed in [12], it
seems that the λ parameter alone is insufficient for locating specific regimes
precisely, even in a subset of the CA rule space like Life.

3. A review of common natural structures

3.1 Fixed structures
The low density of Life 1133 after a few time steps is compensated for by the
rich variety and symmetry of simple Life forms. All the structures shown in
this section occur naturally.
The first kind of structure includes stable patterns that never change.
They represent the commonest objects of Life 1133. Figure 6 gives a selection
of these structures, including the “block:” a four-cell pattern formed by a
two-by-two square which is one of the few structures in common with Life
2333. The most common object of Life 1133 is the “small block” consisting
of two adjacent living cells.

3.2 Period 2 oscillators

Life 1133 shows a rich variety of oscillators. Most of them have a period
of two. Figure 7 gives a selection of these objects. The fourth oscillator in
the upper part of the figure leads to other forms, some of them occurring
naturally, such as the first oscillator in the lower part of the figure. We have
called this oscillator the “barber pole” recalling the same kind of structure
from Life 2333. It is an oscillator that may be stretched to any length, making
it as large as desired (Figure 8). Only small versions occur spontaneously.
374 Jean-Claude Heudin

Figure 8: The barber pole may be stretched to any length.

Figure 9: A selection of period 4 oscillators including the blinker (top

row), the tumbler, the twister, and the rattle.

One of the most interesting features of Life 1133 seems to be its symmetry
property. All structures that have been discovered so far exhibit symmetry
of one form or another: reflection, rotation, etcetera.

3.3 Other oscillators with greater periods

Oscillators with periods other than two have been found, but all with an even
period. Figure 9 shows a selection of period 4 oscillators. When generated on
a high-speed computer, these oscillators create convincing illusions of three-
dimensional rotary motion.
One of the most beautiful and interesting objects is a symmetric com-
bination of four simple period 4 oscillators (Figure 10). This arrangement
recalls the well known “traffic light” from Life 2333, but with a period of
four instead of two and a more sophisticated pattern. With a fast execution
speed, this structure looks like a “twinkling star.”
A quite common oscillator has a period of ten. The second five phases
are the rotated and mirrored images of the first five phases. Figure 11 shows
this oscillator that we have named the “alien clock.”

3.4 Propagating glider

One of the criterion for Life 1133 to be a game of life worthy of the name
is the existence of a natural propagating glider. The glider of Life 1133 was
discovered only after ten primordial soup experiments. However, it seems
A New Candidate Rule for the Game of Two-dimensional Life 375

Figure 10: The twinkling star from Life 1133.

Figure 11: The period 10 alien clock.

Figure 12: The period 4 glider of Life 1133. The upper part shows
the effect of the transition rule (R1: black, R2: gray, and R3: white).

that it is less common than the one of Life 2333, mainly because of the
relative short transients of Life 1133.
The glider appears to creep something like an amoeba, changing its shape
as it goes. Like Conway’s glider, it assumes four different phases and moves
at the same speed: one cell per four generations, or, in other terms, one-
quarter cell per generation. Unlike Conway’s glider, it moves horizontally or
vertically instead of diagonally. Figure 12 shows the four states. When state
one is encountered again, the glider will have moved one cell forward.
The behavior of gliders interacting with other artifacts represents the
foundation for implementing complicated structures including a universal
Turing machine. Therefore, the investigation of the glider of Life 1133 in
more detail is an important part of this study.
376 Jean-Claude Heudin

4. Glider-based computing
4.1 Collisions
What happens when a glider collides with another object? The number of
possible objects leads to a large number of possible collisions between a glider
and other objects. One would expect that, in most cases, the result of such
events is the annihilation of both objects. This is the case, for example, when
two gliders move towards the same point as shown in Figure 13. This collision
is particularly useful for implementing vanish reactions in glider streams (see
section 4.3).
However, in some other cases, the collision leads to the birth of objects
that do not fade instantly. As an example, Figure 14 shows a glider colliding
with a block. The collision results in two debris: a new block and a period 2
oscillator.

Figure 13: A collision between two gliders leads to the annihilation

of all living cells. The last configuration (t10 ), consisting of an empty
array, is not shown here.

Figure 14: A collision between a glider and a block.

A New Candidate Rule for the Game of Two-dimensional Life 377

Figure 15: The collision between a glider and a small block produces
the 6-phase fighter.

Figure 16: The 6-phase fighter in action.

The subject of collision is more complicated than might be thought, for

there are usually many different ways that two objects can collide: respective
positions and phases almost always make a difference.
One of the most interesting collisions occurs when a glider collides with a
small block. This configuration produces a new glider type consisting of both
objects (Figure 15). We have named this glider the “fighter,” because of its
robustness and the fact that it can fire a “torpedo” on a line of small blocks
and destroy any object placed at the end of the line (Figure 16). Besides this
amusing comparison, it gives a clear example of properties of Life 1133 for
constructing objects showing complicated or surprising behaviors.

4.2 Speed of light

Life’s rules limit the speed of propagating structures. The maximum speed
at which any information can be transmitted across the Life plane is one cell
per generation in any direction. This can be viewed as the counterpart of the
speed of light in the real world and is often called by that name. It is quite
easy to find a pattern propagating at this maximum speed in Life 1133. As
seen in the previous section with the fighter (Figure 16), a simple pulse on a
line of small blocks produces that behavior (Figure 17).
378 Jean-Claude Heudin

Figure 17: The propagation of a pulse along a line of small blocks.

4.3 Universal computation

The existence of a glider suggests that, similar to Conway’s Life, Life 1133
could be capable of universal computation. In a constructive proof of uni-
versality [6], a stream of regularly spaced propagating gliders represents a
string of bits. In such a stream, the presence of a glider at a given posi-
tion represents a “1” and absence represents a “0.” Based on such streams,
the implementation of a single logical gate (a NAND or a NOR gate) is re-
quired to be able to design any digital machine, including a universal Turing
machine.
Useful configurations for implementing such a logical element include the
vanish reaction when two gliders collide (see section 4.1) and the “star gate:”
a pattern composed of two twisters that destroy any glider in a stream while
preserving its own structure (Figure 18). In practice, there are further el-
ements required such as elements that will turn a signal stream by right
angles, but we do not go into the details of these elements in this paper.
A series of experiments was performed in order to find a “glider gun:” a
periodic structure that produces the required steady stream of gliders. We
have found many configurations producing a glider (Figure 19), but we must
point out that we have not yet discovered this crucial element. Note that
Carter Bays has not found such an object, or at least reported one, during
several years of extensive research on three-dimensional Life CA. However,
the study of Life 1133 is still recent and is currently undergoing intense
investigation.

5. Implementation
Many implementations of Life and CA tools are available for many platforms
(see H. A. Gutowitz’s FAQ Life page for a good introduction and links to
these tools2 ). Life 1133 was found using a very simple CA applet designed
2
http://alife.santafe.edu/alife/topics/cas/ca-faq/lifefaq/lifefaq.html
A New Candidate Rule for the Game of Two-dimensional Life 379

Figure 18: The star gate (two twisters) destroys any glider that try
to pass.

Figure 19: Two patterns producing a glider.

with the Java Development Kit 1.0.2. Our motivation was to use a modern
object-oriented and highly-portable code accessible to anyone with at least
a Java-enabled browser. The applet source is available on the World Wide
Web.3 Another Java-based implementation of Life designed by Paul Callahan
with a large database of patterns is also available.4 Yet another Java-based
implementation provides a huge universe (1 million × 1 million cells) and a
very fast algorithm.5

3
http://www.devinci.fr/iim/jch/
4
http://www.cs.jhu.edu/∼callahan/lifepage.html
5
http://www.mindspring.com/∼alanh/life/
380 Jean-Claude Heudin

6. Conclusion
Many variants of Conway’s rule of Life have been tried without any having
been reported as being worthy of further attention. In this paper, we have
presented another rule for a game of Life worthy of the name. Life 1133
shares the same global properties of Life 2333 but with shorter transients.
It shows a rich universe of small symmetric stable and oscillating patterns
including a propagating glider. This is quite surprising, since class IV CA
generally combine complex patterns and very long transients. The next phase
of this study will focus on the discovery of a glider gun in order to make a
constructive proof of universality.
Conway’s Life is the ideal example of Wolfram’s class IV automaton for
two-dimensional two-states CA [13]. Life 1133 is another example of such an
automaton. One can consider it as a “trivial variant” of Life 2333, since the
only difference is the value used by the “environment” rule (R2). However,
the discovery of Life 1133 is important since it clearly shows that other rules
for a game of Life exist that require further attention.

References
[1] C. Bays, “Candidates for the Game of Life in Three Dimensions,” Complex
Systems, 1 (1987) 373–400.

[2] C. Bays, “A Note on the Discovery of a New Game of Three-dimensional

Life,” Complex Systems, 2 (1988) 255–258.

[3] C. Bays, “The Discovery of a New Glider for the Game of Three-dimensional
Life,” Complex Systems, 4 (1990) 599–602.

[4] C. Bays, “A New Candidate Rule for the Game of Three-dimensional Life,”
Complex Systems, 6 (1992) 433–441.

[5] E. Berlekamp, J. H. Conway, and R. Guy, Winning Ways for Your Mathe-
matical Plays (Academic Press, 1982).

[6] M. Gardner, “M. Mathematical Games: The Fantastic Combinations of John

Conway’s Game of Life,” Scientific American, 223 (1970) 120–123.

[7] M. Gardner, “On Cellular Automata, Self-reproduction, the Garden of Eden,

and the Game of Life,” Scientific American, 224 (1971) 112–118.

[8] H. A. Gutowitz, J. D. Victor, and B. W. Knight, “Local Structure Theory for

Cellular Automata,” Physica D, 28 (1987) 18–48.

[9] J. C. Heudin, “Evolution at the Edge of Chaos,” Fourth European Conference

on Artificial Life, http://www.cogs.susx.ac.uk/ecal97 (1997).

[10] J. C. Heudin, “Complexity Classes in Two-dimensional Life-like Cellular

Automata,” International Institute of Multimedia Working Paper (1997).
 A New Candidate Rule for the Game of Two-dimensional Life 381

[11] C. Langton, “Life at the Edge of Chaos,” in Artificial Life II, Santa Fe Insti-
tute Studies in the Sciences of Complexity, volume 10, edited by C. Langton,
C. Taylor, J. D. Farmer, and S. Rasmussen (Addison Wesley, 1991).

[12] W. Li, N. Packard, and C. Langton, “Transition Phenomena in Cellular

Automata Rule Space,” Physica D, 45 (1990) 77–94.

[13] H. McIntosh, “Wolfram’s Class IV Automata and a Good Life,” Physica D,

45 (1990) 105–121.

[14] N. Packard and S. Wolfram, “Two-dimensional Cellular Automata,” Journal

of Statistical Physics, 38 (1985) 901–946.

[15] W. Poundstone, The Recursive Universe (Morrow, 1985).

[16] S. Wolfram, “Universality and Complexity in Cellular Automata,” Physica

D, 10 (1984) 1–35.

View publication stats