This project draws heavily on two fields of theory: genetic algorithms and Conway’s Game of Life. Below is some background into our methods.
Conway’s Game of Life
Conway’s game of life is a simulation meant to model population fluctuation due to scarcity, overpopulation, and breeding designed by John Conway in the 70’s. The board consists of a two dimensional array of booleans.
The rules are simple. For each square in a given iteration of the board, if that square is dead, i.e. the boolean value is set to false, and exactly three of its eight neighbors are alive, i.e. the boolean value is set to true, the square in question comes to life in the next iteration, otherwise it remains dead. If that square is alive, and two or three of its eight neighbors are alive, then the cell remains alive, otherwise that cell dies in the next iteration. Below is an example of a cell that is going to die of overpopulation in the next iteration.
|Alive||Current Cell – Alive||Alive|
Our goal is to find boards that are interesting. We plan to quantify this by measuring how long boards last before they die out, i.e. no cells come to life or die in a given iteration, or before they reach an oscillatory state, i.e. they fluctuate between a given number of changes each time.
Genetic Algorithms are often used as a way to find the optimal solution given a population of options that is repeatedly ‘bred’ ideally leading to a better measure of fitness for both the population as a whole and the individual specimens. Here is a link to an excellent and brief write up on genetic algorithms.
Field-Programmable Gate Arrays (FPGAs)
We wish to run 1000 boards for 1000 generations and at least 1000 iterations each. We have boards of size 256×256. In total, this adds up to over 65 trillion cell change operations. This would overwhelm a typical CPU and could take days to compute. This lead us to seek alternatives. One option we considered and decided to implement was the FPGA.
The problem is entirely parallelizable which plays in well to the architecture of FPGA’s and their inherently parallel nature. In total, we are computing 256 cell changes per clock tick. That is, we are computing 256 cell changes ever ten nanoseconds. Below is a high level diagram of our design.