CA rules
Dr. Robert Andreen
> Recently you posted to the ca-list concerning Life rule variants and
> symmetric Moore neighborhood rules. I and some friends of mine have
> found some interesting objects in a Life variant; we'll be posting
> some results soon to the ca-list. If you have some new findings,
> please share them; there are people interested!
>
> I have perused symmetric rules myself, but I find it hard because of the
> size of the rule space. Do you have some automated way of selecting
> `interesting' rules?
>
> thanks,
> - n...@rnd.switch.com
This reply is also in response to Dov Sherman's post, subject: "General CA
Forms?", dated 28 Mar 1994 and Antony Hare's post, subject: "Changing the
Rules of Life for REAL simulation", dated 27 Mar 1994.
I believe that Nathan Thompson has hit home with the problem of dealing
with generalized symmetric rules on the two-state Moore neighborhood when
he writes about the inherent difficulty handling these type of rules
because of the size of the rule space. I agree. The difficulty is not in
the mechanics of determining the new state. This can be done in several
easy ways, (How about a look up table based on the 9-bit number formed by
reading the neighborhood bit pattern in some sequence? Crude, but
effective, yielding a rule space of 2^512 possible rules) The real
difficulty lies in *visualizing* what you are doing when you change values
in the tables and drawing inferences about what values to change to produce
what results. I have an approach that helps simplify this visualization or
formatting problem, for me at least, but first, to make sure we're on the
same wavelength and using the same terms, a few preliminaries on transition
rules and their formats.
A Discussion of Rule Formats
----------------------------
For a given deterministic rule system, in any number of dimensions, a rule
may give the next state of any cell based on two numbers: the integer state
of the cell in question and an integer function of the integer cell states
in its neighborhood. Let X1, X2, X3,...,XN be the integer states in an N
cell neighborhood. Let F(X1,X2,...,XN), abbreviated F(), be an integer
neighborhood function that is sequential, after eliminating unattainable
values, with F()max its maximum. Then a convenient way of describing the
next state of any cell can be found using a `transition table' where the
current states and the neighborhood function are plotted against each other
to determine a cell's new state which appear in the body of the table, as
below, with k possible states:
F() --->
\ 0 1 2 3 4 5 ... F()max
|------------------------------
Current 0 | 0 1 3 0 0 0 ... 4 \
Center 1 | 0 0 1 4 0 0 2 |
Cell 2 | 3 0 0 1 1 1 0 | Values in State
3 | > table are
4 | Etc | new states
: | |
k-1 | 0 0 1 2 2 0 ... 0 /
In totalistic or semi-totalistic CA rules, F() is simply the sum of the
neighborhood states. For example, in the 2d two-state Conway's Life, F()
is the sum of the eight bits in the Moore neighborhood (the eight cells
surrounding the center cell in a rectangular grid). Calling F() the 8sum,
Life is completely described by the transition table below:
8sum
\ 0 1 2 3 4 5 6 7 8
|--------------------------
Center 0 | 0 0 0 1 0 0 0 0 0
Cell 1 | 0 0 1 1 0 0 0 0 0
Other `Life'-like CA's can be developed by changing the pattern of 0's and
1's in the table. Try putting 1's at 0: 6,7, e.g.
In general, the transition table (actually a look-up table itself) is easy
to mechanize in a computer with a k*F()max array and, if needed, another
look-up to determine F(). The total number of transition table entries will
be k*F()max, with (k)^(k*F()max) the total number of possible rules.
With a simple function like the 8sum, it is rather simple to predict or
visualize a particular cell's new state. However, with more complicated
F(), this visualization becomes more difficult and sometimes re-arrangement
of the transition table in a new format makes it simpler for the human
observer to visualize the effect of changing particular values. (The
computer doesn't care - a look-up table is about as easy as it gets for a
computer)
Let us consider some possible refinements. For example, feeling
intuitively that the corner cells and the side cells of the Moore
neighborhood contribute differently to the new state of the center cell
since they are related to it differently in a topological sense, let us sum
them separately and consider all the possible combinations of them. A
convenient way of formatting the possibilities might be:
\ Corners Sum
\ 0 1 2 3 4
---------------
0 | 0 0 0 0 0
Center Sides 1 | 0 0 1 0 0
Cell Sum 2 | 0 1 0 0 0
0 3 | 0 0 0 0 0
4 | 0 0 0 0 0
\ Corners Sum
\ 0 1 2 3 4
--------------
0 | 0 0 0 0 0
Center Sides 1 | 0 1 1 1 0
Cell Sum 2 | 0 1 1 0 0
1 3 | 0 1 0 0 0
4 | 0 0 0 0 0
To convert the above formats to transition tables of the type previously
discussed, put the rows in each case end to end. Since all entries are
attainable, this will yield a 2x25 transition table that can be mechanized
as before. In any event, the number of possible rules, including the
classical Life as a special case, is up to 2^50. BTW, the rule above,
yields an interesting frog-like orthogonal glider, Period 30, V=1/30C, from
this starting pattern:
1 1 1 1
1 1 1
1 1 1
1 1 1 1
Noting that 0, 1, 3, and 4 side or corner cells are always similar under
appropriate rotations, but that 2 cells have two possible configurations,
we might introduce a new twist. Let us distinguish between 2 cell pairs
that are adjacent to or opposite one another and designate them 2 Ad and 2
Op, respectively. The pairs could be either side pairs or corner pairs.
Using a system similar to the one described above, we find a convenient
format to be:
\ Corners Index
\ 0 1 2A 2O 3 4
------------------
0 | 0 0 0 0 0 0
Center Sides 1 | 0 0 1 1 0 0
Cell Index 2A| 0 1 0 0 0 0
0 2O| 0 1 0 0 0 0
3 | 0 0 0 0 0 0
4 | 0 0 0 0 0 0
\ Corners Index
\ 0 1 2A 2O 3 4
------------------
0 | 0 0 0 0 0 0
Center Sides 1 | 0 1 1 1 1 0
Cell Index 2A| 0 1 1 0 0 0
1 2O| 0 1 1 0 0 0
3 | 0 1 1 0 0 0
4 | 0 0 0 0 0 0
Note that we have dropped the term `sum' for `index' now and have increased
the rule space to 2^72 possible rules. We are assuming that somewhere in
the program code, the rule can appear in the above format and is convenient
to change. For example, picking the common langyage BASIC as a model, the
72 entries could be read into appropriate arrays from 12 DATA statements
arranged as the entries above, and the entries (0's and 1's) in these
statements are what are manipulated by the experimenter when the code is
listed.
Using this format, one can often tell what effect an entry will have on the
CA resulting. For example, putting a 1 at (0: 1,1) will cause explosive
growth in all directions, putting a 1 at (0: 0,2A) will cause pairs of
diagonal cells in a 2x2 square to alternate on and off, putting a 1 at (1:
4,4) will cause all solid 1 areas to stay 1 for another cycle, etc.
BTW, the rule table shown above yields an easy-to-generate puffer and other
complex features from an initial random pattern.
Formatting the General Symmetric Moore Neighborhood
---------------------------------------------------
If we confine ourselves to 2-state rules and the 8-cell Moore neighborhood,
the most general transition table would have an F()max of 255 (think of the
neighborhood as an 8-bit binary number or pattern) and 512 table entries,
w/ x = 0,1, to wit:
\ 0 1 2 3 4 5 6 7 8 9 10 ... 254 255
|---------------------------------------------
Center 0 | x x x x x x x x x x x ... x x
Cell 1 | x x x x x x x x x x x ... x x
If we insist on certain symmetries on the basis that the CA should behave
similarly if the cell space was rotated or flipped, we may eliminate many
entries as redundant since they turn into the same pattern on rotation or
flipping. In fact, there are exactly 51 distinguishable patterns that can
be formed on the Moore neighborhood. (How do I know this? I counted
them.) Assume each distinguishable pattern is assigned a number 0 to 50.
Then a generic transition table might be, w/ x = 0,1:
\ 0 1 2 3 4 5 6 7 8 9 10 ... 49 50
|---------------------------------------------
Center 0 | x x x x x x x x x x x ... x x
Cell 1 | x x x x x x x x x x x ... x x
Trying to to adopt the same formatting approach as above (considering sides
and corners separately), we find that some of the features carry-over
nicely, for example, when either index is 0 or 4 and for certain other
combinations, the entries are unique. For others, there may be up to three
possibilities.
Obtained from analyzing all possible patterns, the following table yields
the number of unique patterns for various indices:
\ Corners Index
\ 0 1 2A 2O 3 4
------------------
0 | 1 1 1 1 1 1 6
Sides 1 | 1 2 3 1 2 1 10 Note
Index 2A| 1 3 2 2 3 1 12 symmetry
2O| 1 1 2 1 1 1 7 about
3 | 1 2 3 1 2 1 10 major
4 | 1 1 1 1 1 1 6 diagonal
---
Total 51
For example, consider 2Ad (Corners) vs 3 (Sides). The three unique
patterns are:
0 1 0 1 1 0 0 1 1 NB: No amount of flipping
1 0 1 0 1 0 or rotating will turn one
1 1 1 1 1 0 0 1 1 into another.
Thus, we might consider a transition table based on following format:
Corner Index
\
\ 0 1 2Ad 2Op 3 4
\--------------------------------------------------------------
|^M
0 | ___ ___ ___ ___ ___ ___
|
S 1 | ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
i |
d 2A | ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
e |
2O | ___ ___ ___ ___ ___ ___ ___
I |
n 3 | ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
d |
e 4 | ___ ___ ___ ___ ___ ___
x |
In the table, for definiteness, where more than one entry is found for a
pair of corner/side indices, they are arranged from left to right in order
of the size of their minimums, after appropriate rotations and/or flipping.
As usual, the rule is imposed by putting appropriate 0's and 1's in the
spaces. The spaces are numbered from left to right, top to bottom, 0 to
50. Separate tables are needed for center cells, 0 and 1. The ability to
visualize what effect the a particular entry will cause in the CA is to
large degree preserved. The NW corner is particularly sensitive to
modifications while more subtle effects are caused changes at the opposite
corner. (I am assuming an average high percentage of vacuum.) In between,
we have a vast area to explore. A helpful aid is a graphical portrayal
of the minimized patterns, arranged in the same format as the table above.
The new state values are read into the transition table array in the same
manner described before. Now, finally, the question - How is the F()
formed from the particular pattern sensed in a cell neighborhood. I'm sure
that there are more elegant ways to do this (I've tried some - they slow
things down) but I would recommend a brute force look-up table. In a 0-255
element array (the look-up table), place the values of the appropriate 0-50
neighborhood function, F(). Form the eight bit number 0-255 from the
neighborhood (I start at the SE corner and go clockwise). With F() known,
next state is known from the transition table. In transition table format
above, count left to right and down, locating new state.
How do you find the values of the F() to put in the look-up table?
If you use my transition table format above, the values for F() starting at
0 and ending at 50 (32H), for each possible 2-state neighborhood (0-255)
are in sequence as follows (in hex to save space):
0 1 1 2 1 3 2 4 1 2 3 4 2 4 4 5 6 7 7 9 8 C
A D 8 A C D B E E F 6 8 7 A 7 C 9 D 8 B C E
A E D F 10 11 12 14 11 16 14 18 13 15 17 19 15 1A 19 1B 6 8
8 B 7 C A E 7 A C E 9 D D F 1C 1D 1D 1E 1D 20 1F 21
1D 1F 20 21 1E 21 21 22 10 13 11 15 12 17 14 19 11 15 16 1A 14 19
18 1B 23 24 25 26 25 29 27 2A 24 28 29 2B 26 2B 2A 2C 6 7 8 A
8 C B E 7 9 C D A D E F 10 12 11 14 13 17 15 19 11 14
16 18 15 19 1A 1B 1C 1D 1D 1F 1D 20 1E 21 1D 1E 20 21 1F 21 21 22
23 25 25 27 24 29 26 2A 24 26 29 2A 28 2B 2B 2C 10 11 13 15 11 16
15 1A 12 14 17 19 14 18 19 1B 23 25 24 26 24 29 28 2B 25 27 29 2A
26 2A 2B 2C 23 24 24 28 25 29 26 2B 25 26 29 2B 27 2A 2A 2C 2D 2E
2E 2F 2E 30 2F 31 2E 2F 30 31 2F 31 31 32 (32H=50D)
These values were determined by taking all possible patterns and rotating
and/or flipping them to determine uniqueness, eliminating redundancies, and
the arranging them in the order dictated by the new format.
To review the basic algorithm: For each cell in the grid, determine the
pattern code by reading the eight neighborhood cells as a binary number.
Knowing this number, enter the look-up table to determine F(). Knowing
F(), enter the transition table to determine new state. (Note: For
mechanizing this on a machine, these two operations can be combined into
one straight forward look-up table whose entries could be pre-calculated
for all possible neighborhoods. For visualization purposes, however, it is
better to keep the notions separate.)
And now finally, really finally, here's an `interesting' rule with
which to experiment:
Moorg13 Corner Index
\ 0 1 2A 2O 3 4
|----------------------------------
0 | 0 0 0 0 0 1
Side 1 | 0 0 0 1 1 1 1 0 1 0
Index 2A| 0 1 1 0 0 1 1 0 1 1 0 0
2O| 0 1 1 0 0 0 1
3 | 1 0 0 0 1 0 0 0 1 0
4 | 1 1 0 1 1 0
0 | 0 0 1 0 1 0
Side 1 | 0 1 0 1 1 1 0 1 0 1
Index 2A| 1 1 0 1 0 0 0 0 1 0 1 1
2O| 0 1 1 0 0 1 1
3 | 1 0 0 0 0 1 1 1 0 1
4 | 0 0 1 0 1 0
Comments: Ten easily generated gliders of various periods and velocities
from random mix, quasar and many gun possibilities.
Strategies for Selecting `Interesting Rules'
-------------------------------------------
I forgot. Just one more last item:
Nathan Thompson asks "Do you have some automated way of selecting
`interesting' rules?
Not really, but a strategy might be as follows. From randomized transition
tables with random initial configurations, look for `interesting' small
scale structures, such as gliders, blinkers, quasars, rotators, etc.
Isolate these structures and analytically or experimentally determine their
minimal transition tables, ie, the array of *necessary* transitions to
produce the structure along with indications of the "Don't Care"
transitions. Repeat until you have a decent library of these tables in a
database. Now automate a search, compare and integrate process that will
combine compatible transition tables. Investigate these new transition
tables with random initial configurations. At a minimum, all compatible
structures will be preserved and there will be the possibility of new,
perhaps more complex structures. Isolate them and repeat the process
until, at a limit, all "Don't Care" transitions are filled. This is more
or less what I do, but I really haven't thought out the automated part of
it.
This got a lot longer than I intended. Naturally I'd welcome your
comments. Finally, finally, finally, goodnight!
Bob Andreen
******************************************************************************
Robert B. Andreen E-Mail: and...@whall2.msmc.edu
Director of Academic Computing Phone: (914)-569-3156
Mount Saint Mary College Fax: (914)-562-6762
Newburgh, NY 12550
******************************************************************************