The Chaotic Behaviour of different rules

For general discussion about Conway's Game of Life.
Post Reply
paultsui
Posts: 8
Joined: February 25th, 2012, 1:29 pm

The Chaotic Behaviour of different rules

Post by paultsui » February 28th, 2012, 12:53 pm

The Conway's Game of life has the B3/S23 rule and I believe Conway picked this rule because this system is most chaotic/dynamic. Obviously the game of life would be very boring if B8/S8 was picked instead!

I am wondering whether there exists a parameter that we can calculate (either mathematically or empirically) such that it quantifies the chaotic-ness of the system! I have a feeling that the entropy of the system might have something to do with this...

Thank you : )

User avatar
Wojowu
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: The Chaotic Behaviour of different rules

Post by Wojowu » February 28th, 2012, 1:48 pm

There are Life-like rules which are a lot more chaotic or dynamic than Life. For example, Seeds rule B2/S is very chaotic rule. Nice random seed in it is 2x2 square. There is four classes of CA as described here http://en.wikipedia.org/wiki/Cellular_a ... sification Conway's Life is class 4 and Seeds is class 3. Also, as said by Conway himself
It seems to me that 'B36/S23' is really the game I should have found, since it's so rich in nice things.
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: The Chaotic Behaviour of different rules

Post by Tropylium » February 28th, 2012, 2:17 pm

paultsui wrote:The Conway's Game of life has the B3/S23 rule and I believe Conway picked this rule because this system is most chaotic/dynamic. Obviously the game of life would be very boring if B8/S8 was picked instead!

I am wondering whether there exists a parameter that we can calculate (either mathematically or empirically) such that it quantifies the chaotic-ness of the system! I have a feeling that the entropy of the system might have something to do with this...

Thank you : )
Empirically, I usually think in terms of two parameters:
—How likely is random chaos to remain (and not spontaneously break up)? For "shrinking blob" rules, and most exploding rules (but not all: the likes of B2/S or B37/S23 will quite frequently produce small areas stabilized into objects), this likelihood is close to zero. For rules like B8/S8, or even rules like B3/S8, this is close to one (patches of vacuum will spontaneously develop). I'm less sure how this should be applied to rules that produce solid structures (growing or not — Maze, Coral, Diamoeba, Inkstains, Assimilation etc.) but I'm leaning on treating each phase independantly: none of them support chaos, but what they replace it with varies. Phases themselves form a continuum from regular (vacuum, zebra stripes, mesh generated by B3456/S34567) to somewhat regular (B3567/S4567 makes fairly similar mesh but without overall order) to random but stable (eg. B2/S234) to a mixture of random stable areas and chaos (eg. B34/S345) to "shapely chaos" (B123/S) to pure white noise chaos (something like B257/S135).
— How likely a given phase is to expand over another. This will depend on not only the pair of phases in question (chaos, vacuum, solid space, dot matrix, zebra stripes…) but also the curvature of their boundary. Several slowly growing rules are unlikely to grow much from a small starting point, ie. large positive curvature leads to slower growth. Rules with A0123B4* are unable to grow into vacuum over any positive curvature, but some can grow "inwards" if a hole is cut into a random starting state, ie. negative curvature still allows growth.

(* A = "abstain", to mark the absense of birth. Similarly, D = "death" is useful for specifying classes of rules with varying survival conditions.)

Next post: calculations.

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: The Chaotic Behaviour of different rules

Post by Tropylium » February 28th, 2012, 3:32 pm

It seems unavoidable that any strict mathematical results about the overall behavior of chaotic patterns in a rule must be made in terms of local behavior.

The degree of randomness of chaos (or a random solid state) should at least be possible to quantify in terms of how much each different cell environment occurs. Crystalline phases have fully quantifiable ratios: vacuum is uniformly dead cells with 0 neighbors; zebra stripes is ½ dead cells with 3+3 neighbors, ½ live cells with 2 opposite neighbors; mesh is ¼ dead cells with 8 neighbors, ½ live cells with 3+3 neighbors, ¼ live cells with 4 neighbors in each cardinal direction. For "shapely chaos", eg. B123/S seems to rather favor environments with 2 to 6 neighbors per live cell with contact to vacuum on two sides, and dead cells commonly form small blobs of vacuum. This kind of a thing should be entirely demonstrable with a complicated ruletable — just allocate different cells for different kinds of environments, and apply coloration. I've done an isotropic analysis of Life: see the topic "Life variants" in the other rules forum.

(BTW is there a way to get a detailed population analysis in Golly for a rule with multiple states?)

I mentioned curvature before; on the local level, this of course comes down to the number of neighbors of an edge cells — tho in rules like Inkstains that grow in an irregular shape, "edge cell" may be difficult to define.

There's two ways I see for dealing with rules that create chaos wandering over stable background: first, they could be treated as areas of different phases — but then one would expect only one of the phases, presumably the solid one, to be ultimately stable. In B13/S123 for example, chaos eventually dies down leaving just zebra stripes; an even better example may be B2678/S135678 which ultimately leaves solid space with a few holes ("anti-objects"), but this is anything but apparent immediately. Alternately (for very small-grained cases, like B237/S345, that display no tendency for growth of stable areas) a time dimension could be added to the environment analysis: how long does a cell typically remain before its neighborhood changes? How long does it typically stay alive or dead?

As for determining evolutionary behavior, I wonder about this (but haven't had time to rigorously work thru)… Consider a 4×4 area, treating the 4 inner cells as one cell with 16 states (6, modulo rotations). Given all of its 4096 possible neighborhoods, what proportion of these lead to each state of the inner area? This would reveal how likely certain configurations are to rise, or remain, and I do suspect that phases a rule naturally supports could be determined from this kind of data alone. (Perhaps 5×5 would be a more natural area to consider, being the 2-generation Moore neighborhood, altho that would be a clearly larger number of 512 center states and 65536 environments.)

paultsui
Posts: 8
Joined: February 25th, 2012, 1:29 pm

Re: The Chaotic Behaviour of different rules

Post by paultsui » February 28th, 2012, 8:00 pm

Wojowu: I definitely made a bad guess : D

Tropylium: Thank you for your comprehensive reply! One thing I don't really get - You mentioned that to determine evolutionary behaviour, one should consider a 4x4 or 5x5 area and count the number of possible states that could be evolved. Does one need to use periodic boundary condition (i.e. torus universe) when doing the measurement? Because if one considers only a small patch of the universe, then a lot of information would lost due to the fact that quite a lot of the patterns simply move out of the 4x4 patch. Shouldn't this be a problem?

In addition, can you justify why one should use a 4x4 or 5x5 area?
I guess to truly calculate the chaotic-ness of the system one should really consider the possible evolutionary states of the entire infinite grid - obviously this would take infinite amount of time to do. However, can you explain in more details why focusing on a 4x4 or 5x5 area would be enough? i.e. is it true that the chaotic-ness of a 4x4 patch (more or less_ the same as the chaotic of the corresponding infinite grid?

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: The Chaotic Behaviour of different rules

Post by Tropylium » February 29th, 2012, 3:38 am

paultsui wrote:One thing I don't really get - You mentioned that to determine evolutionary behaviour, one should consider a 4x4 or 5x5 area and count the number of possible states that could be evolved. Does one need to use periodic boundary condition (i.e. torus universe) when doing the measurement? Because if one considers only a small patch of the universe, then a lot of information would lost due to the fact that quite a lot of the patterns simply move out of the 4x4 patch. Shouldn't this be a problem?
The point is not to determine a specific pattern's behavior, it is to determine how much a rule favors certain environments over others. These environments would be expected to become more numerous when a random starting state is created and let evolve (one of 50% density should contain equal proportions of all possible environments, if we treat rotations and reflections as distinct) and from this some conclusions might be drawn.

Also we would consider all possible 4×4 areas, not anything "measured" from a pattern.

For a simple example, in rules with B345678/S234567, a 2×2 area with 3 cells will always become one with 4 cells, no matter what may exist outside of this area. Leave B8 out, and only 128 of the 4096 neighborhoods will not lead to 4 cells in the center from 3 cells in the center… This may still be critical however. In B34567/S234567 it is actually easy to find patterns that fill the plane with regular mesh, ie. in which all 2×2 areas have 3 cells. (Intuitively, this seems to be because an overall high proportion of 3-cell 2×2 areas would also imply an overall high proportion of those 128 neighborhoods in which there are 5 live cells surrounding the dead cell.)
paultsui wrote:In addition, can you justify why one should use a 4x4 or 5x5 area?
Simply because a 3×3 area is not sufficient for getting information on configuration frequency, only how common birth and death would be. This requires assuming that the probability of the states of adjacent cells in another cell's neighborhood are independant (which is not the case).

That still makes for a very quick test run of this idea, tho… So let's consider a few chaotic rules:

— Seeds: 28 B2 environments. 0 survival environments.
A density ρ would approximately mean that each cell has a probability ρ of being live; hence, the probability of finding a dead cell with a B2 environment is 56ρ²(1-ρ)⁷. The density after once generation is exactly the density of the previous kind of cells. If ρ is a stable density, then ρ = 56ρ²(1-ρ)⁷, which has the roots ρ = 0, ρ ≈ 0.0207, ρ ≈ 0.345.

Running 10 random starting configurations and sampling areas of 100×100, it seems the density of random chaos in Seeds is about 0.0209. So the first nontrivial root here actually fairly well corresponds to the empirical results :) I'm not sure what to make of the 2nd root, Seeds has no stable agars and the previous analysis does not apply to oscillators (they can have different densities for different phases). Although I will mention that the first oscillating agar I remembered in Seeds is the following:

Code: Select all

x = 30, y = 30, rule = B2/S
2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo$5bo5bo5bo5bo5bo$o5bo5b
o5bo5bo$bo5bo5bo5bo5bo$2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo
$5bo5bo5bo5bo5bo$o5bo5bo5bo5bo$bo5bo5bo5bo5bo$2bo5bo5bo5bo5bo$3bo5bo5b
o5bo5bo$4bo5bo5bo5bo5bo$5bo5bo5bo5bo5bo$o5bo5bo5bo5bo$bo5bo5bo5bo5bo$
2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo$5bo5bo5bo5bo5bo$o5bo5b
o5bo5bo$bo5bo5bo5bo5bo$2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo
$5bo5bo5bo5bo5bo$o5bo5bo5bo5bo$bo5bo5bo5bo5bo!
…which has an average density of ⅓, not far from 0.345.

— 3-4 Life: 56 B3 environments, 70 B4 enviroments. 56 S3 environments, 70 S4 environments.
Live cells in the next generation should have a density of about 70ρ⁵(1-ρ)⁴ + 126ρ⁴(1-ρ)⁵ + 56ρ³(1-ρ)⁶. For a stable density, we get the non-trivial roots ρ ≈ 0.207 and ρ ≈ 0.496 (and some roots > 1, but we don't care).

From a similar sample of 10 areas of 100×100, I get a density of about 0.427 for random chaos. Seems close (but not too close) to the 2nd root.

— DryLife: 56 B3 environments, 8 B7 environments. 56 S3 environments, 28 S2 environments.
Live cells in the next generation should have a density of about 8ρ⁷(ρ-1)² + 56ρ⁴(1-ρ)⁵ + 56ρ³(1-ρ)⁶ + 28ρ²(1-ρ)⁷. We get 2 real solutions ∈ (0,1] for a stable density: ρ ≈ 0.0448, ρ ≈ 0.404.

Sampling random chaos givs a density of about 0.086 (a very loose estimate, as DryLife becomes homogenous at only much larger scales than 100×100… individual samples ranged from 0.0425 to 0.102). I would not have expected this one to match very well tho, as chaos in DryLife is concentrated in "clouds", and various edge effects are going to be important. The density of a single "cloud" seems it might well be around 0.4, however…

— B12345678/S46: One A0 environment. 70 S4 environments, 28 S6 environments.
Life cells in the next gen should have a density of about (1-ρ)(1-(1-ρ)⁸) + 70ρ⁵(1-ρ)⁴ + 28ρ⁷(ρ-1)². This has only one non-trivial applicable root, ρ ≈ 0.644. Density of chaos in this rule turns out to be about 0.647. Rather close again.

I probably ought to test some "shrinking chaos" rules as well, but it seems that even this method can predict to some extent the density of chaos, at least in the more "white-noisey" rules.
paultsui wrote:However, can you explain in more details why focusing on a 4x4 or 5x5 area would be enough? i.e. is it true that the chaotic-ness of a 4x4 patch (more or less_ the same as the chaotic of the corresponding infinite grid?
I don't know if this is actually the case; this is simply an educated gess that's going to require investigation (but the previous tests look promising). I don't expect a rigorous general proof to exist, as growth behavior of CA patterns includes the halting problem…

User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: The Chaotic Behaviour of different rules

Post by Andrew » February 29th, 2012, 6:06 am

Tropylium wrote:(BTW is there a way to get a detailed population analysis in Golly for a rule with multiple states?)
See histogram.py at http://www.conwaylife.com/scripts/
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

paultsui
Posts: 8
Joined: February 25th, 2012, 1:29 pm

Re: The Chaotic Behaviour of different rules

Post by paultsui » March 14th, 2012, 3:34 am

I read the paper by Langton recently:
http://informatics.indiana.edu/larryy/a ... fChaos.pdf

In the paper, he suggests to use a parameter labelled as λ to measure the chaotic-ness of a cellular automaton rule. In a two states CA, λ is given by 1-n/2^N, where N is number of neighbours and n is number of transitions to the quiescent state in the rule table. (look at p.14 of the paper.)

He suggests that a highly ordered system will have λ = 0 while a highly chaotic system will have λ = 1, therefore forms a parameter to measure the chaotic-ness of the system.

When I plug in the numbers, I found Conway's game of life have λ = 0.273 (140/512), which makes sense as the game is on the edge of chaos. However, according to the definition of λ, it seems that B1/S23 and B7/S78 rules will have the same value of λ - suggesting them to be of the same order of chaotic-ness. However, it is obvious that B1/S23 is much more chaotic!

Can anyone tell me where did my logic go wrong? :shock:

User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: The Chaotic Behaviour of different rules

Post by Andrew » March 14th, 2012, 9:19 am

paultsui wrote:Can anyone tell me where did my logic go wrong?
For starters, I think you've calculated λ incorrectly for B1/S23 and B7/S78. I get 0.180 and 0.033 respectively for those rules (but your value for B3/S23 is correct). I used this script:

Code: Select all

# Calculate Langton's lambda parameter (the probability that a cell is alive
# in the next generation) for the current rule.  For more details see:
# http://informatics.indiana.edu/larryy/al4ai/papers/Langton.EdgeOfChaos.pdf
# Author: Andrew Trevorrow (andrew@trevorrow.com), March 2012.

import golly as g
from math import factorial as fac

# get current rule, removing any topology suffix
rule = g.getrule().split(":")[0]

# this script only handle rules of the form B.../S... or a Generations rule
if g.getalgo() == "Generations":
    survivors, births, notused = rule.split("/")
    # set neighborhood size, including central cell
    N = 9
elif rule.startswith("B") and rule.find("/S") >= 0:
    births, survivors = rule.split("/")
    # set neighborhood size, including central cell
    N = 9
    if rule[len(rule)-1] == 'H': N = 7    # hexagonal
    if rule[len(rule)-1] == 'V': N = 5    # von Neumann
else:
    g.exit("Current rule must be of form B.../S... or use the Generations algorithm.")

bcount = 0
for i in xrange(N):
    if str(i) in births:
        bcount += fac(N-1) / (fac(i) * fac(N-1-i))

scount = 0
for i in xrange(N):
    if str(i) in survivors:
        scount += fac(N-1) / (fac(i) * fac(N-1-i))

L = float(bcount + scount) / float(g.numstates()**N)

g.show("Langton's lambda for %s = %.6f" % (rule, L))
Note that at the end of section 2.4 Langton says λ only discriminates well between dynamical regimes for large values of K and N. Frankly I've got my doubts about that. It certainly doesn't have much predictive power for K=2 and N=9:

Code: Select all

B2            .055  (Seeds)
B3/S23        .273  (Life)
B36/S23       .328  (HighLife)
B367/S125678  .432  (Slow Blob)
B35678/S5678  .473  (Diamoeba)
B34/S34       .492  (3-4 Life)
B1357/S1357   .500  (Replicator)
Don't be too disappointed. Many moons ago I also stumbled across Langton's parameter and got all excited, only to be taken to task by Conway himself for even thinking that such a simple parameter could somehow help find interesting rules (however you might define "interesting").
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

User avatar
Wojowu
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: The Chaotic Behaviour of different rules

Post by Wojowu » March 14th, 2012, 12:31 pm

Maybe some possibility of improving results is measuring each of transition rules in such way, that n in Langton's measurement is defined as sum of some x for each transition rule, which is defined as 1/(number of living neighbors) if resulting cell lives and 0 otherwise
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?

paultsui
Posts: 8
Joined: February 25th, 2012, 1:29 pm

Re: The Chaotic Behaviour of different rules

Post by paultsui » March 14th, 2012, 11:23 pm

I agree with Wojowu's idea - I think a weighted sum would make the parameter (much) better.
Langton's parameter is defined under the premise that the occurrence of 8 cells neighbourhood is as frequent as 1 cell neighbourhood. Obviously it is much often to see 1 cell neighbourhood in life-like CA though! Intuitively one wants to give higher weight to those with less neighbourhoods in the rule table.

The problem is: is there a systemic way to determine what the weighting factors should be?

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: The Chaotic Behaviour of different rules

Post by Tropylium » March 21st, 2012, 3:31 pm

paultsui wrote:I agree with Wojowu's idea - I think a weighted sum would make the parameter (much) better.
Langton's parameter is defined under the premise that the occurrence of 8 cells neighbourhood is as frequent as 1 cell neighbourhood. Obviously it is much often to see 1 cell neighbourhood in life-like CA though! Intuitively one wants to give higher weight to those with less neighbourhoods in the rule table.
I think you're making an assumption here that Langton is not — that we start with a finite pattern set in vacuum. If we instead start with an infinite or periodic random configuration of 2 states, having 8 live neighbors is going to be equally likely as having 1 live neighbor.

Also although something like Seeds or 3-4 Life is explosive if run in vacuum, in a small torus patterns do resolve after some time (a couple kgens in 10×10; longer in bigger ones but still after only a relatively tiny walk thru the phase space of size 2ᵐⁿ), either dying out entirely or leaving a few small objects, so they still in a sense count as type II CA by the λ measure. A "true" chaotic rule like let's say B245/S1468, does no such thing.

I think Langton also avoids imposing a condition of totalism either (at least I see no mention of such thing); "four cells in an L shape" and "four cells in a tub shape" would count as different (Moore) neighborhoods. This has the effect that environments allowing eg. B2 are rather fewer than B4, and the more so, the more states there are (already with 2 live states, 8-cell neighborhoods become the most numerous class). Thus, an exploding-into-void low-λ rule like Seeds is actually a highly exceptional case. Even with the lumping of many different environments into a single neighbor count in Life-like CA, this is apparent — B1/S and B2/S are the only chaotic-behavior rules with a single birth or survival condition, all the others stabilize or die out fast.

It seems Langton's parameter is good for is locating chunks of rulespace where it is very easy to find interesting structures; it says not too much about where less obvious discoveries may lie waiting. I think most rules in Andrew's list would count as exceptional for their λ region (or indeed among the entire space of Life-like CA) — possibly with the exception of 3-4 Life, which actually seems like a fairly typical exploding B34 rule, quite similar to eg. B34/S23 and B34/S24.

User avatar
Wojowu
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: The Chaotic Behaviour of different rules

Post by Wojowu » March 21st, 2012, 4:41 pm

Tropylium wrote:I think you're making an assumption here that Langton is not — that we start with a finite pattern set in vacuum. If we instead start with an infinite or periodic random configuration of 2 states, having 8 live neighbors is going to be equally likely as having 1 live neighbor.
Sorry, but I think you are wrong. Imagine one cell in infinite random space. It is 50% of being on. Take its N (north) neighbor. It also has 50% of being white. NE is having 50% chance for this, etc. So it can be analogy to 9 fair coin tosses. It is chance 1/512 for 0 or 9 neighbors, 9/512 for 1 or 8 neighbors... As far as I know it's Gaussian distribution. But it is easy to see on some random Golly pattern (considering only interior) that 50% soups have much more 4 neighbor cells than 8 neighbor ones.
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: The Chaotic Behaviour of different rules

Post by Tropylium » March 21st, 2012, 7:23 pm

Wojowu wrote:Sorry, but I think you are wrong (…)
Gah. Yeah, I meant that the odds of 1 live neighbor is equal to *7* live ones (and 0 to 8).

With multi-state soups, Golly seems to generate them with a live density of 50% rather than equal parts of every sate, so they're going to look sparser than they "should".

---

If the aim is locating "engineerable" rules (in 2D), one obvious (necessary, but not always sufficient) condition is that patterns must be able to grow beyond their bounds. This actually gets even easier with non-totalistic rules (if we're considering the "objects in vacuum" paradigm), as only 7 Moore neighborhoods can lead to growth beyond bounds:
• 1 neighbor orthogonally
• 1 neighbor diagonally
• 2 neighbors that are adjacent orthogonally
• 2 neighbors that are adjacent diagonally
• 2 neighbors, orthogonally separated by 1 cell
• 3 neighbors in an L shape
• 3 neighbors in a line
This seems like a nearly orthogonal criterion to the definition of λ; it's easy to pick a whole bunch of birth/survival conditions without stumbling on one of these specific ones.

Moreover: in 2-state CA, the first almost always and the 2nd always leads to explosive growth, so they're not of much use. The 4th and 6th only allow growth outside diagonal bounds; the 5th and 7th can only allow growth beyond orthogonal bounds. So we at least need one from both of these pairs, or the third.

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: The Chaotic Behaviour of different rules

Post by Tropylium » March 24th, 2012, 11:37 pm

Another feature of λ is that we can define it for every state of the CA — there is no requirement for which to consider "quiescent". A corollary that I hope is easy to see from this is that maximum chaoticity would not fall at exactly λ = 1, but rather λ = 1–1/N, if there are N states.

If the reductive/chaotic phase transition would still fall around the mid-point of the range, then for a 2-state CA the predicted hotspot would actually be 0.25, which seems to square rather well with the λ value for Life. OTOH most other "well-engineerable" rules — 2x2, HighLife, Move, Day & Night — score higher rather than lower…

Post Reply