-------------------------------------------------
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.
Good work.
ReplyDeleteThe two days of brute force algoritm also works.
I found another solution that is almost 100% simetrical over an horisontal axis.
alex