Chapter 7
Cellular Automata Simulation
This intelligent behavior would be just another one of those or-
ganizational phenomena like DNA which contrived to increase
the probability of survival of some entity. So one tends to sus-
pect, if oneĄfs not a creationist, that very very large LIFE
configurations would eventually exhibit intelligent [character-
istics]. Speculating what these things could know or could find
out is very intriguing . . . and perhaps has implications for our
own existence [79, pp.139–140].
7.1 Game of life
The eminent mathematician John von Neumann studied self-reproducing
automata in 1946, shor tly before his death. He found that self-reproductio n
is possible with 29 cell states, and proved that a machine could not only re-
produce itself, but could also build machines more complex than itself. The
research stopped because of his death; however, in 1966, Arthur B urks edited
and published von Neumann’s manuscripts. John Conway, a B ritish mathe-
matician, expa nded on the work of von Neumann and, in 1970, introduced the
Game of Life, which attracted immense interest. Some people became “Game
of Life hackers,” programmers and designers more interested in ope rating co m-
puters than in eating; they were not the criminal hackers of today. Hackers
at MIT rigorously resear ched the Game of Life, and their results contributed
to advances in computer science and artificial intelligence. The concept of the
Game of Life evolved into the “cellula r automaton” (CA), which is still widely
studied in the field of artificial life. Most of the research on a rtificial life shares
much in common with the world where hackers played in the early days of
computers.
The Game of Life is played on a grid of equal-sized squares (cells). Each
cell can be either “on” or “off.” There are eig ht adjace nt cells to each cell in a
two-dimensional grid (above and b e low, left and right, four diagonals). This
is called the Moore neighborhood. The state in the next step is determined
by the rules outlined in Table 7.1. The “on” state corresponds to a “•” in the
cell, whereas the “off” state corresponds to a blank. The following interesting
patterns can be observed with these rules.
179
180 Agent-Based Modeling and Simulation with Swarm
TABLE 7 .1: State of ce ll in the next step.
Current state of cell States of neighbor cells State in the next step
On two or three are “on” On
Other cases Off
Off three are “on” Off
Other cases Off
(1) Disapp e aring pattern (diagonal triplet)
•
• ⇒ • ⇒ disappears
•
(7.1)
(2) Stable pattern (2 × 2 block)
•• •• ••
•• ⇒ • • ⇒ •• ⇒re mains stable
(7.2)
(3) Two-state switch (Flicker, where vertical triplets and horizontal triplets
appear in tur n)
• •
• ⇒ ••• ⇒ • ⇒repeats
• •
(7.3)
(4) Glider (patter n moving in one direction)
•
• •
••• ⇒ • ⇒ • ⇒ moves to bottom right
••• •
•••
(7.4)
“Eaters” that stop gliders and “glider guns” that shoot gliders can be defined,
and glider guns are generated by the collision of gliders. Such self-organizing
capabilities mean that the Game of Life can be used to configure a universal
Turing machine. The fundamental logic gates (AND, OR, NOT) consist of
glider rows and disappearing reactions, and blocks of s table patterns are used
as memory. However, the number o f cells needed in a self-organizing system
is estimated at about 10 trillio n (3 million × 3 million). The size would be a
square w hose sides are 3 km long, if 1 mm
2
cells are used.
Consider a one-dimensio nal Game of Life, one of the s implest cellular au-
tomata. The sequence of cells in one dimension at time t is expressed as
follows:
Cellular Automata Simulation 181
a
1
t
, a
2
t
, a
3
t
, ··· (7.5)
Here, e ach variable is either 0 (off) or 1 (on). The general rule use d to deter-
mine the state a
i
t+1
of cell i at time t + 1 can be written as a function F of
the state at time t as
a
i
t+1
= F (a
i−r
t
, a
i−r+1
t
, ··· , a
i
t
, ··· , a
i+r−1
t
, a
i+r
t
) (7.6)
Here, r is the radius, or range of cells that affects this cell.
For instance, a rule for r = 1,
a
i
t+1
= a
i−1
t
+ a
i
t
+ a
i+1
t
(mo d 2) (7.7)
results in the determination of the next s tate as follows:
time t : 0010011010101100
time t+1 : *11111001010001*
An interesting problem is the task of finding the majority rule. The task
is to find a rule that would ultimately end in a sequence of all 1 (0) if the
majority of the cells are 1 (0) w ith the minimum radius (r) possible for a
one-dimensional binary sequence of a given length. The g e neral solution to
this problem is not k nown.
A famous example is a majority rule problem with length 149 and radius
3. The problem is reduced to finding a function that assigns 1 or 0 to an input
with 7 bits (= 3 + 1 + 3 , radius of 3 plus itself); therefore, the function space
is 2
2
7
.
How ca n a cellular auto maton (CA) obtain a solution to the majority
problem?
One method is to change the color (black or white) of a cell to the majority
of its neighboring cells. However, this method does not work well, as shown
in Fig.7.1 because it results in a fixed pattern divided into black and white.
In 1978, Gacs, Kurdyumov [37A], and Levin found the rules (GLK) re-
garding this problem. Lawrence Davis obtained an improved version of these
rules in 1995, and Rajarshi Das proposed another modification. There is also
research to find effective rules through GA or GP. The concept of Boolean
functions is applied when GP is used. The fitness value is defined by the
percentage of correctly processed sequences out of 1000 randomly generated
sequences of length 149.
Rules determined by various methods are summarized in Table 7.2. Her e ,
the transition rules are shown from 0000000 to 1111111 in 128 -bit form. In
other words, if the first bit is 0,
F (000 0 000) = 0 (7.8)
Table 7.3 is a comparison of different rules. The rules obtained using GP were
very effective; reference [2] contains the details of this work.
182 Agent-Based Modeling and Simulation with Swarm
FIGURE 7.1 (See Color Insert): CA carrying out majority voting (with
permission of Oxford University Press, Inc. [88]).
FIGURE 7.2 : Behavior of CA driven by GA (with permission of Ox ford
University Press, Inc. [8 8]).
Fig.7.2 shows how a CA obtained by GA can solve this problem well [87,
88]. The regions that were initially do minated by black or white cells become
regions that are completely occ upied by either black or white ce lls . A vertical
line always exists at locations where a black reg ion to the right meets a white
region to the right. In contrast, a triangular region with a chessboa rd pattern
forms where a white region to the right meets a black reg ion to the right.
The two edge s of the growing triangular region at the ce nter with a chess-
board pattern grow at the same pace, progressing the same dista nce per unit
time. The left edge extends until it collides with a vertical boundary. The
right edge barely avoids the vertical b oundary at the left (note that the right
and left edges are connected). Therefor e , the left edge can extend for a shorter
length, which means that the length of the white region limited by the left edge
is shorter than the length of the black region limited by the right edge. The
left edge disappears at the collision po int, allowing the black region to grow.
Cellular Automata Simulation 183
TABLE 7 .2: Majority rules.
Name of Transition rules
rule (year)
GKL (1978) 00000000 01011111 00000000 01011111 00000000 01011111 00000000
01011111 00000000 01011111 11111111 01011111 00000000 01011111
11111111 01011111
Davis (1995) 00000000 00101111 00000011 01011111 00000000 00011111 11001111
00011111 00000000 00101111 11111100 01011111 00000000 00011111
11111111 00011111
Das (1995) 00000111 00000000 00000111 11111111 00001111 00000000 00001111
11111111 00001111 00000000 00000111 11111111 00001111 00110001
00001111 11111111
GP (1995) 00000101 00000000 01010101 00000101 00000101 00000000 01010101
00000101 01010101 11111111 01010101 11111111 01010101 11111111
01010101 11111111
TABLE 7 .3: Pe rformance in the majority problem.
Rule Performance Number of tests
GKL 81.6% 10
6
Davis 81.8% 10
6
Das 82.178% 10
7
GA 76.9% 10
6
GP 82.326% 10
7
Furthermore, the two edges disappear at the bottom vertex and the entire
lattice row becomes black, showing that the correct answer was obtained.
Melanie Mitchell analyzed the infor mation processing structure on CA
that evolved through GA by using the behavior of dynamic systems [87, 8 8].
The boundaries between simple regions (edges and vertical boundaries) are
considered carriers of information, and information is processed when these
boundaries collide. Figure 7.3 shows only the boundaries in Fig. 7.2. These
boundary lines are called “particles” (similar to e lementary particles in a cloud
chamber used in physics). The particles are repr e sented by Greek letters fol-
lowing the tradition in physics. Six particles are generated in this CA. Each
particle represents a different type of b oundary. For instanc e , η is the bound-
ary between a black region and a chessboard-patterned region. A number
of collisions of particles can be obs e rved. For example, β + γ results in the
generation of a new particle η, and both particles annihilate in µ + η.
It is easy to understand how information is coded and calculated when the
behavior of CA is expressed in the language of particles. For insta nce , α and
β pa rticles are coded w ith different information on the initial configuration.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.