Conway’s Game of Life (Evolutionary Algorithms Part 1)

This is the first in a series of posts about natural-world inspired algorithms, building up from simple cellular automaton to more complex examples of evolutionary algorithms and their applications.

The following example dates from the 1970’s and is one of the first attempts at describing natural processes utilizing modern computer science. Conway’s Game of Life is a clear example of how given very simple rules and boundary conditions, complex patterns can emerge. The full C# implementation is available here. The implementation provided sacrifices efficiency for readability – for a much more efficient opensource implementation see Golly.

Simulation Structure

var brd = GetInitialBoard();
var rules = GetDefaultRulesArray();
Console.WriteLine("Initial Board:");
OutputBoardToConsole(brd);
		
for(int i=1;i<=25;i++)
{
   Console.WriteLine(string.Format("Generation {0}:",i));
   IterateWithRules(brd,rules);
   OutputBoardToConsole(brd);
}
Console.WriteLine("End of Simulation");

This Life simulation is set to run for 25 generations to demonstrate the behavior of an oscillator traversing down the grid. Note the repeated call to the ‘IterateWithRules’ method – this is the method that performs the heavy lifting. The pattern is similar to that of optimization and search algorithms where the boundary conditions are defined independently of the algorithm itself. In this case, the boundary condition is running the simulation for 25 iterations, but it could just as easily depend on features of the grid (how many cells are alive/dead, whether specific shapes are present, percent of grid ‘filled’, etc.).

glider_gen4 glider_gen21-25

Simulation Rules

These are the rules of the game:

return new int[9]{0,0,1,2,0,0,0,0,0};

They are the default rules for Life. The array index represents the number of neighbours for any given cell (0-8), and the value of the array cells describe the behavior for a given amount of neighbours. A value of 0 means the cell will die, a value of 1 means a living cell will survive, and a value of 2 means an empty/dead cell will come to life (ie populate). Given these rules and a seed layout the simulation is set. This is all done in the IterateWithRules method:

public static void IterateWithRules(bool [,] board, int[] rulesArray){
	var dieList = new List<Tuple<int,int>>();
	var birthList = new List<Tuple<int,int>>();
		
	for(int i=0; i<board.GetLength(0);i++)
	{
		for(int j=0; j<board.GetLength(1);j++)
		{
			var currentCelVal = board[i,j];
			var neighbourCount = GetNeighbourCount(board,i,j);				
			var rule = rulesArray[neighbourCount];
			if (currentCelVal && rule==0)
				dieList.Add(new Tuple<int,int>(i,j));
			else if (!currentCelVal && rule==2)
				birthList.Add(new Tuple<int,int>(i,j));				
		}
	}
	Console.WriteLine(string.Format("{0} cells died. {1} cells were born",dieList.Count,birthList.Count));
	foreach(var d in dieList)		
		board[d.Item1,d.Item2] = false;	
	foreach(var b in birthList)		
		board[b.Item1,b.Item2] = true;	}

Following this logic (and much more optimized code), along with the appropriate initial layout, a program was written to represent a full-blown Turing Machine. It is a powerful example of a general-purpose algorithm that can govern and generate arbitrarily complex emerging behaviors.

Next Steps:

  • Optimize the implementation provided for
    • a) smaller memory footprint (consider using quadtrees)
    • b) more efficient iteration processing  utilizing a list of ‘changed’ cells carried forward from one iteration to the next.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s