Home  •  LifeWiki  •  Forums  •  Download Golly

Use Smoothiness to classify rules

For discussion of other cellular automata.

Re: Use Smoothiness to classify rules

Hi guys,

I made another attempt to classify rulespace by calculating spatial mutual information. The idea is that if entangling is present, neighboring cells should assciates with each other by sharing mutual information. During the calculation, I assign a new state to each cell according to its 3-gen history (2^3=8 possible states). Then I calclulate the mutual info between 2 neighboring cells (1 on the left, 1 on the right) at each step. The entropy at each step is also included. An additional input entropy is recorded to further resolve the rulespace.

From the result, it's pretty clear that complex rules exhibit an excess of spatial mutual information.

## matlab 3d figure
Attachments
mi_rulespace_2d.jpg (35.53 KiB) Viewed 7327 times
mi_rulespace.jpg (33.33 KiB) Viewed 7327 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

shouldsee wrote:The idea is that if entangling is present, neighboring cells should assciates with each other by sharing mutual information.

There seems to be some issues on biphasic rules like this:

`x = 60, y = 60, rule = B4678/S35678:T60,6013bo3b22o\$9bob28o\$7bob30o\$5bob33o\$2b38o\$42o5b7o2b2obo\$43o2b15o\$60o\$60o\$60o\$60o\$60o\$60o\$60o\$60o\$60o\$60o\$47obo2bobobob3o\$45o13b2o\$42obo15bo\$40o19bo\$ob38o\$4b33obo\$6b28obo\$6b24ob2o\$7b2ob19o\$11b17o\$13bob13o\$16b11o\$20b3o4\$53b4o2bo\$o51b8o\$3o48b9o\$3o46bob9o\$3o44bob11o\$4o43b13o\$4o40b16o\$6o37b17o\$6o37b17o\$8o33b19o\$8o4bo27b20o\$15o25b20o\$15ob3o18bob21o\$23o13b24o\$24o11b25o\$24o11b25o\$23o11b26o\$15ob2o2b2o11b27o\$10o22b28o\$obobobob2o17b2o2b28o\$25b26ob3o\$23b23ob3o\$22b23o\$22b23o\$20b24o\$20b21obo\$18b22o!`

The entropy for each cell is 1 bit. Since there is strong "entangling", the mutual information for two adjacent cells is also ≈1 bit. Such data may lead to results that the rule is somewhat complex, but in fact, it's just a voter rule.

The issue also apply to B0 rules:
`x = 60, y = 60, rule = B014/S2:T60,6020b3o\$20b4obo\$19b7o\$13b2o3b9o\$17b12o\$15b15o4bo\$15b15ob3o2bo\$15b17ob4o\$14b25o14b2o\$14b24o\$13b26obo11b2o\$12b29obo8b2o\$12b31o7b4o\$10b34o5b3obo\$9bob41obo\$8b44obo\$9b43obo\$2bo5b45o3bo\$3o4b27ob10obo3b4o2b4o\$32obo2bob2ob3o8b8o\$31o9b3o10b7o\$30o11bo11b7o\$29o21bob8o\$28o21b11o\$29o21b10o\$29o21b10o\$28o22b10o\$28o11b2o9b10o\$29o9b3o9b10o\$26obo11b4o7b10o\$25o12bob3o7b11o\$25obo9bob5o8b9o\$26o8bo2b5o9b9o\$27o5bob7obo6b11o\$28o5b9o3bo4b10o\$45obo2b11o\$45o3b12o\$47ob12o\$45o2b13o\$60o\$60o\$19o2b39o\$7ob10o4b38o\$5ob2ob8o6b2ob34o\$6o4b8o10b32o\$3o6b8o12b9o2b20o\$obo8b7o10b9o4b19o\$11b8o11b6o5b18o\$12b7o11b5o5b18o\$12b9o9bob2o6b19o\$12b8o13bo6b17o\$11b10o19b17o\$11b10o18b17o\$12b11o18b15o\$12b10o19bob13o\$12b11o19b15o\$12b11o21b7o4bo\$13b10o23b4o\$13b3ob6o24bo\$19b4o!`
Still drifting.
Bullet51

Posts: 529
Joined: July 21st, 2014, 4:35 am

Re: Use Smoothiness to classify rules

Bullet51 wrote:The rule B378S126 may be a good sample to test. How many states are there near Bunc=0?

Good news. With my newest criteria, I have successfully detected B3578/S126 as complex rule.

Bullet51 wrote:The entropy for each cell is 1 bit. Since there is strong "entangling", the mutual information for two adjacent cells is also ≈1 bit. Such data may lead to results that the rule is somewhat complex, but in fact, it's just a voter rule.

I agree that the spatial domain of complex behaviour is an important factor. We are naturally interested in glider-behavior on a blank background, and it's true that complex behavior on a ring is not as interesting.

Hi guys,

I want to announce my most recent attempt. Instead of calculating mutual information between spatial neighbors, this time I measured mutual information between neighbors in time, i.e. between history states of a cell. The input NH of each cell is recorded over time to represent a random variable. H(NH_0) is the input entropy of current universe. H(NH_-4) is the entropy of 4 steps back. H(NH_0,NH_-4) is the joint entropy between distribution of current universe and 4 steps earlier. I(NH_0,NH_-4) is deduced to be H(NH_0)+H(NH_-4)-H(NH_0,NH_-4). An lag of 4 is taken here to reduce the periodicity in the statistics.

This mutual information comes out to be a better measure than the last one and achieve a better resolution. I plotted (H(NH_0),I(NH_0,NH_-4)) for each soup evolution. To extract stats, mean, total variance and covariance are calculated. During the final visualisation of rulespace, mean and covariance is plotted.

It can be seen clearly from the result that the complex rules occupy a region with reduced temporal mutual information (tMI_input), and a small covariance. This is consistent with the fact that successive steps of complex rules are usually distinguishable, while those of chaotic rules are indistinguishable (contains the same information over and over). A small covariance implies that H_input and tMI_input are decoupled/ some of them is too stable to show any coupling.

Apart from the complex rules, other regions are also indicative of the behavior of corresponding rules. The line of H=I implies H is completely redundant and no new information is generated over time, i.e. the information content decays over time. The chaotic core near H=4,I=0 corresponds to that no information is passed on over time, all information are completely new. Under such definition, complex rules pass on some existing information to the next generation, while generating some novel information as well.

Other features include a curve on the H=I plane, and a dense region connecting chaotic core to H=I plane. I can't interpret any of them yet.

EDIT: The second feature is seemingly related to the fact that emergent behavior is more abundant on an irregular background than a regular background.
Attachments
tMI_rulespace.jpg (63.8 KiB) Viewed 7279 times
all points here has a Covariance<0.25
tMI_rulespace_2d_thresholded.jpg (64.32 KiB) Viewed 7279 times
tMI_rulespace_2d.jpg (75.77 KiB) Viewed 7279 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

There seems to be some issue on the cov statistic: Different H-I behavior may yield similar cov values.
H-I graph of B3/S125
6.png (4.06 KiB) Viewed 7255 times

H-I graph of B3/S2368
B3S2368.png (4.94 KiB) Viewed 7255 times

Is there any statistics that can capture the non-linear behavior of the H-I graphs?
Still drifting.
Bullet51

Posts: 529
Joined: July 21st, 2014, 4:35 am

Re: Use Smoothiness to classify rules

Bullet51 wrote:There seems to be some issue on the cov statistic: Different H-I behavior may yield similar cov values.
Is there any statistics that can capture the non-linear behavior of the H-I graphs?

It's indeed a pain-in-the-ass to extract stats from a phase diagram.

First, you can try calculate total variance (trace of covariance matrix) along-side covariance. Secondly, you can apply a random walk model and yield some statistics from it. One way it to plot a return map according to H-I phase diagram, which would reflect the volume experienced by the trajectory.

On the other hand, I did try to apply MI as a distance between 2 different universe. This method is capable of resolving some linear/near-linear oscillation, but is very prone to noise.

I want to mention the first figure specifically. It's clear how the ring behavior masked the along-side complex behaviour in the return map/distance matrix.
Attachments
B012348S0236_soup57.jpg (115.58 KiB) Viewed 7237 times
B3S23 _soup1.jpg (130.54 KiB) Viewed 7245 times
B012S1256_soup5.jpg (111.35 KiB) Viewed 7245 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

Here are some snapshots of spatial mutual information. Each point is associated with a 2-d shift vector, and its color determined by the value of the mutual information associated. By summing the value near vector(0,0), one can estimate the local entangling at any instantaneous moment.

The problem of making such plot in 3D is that time is not bounded, and one can not easily shift a time-space pattern to itself.

Point (0,0) is manually centred in the plots.
Attachments
B3S23 _soup3.jpg (120.01 KiB) Viewed 7211 times
B0123456S0246_soup30.jpg (161.18 KiB) Viewed 7211 times
B012S1256_soup1.jpg (173.16 KiB) Viewed 7211 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

The H and I time series differ much from convectional time series, mainly from the auto-correlation profile:
Sample autocorrelation for B37S23
2.png (5.26 KiB) Viewed 7183 times

Sample autocorrelation for B3S023
3.png (3.64 KiB) Viewed 7183 times
Still drifting.
Bullet51

Posts: 529
Joined: July 21st, 2014, 4:35 am

Re: Use Smoothiness to classify rules

Bullet51 wrote:The H and I time series differ much from convectional time series, mainly from the auto-correlation profile:
The attachment 2.png is no longer available

The attachment 3.png is no longer available

Indeed. The perservation of information is a central topic in CA.

I have recently develop the idea of "vicinity counting". That is, counting every pair of cells separated by a spatial-temporal distance of 1. Calculate this entropy to be H_vic. The mutual info follows as 2*H_x-H_vic. By taking MI of a spatial-temporal block,the dynamics is better analysed.

Edit: Vincinty counting can be done with or without directionality. For every base direction, there are two postivity. We can either only count along one direction of each vector (with direction), or along both (without direction).
Attachments
vic_rulespace_2d.jpg (72.15 KiB) Viewed 7180 times
vic_rulespace.jpg (74.09 KiB) Viewed 7180 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Divergence of trajectories is dependent on the initial densi

The divergence here is visualised by computing std(H_input) over a set/collection of configurations. The higher the std, the more diverged is this set.(I have just started measure theory so I am not sure whether this would count as a measure over this set). Here, I recursively take the divergence of a 500-point sample after each step of mapping, which started as a random collection with a fixed density p0.

One can choose to normalise the divergence by the mean(H_input) of the set. This needs more discussion.

From preliminary results, this measurish variable is capable of characterising the dynamics.

PS: The colormap of the pictures are not normalised yet.
PPS: The previous plots appear to be faulty. They are NOT fully fixed yet.
Attachments
B024S0123_soup19.jpg (130.91 KiB) Viewed 7076 times
B3S23_soup91.jpg (135.9 KiB) Viewed 7076 times
B15S23478 _soup19.jpg (128.2 KiB) Viewed 7076 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

I am curious how the rule below fits into the classification scheme you have been working on here.

There are no known gliders but it seems possible that there are gliders of a sort on some periodic tiling.

`x = 90, y = 90, rule = B345678/S012678:T90,90obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$44o2b44o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o\$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo\$90o!`
The latest version of the 5S Project contains over 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1209
Joined: August 9th, 2013, 12:45 am

Re: Use Smoothiness to classify rules

wildmyron wrote:I am curious how the rule below fits into the classification scheme you have been working on here.

There are no known gliders but it seems possible that there are gliders of a sort on some periodic tiling.

HI wildmyron,

Unfortunately I can't remember exactly how I undertook the classification earlier on. I remember heavily relied on the notion of mutual information which I had just touched upon. The algorithm was largely based on statistical inference and I am not quite sure whether they were really valid.

I might not able to re-classify them under the earlier notation (since I was hugely disappointed by them after realised that I can be quite biased when interpreting my result). The pleasure I had was limited to the discovery of new exciting rules containing gliders, but it was more like a manual annotation rather than a machine one. Thus, I regret to tell you I might not be able to redo the classification under the earlier framework (because it was too, too messy from my current perspective).

Apologies for not being helpful.
Feng
Last edited by shouldsee on February 13th, 2017, 9:01 pm, edited 1 time in total.
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

Meanwhile, I want to discuss some recent ideas I was testing on a ECA exploratory toolkit: expt branch

The story began with I spent some good time learning density matrix renormalisation group(DMRG) as posted by Nishino in 1995. I was particularly interested in its application to 2D-ising model. DMRG is fascinating in that it can deal with an infinite system with good approximation. But to me, the biggest gift is to become familiar with density matrix(DM) as a linear algebraic object. Importantly, DMRG uses an earlier technique called transfer matrix as introduced by Onsager, which allows one express partition function as a product of matrixes and thus a big matrix itself. Yvan pointed out that the eigenvector of a transfer matrix correspond to a stationary distribution (which hugely clarify my confusion).

I then tried to construct some statistical model as a layered state vectors, where adjacent layer interacts with an energy defined by how likely the lower layer is the image of higher layer under the projection of a cellular automata. The larger the difference, the higher the energy, and less likely the configuration would appear. A stringency constant was introduced (reciprocal of temperature, denoted K), As K->+Inf, only the trajectory produced by the specified CA will have a non-zero probability. The model respond to K in some obscured fashion. Strangely, the transfer matrix give a uniform distribution for any K. This means at any layer, no preference is given to any particular state. This is reasonable given that the partition for any layer is a sum over all possible choices of the lower layer, and this result of such operation does not depend on the identity of the higher layer. Well, that means we can't simply apply TM technique in this fashion.

During the process, I tried to marginalise over the higher layer and compute the entropy of the resultant distribution. Unfortunately back then I did not have reliable rule-generator. (Mostly of times I believed I was investigating rule 172 only to realise it actually is rule 110), so I have yet to test the usefulness of this entropy. The observation is this entropy does depend on K, unlike the stationary TM eigenvector.

More ideas came to me during the process:
1. Ising model effectively uses hamming distance as energy function. What would happen if we replace it with mutual information instead?

Accidentally, while I was searching for new ideas, I bumped into Derrida plot again. (I met it earlier in DDLab, but didn't understand it since the manual wasn't clear). This time with some concentration I was able to use it to classify 1D ECA to some extent. I hope this can be readily generalised to 2D. It's important to note these plots aren't strict Derrida plots. Derrida plots take average along the second dimension (marginalised), while here the whole joint distribution is displayed. In such way, more information is kept.

Here are some demos from the tool box. The observation is that, if there is strong correlation in the lower plot, then the underlying CA can't afford complex dynamics. The problem remains: a chaotic rule can't be distinguished from a complex rule. I plan to resolve the issue by abstracting a heatmap into a single number, then use this distance/correlation function to visualise the auto-correlation profile of the distance set.

Last edited by shouldsee on February 14th, 2017, 7:11 pm, edited 1 time in total.
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

I've manged to adapt the aforementioned methodology, namely replacing the joint distribution with a correlation value. In this way, a metric is defined between two timepoints/horizons |t_1,t_2|=1-corr(hamm(t_1),hamm(t_2)), where hamm(t) is random variable denoting the hamming distance between 2 trajectories at time t.

I've managed to calculate an atlas of such plot for 256 ECA rules. Please see CorrProfile_ECA

I've also hand-picked chaotic/complex rules according to the profile (s for short dynamics, ss for supershort dynamics):
`253032s40s41455457s607586899096ss97101102105106107110120121122s124126s129s135136s137146s147149150151s153160s161s165169182s183s192ss193195225`

demos:

shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

shouldsee wrote:
wildmyron wrote:I am curious how the rule below fits into the classification scheme you have been working on here.

There are no known gliders but it seems possible that there are gliders of a sort on some periodic tiling.

HI wildmyron,

Unfortunately I can't remember exactly how I undertook the classification earlier on. I remember heavily relied on the notion of mutual information which I had just touched upon. The algorithm was largely based on statistical inference and I am not quite sure whether they were really valid.

I might not able to re-classify them under the earlier notation (since I was hugely disappointed by them after realised that I can be quite biased when interpreting my result). The pleasure I had was limited to the discovery of new exciting rules containing gliders, but it was more like a manual annotation rather than a machine one. Thus, I regret to tell you I might not be able to redo the classification under the earlier framework (because it was too, too messy from my current perspective).

Apologies for not being helpful.
Feng

No problem,

I mentioned it as a curiousity as the rule seemed to exhibit some similar dynamics to other rules you are exploring, but I have no need for an answer to the question I posed. Thank you for responding.

Good luck with your ECA exploration and analysis
The latest version of the 5S Project contains over 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1209
Joined: August 9th, 2013, 12:45 am

Re: Use Smoothiness to classify rules

shouldsee wrote:
Bullet51 wrote:
And how on earth did you find such amazing rules?

Thank you for you appreciation. The short answer is: I don't know. The discovery of checkerlife is merely an accident: I was trying to stabilise [B12e3eijkr4ejqrtwz5cn6-ce7e/S01c2in3aejkr4ejkqtyz5ckq6-a], and attempted various modifications, and some mod give up to puffers and guns.

The discovery of [B12e3eijkr4ejqrtwz5cn6-ce7e/S01c2in3aejkr4ejkqtyz5ckq6-a], however, is due to my ongoing screening of non-totalistic rules. The screen is semi-automated: I used a matlab script to generate random rules and plot their dynamics into a pairwise distance map (aka profile), along with its space-time trajectory beside it. These rules are then ranked according to their profiles (specifically, the average of the profile plot). Then I manually inspected the top ranked rules, with some criteria. Usually the most interesting rules are of top 50-300 of each 10000 rules, but it's largely empirical (As long as the profile is not extreme, there is always space for interesting dynamics). I would say there is certain logic behind this method but it's not formally established yet.

The script is included in the expt branch of CA_tfmat repository, it current supports both non-totalistic rules, totalistic rules, ECA and coupled logistic maps. The major script is derrida_general.m. Generate an example through samplesys.m to get familair with the idea. I also included manual annotation under CA_tfmat/Annotations.

Another important factor to consider is the vast rulespace of the non-totalistic rules. Whereas totalistic rulespace has 2^18 possibilities, nt-rules (nt for non-totalistic) has 2^102 possibilities. (1d semi-totalistic has 2^4 possibilities). Thus it's not too surprising that nt-rules exhibit a richer diversity than T-rules. (From another perspective, NT-rules are subject to less symmetry than T-rules).

Coming back to the methodology: The general derrida plot (GDP) is intimately related to the concept of the attractor basin. The GDP contained information about deviation at 2 time points: whether two closely related configs diverge, or two diverged configs coalesce. These relations can be treated statistically, and the observation is that the covaraince between deviation_t1 and deviation_t2 is an important indicator of the dynamics. The GDP merely listed the covariance for every (t1,t2) combination. Consider a rule with a strong early-onset attractor, then we will see an early intensive covariant region on GDP. If the rule project the configs into a small number of basins, the GDP will show an early plateau. There is much to reason about GDP, and I think it might even be possible to extract information about the dominant attractor basin from the randomly generated ensemble. Interestingly, if you start with a random soup in checkerlife, the interesting glider dynamics is absent. On one hand, one can argue that GDP captures more information about a rule than glider-based criteria do. On the other hand, GDP seem to diverge from my perception of dynamics -- two dyanmically different rule might show a similar GDP (Although this similarity is often limited to coarse level. i.e. if one expand the GDP into distribution heatmap, then there is still perceviable difference, but that precludes efficient ranking of rules).

Somehow I feel it's not appropriate to rank rules in a linear fashion. Instead, a hierarchial organisation maybe more appropriate. Take checkerlife as an example, there are 102 possible mutations one can make. Some mutations abolish the dynamics completely. while others only incur minor changes. Personally I am mostly intrigued by the self-organised gliders from randomness, but once the glider became somehow replicative/regenerative, it would fill up the space too rapidly to result in a gaseous phase. How can we describe these relations with the language of attractor basins? I don't know. But we can at least figure out some incremental changes along a mutation path. More specifically, the hamming distance between 2 given rulestring is distorted. Starting from B3/S23, B23/S23 changes the dynamics greatly with 1 bit fliped, whereas B368/S238 endures 3 fliped bits but bear greatly similarity to B3/S23. Thus it'd be great if we can find a universal way to quantify the dynamical difference between 2 given rules given their rulestring, or at least spot the important bits of a given rulestring. (obviously not all 102bits in a nt-rule is important)

The kind of image generated is like this (the color might be inverted depending on how the distance is defined, d=1-corr(x,y) or d=cov(x,y))

Additionally, I wrote a Chinese blog with some nice graphics embedded to illustrate the idea of generalised derrida plot.

I want to discuss yet another piece of experience I had: the easiest way to find a novel interesting CA is not with any program, but human brain. It's incredibly difficult to write a automated evaluation function, but it's incredibly easy to look at the dynamics and say: "Hmm, I think this is amazing". Take some boring rule, mutate the bits randomly, and there is a good chance you find a rule with spontaneous gliders in 10 iterations. The problem with NT-rule/T-rule is that, the rulespace is simply too large to be completely searched with human brain, and some complex rules posess a larger territory while some complex rules are very stringent about mutations.

Essential Elements for a glider:
1. A self-sustainable stable background/agar. (All 0's, zebrastrip, checkerboard).
2. A transmitting pattern.

General descriptor for a rule:
1. Behavior from a random soup:
Does the evolution leaves debris/still lives behind it?
Does the evolution leaves dislocation/defects behind it?
Is the evolution sparky?
Does the evolution create correlation between space?
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

An incomplete ATLAS of outer semi-totalistic rulespacem, with TCA_id indexed. Rules are grouped according to similarity in dynamics.
Generated with dstgraph.m in CA_tfmat/expt

PS: What's the best file format to exchange graph structure?

tca_atlas.jpg (218.71 KiB) Viewed 6428 times
Attachments
tca_atlas.fig.tar.gz
matlab fig in archieve
(113.44 KiB) Downloaded 108 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

shouldsee wrote:PS: What's the best file format to exchange graph structure?

Graphviz is fairly universal (the file format, not the program), but there's a variety of other formats as well. Here's an overview from the Gephi website.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1025
Joined: July 27th, 2015, 2:06 pm

Re: Use Smoothiness to classify rules

visulisation with vis.js
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

Snapshot of rules similar to B3/S23 (6152)
Edge with similarity higher than exp(-4) is retained.

The applet can be found at here hi-def image at here
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

Guys, I'm detecting something special about 6152/B3_S23.
Firstly, adding B8 or S8 largely perserves its dynamic.
ie B3_S23 ~ B3_S238 ~ B38_S23 ~ B38S238

Secondly, these four rules are susceptible to B7 or S7 similarly. In other words, B3_S237 is slightly different from B3_S23, so is other 2 rules. And B3_S237's dynamics is also largely perserved when subject to B8 | S8.

Notably, B7|S7 changes the dynamics more than B8|S8.
Thus, I here coin B8|S8 as group A mutation, B7|S7 as group B mutation. And B3_S23 family has a hierarchial structure of "a2b2". This can be visualised in the following group plot. Thicker edges correspond to more similar dynamics.
6152_a2b2_phd.png (154.56 KiB) Viewed 6350 times

When physics engine of vis.js is enabled, the graph relax to the following shape
6152_a2b2_ph.png (192.74 KiB) Viewed 6350 times

Intriguingly, B3_S23 family is not the only rule family exhibit such phenomena. Other instances are available, like 131764, 185845, 193384. Unfortunately, their dynamics does not coincide with 6152/B3_S23. Nevertheless, such structure should deserve a deeper explanation.
193384_a2b2_phd.png (197.62 KiB) Viewed 6350 times

Hierarchial structures other than a2b2 are also available, such as a1b3(195827) a1*(235503).
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

I have updated my git repository at shouldsee/CA_tfmat (expt branch), adding densi_fluct.m using density fluctuation to probe complex dynamics
it should be fairly straight-forward to run profile_script.m and profile_script_nt.m (You also need to define \$repos in your environment variable to direct the output of pictures)
Accompanied is some examples from densi fluct. Note the algorithm is not particularly good at identifying glider, but it does give you sparky rules. The fluctuating rules are particularly intriguing.

Much more can be done about this algorithm, and it is superior to any of my previous implementation.

For example this one has 3 meta-stable dynamics.
`x = 172, y = 119, rule = B12a3en4cintwyz5aejky6-in7c8/S1e2cin3-akr4-eijkr5eijry6-a78b2o4b2o4b2o2b4obobob2obob2ob2obobob2ob2obob2ob2ob2ob2obobob2ob4obob6obob2ob2obobob2obobob2obobobobobob6obobobobobob2ob2ob6obobobobobobobobobobobo5b2o\$bo2b3o3bobo2bobo14bobo7bobo4bobobo2bobo7b3o7bo3bo4b3o6b2o20b2o9bo3b2o2b2o5bo5bo3bo3bo3bo2bo7bo\$obob3obobo2b2obobo5b3obo2bobob2obob2obob2o2bobobobobob2o3b4o4b3obobo4bob3obo3bo2bo3b4o8b2ob4ob2o4b3o2bob2ob6o5b3ob3ob3ob3obob3obo\$2ob6ob2o5b3o3b2obob2obobo2b2obo2b3o3bobo5b3o3bobobobob2o5bo7b3obo4b2ob2ob4ob2o4b2o6bobo2b5ob3o2bo5b4ob6o5b3o2bobobo2b3o\$2bobobob2o2bo5bo2b2ob2obobobo3bo2b4obob3obo2b2o3bob2o2bo2b2ob2o2bo2b7o2bo4bob5o4b2o5b3o4bo2bo2b2ob3o2bobob2ob2o4bo4b6obo6bobo3bobo\$2bo2bobo2b2o2b2obob2obo2b2obobo2b2ob3ob6o2bobob2ob3o3b2o4b6obo2bobobob2obo2bobo2b3obob3o6bob2o2b2o2b2ob3o4b4ob2o2bo2bo2bobobobo2bo2bo3bobobobob4o\$2bobob4o2bo2bobo3bobobobob5ob2ob4ob8ob2obobob2o4bob2obob5obobobo2bo2bo3b2obob3ob4ob3obob3ob2obobo3bo3bo2bobobo3bob4ob5o3bobobobobo2bob2o\$bo2bo2bobo2b3o3b3obobob2ob2obo3b7o2bobobobobobo2bob2ob2ob4ob2o2bob5obo6b2o6b2ob2obob2obo2b4o2bobobobo3b2ob4obo2bob4obob2o2b5obobobob3o2bobo\$obobo3b3ob2obob5obob3ob3obob6o3b4o2bo2b4ob2ob6obobob3ob7ob3obobobobobob4obobo2b3obobo2bob3ob2o2b4obobobob3ob3o3bobob2ob3obobob5o\$obob4ob2ob2ob3obob2ob3ob3ob2ob2ob2o3b5obo3bob2ob5ob2o2b4obob9obob4obo2bobobo2bobobo2b3obobo2bobobobobobobob3obo2bob5o2b4ob4ob5ob3o2bobo\$obo2bo2bob3obob2o3b8o2bob8o2b5ob2o3b6obob2o2bob4ob9obobo3bobobobob6ob4obobob4obob2ob4ob3o3b4obobob5obob2ob3obobobob2o\$4ob11ob4obob2o3bob9o3bob4obo2b2o3bobobobob3obob10obobob2o4bobob4obobobo2bob6obobo2b2o2bo2bo2b5obob9obobo2bobobobobo3b2obo\$bobob3ob9ob8ob4ob2obo2b2ob2o5b11obob3obo2b2obobo2bobobobob2ob2o2b2obob4obob4obobob2o2b3o3bobob2obobob6obobobobob4obob3obo3b3o\$2bobo4b4o2b3obo2b3obob2obob4ob3o2b2o2bob3ob2obobob5obob2ob2ob4obobobob4o3b2obob8obob2ob2obob2o2bo2b4ob5o2bobobob5obobo2bobobobobob4o5bo\$o5bo2b2ob4o2bobob2obobo2bob3ob2obobob2o2bobobob3obobob5obo4bo3bobobobobobobobo3bobobo4bobo2bobobobo2b2obobobob2obob10obobobob4obobo2bobobob4obo\$4o3b4obob2ob3ob2o3bobo2bobob2ob3obo3bo2b4o3bobobobobobobobobob2obobobobob5o2bo2b3ob2obobo2bob7ob5o2b5o2b3obobob5obob2obobobob3o2b5o2bo2bo\$o2b2obobob2obo2bob10ob2obob2ob3obob3obobobobobobob5obobobo4bobob3ob7obob2ob2obob2obo2bo2b2obobobobobob4obob14obob2obobobob4obo2bobo2bo\$o5b2ob4ob4obobobo2bobo4b3o2b3obobobob5ob3obobobobo3bobobo2bobobo3bobo2b2o2bobobo3bob5o2b10obobobob2o3bobobo2bob3o3bobob5obobo3bo3bobo2bo\$2bo2b3ob5o2b3ob4ob3ob9obob3obobob5o3b8ob2obob4obob3obobob3o2b3ob3o2b2o4b4obo2bob3ob2obob3o2bob8ob2o2bob2ob2ob2obob3o2bo\$obobob3o2b4o3bo2b2ob3obo2bob2ob2ob5o2bob7obobobo2bobobo2b3obob4obob4obo3bob4ob3ob4obob2o4b3obobo3bobo2bobobobo2bob5o2bobobo5bo2b2o7bo\$4b4ob3ob2ob16o3bobobobobobob2ob3o2bob3ob6obo2b3o3bo2bobo3b5ob9o2b5obo2b6obobob2o2b13obobobo2bob2obo2b3ob7o\$obob2ob2ob2o6b10ob3o2bob9o2b3obob6obo2bobobob2o2b2obob4ob2o2b2ob3ob13ob2ob3obo2bobobo4b3obobobob4obo2bobobob5obob2ob3o3b2obo\$2b6o4b6ob9ob2ob4obobobobo2bobo3bo3b2ob3o2bobob2o2b2o3b2ob4obobobo2b13obob2ob3ob3obobob15obob8obo3bobob4o2b2o2bo\$o3b3ob21obob2o2bob6obob2obobo3b2ob3o5bob5obob3o3b6obob14o2b8o2bobobo2b3obob3obo2b4obob3obob7obobobo3bobobo\$2o3bob3ob4ob11ob2ob3obobobobobo2bobo2bo2b2o2bob4obo2b2obob2ob4ob2obob4ob11ob2ob8obob3obo2b17ob3ob13ob4obo\$b2o2bob3ob7ob7o2bobobobobob7o2bob3o3b3o2bo3b4obob6ob2ob2o5bobobob10o2bo2b4ob7o2bobobob7obobobobob4o2b7obo2bob2obobobo\$4obob2obob3ob9ob3ob2obobob2ob2obobob2obob2o2bob3o2bo4bob3ob9ob3o2bob10o2bob2ob11obobob6ob8ob2o3bobobob8ob6o2bo\$obobo2bob2ob13ob3ob3obobobo2b4obobo2bob8obob5ob5ob4obobo2bo2bob2ob8o4b2obo2bob6obobobob11ob3ob18o3bo3b2obo\$2b7obobobob11o2bobobobob2o2b2o2bo2b2obo2b5ob2ob5ob7o2b2o2b2o2b3obob11o2b4o2b8obobobobobob8o5bobobob3obobobob3o3b2o\$o2b2ob6obo2b11obobobobob6obobob3obob3obo3b2ob4o2bobob2o2b3o2bobo2bob2o2b9ob2ob3o2bob2o2b2obobobobobob7obobob4obobob8o4b2obo3bo\$3bobob2ob3obo3b10o3bobo2bob3obo3bobobo2bob2obo2bobobobo3bob3o2b2obob2obobobob18ob2ob7obob3obob8obo2b2ob3o2b4obobo2bobob3ob2o\$5ob4o4bob2ob10obobo2bob3obo3b3obo4bobobo3b5o2b2obob3obo2bobo2b4ob10o2b8ob2o3bobob5obobob16o4b7obobobobobobo\$b3obobob2ob2obo2b10ob4obobobobob2o2bobobob2obobo2b2obobo6bob2ob3ob2obobobo3bob7ob14ob2obob5obobob4ob3obob4o2b2o2bob4o2b6o4bo\$b2obob3o2bobob3ob9ob3obobobobo2bobob4obobo2b4ob7obobo2b2ob2o2bob3o3b4o2b4o3b9ob4o2bobob2obobobobob6obobo3bobo3bob12ob2o\$2obob3ob8ob2o2bo2b8obobobob7obobobo2bobobobobob4ob5obo3bobo3b3o2b7ob3ob6obobo2bob5obob2obobobobob7o3b2obobobob6ob3o2bo3bo\$3bo3bobobobobob2ob5ob5ob4obobo2bobob4obob10obob6o2b2o2bo2b3o4bo3b3obobobob8ob2ob2ob4o4bobob3ob2obob3ob6o2bobob6obob4obo\$o2b4obob10obobo2bob4obo2b3o4bo2b3obob4obobobobob9ob3ob2o2b6o2b10o3b6o5bob8obobob3o2b5ob6obo2bob8obo2b4o2bo\$3b2o2bobobobobob9o2b3ob3ob4ob2ob2ob2obo2bobob8obob3o3b3o3b8o2b3obobobobob5o2b2ob16ob2o3bobobo3b4obobo2bo2b2o2bobobo4bo\$o4b2obob6obobobobob3ob4ob7ob2ob2ob3o3bobob2ob3obob2ob2o2b2o2b2ob2ob2o2b2ob2ob12ob2ob5obob5obobob2o3bob3o2bob2o2bobobo2b3ob2obob2o2b2o3bo\$2b3ob2obobob2o2b15ob4obob7obobo2bobobob6o2b3obo5bobob4obob2obo2b3obobobob2ob4ob7ob8ob2o2bob2o2bob5ob4obo6bob2obobobo\$o7b6o2b2ob9obo2b6obob7obob4obobobo2bob2obobob2o2b9obo3b8obob3o2bobo2b4obob3obobobo2b3o2bo5bob2o2bobob2o2b2ob4o2bobo2bo2bo\$ob3o2bobobob2o2b2ob2ob4o3bo2b4ob10ob2o2bobobobob2obo2bobob3ob13ob6obo5b3o2b6o2b3obob9ob2ob2obo3b11ob5obobobob2ob2o\$b3ob3o2b5o2bo2bobobobobo2bobob2o3bob6ob3ob2obobobo2bob3ob2ob13ob3ob5obobobo5b2ob4o3b3obobobobo2b2ob3o3b9obob2obobo2b2o2bo2b3ob3o\$ob5o2bobobobob3obo3bob2o3b2ob3ob2ob5o3bob2ob3obob6obo3b13o2bo2b4obobobobobob3obob3o2bobob5o2bo2b2ob7ob14o2bo3bo5b3o\$obobo3bobob4obob2ob3obobo2bobo2b3o3b6ob3ob7obobo3bo2bobo2b9obo3bob6ob2o2bob10obob3o2bobobob11obob7ob2ob2o6bob2o2bo3bo\$2bob2obob3obobob2o2b3obo4b3o3bo4b4obobob3ob13obob3o2b9obo3b11o3bobob2o2b2obobobob3o2bobo2b5o2b2obo2bob14o2b5ob3o\$obob3ob4ob6o2b2obo2b2ob3obob9ob4o3b9o2bobo3b3obob10obobob7obobob6o2b9ob6obo2b5ob5o2b2ob2obob2obo3b3obo5b3o\$2bob6obo3bobobob5o2bo2b6ob4ob7o2bob4ob2obob5obo2bo2b16ob4obobob2obobo2b3obobobob2obobob2ob2o3bo2bobo2bobo2b2ob5obobob3obobobo\$obo3b2ob2ob9obobob3ob6o4b7o2b8ob15o4b11obobob4ob2ob16o5b7ob2obob6obo2bob5ob4obo2b6o4bo\$o4b2ob3o2bobobobobobobobob2o2b2ob7ob2obo3b2ob2obo6b5obobob17obob4o3bo2b2obob2obobob4obobobobob2ob4o2b2obob2obo2bob5ob4ob2obob2o\$b5o3b5obob2obob5obob5ob2ob2ob5ob2ob4obobobo3b6obob9ob8ob2ob8ob2ob2ob4o2bob8obo2b6o2bobo2bob4ob2obobob8obobo2bo\$bo2bo2b9obobobobobob15ob12o2bob2o2bob4ob4ob4o2b2obo2b17ob2ob7o2b9o2bo2b5obo6b2o2b2o2bobob5ob2ob6o\$2o4b3o2bobobo2bobob6ob19obob6ob2ob2o3b2obobob6o4bobo2bobobob8o2b4o2b7ob5o2bo2bo2b3ob2ob2o2b2obo2b3obo2bobobobo2bo3bo2bo\$o2b2o3bob5o2bob6obob12obo3b2obobob6obo2bob5obob2o2b3obobobob16o3b3o2b8ob9ob3obob3obo2bob3o2bob3ob2obob4ob3o\$2b2o2b3o2bob2ob5ob24o6b5obob2o3bobobobobo2bobo2b3obo2bobobobob12o2bob3o3b4o3b2ob7o4bo2b4obob5o3bobo2b2obobo3bo\$o2bob2obo3b4o2b15obob4obobobobobobo2b2obob4obobobobobob6ob4obob7ob6o3bobo2bobob2o2b2ob3o3bob4obo3bo4bob4ob9obobobobo2bo\$2bob2ob2o2b5o2b3ob8obobobob8ob3o2b2ob3obob2obo3bobobobob3obobo2b5obobob2obob3o2b5o2b3ob2ob3o2b3o2b3obobo2bobo2bob2ob2o3bob5ob4obobob3o\$o5bo3bobo3b4ob10obobob3o2bob7o2bobo2bob2obob3obobobobo2bob4o2b10ob8obobobob2obob4obobo3b4o2b4obob2o3bob2o2bobo2bob3obobob6o\$2b5o2bobobo3b4ob3o3b2ob5obob2obob8ob2ob10ob3obobobo2b3ob7obobo2bobob8obobo2b2ob5o2bo2b3obobobo4bobob2obobo5b8ob3obobo\$o3b3obobo2b4obob9ob5obob2obob7o2bob7o2b5ob2ob4obo2bo4b12obob6obob13o2bob3ob4o2bob2o2b2obobob2obob3obo2b2ob4obobo\$2b2obo2b12o2bobob4obob3obobo3b2obobo2bob3obobobob3ob2ob2o4b2o2b4ob4obob2obobob6o3b14obob2ob8obobobobob2o3b2obob6ob2obobobobo\$o3b6obob3o2bob4obob8ob2ob3ob5o2bob9ob2obob7o2b5o3b6o2b5obobob4obob14o3b4obob12ob2o2b3ob3obo2bob3o2bobo\$o4b12obob3obobob2o2b2obo3b2o3bob4obobobobobobob2ob6ob3ob2ob10ob3obob9o2b2o2b5o2b4obo3b3obob2obobobobo2bo2bob3o3bob4ob4o2b2o\$2o2b5ob2ob4obobo2b7ob4ob4o2b2obo2b16obobobob3ob15obo2b3obobobobob3obob4ob5o3bo3bob11o3bob3ob2ob7o2b3o2b4o\$3obobobobobob9obobobob2obobob2o2bobo2b6ob5obobobob6obob2obo2b5ob5o2bobob12o2b4obob4o6bob3obo2bobob3ob2o2b7obobo2bob2obobobo\$o2b3obo2b2obo2b2obob12o3b2o2b6obobo2b11obo3bo3b3ob2o2bob8ob4obobobob2o2b8obob6ob3obo2b5ob5o3bob4ob3obob6ob5obo\$obob2ob4ob3ob2ob2obobobob2obo3b2o2bobobobob4ob8obobobobo4b5obo2bob6obo2b10obobo6bob2obobobo2b3ob4obob2o5b7ob2o2b2o2b3o2b4obo\$3bob4o4bob4ob4obo3b2obo2bo2bobob8ob6o5bobob4o2b9o7b3ob3obo3b8o2b2o2bob2obo2bobobobobob4ob3o2b4obobobobo2bob4obo2bo4bo\$o3b2ob3ob4obob2ob2o5b4ob2obob2obobobob4o2b5o5bobobob13obo3b2obo2b4ob7obobob2obob2obobob4obo2b12ob4ob3obo2bobobobo2bob2obo\$2b2o2bo3bob2obobob2ob3ob5obobobobobob5ob3ob5ob3obobobobob6o2b6o3b8obo2bob12o2b7o2bobob2o2bo2b5obo3b3obobob2obobobobo2bobo3bo\$ob3o2b2o2bo2bobob3ob10obob3obobobobob3obobobobobobobobobo2b7ob6ob8o2b3o2b2ob3o2bob17o2bo2bo2b2ob5o2b2obobob4ob3ob4o4bo\$2bo4b4ob4ob5ob2obob3obobob5obobo2b3o2b5o2b4ob4obob3o2bobo2b2obo4bob2o2bo2b2ob4ob2o2bo3b15ob3ob3ob2obobob3obobo2bobob2ob2o2b2o4bo\$o2bo2bobobo2b2obob12obobobob3obobobo2b3o2bobob7ob2obob4obo3b3ob4o2bobobobo2bob2ob3obo2bobob13o6b5ob2ob5obob4obo2b3obo2b3o\$3bo3bob2o2bobob10ob3obobobob5ob2o3bobob2obob8obobobobobobo2b5ob3o4b2o2bobo2b9ob25o2b11ob4o2bob6obo4bo\$o2bobob2ob7ob10o4b2obob3ob3o3bo2b4obobob3ob3o2bob7o3b4o2bo2bo3b2obob2o2b2obobobobo2b4obobo2b2ob5o2b3o2bo2bo2b2ob3o4b4obobo2bo\$5bobo5bobob13ob3ob3o2b7o2bobob2obobob2ob2ob2obobobobo3b9ob4ob2ob2ob2o2b2o2b6obob6ob2ob11o4bobobob2obo7bobobo6b2o\$3obo2bob16o2b2obob4o2bob13ob2obob3ob2ob2o2b5obob4o3b3ob3obo2bo2b2obob3o2bobob2o2bo2bo2b3o2b9obo2b3o2bob5o3b2o2bobo2bobo2b2o\$3o2b4ob2obob6obobo5bo6b5o2b9obobobobob3obobo2bob3obobo3b4obo2b3obobo3b3ob14ob15o2bo2bobo2bob5ob4o3b3obo\$2bo3b2obob2ob9o5bo2bo3b19ob7ob5obob2obobobob3obo2b2o2bo2bob2ob2o2b7obo3bobobob16ob4obob11obob2ob3obobo2bo\$obobobobobob10obob2ob4obo3b2obob10o2b3obob3ob4o5b5ob4o3b4obo3b2o3b2ob3obob4obo2b12o2bo2bo5b2ob2ob9ob7o2bo\$o6bobob2obob6o2bo2b8o2b5o2b10ob3ob2o2b10obobob4obo4bobo2b2o2b4obobo2bobob2ob4ob10obobobobob4o2bob8obob3ob7obobo\$2b2ob2o3bobobo3bo2bobob10o2b4o2b12ob2o2b2obo4bob2ob5obo2b2o3b3obobo3b7o2bobo4bob2ob3ob8obobobob5obob10o3b6ob2o\$o2bob2ob2ob6ob3obobo2b2o2b8o2b2ob3ob3ob2o3bobo2bobo2b8obob3o2b4ob3ob4o4bobobob4ob4ob10o2b5obobob10ob2obo6b3ob4obo2bo\$3bob2o3bobobobo3b2ob3obob2ob4o2bo2bob2obob8o2bobobob12obobobobobo3bobobobo2b8o3b4obobobobob3ob10obobob2ob6ob3o4bobobo2bob2o\$3obo2b18obobo3b6ob3obobobo2b6obob3obobo2b5obob7obo2bo2bobobobo2b4obobobo2bob13obo2b5obobob7ob5o2b2o2b5obob2ob2o\$3o2bo2bob8o3bob3obo4b2o2bo2b3ob4o3bob8ob15obobobobo2bo2bobobobob11o2b3obobobobob7ob4obobobob2ob3obo2bob3ob2obo2bob4ob2o\$2b2obobobob11obo2bo3b4ob3obo2bob2o3b2ob4obob7o2b3obob12o4bobob11obob4obob9ob2obob2o2b3obob3o6b5obob9o\$o3b3ob2ob3o2b7o2bobob3o2bo2b2ob6o2b5obob4ob6ob10obobob4o2bob2ob19o4b2obobobob2ob2ob4obob4obo2b4ob3obobob2ob2o2bo3bo\$2bob5obob2ob8ob5ob2ob4ob3obobob3ob17o3bobob13ob12ob4obobob19ob2o6b3o2bo3bob2obo3b6obo2b2o\$3ob11ob3obob8ob2o4b12obobobobob2ob2ob3o3b4o2b4ob6o3b7o2b14ob7obobo2bob3obob2o2b8ob2ob3o4bob4o3bo3bo\$2b3obobobobobo3b2o2b7obobo2b2ob4ob2obob2ob5o2bobob3obo2bo4bob3ob8o2b8obob4ob5ob2ob9o4bobob2obobob3ob3obo3b4o2bobobo2bo2bobo\$o2b2ob2obobob3obob3ob7ob3o3bob2obobob2ob2obobob4o5b4obobob3o2bob5ob7ob7obobo5bo2b9o4b3ob7obob2obobob4obob7obo7bo\$6bob3obobobobob10o2b2ob12ob4ob2obobobobo2bo3bob8ob3ob17obo2b4ob7ob5o2b11o3b2obobobobobob6ob4ob2obobo\$ob2ob2o3bo2bobobo5bo2b2obo3b2o2b6obo2bobo5b7obobo3b6ob2obobobobo3bobob9o2b3o2b2ob3obo2b3o2b2obobob7o3bob2o2bobobob9obo7bo\$3b9obo2b3o2bobobob3ob4o2b6obob7obobobob6o2bob2ob2ob2o2bobo3b5o2b8obo2bo2b4ob2o4bob2ob7o2bobob4obob3obobo2b5obo2bob2obobo\$obob2o4bob4obob2obob2ob2o3bobo2b7ob13obo3bob6o3bobob4o3bobobo4b6obobobo3bob8o4bob3ob2o3b10o3b2o2b11obobobo3bo\$3b2obob3obobobob6ob3o2b2obob9ob4o2bo2b3obo2bobob4obo2bob3obobob2obobo2b6obobobobob10o3b3o3bobo2b2o2b3ob3obobo2bo2b2ob8o3bob2o\$obob2obo2b2obobobo3b7o2bo2b9ob6ob2obob6ob3o2b2ob5ob11obo3bob2obob4o2bobob7o7b9obo2bo2b5obob12ob2o3bob3obo\$3bob3ob3o2bobo2b11o2b2ob5obobobob2obo2bo2b3o4b7o3bobob5obob5ob6obob9o2b2obob2o4bo2bobo4bob2ob4obob2obobo4b5o2b2o3b2o\$ob2obob3obo3bob14o2bo2b9obo2b3ob6o3b13ob12o2b5o5b4obobob6o2bob3obo2bob3o2b3ob3ob3ob6obob5obo2bobobobobo\$4bo5bo3bobo2b10obo2bobobobob7ob3ob5o2b14obobobobob10o2b10ob2ob5obob2o2b2obo2bob2ob5ob2o2bo2bob4o2b4ob2obo2bo2bo\$o2bo3bo4bobob10ob2ob2ob12ob10obob5o2b11ob10o2b2ob4ob4obob2obobo3bob4obobobo2b5o2b2o5b7obobob3ob3obobobobo2bo\$4b2o3bob2obo2b11ob5obobob6o4b7ob5obo2b6obob5obobob3o2bo2bobob6o2bobob3obob3o2b3obob2obobobob2ob3o2bob9ob9ob2o\$o3bob5o2bo2b10o3bo3bob10o2bo2b5obo2bob2ob4o2bob7o2b4obob2o4b4ob5o2bobobobob4obobobob4obobo2b3obo2b5obobob3obobobobo3bobo2bo\$5bob7o2bobob3ob2ob6obo2bobob4ob2ob5o2b6obob7o2b7o2bobobob3o2b2ob6obo2bob14obob2obobobobo5bobo2bob2ob2ob11ob3o\$o2b2ob10o5b3ob2o2bobob8obob8ob2obobobo5bo2b13ob4obo3b3ob2ob5o2b3o3bo2bobob2ob2obo2bobob6ob6o2b5o2b3obobob4o5bo\$2bo3bob8o4bob7obobobo2b7obob5o3bobobo2b4obobob2ob5ob3o2bobobob6ob2o2bob2obobobob7o3b2o2bobobobob4ob4ob2obob3o2b10o3b2o\$o2b3ob8o2b3obobo3b3obob4obobobob4ob4o4b3o8b2ob4obo2bobob6obob9ob2o2b3o3b2obob7obo2bobobob6o4b3ob2ob2obobo2b2obob5o2bo\$6b7o3bobobob2o4bobobobob8ob3o2bobobo2b9obob2obob5ob4obobobobo2bo4b3obo2b4obob4o2bob2o4bobobobob6o2b3obo2bob4obob8obo\$ob2obob9o2b2obobo2bob2obob3o2b3obobobob2ob2o2bo4b3obobobob2obo2b2obo2b6ob4obobob7o2bob3ob3ob2obobob2ob2obobob7obob3obobob3obobobob7o2bo\$2bobobob6o4b3obobob5obobobob11o2bobo2bobo4b5ob4ob2o2b4obob3obobobob3obobo2b3ob7ob2ob3o2bobob2obob2ob4ob3o3bobo2bobo4b11o\$2obobob8o3b2obobobo3bob2ob7obobo2b4obob2obob6obobo2bobobobo3b2obobobobobobobobob2o2bo2bobo3b3o2bobo2bob4obob2ob6o4bo2bobobob2ob2obo2b5o2b2o\$b4ob6obo2bo2bo2bobobobobo2bobo2bobob5ob2obobobo4b3o2bobo2bobobo3b4ob3ob3obobobo3bobob3o2b6obobobobo4b4ob5ob11obob4obobo2bob5o2bo\$b3obob3o2b4ob2ob2obo2b2o4bob4o2b5o2bobo2b5o5b2o5bobo2bob2o3b3obo2bobo2b2ob2ob3obo3bob5o2b6o2b3o2b6ob4o2bo2b3ob2obo5bobo2bo3b2obo\$b2ob3obo2b2obobo2bo2b2o2bob4ob2o3b7o2b3o5b2o3bob2obob6o2b3obobob4ob5ob2obob3obob2o2bo2b8ob7o2b6o2b4obo6b3ob2o5bob5ob2o\$bob6obo2bobo5bobob3ob2obobob4o5b2o2bobo2bobobo8b3ob2o2bo4b2obo2b3o3b2o4bob3o4b5obo2b2obob2o6bob3o2bobo3bobo2b3o7bobo4bobob3o\$2bob3o2bobo2bo10b3o6bob4ob2ob4o4b3o4bo9bob2o2bo3bobobo2b3ob3o2bobobobobobo6b3o3bo2bob3o2b4o2b2obob3o3b3o4bobo2bobo6b4o\$o2bobo22b4o8bobobo3b4o3b4o7bob2obo8bobo8bo3bob3obo8b4o5b4o3b2o3bo3bob2obo5b2o19bo3bo\$2obobobobobobobobobobobo2bobo2bobob2obob2ob2obobo2bobobo2bobobob2ob2ob2obobobob2ob2obobobobobob2ob2ob2obobobobo2bobobobo2bobob2ob2ob2ob2ob2ob2obob2obobobobobobobobobobob3o!`
Attachments
examples.tar.gz
(247.91 KiB) Downloaded 97 times
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

shouldsee wrote:...we can at least figure out some incremental changes along a mutation path. More specifically, the Hamming distance between 2 given rulestrings is distorted. Starting from B3/S23, B23/S23 changes the dynamics greatly with 1 bit flipped, whereas B368/S238 endures 3 flipped bits but bears great similarity to B3/S23. Thus it'd be great if we can find a universal way to quantify the dynamical difference between 2 given rules given their rulestring, or at least spot the important bits of a given rulestring. (obviously not all 102bits in a nt-rule is important)

There's no real way to do this purely theoretically, because - as I'm sure you realized - the Hamming distance treats all bits equally when we know they should not be. (e.g. B0 definitely changes dynamics much more than S8)
However, in my mild experimentation with non-totalistic rules there is one thing I have noticed, that being cognizant of the relative frequency of certain neighborhoods gives one greater control over dynamics, which leads to my little rookie's suggestion:
Instead of expressing dynamic difference purely on the difference between rulestrings, weight the changed neighborhoods based on the frequency in which they appear naturally in the two rules. (I say check both rules to preserve transitiveness of the dynamic difference and give a more refined estimate)
This may be difficult for rules with large differences in dynamics that cause very disparate "transition profiles", but it looks like it could still be a better approach that a naive Hamming comparison.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

BlinkerSpawn

Posts: 1882
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Use Smoothiness to classify rules

BlinkerSpawn wrote:There's no real way to do this purely theoretically, because - as I'm sure you realized - the Hamming distance treats all bits equally when we know they should not be. (e.g. B0 definitely changes dynamics much more than S8)
However, in my mild experimentation with non-totalistic rules there is one thing I have noticed, that being cognizant of the relative frequency of certain neighborhoods gives one greater control over dynamics, which leads to my little rookie's suggestion:

Hi BlinkerSpawn,

In a way, it is a good thing that bits contribute differently to the dynamics. This is both an inevitable, and exploitable phenomena. Think about it, say you have a coupon-picker rule, B/S012345678, how many mutations could it take? Most possibly it can have 6-7 bits mutated but still giving unchanged dynamics. However, if we are looking at B3/S23 instead, it is far more sensitive to rulestring mutation, and we are only allowed to touch B8,S8. It is this difference that I want to exploit here.

BlinkerSpawn wrote:Instead of expressing dynamic difference purely on the difference between rulestrings, weight the changed neighborhoods based on the frequency in which they appear naturally in the two rules. (I say check both rules to preserve transitiveness of the dynamic difference and give a more refined estimate)
This may be difficult for rules with large differences in dynamics that cause very disparate "transition profiles", but it looks like it could still be a better approach that a naive Hamming comparison.

Just to clarify, I am not "expressing dynamic difference" with difference between rulestrings, I used correlation to do that. I simulate say 500 soups on a 20x20 torus for 11 steps, and collapse all trajectories into 500x20x20x11 bits, and check the correlation between the 2 sets of trajectories (one from each rulestring). The hamming distance is merely there to restrict searching depth to nearby rules (so that we only calculate similarity between superficially/naively related rules! )

I hope this clarifies a bit.
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

shouldsee wrote:
BlinkerSpawn wrote:Instead of expressing dynamic difference purely on the difference between rulestrings, weight the changed neighborhoods based on the frequency in which they appear naturally in the two rules...

Just to clarify, I am not "expressing dynamic difference" with difference between rulestrings, I used correlation to do that. I simulate say 500 soups on a 20x20 torus for 11 steps, and collapse all trajectories into 500x20x20x11 bits, and check the correlation between the 2 sets of trajectories (one from each rulestring). The hamming distance is merely there to restrict searching depth to nearby rules (so that we only calculate similarity between superficially/naively related rules! )

I hope this clarifies a bit.

Well, my response was geared more toward where you said
Thus it'd be great if we can find a universal way to quantify the dynamical difference between 2 given rules given their rulestring, or at least spot the important bits of a given rulestring.

but yes, that clarifies the search process a little bit.
I still think it would be a better determinant of what constitutes a "superficially related rule", considering that even though specific profiles (what I think you call trajectories) can vary between rules, certain transitions are basically always more or less important than others (e.g. 2a or 2e as opposed to 2n). So you could say that a bitflip in 3a or somesuch may or may not constitute a "superficial variation" and better fine-tune your search.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

BlinkerSpawn

Posts: 1882
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Use Smoothiness to classify rules

BlinkerSpawn wrote:I still think it would be a better determinant of what constitutes a "superficially related rule", considering that even though specific profiles (what I think you call trajectories) can vary between rules, certain transitions are basically always more or less important than others (e.g. 2a or 2e as opposed to 2n). So you could say that a bitflip in 3a or somesuch may or may not constitute a "superficial variation" and better fine-tune your search.

Let me explain this idea in a little bit more detail. The idea originates really in bioinformatics, where you have important sequences conserved across evolution, because they are of functional importance. The whole point of enforcing hamming distance to search superficially realted rules is to simulate the process of random mutations. i.e. we assume only a single-base flip is allowed. Say we take B3/S23, and allow it to randomly mutate and kill off the progeny with non-similar dynamics (die off due to poor biological functionality) . Then we should get a bunch of sequences/rulestrings with closely related dynamics. It is by looking the conservation of individual bits (across this bunch of sequences) that we infer their relative importance towards the wanted dynamics. As for hamming distance/superficially metric, it's merely saying "the rulestring is only allowed to change 1 bit at a time“, and has absolutely no connection towards predicting the resultant dynamics.

I have nearly abandon the idea of "looking at a rulestring and infer the type of resultant dynamics". We are simply not at that stage yet. All I am trying to do now is to construct a reliable metric to characterise the dynamics. If you look at the examples.tar.gz, you should see the profiles correspond well with the amount of density fluctuation, and that's how my script can be useful. i.e. there are 2^102 rules out there in nt-rulespace, it's simply not possible to manually review them one by one.
shouldsee

Posts: 406
Joined: April 8th, 2016, 8:29 am

PreviousNext

Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 2 guests