Variations on Conway's LIFE
dave boll
Variations on Conway's LIFE
After checking a reference that someone was kind enough to
send me, and receiving several other replies that basically
said "post it", here's some information on other types of 2-D
life rules that are kind of interesting.
Notation: In Conway's LIFE, the rules for calculating a new
generation of cells from a current configuration are as
follows:
1) If a cell is currently alive, and 2 or 3 of its neighbors
are also alive, it survives into the next generation;
otherwise it dies.
2) If a cell is dead, and exactly three of its neighbors are
alive, it becomes alive in the next generation; otherwise,
it stays dead.
In my notation, these rules are expressed as follows:
Life: 2,3 Birth: 3
Generalizations to other rules are EZ.
In order to test the 'interesting-ness' of various rules, I
applied three tests:
1) How many of the 5 quad-ominoes do not die out?
2) How many of the 12 quint-ominoes do not die out?
3) Start with a large random population, and watch it
evolve for a while. If it looks interesting, do some
more testing.
The results for #'s 1 and 2 are given in the following listing
as (for example):
Quads: 2/5 Quints:8/12
This means that for this particular rule set, 2 out of the 5
quad-ominoes survive, and 8 of the 12 quint-ominoes survive.
Also given for the 'good' rules are a few common oscillators,
with the period of the oscillator given in parenthesis. If a
glider is found, its speed is given in parentheses, prefaced by
a "g", for glider. For example, in Conway's life, the blinker,
block, and glider would be given as follows:
*** ** ***
(2) ** *
*
(g sqrt(2)/4 )
Note: The following list is in no way intended to be comprehensive.
Life:1,2 Birth: 3
Quads: 2/5 Quints: 5/12
Oscillators:
** * ** * * * ** **
* * * * * ** * * ** *
** ** * ** ** * * *
(2) (4) * (4) (2) ** *
** (4) (2)
(4)
Life:1,3 Birth: 3
Quads: 2/5 Quints: 5/12
Notes: Several small, boring oscillators. But, we do have a glider:
*
*
*
**
*
I forgot to record the speed for this. As shown, it will travel up
and to the right, so a speed of sqrt(2)/4 seems like a good guess.
Life:1,3 Birth: 3,4
Quads: 2/5 Quints: 4/12
Oscillators:
** * ** * * ** * ** **
* * ** * ** * *
(2) * (2) (2)
(2)
** *** ** *
** * * **** *
(2) * * ** ***
* * (3) (g sqrt(2)/4)
***
(2)
Life:1,4 Birth: 3,4
Quads: 0/5 Quints: 3/12
Notes: Small boring oscillators + a glider:
***
** **
*
(g 1/2)
Life:1,3 Birth: 3,5
Quads: 3/5 Quints: 3/12
Notes: 1333 glider works here also
Life: 2 Birth: 3 and up
Quads: 0/5 Quints: 1/12
Notes: Not much, but the glider is quite unusual.
Oscillators:
* ** * * ***
** **** **** * * *
* * * ** *
(4) (4) (2) (2)
**
(g sqrt(2)/8)
Life:2,4 Birth: 3
Quads: 0/5 Quints: 5/12
Oscillators:
** ** * * * * * * **
* *** *** *** * * ** * ** * *
** * * * * * * *** * *
*** **
(4) (4) (2) (4) (2) (2)
Life:2,4 Birth: 3,5
Quads: 1/5 Quints: 5/12
Notes: One of the best alternate rules. Residue tends to be very sparse
compared to 2333 life, but there are some interesting oscillators.
Despite fairly extensive checking, no gliders yet.
Oscillators:
* * * * * * * ** * **
* * ** ** * * * ** *** * *** * *
* * * * ** * ** * ** * * *
**
(4) (4) (2?) (2) (4) (2) (4)
Life: 3,5 Birth: 3,4
Quads: 3/5 Quints: 4/12
Notes: Like 2435, a nice rule set with lots of small oscillators. Again,
finding a glider would be nice.
*** * * * * ** * * **
*** ** * ** ** ** *** * *
* * * * * * * * * * *
* ** * **
*
(2) (8) (2) (6) (2) (8) (2) (2)
Life: 3,4 Birth: 3,5
Quads: 2/5 Quints: 4/12
Notes: Another decent alternate rule set in search of a glider.
Oscillators:
* * *** ** *** *** ** ***
** * * ** * * *** ** * **
* ** * * * ** ** ***
* * * ** **
*** ** **
***
***
(2) (16) (2) (2) (3) (2) (?)
Life: 3,4 Birth: 3,4
Notes: This rule set results in explosive growth, but there is a
small glider that is interesting in that it has a speed of
1/3:
**
**** (travels up)
Life: none Birth: 2
Notes: A rule set that (very probably) results in explosive growth;
certainly in area if not population. But, it has a small glider
that moves at a speed of 1:
**
(travels up)
* *
There are many other gliders; but I think this is the smallest.
Hex Life: Life on a hexagonal grid. As near as I can tell, there is only
one good rule set. But, that one set is very good - much better, IMHO,
than any of the alternate rules I presented above for square life. I
haven't found a glider yet, but I'm pretty sure one exists. I have
a 'glider finder' program that puts a small random configuration in the
middle of an area, then runs about 100 generations and saves all
starting configurations that escape from some predefined area. When
I ran this program on this rule set, I came up with a list of about 50
(out of 30,000 or so) confugurations that escaped. I haven't yet had
time to check these out.
Life: 3,4 Birth: 2
Oscillators: ("-" indicates an empty cell)
- - @ - @ - - - @ - - - - - @ - - - - - @ - - @ - @ - - - - @ - @ - -
- - - - - - - - - @ - - - @ - - - - - - @ - - - - - - - - - - - - - -
- @ - @ - - - @ @ - - - - - @ - - - - -2- - - @ @ - - - - @ - @ - - -
@ - -4- - - - - -4- - - - - -2- - - - - - - - - -2- - - - - - -4- - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - @ @ - - - - - @ - - - - @ @ - - - @ - - - - - @ - @ - - - - - - -
- - @ - - - - - - - - - - - @ - @ - - - - - - - - - - @ @ - - - - - -
@ @ - - - - - - @ @ - - - - @ @ - - @ - @ - - - - - - @ @ - - - - - -
- - -4- - - - - @ @ - - - - - - - - - -2- - - - - - - - - - - - - - -
- - - - - - - - - - - - - - -3- - - - - - - - - - - - @ - - - - - - -
- - - - - - - - @ - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - -4- - - - - - - - - - - - - - - - - - 48! - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - @ - - - - - - @ @ - - - - - - - - - - - - - - - - - - - - - -
- - @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - @ - - - - - - @ @ - - - - - - - - @ - - - - - - - - - - - - -
- @ - - - - - - - - @ - @ - @ - - - - - - @ @ @ - - - - - - - - - - -
- - 12- - - - - - - @ - - @ - - - - - - - - @ - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - -12 - - - - - - - - -4- - - - - - - - - - - - -
Triangular life: A triangular lattice seemed to me to provide excellent
possibilities for interesting life rules. If we define a neighborhood
as the set of 12 triangles that share a vertex or edge with a given
triangle, we have more #s to work with than the 8 neighbors of square
life or the 6 neighbors of hex life. Furthermore, there is no obvious
number to choose for birth. On a square grid, it is pretty clear that
three is the interesting birth number (although higher ones can be
added), and on a hex grid, two is the interesting birth number.
(Note: to see this, consider the max # of neighbors an empty square or
hex can have if it is next to a line.)
There is no obvious lowest birth # for a triangular lattice; anything
in the range 3-5 would seem to work. So, we have more flexibility in
selecting birth #s for triangular life.
Despite these facts, my (very incomplete) searches for triangular life
rules that are 'interesting' (whatever that is!) was a complete failure.
Several rules such as (life: birth:3,4), (life:4,6 birth:3,3) have nice
percolation (sp?), but almost no residue.
--
------------------------------------------------------------
Dave Boll bo...@handel.cs.colostate.edu
"The speed of time is 1 second per second"
------------------------------------------------------------
Nelson Minar
>(1) There were the interesting 3-D rules published in Sci Am about three years
>ago. It made for fascinating 3-D graphics.
yeah, and I've always wanted to play with those, only I'm too lazy to
write the software to display the 3d automata.
Are there any such programs available for free? I've seen some 3d
automata programs, but the display they provided wasn't very useful -
just slices through the grid. I'm more interested in some nice
perspective view.
Any software, for X, IBM, or Mac, would be much appreciated.
--
__
nel...@reed.edu \/ Death needs time for what it kills to grow in
Richard Ottolini
ago. It made for fascinating 3-D graphics.
(2) Generalized "life" is cellular-automata. Several groups are trying to
unstand phsyics and biology that way. MIT Press has published at least three
volumes on the subject.
Allan C. Wechsler
Date: Wed, 3 Jun 1992 08:02 EDT
From: tor...@diku.dk (Torben AEgidius Mogensen)
I also tried hexagonal life, and as far as I recall I came up with the
same rules as the above. I found lots of periodic cases (though not
all of the above), but I never found a stable (constant)
configuration. Did you? If not, can it be proven that none exist?
None exist. Here is an easy proof. Proceed by indirection. We suppose
we have found a finite stable pattern. Consider the northernmost row
that contains any live cells. It may not have two adjacent live cells,
because this would cause a birth in the row above. Therefore the live
cells in the top row have no neighbors in the top row or the row above.
Their only neighbors can be in the row below. So they have at most two
live neighbors, and therefore will die in the next generation.
Richard Ottolini
>In article <1992Jun2.1...@unocal.com> stg...@xing.unocal.com (Richard Ottolini) writes:
>>(1) There were the interesting 3-D rules published in Sci Am about three years
>>ago. It made for fascinating 3-D graphics.
>
>yeah, and I've always wanted to play with those, only I'm too lazy to
>write the software to display the 3d automata.
>
>Are there any such programs available for free? I've seen some 3d
>automata programs, but the display they provided wasn't very useful -
>just slices through the grid. I'm more interested in some nice
>perspective view.
>
>Any software, for X, IBM, or Mac, would be much appreciated.
Sorry, I wrote the display in a machine-dependent 3-D language called Dore.
When MIT-PEX implements lighting models for SPARCs (the R5 version doesn't)
then I may convert some codes to PEX.
Torben AEgidius Mogensen
> Variations on Conway's LIFE
I also tried hexagonal life, and as far as I recall I came up with the
same rules as the above. I found lots of periodic cases (though not
all of the above), but I never found a stable (constant)
configuration. Did you? If not, can it be proven that none exist?
I also tried to find symmetric Life rules on a square grid. Symmetric
in the sense that a pattern of holes in a filled area would behave
exactly the same as a pattern of filled cells in an empty area. I came
up with a rule set that gave fairly interesting results: several
periodic configurations and not too much death or wild growth. I don't
recall the rules, but I can dig them up at home if there is any
interest. I suspect that you may have tried the same rule set, but
perhaps not realizing that it was symmetric.
I think that hex life can yield many more interesting rules if you
allow 3 possible values of each cell. I have not studied this
intensively, but it might be worthwhile to try.
Torben Mogensen (tor...@diku.dk)
David Seal
AEgidius Mogensen) writes:
>bo...@CS.ColoState.EDU (dave boll) writes:
>> Variations on Conway's LIFE
>>
>>Hex Life: Life on a hexagonal grid. As near as I can tell, there is only
>> one good rule set. ...
>>Life: 3,4 Birth: 2
>
>I also tried hexagonal life, and as far as I recall I came up with the
>same rules as the above. I found lots of periodic cases (though not
>all of the above), but I never found a stable (constant)
>configuration. Did you? If not, can it be proven that none exist?
For a pattern to be stable under this rule, it must be infinite. A section
of one such pattern is:
* * - * * - * * - * * - * * -
- * * - * * - * * - * * - * *
* * - * * - * * - * * - * * -
- * * - * * - * * - * * - * *
* * - * * - * * - * * - * * - * = live
- * * - * * - * * - * * - * * - = dead
* * - * * - * * - * * - * * -
- * * - * * - * * - * * - * *
* * - * * - * * - * * - * * -
- * * - * * - * * - * * - * *
To prove that finite patterns cannot be stable, suppose a stable finite
pattern exists. Now look at the topmost occupied row in this pattern (this
row must exist because the pattern is finite). Consider the neighbourhood of
a live cell in that row:
- - -
- - - -
(a) (b)
? * ?
(c) (d) (e)
? ?
Observe that for the pattern to be stable, every live cell must have
precisely 3 or 4 live neighbours and no dead cell may have precisely 2 live
neighbours. So the cell labelled (a) must not have 2 live neighbours, i.e.
the cell labelled (c) must be dead. Similarly, the cell labelled (b) must
not have 2 live neighbours, so the cell labelled (e) must be dead. So the
cell labelled (d) has at most 2 live neighbours, whereas it must have 3 or 4
for the pattern to be stable.
This contradiction shows that no stable finite pattern can exist.
David Seal
ds...@armltd.co.uk
All opinions are mine only...
Brett Fishburne
on different (perhaps interacting) rule sets? Is this a worthwhile
excercise (I'm willing to get started on it in my spare time)?
-- Brett
bf...@sequent.com
Dave Hiebeler
> Date: 12 Jun 92 20:16:04 GMT
> From: bf...@sequent.com (Brett Fishburne)
>
> Has anyone tried a variation on LIFE that has two types of automata
> operating on different (perhaps interacting) rule sets? Is this a
> worthwhile excercise (I'm willing to get started on it in my spare
> time)?
Rudy Rucker has done some experimentation where he runs 2 different
rules on different bitplanes, and has special regions marked in the
array where the two rules can interact with each other.
It was written up in the _Complex Systems_ journal, and I think he's
described it on this mailing-list/newsgroup as well.
The two rules that I remember him mixing were "Life" and the "Brain"
rule from the Toffoli and Margolus CAM book.
--
Dave Hiebeler | hieb...@think.com
Thinking Machines Corporation | (617) 234-4070