Use Smoothiness to classify rules

For discussion of other cellular automata.
shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

Re: Use Smoothiness to classify rules

Post by shouldsee » August 26th, 2016, 6:09 pm

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
mi_rulespace_2d.jpg (35.53 KiB) Viewed 13244 times
mi_rulespace.jpg
mi_rulespace.jpg (33.33 KiB) Viewed 13244 times

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Use Smoothiness to classify rules

Post by Bullet51 » August 28th, 2016, 6:14 am

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:

Code: Select all

x = 60, y = 60, rule = B4678/S35678:T60,60
13bo3b22o$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$23o
13b24o$24o11b25o$24o11b25o$23o11b26o$15ob2o2b2o11b27o$10o22b28o$obobob
ob2o17b2o2b28o$25b26ob3o$23b23ob3o$22b23o$22b23o$20b24o$20b21obo$18b
22o!
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:

Code: Select all

x = 60, y = 60, rule = B014/S2:T60,60
20b3o$20b4obo$19b7o$13b2o3b9o$17b12o$15b15o4bo$15b15ob3o2bo$15b17ob4o$
14b25o14b2o$14b24o$13b26obo11b2o$12b29obo8b2o$12b31o7b4o$10b34o5b3obo$
9bob41obo$8b44obo$9b43obo$2bo5b45o3bo$3o4b27ob10obo3b4o2b4o$32obo2bob
2ob3o8b8o$31o9b3o10b7o$30o11bo11b7o$29o21bob8o$28o21b11o$29o21b10o$29o
21b10o$28o22b10o$28o11b2o9b10o$29o9b3o9b10o$26obo11b4o7b10o$25o12bob3o
7b11o$25obo9bob5o8b9o$26o8bo2b5o9b9o$27o5bob7obo6b11o$28o5b9o3bo4b10o$
45obo2b11o$45o3b12o$47ob12o$45o2b13o$60o$60o$19o2b39o$7ob10o4b38o$5ob
2ob8o6b2ob34o$6o4b8o10b32o$3o6b8o12b9o2b20o$obo8b7o10b9o4b19o$11b8o11b
6o5b18o$12b7o11b5o5b18o$12b9o9bob2o6b19o$12b8o13bo6b17o$11b10o19b17o$
11b10o18b17o$12b11o18b15o$12b10o19bob13o$12b11o19b15o$12b11o21b7o4bo$
13b10o23b4o$13b3ob6o24bo$19b4o!
Still drifting.

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

Re: Use Smoothiness to classify rules

Post by shouldsee » August 28th, 2016, 7:54 am

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
tMI_rulespace.jpg (63.8 KiB) Viewed 13196 times
all points here has a Covariance<0.25
all points here has a Covariance<0.25
tMI_rulespace_2d_thresholded.jpg (64.32 KiB) Viewed 13196 times
tMI_rulespace_2d.jpg
tMI_rulespace_2d.jpg (75.77 KiB) Viewed 13196 times

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Use Smoothiness to classify rules

Post by Bullet51 » August 30th, 2016, 2:15 am

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
H-I graph of B3/S125
6.png (4.06 KiB) Viewed 13172 times
H-I graph of B3/S2368
H-I graph of B3/S2368
B3S2368.png (4.94 KiB) Viewed 13172 times
Is there any statistics that can capture the non-linear behavior of the H-I graphs?
Still drifting.

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

Re: Use Smoothiness to classify rules

Post by shouldsee » August 30th, 2016, 4:52 am

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
B012348S0236_soup57.jpg (115.58 KiB) Viewed 13154 times
B3S23 _soup1.jpg
B3S23 _soup1.jpg (130.54 KiB) Viewed 13162 times
B012S1256_soup5.jpg
B012S1256_soup5.jpg (111.35 KiB) Viewed 13162 times

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

Re: Use Smoothiness to classify rules

Post by shouldsee » September 1st, 2016, 8:00 am

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
B3S23 _soup3.jpg (120.01 KiB) Viewed 13128 times
B0123456S0246_soup30.jpg
B0123456S0246_soup30.jpg (161.18 KiB) Viewed 13128 times
B012S1256_soup1.jpg
B012S1256_soup1.jpg (173.16 KiB) Viewed 13128 times

Bullet51
Posts: 663
Joined: July 21st, 2014, 4:35 am

Re: Use Smoothiness to classify rules

Post by Bullet51 » September 4th, 2016, 7:26 am

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

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

Re: Use Smoothiness to classify rules

Post by shouldsee » September 4th, 2016, 7:55 am

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
vic_rulespace_2d.jpg (72.15 KiB) Viewed 13097 times
vic_rulespace.jpg
vic_rulespace.jpg (74.09 KiB) Viewed 13097 times

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

Divergence of trajectories is dependent on the initial densi

Post by shouldsee » September 28th, 2016, 4:53 am

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
B024S0123_soup19.jpg (130.91 KiB) Viewed 12993 times
B3S23_soup91.jpg
B3S23_soup91.jpg (135.9 KiB) Viewed 12993 times
B15S23478 _soup19.jpg
B15S23478 _soup19.jpg (128.2 KiB) Viewed 12993 times

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Use Smoothiness to classify rules

Post by wildmyron » December 7th, 2016, 2:30 am

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.

Code: Select all

x = 90, y = 90, rule = B345678/S012678:T90,90
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$
90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
o$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$44o2b44o$o
bobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo
bobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobobobobobo
bobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobobobobobo
bobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$90o
$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo
bobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobobobobo
bobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobobobobo
bobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobo$
90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
o$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobo$90o$obobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobo$90o$obobobobob
obobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobo$90o$obobobobobobobobobobobobobobobobobobobobobobobobobobobob
obobobobobobobobobobobobobobobobo$90o!
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

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

Re: Use Smoothiness to classify rules

Post by shouldsee » February 13th, 2017, 8:24 pm

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

Post by shouldsee » February 13th, 2017, 8:56 pm

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.
XAaVRb2.png
XAaVRb2.png (137.09 KiB) Viewed 226 times
kvUuqbk.png
kvUuqbk.png (146.76 KiB) Viewed 226 times
zXI3w12.png
zXI3w12.png (158.46 KiB) Viewed 226 times
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

Post by shouldsee » February 14th, 2017, 7:02 pm

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):

Code: Select all

25
30
32s
40s
41
45
54
57s
60
75
86
89
90
96ss
97
101
102
105
106
107
110
120
121
122s
124
126s
129s
135
136s
137
146s
147
149
150
151s
153
160s
161s
165
169
182s
183s
192ss
193
195
225

demos:
Jk0zIO0.jpg
Jk0zIO0.jpg (40.75 KiB) Viewed 226 times
x2Q2SfO.jpg
x2Q2SfO.jpg (38.43 KiB) Viewed 226 times
viyMkHg.jpg
viyMkHg.jpg (25.27 KiB) Viewed 226 times
qpxcIc5.jpg
qpxcIc5.jpg (53.12 KiB) Viewed 226 times
EdUEM4M.jpg
EdUEM4M.jpg (25.21 KiB) Viewed 226 times

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Use Smoothiness to classify rules

Post by wildmyron » February 14th, 2017, 10:07 pm

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 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

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

Re: Use Smoothiness to classify rules

Post by shouldsee » February 24th, 2017, 4:13 pm

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))
rU5Ov4I.jpg
rU5Ov4I.jpg (29.01 KiB) Viewed 226 times
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

Post by shouldsee » February 28th, 2017, 8:58 pm

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
tca_atlas.jpg (218.71 KiB) Viewed 12345 times
Attachments
tca_atlas.fig.tar.gz
matlab fig in archieve
(113.44 KiB) Downloaded 249 times

User avatar
Apple Bottom
Posts: 1034
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: Use Smoothiness to classify rules

Post by Apple Bottom » March 1st, 2017, 8:50 am

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!

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

Re: Use Smoothiness to classify rules

Post by shouldsee » March 2nd, 2017, 5:41 pm

visulisation with vis.js

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

Re: Use Smoothiness to classify rules

Post by shouldsee » March 5th, 2017, 10:10 am

Snapshot of rules similar to B3/S23 (6152)
Edge with similarity higher than exp(-4) is retained.
bWDyGpl.png
bWDyGpl.png (313.26 KiB) Viewed 216 times
The applet can be found at here: https://flaw.000webhostapp.com/CA_Atlas/index.html (Mod edit: link no longer works)

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

Re: Use Smoothiness to classify rules

Post by shouldsee » March 5th, 2017, 7:13 pm

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
6152_a2b2_phd.png (154.56 KiB) Viewed 12267 times
When physics engine of vis.js is enabled, the graph relax to the following shape
6152_a2b2_ph.png
6152_a2b2_ph.png (192.74 KiB) Viewed 12267 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
193384_a2b2_phd.png (197.62 KiB) Viewed 12267 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

Post by shouldsee » March 8th, 2017, 7:26 pm

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.

Code: Select all

x = 172, y = 119, rule = B12a3en4cintwyz5aejky6-in7c8/S1e2cin3-akr4-eijkr5eijry6-a78
b2o4b2o4b2o2b4obobob2obob2ob2obobob2ob2obob2ob2ob2ob2obobob2ob4obob6ob
ob2ob2obobob2obobob2obobobobobob6obobobobobob2ob2ob6obobobobobobobobob
obobo5b2o$bo2b3o3bobo2bobo14bobo7bobo4bobobo2bobo7b3o7bo3bo4b3o6b2o20b
2o9bo3b2o2b2o5bo5bo3bo3bo3bo2bo7bo$obob3obobo2b2obobo5b3obo2bobob2obob
2obob2o2bobobobobob2o3b4o4b3obobo4bob3obo3bo2bo3b4o8b2ob4ob2o4b3o2bob
2ob6o5b3ob3ob3ob3obob3obo$2ob6ob2o5b3o3b2obob2obobo2b2obo2b3o3bobo5b3o
3bobobobob2o5bo7b3obo4b2ob2ob4ob2o4b2o6bobo2b5ob3o2bo5b4ob6o5b3o2bobob
o2b3o$2bobobob2o2bo5bo2b2ob2obobobo3bo2b4obob3obo2b2o3bob2o2bo2b2ob2o
2bo2b7o2bo4bob5o4b2o5b3o4bo2bo2b2ob3o2bobob2ob2o4bo4b6obo6bobo3bobo$2b
o2bobo2b2o2b2obob2obo2b2obobo2b2ob3ob6o2bobob2ob3o3b2o4b6obo2bobobob2o
bo2bobo2b3obob3o6bob2o2b2o2b2ob3o4b4ob2o2bo2bo2bobobobo2bo2bo3bobobobo
b4o$2bobob4o2bo2bobo3bobobobob5ob2ob4ob8ob2obobob2o4bob2obob5obobobo2b
o2bo3b2obob3ob4ob3obob3ob2obobo3bo3bo2bobobo3bob4ob5o3bobobobobo2bob2o
$bo2bo2bobo2b3o3b3obobob2ob2obo3b7o2bobobobobobo2bob2ob2ob4ob2o2bob5ob
o6b2o6b2ob2obob2obo2b4o2bobobobo3b2ob4obo2bob4obob2o2b5obobobob3o2bobo
$obobo3b3ob2obob5obob3ob3obob6o3b4o2bo2b4ob2ob6obobob3ob7ob3obobobobob
ob4obobo2b3obobo2bob3ob2o2b4obobobob3ob3o3bobob2ob3obobob5o$obob4ob2ob
2ob3obob2ob3ob3ob2ob2ob2o3b5obo3bob2ob5ob2o2b4obob9obob4obo2bobobo2bob
obo2b3obobo2bobobobobobobob3obo2bob5o2b4ob4ob5ob3o2bobo$obo2bo2bob3obo
b2o3b8o2bob8o2b5ob2o3b6obob2o2bob4ob9obobo3bobobobob6ob4obobob4obob2ob
4ob3o3b4obobob5obob2ob3obobobob2o$4ob11ob4obob2o3bob9o3bob4obo2b2o3bob
obobob3obob10obobob2o4bobob4obobobo2bob6obobo2b2o2bo2bo2b5obob9obobo2b
obobobobo3b2obo$bobob3ob9ob8ob4ob2obo2b2ob2o5b11obob3obo2b2obobo2bobob
obob2ob2o2b2obob4obob4obobob2o2b3o3bobob2obobob6obobobobob4obob3obo3b
3o$2bobo4b4o2b3obo2b3obob2obob4ob3o2b2o2bob3ob2obobob5obob2ob2ob4obobo
bob4o3b2obob8obob2ob2obob2o2bo2b4ob5o2bobobob5obobo2bobobobobob4o5bo$o
5bo2b2ob4o2bobob2obobo2bob3ob2obobob2o2bobobob3obobob5obo4bo3bobobobob
obobobo3bobobo4bobo2bobobobo2b2obobobob2obob10obobobob4obobo2bobobob4o
bo$4o3b4obob2ob3ob2o3bobo2bobob2ob3obo3bo2b4o3bobobobobobobobobob2obob
obobob5o2bo2b3ob2obobo2bob7ob5o2b5o2b3obobob5obob2obobobob3o2b5o2bo2bo
$o2b2obobob2obo2bob10ob2obob2ob3obob3obobobobobobob5obobobo4bobob3ob7o
bob2ob2obob2obo2bo2b2obobobobobob4obob14obob2obobobob4obo2bobo2bo$o5b
2ob4ob4obobobo2bobo4b3o2b3obobobob5ob3obobobobo3bobobo2bobobo3bobo2b2o
2bobobo3bob5o2b10obobobob2o3bobobo2bob3o3bobob5obobo3bo3bobo2bo$2bo2b
3ob5o2b3ob4ob3ob9obob3obobob5o3b8ob2obob4obob3obobob3o2b3ob3o2b2o4b4ob
o2bob3ob2obob3o2bob8ob2o2bob2ob2ob2obob3o2bo$obobob3o2b4o3bo2b2ob3obo
2bob2ob2ob5o2bob7obobobo2bobobo2b3obob4obob4obo3bob4ob3ob4obob2o4b3obo
bo3bobo2bobobobo2bob5o2bobobo5bo2b2o7bo$4b4ob3ob2ob16o3bobobobobobob2o
b3o2bob3ob6obo2b3o3bo2bobo3b5ob9o2b5obo2b6obobob2o2b13obobobo2bob2obo
2b3ob7o$obob2ob2ob2o6b10ob3o2bob9o2b3obob6obo2bobobob2o2b2obob4ob2o2b
2ob3ob13ob2ob3obo2bobobo4b3obobobob4obo2bobobob5obob2ob3o3b2obo$2b6o4b
6ob9ob2ob4obobobobo2bobo3bo3b2ob3o2bobob2o2b2o3b2ob4obobobo2b13obob2ob
3ob3obobob15obob8obo3bobob4o2b2o2bo$o3b3ob21obob2o2bob6obob2obobo3b2ob
3o5bob5obob3o3b6obob14o2b8o2bobobo2b3obob3obo2b4obob3obob7obobobo3bobo
bo$2o3bob3ob4ob11ob2ob3obobobobobo2bobo2bo2b2o2bob4obo2b2obob2ob4ob2ob
ob4ob11ob2ob8obob3obo2b17ob3ob13ob4obo$b2o2bob3ob7ob7o2bobobobobob7o2b
ob3o3b3o2bo3b4obob6ob2ob2o5bobobob10o2bo2b4ob7o2bobobob7obobobobob4o2b
7obo2bob2obobobo$4obob2obob3ob9ob3ob2obobob2ob2obobob2obob2o2bob3o2bo
4bob3ob9ob3o2bob10o2bob2ob11obobob6ob8ob2o3bobobob8ob6o2bo$obobo2bob2o
b13ob3ob3obobobo2b4obobo2bob8obob5ob5ob4obobo2bo2bob2ob8o4b2obo2bob6ob
obobob11ob3ob18o3bo3b2obo$2b7obobobob11o2bobobobob2o2b2o2bo2b2obo2b5ob
2ob5ob7o2b2o2b2o2b3obob11o2b4o2b8obobobobobob8o5bobobob3obobobob3o3b2o
$o2b2ob6obo2b11obobobobob6obobob3obob3obo3b2ob4o2bobob2o2b3o2bobo2bob
2o2b9ob2ob3o2bob2o2b2obobobobobob7obobob4obobob8o4b2obo3bo$3bobob2ob3o
bo3b10o3bobo2bob3obo3bobobo2bob2obo2bobobobo3bob3o2b2obob2obobobob18ob
2ob7obob3obob8obo2b2ob3o2b4obobo2bobob3ob2o$5ob4o4bob2ob10obobo2bob3ob
o3b3obo4bobobo3b5o2b2obob3obo2bobo2b4ob10o2b8ob2o3bobob5obobob16o4b7ob
obobobobobo$b3obobob2ob2obo2b10ob4obobobobob2o2bobobob2obobo2b2obobo6b
ob2ob3ob2obobobo3bob7ob14ob2obob5obobob4ob3obob4o2b2o2bob4o2b6o4bo$b2o
bob3o2bobob3ob9ob3obobobobo2bobob4obobo2b4ob7obobo2b2ob2o2bob3o3b4o2b
4o3b9ob4o2bobob2obobobobob6obobo3bobo3bob12ob2o$2obob3ob8ob2o2bo2b8obo
bobob7obobobo2bobobobobob4ob5obo3bobo3b3o2b7ob3ob6obobo2bob5obob2obobo
bobob7o3b2obobobob6ob3o2bo3bo$3bo3bobobobobob2ob5ob5ob4obobo2bobob4obo
b10obob6o2b2o2bo2b3o4bo3b3obobobob8ob2ob2ob4o4bobob3ob2obob3ob6o2bobob
6obob4obo$o2b4obob10obobo2bob4obo2b3o4bo2b3obob4obobobobob9ob3ob2o2b6o
2b10o3b6o5bob8obobob3o2b5ob6obo2bob8obo2b4o2bo$3b2o2bobobobobob9o2b3ob
3ob4ob2ob2ob2obo2bobob8obob3o3b3o3b8o2b3obobobobob5o2b2ob16ob2o3bobobo
3b4obobo2bo2b2o2bobobo4bo$o4b2obob6obobobobob3ob4ob7ob2ob2ob3o3bobob2o
b3obob2ob2o2b2o2b2ob2ob2o2b2ob2ob12ob2ob5obob5obobob2o3bob3o2bob2o2bob
obo2b3ob2obob2o2b2o3bo$2b3ob2obobob2o2b15ob4obob7obobo2bobobob6o2b3obo
5bobob4obob2obo2b3obobobob2ob4ob7ob8ob2o2bob2o2bob5ob4obo6bob2obobobo$
o7b6o2b2ob9obo2b6obob7obob4obobobo2bob2obobob2o2b9obo3b8obob3o2bobo2b
4obob3obobobo2b3o2bo5bob2o2bobob2o2b2ob4o2bobo2bo2bo$ob3o2bobobob2o2b
2ob2ob4o3bo2b4ob10ob2o2bobobobob2obo2bobob3ob13ob6obo5b3o2b6o2b3obob9o
b2ob2obo3b11ob5obobobob2ob2o$b3ob3o2b5o2bo2bobobobobo2bobob2o3bob6ob3o
b2obobobo2bob3ob2ob13ob3ob5obobobo5b2ob4o3b3obobobobo2b2ob3o3b9obob2ob
obo2b2o2bo2b3ob3o$ob5o2bobobobob3obo3bob2o3b2ob3ob2ob5o3bob2ob3obob6ob
o3b13o2bo2b4obobobobobob3obob3o2bobob5o2bo2b2ob7ob14o2bo3bo5b3o$obobo
3bobob4obob2ob3obobo2bobo2b3o3b6ob3ob7obobo3bo2bobo2b9obo3bob6ob2o2bob
10obob3o2bobobob11obob7ob2ob2o6bob2o2bo3bo$2bob2obob3obobob2o2b3obo4b
3o3bo4b4obobob3ob13obob3o2b9obo3b11o3bobob2o2b2obobobob3o2bobo2b5o2b2o
bo2bob14o2b5ob3o$obob3ob4ob6o2b2obo2b2ob3obob9ob4o3b9o2bobo3b3obob10ob
obob7obobob6o2b9ob6obo2b5ob5o2b2ob2obob2obo3b3obo5b3o$2bob6obo3bobobob
5o2bo2b6ob4ob7o2bob4ob2obob5obo2bo2b16ob4obobob2obobo2b3obobobob2obobo
b2ob2o3bo2bobo2bobo2b2ob5obobob3obobobo$obo3b2ob2ob9obobob3ob6o4b7o2b
8ob15o4b11obobob4ob2ob16o5b7ob2obob6obo2bob5ob4obo2b6o4bo$o4b2ob3o2bob
obobobobobobob2o2b2ob7ob2obo3b2ob2obo6b5obobob17obob4o3bo2b2obob2obobo
b4obobobobob2ob4o2b2obob2obo2bob5ob4ob2obob2o$b5o3b5obob2obob5obob5ob
2ob2ob5ob2ob4obobobo3b6obob9ob8ob2ob8ob2ob2ob4o2bob8obo2b6o2bobo2bob4o
b2obobob8obobo2bo$bo2bo2b9obobobobobob15ob12o2bob2o2bob4ob4ob4o2b2obo
2b17ob2ob7o2b9o2bo2b5obo6b2o2b2o2bobob5ob2ob6o$2o4b3o2bobobo2bobob6ob
19obob6ob2ob2o3b2obobob6o4bobo2bobobob8o2b4o2b7ob5o2bo2bo2b3ob2ob2o2b
2obo2b3obo2bobobobo2bo3bo2bo$o2b2o3bob5o2bob6obob12obo3b2obobob6obo2bo
b5obob2o2b3obobobob16o3b3o2b8ob9ob3obob3obo2bob3o2bob3ob2obob4ob3o$2b
2o2b3o2bob2ob5ob24o6b5obob2o3bobobobobo2bobo2b3obo2bobobobob12o2bob3o
3b4o3b2ob7o4bo2b4obob5o3bobo2b2obobo3bo$o2bob2obo3b4o2b15obob4obobobob
obobo2b2obob4obobobobobob6ob4obob7ob6o3bobo2bobob2o2b2ob3o3bob4obo3bo
4bob4ob9obobobobo2bo$2bob2ob2o2b5o2b3ob8obobobob8ob3o2b2ob3obob2obo3bo
bobobob3obobo2b5obobob2obob3o2b5o2b3ob2ob3o2b3o2b3obobo2bobo2bob2ob2o
3bob5ob4obobob3o$o5bo3bobo3b4ob10obobob3o2bob7o2bobo2bob2obob3obobobob
o2bob4o2b10ob8obobobob2obob4obobo3b4o2b4obob2o3bob2o2bobo2bob3obobob6o
$2b5o2bobobo3b4ob3o3b2ob5obob2obob8ob2ob10ob3obobobo2b3ob7obobo2bobob
8obobo2b2ob5o2bo2b3obobobo4bobob2obobo5b8ob3obobo$o3b3obobo2b4obob9ob
5obob2obob7o2bob7o2b5ob2ob4obo2bo4b12obob6obob13o2bob3ob4o2bob2o2b2obo
bob2obob3obo2b2ob4obobo$2b2obo2b12o2bobob4obob3obobo3b2obobo2bob3obobo
bob3ob2ob2o4b2o2b4ob4obob2obobob6o3b14obob2ob8obobobobob2o3b2obob6ob2o
bobobobo$o3b6obob3o2bob4obob8ob2ob3ob5o2bob9ob2obob7o2b5o3b6o2b5obobob
4obob14o3b4obob12ob2o2b3ob3obo2bob3o2bobo$o4b12obob3obobob2o2b2obo3b2o
3bob4obobobobobobob2ob6ob3ob2ob10ob3obob9o2b2o2b5o2b4obo3b3obob2obobob
obo2bo2bob3o3bob4ob4o2b2o$2o2b5ob2ob4obobo2b7ob4ob4o2b2obo2b16obobobob
3ob15obo2b3obobobobob3obob4ob5o3bo3bob11o3bob3ob2ob7o2b3o2b4o$3obobobo
bobob9obobobob2obobob2o2bobo2b6ob5obobobob6obob2obo2b5ob5o2bobob12o2b
4obob4o6bob3obo2bobob3ob2o2b7obobo2bob2obobobo$o2b3obo2b2obo2b2obob12o
3b2o2b6obobo2b11obo3bo3b3ob2o2bob8ob4obobobob2o2b8obob6ob3obo2b5ob5o3b
ob4ob3obob6ob5obo$obob2ob4ob3ob2ob2obobobob2obo3b2o2bobobobob4ob8obobo
bobo4b5obo2bob6obo2b10obobo6bob2obobobo2b3ob4obob2o5b7ob2o2b2o2b3o2b4o
bo$3bob4o4bob4ob4obo3b2obo2bo2bobob8ob6o5bobob4o2b9o7b3ob3obo3b8o2b2o
2bob2obo2bobobobobob4ob3o2b4obobobobo2bob4obo2bo4bo$o3b2ob3ob4obob2ob
2o5b4ob2obob2obobobob4o2b5o5bobobob13obo3b2obo2b4ob7obobob2obob2obobob
4obo2b12ob4ob3obo2bobobobo2bob2obo$2b2o2bo3bob2obobob2ob3ob5obobobobob
ob5ob3ob5ob3obobobobob6o2b6o3b8obo2bob12o2b7o2bobob2o2bo2b5obo3b3obobo
b2obobobobo2bobo3bo$ob3o2b2o2bo2bobob3ob10obob3obobobobob3obobobobobob
obobobo2b7ob6ob8o2b3o2b2ob3o2bob17o2bo2bo2b2ob5o2b2obobob4ob3ob4o4bo$
2bo4b4ob4ob5ob2obob3obobob5obobo2b3o2b5o2b4ob4obob3o2bobo2b2obo4bob2o
2bo2b2ob4ob2o2bo3b15ob3ob3ob2obobob3obobo2bobob2ob2o2b2o4bo$o2bo2bobob
o2b2obob12obobobob3obobobo2b3o2bobob7ob2obob4obo3b3ob4o2bobobobo2bob2o
b3obo2bobob13o6b5ob2ob5obob4obo2b3obo2b3o$3bo3bob2o2bobob10ob3obobobob
5ob2o3bobob2obob8obobobobobobo2b5ob3o4b2o2bobo2b9ob25o2b11ob4o2bob6obo
4bo$o2bobob2ob7ob10o4b2obob3ob3o3bo2b4obobob3ob3o2bob7o3b4o2bo2bo3b2ob
ob2o2b2obobobobo2b4obobo2b2ob5o2b3o2bo2bo2b2ob3o4b4obobo2bo$5bobo5bobo
b13ob3ob3o2b7o2bobob2obobob2ob2ob2obobobobo3b9ob4ob2ob2ob2o2b2o2b6obob
6ob2ob11o4bobobob2obo7bobobo6b2o$3obo2bob16o2b2obob4o2bob13ob2obob3ob
2ob2o2b5obob4o3b3ob3obo2bo2b2obob3o2bobob2o2bo2bo2b3o2b9obo2b3o2bob5o
3b2o2bobo2bobo2b2o$3o2b4ob2obob6obobo5bo6b5o2b9obobobobob3obobo2bob3ob
obo3b4obo2b3obobo3b3ob14ob15o2bo2bobo2bob5ob4o3b3obo$2bo3b2obob2ob9o5b
o2bo3b19ob7ob5obob2obobobob3obo2b2o2bo2bob2ob2o2b7obo3bobobob16ob4obob
11obob2ob3obobo2bo$obobobobobob10obob2ob4obo3b2obob10o2b3obob3ob4o5b5o
b4o3b4obo3b2o3b2ob3obob4obo2b12o2bo2bo5b2ob2ob9ob7o2bo$o6bobob2obob6o
2bo2b8o2b5o2b10ob3ob2o2b10obobob4obo4bobo2b2o2b4obobo2bobob2ob4ob10obo
bobobob4o2bob8obob3ob7obobo$2b2ob2o3bobobo3bo2bobob10o2b4o2b12ob2o2b2o
bo4bob2ob5obo2b2o3b3obobo3b7o2bobo4bob2ob3ob8obobobob5obob10o3b6ob2o$o
2bob2ob2ob6ob3obobo2b2o2b8o2b2ob3ob3ob2o3bobo2bobo2b8obob3o2b4ob3ob4o
4bobobob4ob4ob10o2b5obobob10ob2obo6b3ob4obo2bo$3bob2o3bobobobo3b2ob3ob
ob2ob4o2bo2bob2obob8o2bobobob12obobobobobo3bobobobo2b8o3b4obobobobob3o
b10obobob2ob6ob3o4bobobo2bob2o$3obo2b18obobo3b6ob3obobobo2b6obob3obobo
2b5obob7obo2bo2bobobobo2b4obobobo2bob13obo2b5obobob7ob5o2b2o2b5obob2ob
2o$3o2bo2bob8o3bob3obo4b2o2bo2b3ob4o3bob8ob15obobobobo2bo2bobobobob11o
2b3obobobobob7ob4obobobob2ob3obo2bob3ob2obo2bob4ob2o$2b2obobobob11obo
2bo3b4ob3obo2bob2o3b2ob4obob7o2b3obob12o4bobob11obob4obob9ob2obob2o2b
3obob3o6b5obob9o$o3b3ob2ob3o2b7o2bobob3o2bo2b2ob6o2b5obob4ob6ob10obobo
b4o2bob2ob19o4b2obobobob2ob2ob4obob4obo2b4ob3obobob2ob2o2bo3bo$2bob5ob
ob2ob8ob5ob2ob4ob3obobob3ob17o3bobob13ob12ob4obobob19ob2o6b3o2bo3bob2o
bo3b6obo2b2o$3ob11ob3obob8ob2o4b12obobobobob2ob2ob3o3b4o2b4ob6o3b7o2b
14ob7obobo2bob3obob2o2b8ob2ob3o4bob4o3bo3bo$2b3obobobobobo3b2o2b7obobo
2b2ob4ob2obob2ob5o2bobob3obo2bo4bob3ob8o2b8obob4ob5ob2ob9o4bobob2obobo
b3ob3obo3b4o2bobobo2bo2bobo$o2b2ob2obobob3obob3ob7ob3o3bob2obobob2ob2o
bobob4o5b4obobob3o2bob5ob7ob7obobo5bo2b9o4b3ob7obob2obobob4obob7obo7bo
$6bob3obobobobob10o2b2ob12ob4ob2obobobobo2bo3bob8ob3ob17obo2b4ob7ob5o
2b11o3b2obobobobobob6ob4ob2obobo$ob2ob2o3bo2bobobo5bo2b2obo3b2o2b6obo
2bobo5b7obobo3b6ob2obobobobo3bobob9o2b3o2b2ob3obo2b3o2b2obobob7o3bob2o
2bobobob9obo7bo$3b9obo2b3o2bobobob3ob4o2b6obob7obobobob6o2bob2ob2ob2o
2bobo3b5o2b8obo2bo2b4ob2o4bob2ob7o2bobob4obob3obobo2b5obo2bob2obobo$ob
ob2o4bob4obob2obob2ob2o3bobo2b7ob13obo3bob6o3bobob4o3bobobo4b6obobobo
3bob8o4bob3ob2o3b10o3b2o2b11obobobo3bo$3b2obob3obobobob6ob3o2b2obob9ob
4o2bo2b3obo2bobob4obo2bob3obobob2obobo2b6obobobobob10o3b3o3bobo2b2o2b
3ob3obobo2bo2b2ob8o3bob2o$obob2obo2b2obobobo3b7o2bo2b9ob6ob2obob6ob3o
2b2ob5ob11obo3bob2obob4o2bobob7o7b9obo2bo2b5obob12ob2o3bob3obo$3bob3ob
3o2bobo2b11o2b2ob5obobobob2obo2bo2b3o4b7o3bobob5obob5ob6obob9o2b2obob
2o4bo2bobo4bob2ob4obob2obobo4b5o2b2o3b2o$ob2obob3obo3bob14o2bo2b9obo2b
3ob6o3b13ob12o2b5o5b4obobob6o2bob3obo2bob3o2b3ob3ob3ob6obob5obo2bobobo
bobo$4bo5bo3bobo2b10obo2bobobobob7ob3ob5o2b14obobobobob10o2b10ob2ob5ob
ob2o2b2obo2bob2ob5ob2o2bo2bob4o2b4ob2obo2bo2bo$o2bo3bo4bobob10ob2ob2ob
12ob10obob5o2b11ob10o2b2ob4ob4obob2obobo3bob4obobobo2b5o2b2o5b7obobob
3ob3obobobobo2bo$4b2o3bob2obo2b11ob5obobob6o4b7ob5obo2b6obob5obobob3o
2bo2bobob6o2bobob3obob3o2b3obob2obobobob2ob3o2bob9ob9ob2o$o3bob5o2bo2b
10o3bo3bob10o2bo2b5obo2bob2ob4o2bob7o2b4obob2o4b4ob5o2bobobobob4obobob
ob4obobo2b3obo2b5obobob3obobobobo3bobo2bo$5bob7o2bobob3ob2ob6obo2bobob
4ob2ob5o2b6obob7o2b7o2bobobob3o2b2ob6obo2bob14obob2obobobobo5bobo2bob
2ob2ob11ob3o$o2b2ob10o5b3ob2o2bobob8obob8ob2obobobo5bo2b13ob4obo3b3ob
2ob5o2b3o3bo2bobob2ob2obo2bobob6ob6o2b5o2b3obobob4o5bo$2bo3bob8o4bob7o
bobobo2b7obob5o3bobobo2b4obobob2ob5ob3o2bobobob6ob2o2bob2obobobob7o3b
2o2bobobobob4ob4ob2obob3o2b10o3b2o$o2b3ob8o2b3obobo3b3obob4obobobob4ob
4o4b3o8b2ob4obo2bobob6obob9ob2o2b3o3b2obob7obo2bobobob6o4b3ob2ob2obobo
2b2obob5o2bo$6b7o3bobobob2o4bobobobob8ob3o2bobobo2b9obob2obob5ob4obobo
bobo2bo4b3obo2b4obob4o2bob2o4bobobobob6o2b3obo2bob4obob8obo$ob2obob9o
2b2obobo2bob2obob3o2b3obobobob2ob2o2bo4b3obobobob2obo2b2obo2b6ob4obobo
b7o2bob3ob3ob2obobob2ob2obobob7obob3obobob3obobobob7o2bo$2bobobob6o4b
3obobob5obobobob11o2bobo2bobo4b5ob4ob2o2b4obob3obobobob3obobo2b3ob7ob
2ob3o2bobob2obob2ob4ob3o3bobo2bobo4b11o$2obobob8o3b2obobobo3bob2ob7obo
bo2b4obob2obob6obobo2bobobobo3b2obobobobobobobobob2o2bo2bobo3b3o2bobo
2bob4obob2ob6o4bo2bobobob2ob2obo2b5o2b2o$b4ob6obo2bo2bo2bobobobobo2bob
o2bobob5ob2obobobo4b3o2bobo2bobobo3b4ob3ob3obobobo3bobob3o2b6obobobobo
4b4ob5ob11obob4obobo2bob5o2bo$b3obob3o2b4ob2ob2obo2b2o4bob4o2b5o2bobo
2b5o5b2o5bobo2bob2o3b3obo2bobo2b2ob2ob3obo3bob5o2b6o2b3o2b6ob4o2bo2b3o
b2obo5bobo2bo3b2obo$b2ob3obo2b2obobo2bo2b2o2bob4ob2o3b7o2b3o5b2o3bob2o
bob6o2b3obobob4ob5ob2obob3obob2o2bo2b8ob7o2b6o2b4obo6b3ob2o5bob5ob2o$b
ob6obo2bobo5bobob3ob2obobob4o5b2o2bobo2bobobo8b3ob2o2bo4b2obo2b3o3b2o
4bob3o4b5obo2b2obob2o6bob3o2bobo3bobo2b3o7bobo4bobob3o$2bob3o2bobo2bo
10b3o6bob4ob2ob4o4b3o4bo9bob2o2bo3bobobo2b3ob3o2bobobobobobo6b3o3bo2bo
b3o2b4o2b2obob3o3b3o4bobo2bobo6b4o$o2bobo22b4o8bobobo3b4o3b4o7bob2obo
8bobo8bo3bob3obo8b4o5b4o3b2o3bo3bob2obo5b2o19bo3bo$2obobobobobobobobob
obobo2bobo2bobob2obob2ob2obobo2bobobo2bobobob2ob2ob2obobobob2ob2obobob
obobob2ob2ob2obobobobo2bobobobo2bobob2ob2ob2ob2ob2ob2obob2obobobobobob
obobobobob3o!
Attachments
examples.tar.gz
(247.91 KiB) Downloaded 206 times

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

Re: Use Smoothiness to classify rules

Post by BlinkerSpawn » March 8th, 2017, 11:23 pm

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]

Image

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

Re: Use Smoothiness to classify rules

Post by shouldsee » March 9th, 2017, 5:27 am

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.

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

Re: Use Smoothiness to classify rules

Post by BlinkerSpawn » March 9th, 2017, 9:37 am

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]

Image

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

Re: Use Smoothiness to classify rules

Post by shouldsee » March 9th, 2017, 10:45 am

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.

Post Reply