Langton's ant Or order out of chaos

This time we will talk about Langton's ant - the simple system of simple rules, but with complex behavior. Simple system of Langton`s ant is defined as :
* At a white square, turn 90° left, flip the color of the square, move forward one unit
* At a black square, turn 90° right, flip the color of the square, move forward one unit
This is so called L/R system. But what if for the one color we will have not the one direction, but the direction chain ? That is- for the white squares we will have some chain of 'LRLRR...' events and for the black squares we will have another chain of 'RRLRRL...' events ?? Then we will get so called turmite - a 2D turing machine. So this experiment tests this turmite idea of multiple direction row for the same color. Experiment python script is this:

---

from Tkinter import *

rs = raw_input("Enter rule set (e.g.: L/R) => ")
str0 = rs.split('/')[0]
str1 = rs.split('/')[1]   
i0, i1 = -1, -1
w,h = 500, 500
lx,ly = w/2, h/2
dirx,diry = 0,-1

# defining absolute directions
vec = {
    (0,1,'L'):(1,0),
    (1,0,'L'):(0,-1),
    (0,-1,'L'):(-1,0),
    (-1,0,'L'):(0,1),
    (0,1,'R'):(-1,0),
    (1,0,'R'):(0,1),
    (0,-1,'R'):(1,0),
    (-1,0,'R'):(0,-1)
    }
mod = 2
grid = dict([((x,y),0) for y in range(0,h,mod) for x in range(0,w,mod)])

# Initialize Tk window
root = Tk()
ant = Canvas(root,width=w, height=h, bg='white')
ant.pack(fill=BOTH)

while 1:
    if lx < w and ly < h and lx > 0 and ly > 0:
      if grid[(lx,ly)] == 0:
        i0 = (i0+1)%len(str0)
        rdir = str0[i0]
      elif grid[(lx,ly)] == 1:
        i1 = (i1+1)%len(str1)
        rdir = str1[i1]
      dirx, diry = vec[(dirx,diry,rdir)]
      grid[(lx,ly)] = grid[(lx,ly)]^1
      col = "white" if grid[(lx,ly)] == 0 else "darkorange"
    ant.delete("current")
    ant.create_rectangle(lx, ly, lx+mod-1, ly+mod-1, fill="black",outline="black",tags="current")
    ant.update()
    ant.delete((lx,ly))
    ant.create_rectangle(lx, ly, lx+mod-1, ly+mod-1, fill=col,outline=col,tags=(lx,ly))
    lx,ly = lx+dirx*mod, ly+diry*mod

---

Results are somewhat interesting. At first, the classic Langton`s ant example-

Can we have system with shorter steps to "highway" ? Seems - yes we can. This is it:

But this is not the end. There is system which is almost "highway" from the scratch:


And finally- some exotic general Langton`s ant systems:







Conclusion
Seems that systems L/R and L/LRL is unstable and switches to stable system L/RLL.
Another conclusion is that there are some other systems that gets to the different types of "highway" - the order out of chaos.

Have fun with Langton`s ant !!

IBM Ponder This, May 2008 - cellular automaton

From the IBM project "ponder this", may 2008:
-------------------------------------------------
This month's puzzle is about Conway's Game of life.
The game is a cellular automaton on a grid where in each generation, every cell determines its state (dead or alive) based on its eight neighbors: a dead cell will change its state to alive if and only if exactly three of its neighbors are alive; A live cell will stay alive if and only if two or three of its neighbors are alive.
All the changes are done simultaneously.
Find a possible state of the universe whose next generation is depicted below.

....................
....................
..###..###...#...#..
...#....#.#..##.##..
...#....##...#.#.#..
...#....#.#..#...#..
..###..###...#...#..
....................
....................

"." denotes dead cells and "#" denotes live cells.
-------------------------------------------------

So after a bit of thinking i chose Selfish Gene Algorithm, which I also presented on my blog article. Please note - I will present solution which will use 4 classes from the given my blog link above. So if you need to test this solution - download the code from that article also and import these classes:
- SGAallele.cs
- SGAgenotype.cs
- SGAlocus.cs
- SGAlocusGroup.cs
Now about solution. In general - solution with the help of selfish gene algorithm, tries to evolve cellular automaton configuration which next generation is similar to the one described in problem definition. Fitness is calculated as wrong cell amount - that is cell, which is not in place of target configuration, amount. Algorithm tries to minimize that wrong cell amount. So solution is this:

---

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SGA;

namespace ConsoleApplication18
{
    class Program
    {
        static int counter = 0;
        static bool[][] grid = InitialGrid();
        static SGAgenotype gen;

        static void ShowCells(bool[][] cells)
        {
            string outp;
            outp = cells.Aggregate("", (acc1, ba) => 
                                   acc1 + ba.Aggregate("", (acc2, b) => 
                                        acc2 + ((b) ? "#" : ".")) + "\n");
            Console.Write(outp);
        }

        static bool[][] InitialGrid()
        {
            bool[][] c = new bool[9][];
            c[0] = new bool[20];
            c[1] = new bool[20];
            c[2] = new bool[] { false, false, true, true, true, false, false, 
                                true, true, true, false, false, false, true, 
                                false, false, false, true, false, false };
            c[3] = new bool[] { false, false, false, true, false, false, false, 
                                false, true, false, true, false, false, true, 
                                true, false, true, true, false, false };
            c[4] = new bool[] { false, false, false, true, false, false, false, 
                                false, true, true, false, false, false, true, 
                                false, true, false, true, false, false };
            c[5] = new bool[] { false, false, false, true, false, false, false, 
                                false, true, false, true, false, false, true, 
                                false, false, false, true, false, false };
            c[6] = new bool[] { false, false, true, true, true, false, false, true, 
                                true, true, false, false, false, true, false, 
                                false, false, true, false, false };
            c[7] = new bool[20];
            c[8] = new bool[20];

            return c;
        }

        static int LiveCells(bool[][] grid, int row, int col)
        {
            int live = 0;

            for (int i = row - 1; i <= row + 1; i++)
            {
                for (int j = col - 1; j <= col + 1; j++)
                {
                    if (i != row || j != col)
                    {
                        if (grid[i][j])
                            live++;
                    }
                }
            }

            return live;
        }

        static bool WillLive(bool IsLive, int LiveNeighbours)
        {
            bool state;

            if (IsLive)
                state = (LiveNeighbours < 2 || LiveNeighbours > 3) ? false : true;
            else
                state = (LiveNeighbours == 3) ? true : false;
           
            return state;
        }

        static bool[][] ComputeStates(bool[][] grid)
        {
            bool[][] res = new bool[9][];
            res[0] = new bool[20];
            res[1] = new bool[20];
            res[2] = new bool[20];
            res[3] = new bool[20];
            res[4] = new bool[20];
            res[5] = new bool[20];
            res[6] = new bool[20];
            res[7] = new bool[20];
            res[8] = new bool[20];

            for (int i = 1; i < grid.Length - 1; i++)
            {
                for (int j = 1; j < grid[i].Length - 1; j++)
                {
                    res[i][j] = WillLive(grid[i][j], LiveCells(grid, i, j));
                }
            }

            return res;
        }

        static bool[][] CellGridFromGenotype(SGAgenotype gen, SGAgenotype.GenomeNo num)
        {
            int row, col;
            bool v;
            int gene = -1;
            bool[][] res = new bool[9][];
            res[0] = new bool[20];
            res[1] = new bool[20];
            res[2] = new bool[20];
            res[3] = new bool[20];
            res[4] = new bool[20];
            res[5] = new bool[20];
            res[6] = new bool[20];
            res[7] = new bool[20];
            res[8] = new bool[20];

            for (int i = 0; i < gen.locusGroups.Length; i++)
            {
                row = (i) / 20;
                col = (i) - (row * 20);

                if (num == SGAgenotype.GenomeNo.FirstGenome)
                    gene = gen.locusGroups[i].loci[0].FirstGeneIndex;
                else if (num == SGAgenotype.GenomeNo.SecondGenome)
                    gene = gen.locusGroups[i].loci[0].SecondGeneIndex;
                else if (num == SGAgenotype.GenomeNo.None)
                    gene = gen.locusGroups[i].loci[0].BestGeneIndex;

                v = Convert.ToBoolean(gen.locusGroups[i].loci[0].Alleles[gene].Value);

                res[row][col] = v;
            }

            return res;
        }

        static int WrongCellCount(bool[][] previousStates)
        {
            int res = 0;
            bool[][] nextStates = ComputeStates(previousStates);

            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[i].Length; j++)
                {
                    if (nextStates[i][j] != grid[i][j])
                        res++;
                }
            }

            return res;
        }

        static SGAgenotype.CompareResults CompareCellAutomata()
        {
            SGAgenotype.CompareResults cr;
            bool[][] grid1 = CellGridFromGenotype(gen, SGAgenotype.GenomeNo.FirstGenome);
            bool[][] grid2 = CellGridFromGenotype(gen, SGAgenotype.GenomeNo.SecondGenome);
            bool[][] gridb = CellGridFromGenotype(gen, SGAgenotype.GenomeNo.None);

            int wcellsGene1 = WrongCellCount(grid1);
            int wcellsGene2 = WrongCellCount(grid2);
            int wcellsGeneb = WrongCellCount(gridb);

            cr.CompareEachOther = SGAgenotype.GenomeNo.None;
            cr.CompareWithBest = SGAgenotype.GenomeNo.None;

            if (wcellsGene1 < wcellsGene2)
                cr.CompareEachOther = SGAgenotype.GenomeNo.FirstGenome;
            else if (wcellsGene2 < wcellsGene1)
                cr.CompareEachOther = SGAgenotype.GenomeNo.SecondGenome;

            if (wcellsGene1 < wcellsGeneb)
                cr.CompareWithBest = SGAgenotype.GenomeNo.FirstGenome;
            else if (wcellsGene2 < wcellsGeneb)
                cr.CompareWithBest = SGAgenotype.GenomeNo.SecondGenome;

            counter++;

            if (counter%1000==0)
            {
                Console.Clear();
                ShowCells(gridb);
                Console.WriteLine("====================");
                ShowCells(ComputeStates(gridb));
                Console.WriteLine("====================\nPlease wait...");
            }

            return cr;
        }
        
        static void Main(string[] args)
        {
            gen = new SGAgenotype(new SGAlocus[] { new SGAlocus(0, 1, 1) }, 
                                       180, CompareCellAutomata);
            gen.AlleleAffectValue *= 0.1;
            gen.MutationProbability *= 1.5;
            gen.Evolve(400000);
            Console.WriteLine("DONE.");
            Console.ReadLine();
        }
    }
}

---

After execution we get this picture-

...............#....
.#....#.....#.....##
...##...##..........
...#....#....##.##.#
....#....##..#...#.#        ANSWER
..#.....#.....#..#..
...#....##..#.....#.
...#..#.....#...#...
....................
====================
....................
....................
..###..###...#...#..
...#....#.#..##.##..
...#....##...#.#.#..    NEXT GENERATION OF CELLS
...#....#.#..#...#..
..##...###...#...#..
....................
....................
====================

First picture is answer and second (below) is next generation of cells.
We see that this is approximate answer because next generation differs by 1 cell from the given situation in problem definition. Well, this is because I`ve used genetic algorithm which by definition is probabilistic and doesn`t guarantee to give exact solution. But very well calculates approximate solutions.
So all in all - it was fun to play with selfish gene algorithm and cellular automaton.