Most Chaotic Cellular Automata

[Timeroot]

Hi, I'd just been playing around with Cellular Automata (the 1D vs. Time kind), and I was wondering what the "most chaotic" was. When I say chaotic, I don't mean like the Sierpinksi triangle type systems. There, the pattern is easily discernible. For rules like 30 and 110, you get the same triangles, but with not obivous pattern to them. For more ranges/colors, you get even more chaotic results; some areas filled with triangles, while other areas - whose distribution is totally random - have "straight" areas. For example, look at rule 185720 with r=2. Then there are rules like 185740 (with r=2) which produce boring results from simple initial conditions, but very interesting patterns from random initial conditions. I would like to see if people could come up with the "most" chaotic rules - within a certain range and number of colors. Anyone want to try?

[kram1032]

According to wolfram alpha, rule 110 is complex and rule 30 is chaotic.
And they seem to mark "the most interesting" rules out there

[Timeroot]

Keep in mind that 110 can be quite chaotic - Wolfram|Alpha checks chaos by searching for patterns down the center. The only reason it's not Class IV, or marked as "chaotic", is because it has occasional triangles. And that introduces "temporary structure". If you look at the Wikipedia article, it mentions that they interact in "complex ways". But besides, I'm more curious about other ranges or colors, as I said...

[kram1032]

the most chaotic would be the one with the most random results...
If I was capable for this (Which I'm really not^^), I'd probably try to find that out with a GA, where the fitness function is a set of randomness-checkers.
Then do a single black dot and check for the randomness of the first 1000 or so lines. Do evolution stuff and voila, after a few generations, you have your (candidate for the) most chaotic CA.

I don't think, something like that actually is found yet and I guess, that would be one of the problems, you can't actually solve, other than checking every single system.
Rule 30 is used for random generators, though there are other CAs in use which produce even "more random" results...

[Timeroot]

I like the GA idea. I have two questions: does anyone know of a relatively simple way to check randomness? Or maybe some piece of code floating around somewhere? Second, how will the mutation/recombination work? Simply changing/mixing the bits isn't very effective, because that can cause huge changes. What really needs to be done is changing the patterns. Perhaps each on/off switch in a given rule could instead be stored as a series of nots, ands, and ors of each other, and then there would just be two or three "governing bits". Two or three isn't very many, either, considering that in a 3 color, 2 range rule you have 243 bits. Then, by changing or adding some gates in the definitions of "high level" bits, that is, ones that many others depend on and don't depend on many besides the top bits themselves, we could maybe introduce rule-wide changes that would be relevant. Also, flipping one governing bit might lead to changes that make sense. For recombination, perhaps something could be done where the "father" rule donates the low-level gates, while the "mother" rule donates the high-level gates and the governing bits.

Does anyone think this would work? 

[kram1032]

of course it would but I think it's actually not that a bad idea to just use the value of a certain rule as gen and the whole set of rules as genome.

I'm trying a simpler task right now but I have an error, I can't spot... (It's the first time, I actually try to program a CA and the genetic portion comes later)

Maybe there is some useful information on that page:
http://web.cecs.pdx.edu/~mm/#Research


And here is the "spot the error" if you'd bother (most likely it's some stupid beginner mistake I do...)

Code:

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <math.h>
using namespace std;

int main()
{
    int n=128; //how many values in the array?
    int m=128; // how many iterations?
    int array[n];
    int newar[n];
    int i; //counter variables
    int j;
    int start; //variable for random binary array
    int rulev; //value of the rule
    int cellv[n]; //resulting cell value
    srand((unsigned)time(0)); //initialize random seed


    for (i=0;i<n;i++) //random rule (for binary values only for now)
    {
        start=rand()%2;
        cellv[i]=start;
    }

    for (i=0;i<n;i++)
    {

        start=rand()%2; //random sequence of 0s and 1s
        array[i]=start; //put sequence into array
    }

    for (j=0;j<m;j++)
    {
        switch (i) //torodial world rule calculation and get the new array
        {
        case 0:
            rulev=4*array[n-1]+2*array[0]+array[1];
            newar[i]=cellv[rulev];
            break;
        case 127:
            rulev=4*array[i-1]+2*array[i]+array[0];
            newar[i]=cellv[rulev];
            break;
        default:
            rulev=4*array[i-1]+2*array[i]+array[i+1];
            newar[i]=cellv[rulev];
        }


        for (i=0;i<n;i++) // print array loop
        {
            if (array[i]==0)
            {
                cout << "_";
            }
            else
            {
                cout << "#";
            }
        }

        for (i=0;i<n;i++) // replace old array with new one
        {
            array[i]=newar[i];
        }

        cout << "\n";
    }

    cin.get();
}

[Timeroot]

I found the mistake. I win! In the section

Code:

for (j=0;j<m;j++)
    {
        switch (i) //torodial world rule calculation and get the new array
        {
        case 0:
            rulev=4*array[n-1]+2*array[0]+array[1];
            newar[i]=cellv[rulev];
            break;
        case 127:
            rulev=4*array[i-1]+2*array[i]+array[0];
            newar[i]=cellv[rulev];
            break;
        default:
            rulev=4*array[i-1]+2*array[i]+array[i+1];
            newar[i]=cellv[rulev];
        }

you say switch(i), while I think you meant switch(j). Also, it might be a best practice to replace the 127 after "case" with "n-1". Good luck!

I would probably be trying something like this myself right now, but my three month old laptop has already broken down. In more than one regard. 

[kram1032]

I wanted to use n-1 but what would you think? "no variable allowed in a constant value" - switch seems to only work for non-variable values for some reason I can't really see.

The mistake you spotted wasn't the right mistake. I rewrote from scratch and found a better way to do it. At the same time, I found out that either I figured something totally wrong or modulo behaves strangely...

Here is correctly working code which just needs to be extended step by step to work as a GA. It already does produce random CAs but rather than doing this once and then throwing away both the result and the rules, I need to somehow check for what I want to reach, save, wether this goal was reached, which rule that was and how long it took to get to that result.
Then I need to do, say, 100 CAs and pick the best, say, 10.
Then, which probably is the hardest part, I need to do genetic stuff on the rules, that means, recombine all the sets and then add random variations via "crossing over".
With the new rules - hopefully 100 again, do the same process.
Now, repeat that, say, 100 times and you'll probably have a pretty good CA in the allowed conditions.
What that means is, I currently use conditions with neighbourhood 1 only. I'd need to extend that to aribitary neighbourhood.
Same goes for colours.
This extension, however, is one of the easiest and I only have to make sure, that I don't kill any int. I'll probably have to use longs for that on one spot or the other

Code:

#include <bitset>
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;

int main()
{
    int i; // count variables
    int j;
    int k;

    signed int n=61; //world size
    signed int iter=750; // amount of iterations
    signed int start[n]; //arrays
    signed int ruleset[8];
    signed int next[n];
    signed int rule;

    char execute='1'; //uservariables

    srand ( time(NULL) ); //initialize random seed

    while (execute=='1') //main loop
    {
        for (i=0;i<8;i++) //random values for rules
        {
            ruleset[i]=rand()%2;
        }
        for (i=0;i<n;i++) //random start conditions
        {
            start[i]=rand()%2;
        }
        cout<<"\n\nstart: ";
        for (i=0;i<n;i++) //test print starting conditions
        {
            cout<<start[i]<<"_";
        }
        cout << "\nrules: ";

        rule=0; //clear out previous rule
        for (i=0;i<8;i++) // test print rules
        {
            cout<<ruleset[i]<<"_";
            rule=(int)(rule+ruleset[i]*pow((float)2,(float)i));
        }
        cout << "(=rule "<<rule<<")\n\n";
        for (k=0;k<iter;k++)
        {
            for (i=0;i<n;i++)
            {
                if (i==0)
                {
                    next[i]=ruleset[4*start[(n-1)%n]+2*start[0]+start[(1)%n]];
                }
                else if (i==n-1)
                {
                    next[i]=ruleset[4*start[n-2]+2*start[n-1]+start[0]];
                }
                else
                {
                    next[i]=ruleset[4*start[i-1]+2*start[i]+start[i+1]];
                }
            }
            cout<<"|";
            for (i=0;i<n;i++)
            {
                start[i]=next[i];
                if (start[i]==0)
                {
                    cout<<"#";
                }
                else
                {
                    cout<<" ";
                }
            }
            cout<<"| "<<k<<"\n";
        }
        cout<<"\n\do you want to try again? (if yes, type 1)\n";
        cin>>execute;
    }
}

I now found a nice one in that range: Rule 45 - Check it out

EDIT: The most chaotic one I came across sofar: Rule 165

[kram1032]

I tried around with more CAs and tried to combine rule 110 with rule 30.

What I got is this:

rule 2223726873945 r=1 k=3

which has the following rules:

Code:

___->_
__1->2
__2->1
_1_->2
_11->2
_12->1
_2_->1
_21->2
_22->1
1__->2
1_1->_
1_2->1
11_->_
111->_
112->1
12_->1
121->1
122->2
2__->_
2_1->2
2_2->1
21_->2
211->1
22_->1
221->2
222->_

The pattern, created by this is quite nice
I chose the rules by the following conditions:

operations only including 1 and _ follow the rule 30 but the result is switched to 2 and _

operations only including 2 and _ follow the rule 110 but the result is switched to 1 and _

operations only including 1 and 2 are set to maximum. 2x1 and 1x2 -> 1 OR 1x1 and 2x2 -> 2

operatons, including every symbol are (hopefully) working against bias: rule 30 is slightly biased to the right because it cancels out this case:
##_ -> _
but doesn't cancel out that one:
_## -> #
rule 110 is heavily biased to the left as you already can see whilte it's building: the left side grows, the right side stays equal all the time.

So I chose to let the value win that's leftmost. (Actually, thinking about it while writing this, I guess, directional bias isn't avoided that way at all...)

Anyhow, here it is:
http://www.wolframalpha.com/input/?i=rule+2223726873945+k%3D3
A very ordered pattern on the left side, a rather random-ish pattern on the right side, with half growing speed.
Under random conditions, it's very random

What do you think about this one?

[Timeroot]

That is pretty neat... I was just playing around (randomly), and I think that 2211315363384 and 2211315363386 both give interesting patterns. ..386 reminds me a bit of spaghetti, the way the chaos forms little strings that go left and down, and then left-down. (Did that make any sense?) I've been thinking maybe simply changing one of the bits would be the best way to go when it comes to genetic algorithms, especially if you have very large rule space (say, k=5 r=5, whose rule-space size has about 34129394 digits, more than the Y chromosome gene-space), because then one single bit won't make such a world changing difference (hopefully) as in k=2 r=1. Of course, the question of how to adequately store a genome - literally, the about same degrees of freedom as a humane chromosome - becomes a new problem. With k=5 r=5, the genome takes up 11375396 bits, or 1.39 Megabytes. That's pretty big... oh dear, technology advances so slowly...

Hehe, I just realized that your DNA, the code that describes everything about you, even who you are... is smaller than many high resolution photographs. A picture is a worth a thousand words... and about 1.5 of you.  

EDIT: More playing around! 2711339563384 looks like it's dripping all over...

[kram1032]

I see, you like the oscillating ones

Interesting idea for the DNA, lol.

Well, the last rule you edited in actually also is nice with k=2 and r=3. Check it out
http://www.wolframalpha.com/input/?i=rule+2711339563384

Also, I played around with my 110 30 mix and came to this one now, doing different stuff.

rule 309295520241, k=3
It looks a lot more related to rule 30 (look at the random version) and somehow also to rule 110 (rather visible-ish in the simple starting condition version...)

Oh and for the programming part:
I tried to expand my approach to both multiple colours and bigger neighbourhoods. There is an array overflow problem which I can't spot...

Code:

#include <bitset>
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;

char test;

int main()
{


    char execute='1'; //uservariables

    srand ( time(NULL) ); //initialize random seed

    while (execute=='1') //main loop
    {
        long i; // count variables
        unsigned long j;
        unsigned long k;
        long l;
        long m;
        unsigned long n;

        unsigned long size=100; //world size
        unsigned long iter=1000; // amount of iterations
        long neighbourhood=1;
        unsigned short base=2;

        cout<<"\n\nHow big should the world be?\n";
        cin>>size;
        cout<<"\nHow many steps shall I do?\n";
        cin>>iter;
        cout<<"\nHow distant Neighbours should be know?\nPlease stay between 1-4!\n";
        cin>>neighbourhood;
        cout<<"\nHow many different elements has your universe?\nPlease keep it between 2-9!\n";
        cin>>base;

        unsigned long ruledgt=(unsigned long)pow(base,2*neighbourhood+1);

        unsigned long start[size]; //arrays
        unsigned long ruleset[ruledgt];
        unsigned long next[size];
        unsigned long rule;


        for (i=0;i<ruledgt;i++) //random values for rules
        {
            n=rand();
            while (n>=base || n<0)
            {
                while (n>=base)
                {

                    n=n-base;
                }
                while (n<0)
                {
                    n=base+n;
                }
            }
            ruleset[i]=n;
        }
        for (i=0;i<size;i++) //random start conditions
        {
            n=rand();
            while (n>=base || n<0)
            {
                while (n>=base)
                {
                    n=n-base;
                }
                while (n<0)
                {
                    n=base+n;
                }
            }
            start[i]=n;
        }
        cout<<"\n\nstart: ";
        for (i=size;i>0;i--) //test print starting conditions
        {
            cout<<start[i]<<"_";
        }
        cout << "\nrules: ";

        rule=0; //clear out previous rule
        for (i=0;i<ruledgt;i++) // test print rules
        {
            cout<<ruleset[i]<<"_";
            rule=(unsigned long)(rule+ruleset[i]*pow(base,i));
        }
        cout << "(=rule "<<rule<<")\n\n";
        for (k=0;k<iter;k++)
        {
            for (i=0;i<size;i++)
            {
                n=0;
                for (l=-neighbourhood;l<neighbourhood;l++)
                {
                    m=i+l;
                    while (m<0 || m>=size)
                    {

                        while (m<0)
                        {
                            m=m+size;

                        }
                        while (m>=size)
                        {
                            m=m-size;

                        }

                    }
                    n=n + (unsigned long)(pow(base,neighbourhood-l)*start[i-m]);
                    /*cout<<"\nn="<<n<<" & i="<<i<<" & m="<<m<<" & l="<<l<<" & k="<<k<<"\n";
                    cin>>test;*/
                }

                /*next[i]=ruleset[n];
                cout<<"\nn=";
                cout<<n;
                cout<<" & i=";
                cout<<i;
                cout<<" & m=";
                cout<<m;
                cout<<" & l=";
                cout<<l;
                cout<<" & k=";
                cout<<k;
                cout<<" & ruleset[n]=";
                cout<<ruleset[n];
                cin>>test;*/

            }
            cout<<"|";
            for (i=0;i<size;i++)
            {
                start[i]=next[i];
                //cout<<start[i];
                switch (next[i])
                {
                case 0:
                    cout<<"#";
                    break;
                case 1:
                    cout<<"*";
                    break;
                case 2:
                    cout<<"-";
                    break;
                case 3:
                    cout<<"+";
                    break;
                case 4:
                    cout<<"|";
                    break;
                case 5:
                    cout<<"/";
                    break;
                case 6:
                    cout<<"\\";
                    break;
                case 7:
                    cout<<"X";
                    break;
                case 8:
                    cout<<"O";
                    break;
                case 9:
                    cout<<"Y";
                    break;
                default:
                    cout<<" "<<next[i]<<" ";
                }
            }
            cout<<"| "<<k<<"\n";
        }
        cout<<"\nDo you want to try again? (if yes, type 1)\n";
        cin>>execute;
    }
}

I tried to help me with some debug extra lines to find exactly, where the error is positioned....
Now it runs through but after the first iteration, the same pattern just repeats over and over again and most places are just empty for overflow reasons.

I also noticed that I need a different way to handle bigger neighbourhoods and state-sets... - currently, the needed rule-array grows way too fast, so I either need a rule array that possibly exceeds a standard array's lenght by FAR or I need a totally different but equally "automatic" approach...

[Timeroot]

Actually, I don't really like oscillating ones, in general I try to avoid them. It's just that they sometimes produce results otherwise unattainable.

I'm sorry, I don't know what the error in your program is... as for the data allocation: as I just said, the sheer size is very large. If you have a rule-space with k colors and a range of r, then the size needed to hold the rule is log(k)*(k^(2r+1)). In theory, maybe the best way to work it through would be running 10 iterations or so, after a possible transient of 2, and then saving the full rule to the hard drive, leaving only the rules that were ever used in that time frame. Those could be used exclusively, and in the event of one other being needed, it would be fetched from the HDD and from then on kept in the RAM. It would be tricky to program, but might make a big difference in the maximum rule space. I don't know much about C, but in Visual Basic there's a data type called BigInt, which stores arbitrarily large not too inefficiently. During the initial "filter" phase, this might be best for storing the rule. But remember you garbage pickup! 

[kram1032]

No way to do so with the current programming method I use.
I guess, rather than a long rule array, I'd need some kind of not-array based lookup-table which could have aribitary lenght...
A hyper long switch loop or something...
However, I'm not exactly sure, wether that would be too fast or how many cases I could set behind each other. Do switches allow for more than 256 cases?

There must be a much more efficient way to do this...