The goal of this program is to explore the ability of a genetic algorithm to produce the most complexity (defined as how much non-cyclic activity occurs) with the smallest initial state, within John Conway's "Game of Life".
The simulation has 4 rules, as others have described it:
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
My fifth rule is that, outside the edges of each "world", the cells are considered dead.
Each simulation is scored by:
- [number of iterations before cyclic stability] / (1 + [number of initial cells/blocks])
For each generation, the two highest scoring simulations are combined to spawn variations for the next generation.
As the generations continue, the trend is more complexity with fewer starting blocks.
Related Articles
Styles
canvas {
border: solid 2px grey;
}
.statpanel {
padding: 15px;
border: solid 1px #ddd;
margin: 10px 0;
}
#controls, .statpanel .row {
padding: 5px 0;
}
#controls input {
padding: 5px;
border-radius: 10px;
}
div.note {
font-size: 0.9em;
font-style: italic;
padding-left: 10px;
}
#logoutput {
height: 300px;
overflow: scroll;
}
#startsim {
padding: 15px;
border-radius: 7px;
font-size: 1.15em;
}Scripting
//Constants
var rwidth = 300; //Width of canvas
var rheight = 200; //Height of canvas
var div = 2; //Cell width
var historyDepth = 24; //Complexity history analysis depth
//Calclated/loaded/temp
var canvasInitial, canvasFinal;
var gwidth = rwidth/div,gheight = rheight/div; //Calculated grid width/height
var log_output = "";
var generation_index = 0;
$(document).ready(function() {
$("#startsim").bind("click", function() {
canvasInitial = document.getElementById('canvasInitial');
canvasFinal = document.getElementById('canvasFinal');
$("article canvas").each(function() {
//Set up drawing context
var ctx = this.getContext("2d");
this.width = rwidth;
this.height = rheight;
ctx.width = rwidth;
ctx.height = rheight;
});
//Establish each canvas grid
$("canvas.simulate").each(function(i) {
$("#startsim").hide();
var code = randomGeneticCode();
//Initial grid, with random bits
var grid = newGridFromCode(gwidth,gheight,code);
var ctx = this.getContext("2d");
var canvas = this;
$(this)
.data("ctx",ctx) //Drawing context
.data("code",code) //Genetic code
.data("grid",grid) //Current grid
.data("history",false) //Grid history (none, initially)
.data("totalSteps",0) //Total change/energy generated
.data("initialState",calcGridState(grid)) //How many blocks did we start with?
.data("initialGrid",grid) //Initial setup
.data("status",1); //Calculation status
//Main engine
setInterval(function() {
//Skip frame if pending (so we don't stack calls)
if ( $(canvas).data("status") == 2 ) return;
//Skip frame if inactive
if ( $(canvas).data("status") == 0 ) return;
$(canvas).data("status",2); //Calculation pending
//Calculate grid
var newGrid = calculate($(canvas).data("grid"));
//How far are we making it?
var totalSteps = $(canvas).data("totalSteps");
totalSteps += 1;
$(canvas).data("totalSteps",totalSteps);
redraw(ctx,newGrid,$(canvas).data("totalSteps"));
$(canvas).data("grid",newGrid);
$(canvas).data("status",1); //Active; calculation done
//See if it's in a stable state
var counter = incrementHistory(canvas);
if ( counter == 60 ) {//When 2,3,4 and 5 frame animation cycles will all line up
//... if they do, and the frames match, we're likely stable
//Stable state - simulation complete
if ( !isStillActive(canvas) )
$(canvas).data("status",0)
pushHistory(canvas);
}
},15);
});
//Monitor simulations, and run meta simulation
setInterval(function() {
//Are any still going?
var isStillGoing = false;
$("canvas.simulate").each(function(i) {
if ( $(this).data("status") )
isStillGoing = true;
});
//Tally results and start new generation
if ( !isStillGoing ) {
//Find two best
var scores = [];
$("canvas.simulate").each(function(i) {
//How far it got, per initial blocks it took to do it
var score = $(this).data('totalSteps') / ($(this).data('initialState')+1);
scores.push({
score: score,
scoretext: $(this).data('totalSteps') +"/"+ ($(this).data('initialState')+1),
initialState: $(this).data('initialState'),
totalSteps: $(this).data('totalSteps'),
start: $(this).data("initialGrid"),
end: $(this).data("grid"),
code: $(this).data("code"),
sortproc: false
});
});
//Sort by score
var sorted = [];
for(var i = 0; i < scores.length; i++) {
var max = -1;
var index = -1;
for(var i2 = 0; i2 < scores.length; i2++) {
if ( !scores[i2].sortproc && scores[i2].score > max ) {
max = scores[i2].score;
index = i2;
}
}
if ( index >= 0 ) { //Found a max
sorted.push(scores[index]);
scores[index].sortproc = true;
}
}
//Display results of top score
redraw(canvasInitial,sorted[0].start,false,"Start");
redraw(canvasFinal,sorted[0].end,false,"End");
generation_index++;
$("#statGen").text(generation_index);
$("#statScore").text(sorted[0].score);
$("#statInitialBlocks").text(sorted[0].initialState);
$("#statIterations").text(sorted[0].totalSteps);
logoutput("Generation " + generation_index + "\n Top Score: " + sorted[0].score + "\n Initial blocks: " + sorted[0].initialState + "\n Total iterations: " + sorted[0].totalSteps);
//Combine the top two, and
//Restart all
$("canvas.simulate").each(function(i) {
restartCanvas(this,sorted[0].code,sorted[1].code);
});
}
},1000);
//Restarts a canvas
function restartCanvas(canvas,code1,code2) {
var ppt = parseInt($("#control_ppt").val());
if ( ppt < 0 ) { ppt = 0; $("#control_ppt").val(0); }
if ( ppt > 1000 ) { ppt = 1000; $("#control_ppt").val(1000); }
var code = combineCode(code1,code2,5);
//Initial grid, with random bits
var grid = newGridFromCode(gwidth,gheight,code);
$(canvas)
.data("grid",grid)
.data("code",code) //Genetic code
.data("initialGrid",grid) //Initial setup
.data("history",false) //Grid history
.data("lastState",0) //Last energy state
.data("totalSteps",0) //Total change/energy generated
.data("initialState",calcGridState(grid)) //How many blocks did we initially need?
.data("status",1); //Calculation status
}
});
});
/*
Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by over-population.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
*/
function calculate(grid) {
var next = newGrid(gwidth,gheight,true);
var w = grid[0].length;
var h = grid.length;
for(var ey = 0; ey < grid.length; ey++) {
for(var ex = 0; ex < grid[ey].length; ex++) {
var count = 0;
count += (ey > 0 && grid[ey-1][ex] ? 1 : 0);
count += (ey < h-1 && grid[ey+1][ex] ? 1 : 0);
count += (ex > 0 && grid[ey][ex-1] ? 1 : 0);
count += (ex < w-1 && grid[ey][ex+1] ? 1 : 0);
count += (ey > 0 && ex > 0 && grid[ey-1][ex-1] ? 1 : 0); //top-left
count += (ey > 0 && ex < w-1 && grid[ey-1][ex+1] ? 1 : 0); //top-right
count += (ey < h-1 && ex < w-1 && grid[ey+1][ex+1] ? 1 : 0); //bottom-right
count += (ey < h-1 && ex > 0 && grid[ey+1][ex-1] ? 1 : 0); //bottom-left
if ( !grid[ey][ex] ) {
next[ey][ex] = (count == 3);
} else {
if ( count < 2 )
next[ey][ex] = false;
else if ( count == 3 || count == 2 )
next[ey][ex] = true;
else if ( count > 3 )
next[ey][ex] = false;
}
}
}
return next;
}
//Redraw grid canvas
function redraw(obj,grid,steps,label) {
var ctx;
if ( obj.nodeName == 'CANVAS' ) {//If it's a canvas instead
ctx = obj.getContext("2d");
} else //Is a context
ctx = obj;
ctx.fillStyle="#000000";
ctx.fillRect(0,0,rwidth,rheight);
ctx.fillStyle="#00ff00";
for(var ey in grid)
for(var ex in grid[ey]) {
if ( grid[ey][ex] )
ctx.fillRect(ex*div,ey*div,div,div);
}
ctx.fillStyle="rgba(0,0,0,0.65)";
if ( label )
ctx.fillRect(0,0,100,15);
if ( steps )
ctx.fillRect(0,rheight-15,100,15);
ctx.fillStyle="#ffffff";
ctx.font = "13px Arial";
if ( label )
ctx.fillText(label,2,11);
if ( steps )
ctx.fillText("S: " + steps,2,rheight-2);
}
//Creates a new grid
function newGrid(w,h, blank) {
var list = [];
for(var i = 0; i < h; i++) {
list.push([]);
for(var i2 = 0; i2 < w; i2++)
list[i].push(blank ? false : bit());
}
return list;
}
//Creates a new grid from code
function newGridFromCode(w,h, code) {
var list = [];
for(var i = 0; i < h; i++) {
list.push([]);
for(var i2 = 0; i2 < w; i2++)
list[i].push(0);
}
//Add code
for(var i in code) {
list[code[i][1]][code[i][0]] = true;
}
return list;
}
//Random bits
function bit() { return Math.random() < 0.4; }
function randInt(m) { return Math.floor(Math.random() * m); }
//Returns true if canvas is still "active"
//If the current frame is identical to the historical frame, we've reached a stable state
function isStillActive(canvas) {
var history = $(canvas).data("history");
if ( !history )
return true; //We haven't taken our first frame yet
var grid = $(canvas).data("grid");
for(var ey = 0; ey < history.length; ey++) {
for( var ex = 0; ex < history[ey].length; ex++) {
if ( history[ey][ex] != grid[ey][ex] )
return true;
}
}
return false;
}
//Pushes current state into the history last frame
function pushHistory(canvas) {
$(canvas).data("history",$(canvas).data("grid"));
$(canvas).data("historyCount",0);
}
//Incrmeents history counter and returns current
function incrementHistory(canvas) {
var count = $(canvas).data("historyCount");
if ( !count )
count = 0;
count++;
$(canvas).data("historyCount",count);
return count;
}
//returns what ratio of grid is set
function calcGridState(grid) {
var total = 0;
for(var ey = 0; ey < grid.length; ey++) {
for( var ex = 0; ex < grid[ey].length; ex++) {
total += grid[ey][ex] ? 1 : 0;
}
}
return total;
}
//Generates a genetic code
function randomGeneticCode() {
var length = Math.floor(Math.random() * (gwidth*gheight-100))+100;
var code = %5b%5d%3b.html
for(var i = 0; i < length; i++) {
code.push([randInt(gwidth),randInt(gheight)]);
}
return code;
}
//Combines two genetic codes
function combineCode(code1,code2,ratePerThousand) {
var maxlength = code1.length > code2.length ? code1.length : code2.length;
//Randomly combine from one bit to the next
var newCode = [];
for(var i = 0; i < maxlength; i++) {
if ( i > code1.length-1 )
newCode.push(code2[i]);
else if ( i > code2.length-1 )
newCode.push(code1[i]);
else {
//Randomly choose one over the other
if ( Math.random() > 0.5 )
newCode.push(code1[i]);
else
newCode.push(code2[i]);
}
}
//Random mutations
var newCodeMutated = [];
for(var i = 0; i < newCode.length; i++) {
if ( Math.random() * 10000 < ratePerThousand ) //Point mutation
newCodeMutated.push([randInt(gwidth),randInt(gheight)]);
else if ( Math.random() * 10000 < ratePerThousand ) {} //Point deletion
else if ( Math.random() * 10000 < ratePerThousand ) { //Point insertion
newCodeMutated.push(newCode[i]);
newCodeMutated.push([randInt(gwidth),randInt(gheight)]);
} else {//Normal copy
newCodeMutated.push(newCode[i]);
}
}
return newCodeMutated;
}
//Log to screen
function logoutput(str) {
log_output = str + "\n" + log_output;
$("#logoutput").text(log_output);
}
This will be applied each new generation.
Simulations for current generation
When all have reached a stable state, the top two will be combined for the next generation.
Generation Best Configuration
Generation:
Score:
The score is the ratio between iterations and initial blocks. So if it goes 1000 iterations, but started with 2 blocks, the score is about 500.
Initial blocks:
Iterations: