I've tried to create a software in Python that uses genetic algorithms to face Conway's Game of Life.
Game of Life, simplifying a bit, is a model that simulates how entities survive and evolve according to certain rules. The game takes place on an infinite grid made up of square cells. Each can have only two states: Live / Death (or Populated / Empti)
First, the grid must be populated: it is defined how many cells are alive and their position. Then, as time goes on, the grid changes according to these rules:
The software must be able to find the initial layout of live cells that survives the longest.
In order to write the game I've used tkinter module, that allows to build the interface and graphical elements with relative ease.
The game is completely handled by class Game, that for now contains:
How the three rules are applied:
if self.grid[i][j] == 1 and nearby<2: #1
self.parallel_grid[i][j] = 0
if day==1 and nearby == 0:
alone_first_day = alone_first_day + 1
elif self.grid[i][j] == 1 and nearby <= 3: #2
self.parallel_grid[i][j] = 1
elif self.grid[i][j] == 1 and nearby > 3: #3
self.parallel_grid[i][j] = 0
elif self.grid[i][j] == 0 and nearby == 3: #3
self.parallel_grid[i][j] = 1
The initial population consists of a set of 100 random layouts of 10 live entities on the grid.
Setting up the initial population:
...
self.population = [[[0 for x in range(2)] for y in range(self.pop_size)] for z in range(100)]
...
def generatePopulation(self):
self.population = self.rand.randint(self.grid_size, size=(100, self.pop_size, 2))
Each layout of the initial population plays the game and is given a score. This score is based on: how many days it has survived, how many cells were live the cycle before the extinction, how many cells were isolated at the beginning and the starting number of live cells.
The fitness function I decided to use is:
self.fitness[popolazione] = day + (count_alive/(self.pop_size * 1.0)) - (alone_first_day/(self.pop_size * 100.0))
Mutations are probably one of the most delicate part of the algorithm: it must be decided which layouts of the population must be discarded, which must be saved and how should they mutate in order to generate the next population.
I've decided to save the best layout of the population, that is the one that obtained the highest fitness score. The new generation's layouts will have 10% chance for each single coordinate of its cells to mutate, that is being substituted by a random number, and 90% chance of being the same as in the best layout.
The code that handles the mutation:
def mutatePopulation(self):
best_individuo = [[0 for x in range(2)] for y in range(self.pop_size)]
best_score = 0
for i in range(0,100):
if self.fitness[i] > best_score:
best_individuo = self.population[i]
best_score = self.fitness[i]
rand_coordinates = self.rand.randint(self.grid_size, size=(100, self.pop_size, 2))
mutation_rate = self.rand.randint(100, size=(100, self.pop_size, 2))
print(self.generation, "MIGLIOR SCORE:", best_score)
self.population = [[[0 for x in range(2)] for y in range(self.pop_size)] for z in range(100)]
self.population[0] = best_individuo
for p in range(1, 100):
for d in range(0,self.pop_size):
for c in range(0,2):
if (mutation_rate[p][d][c] < 10):
self.population[p][d][c] = rand_coordinates[p][d][c]
else:
self.population[p][d][c] = best_individuo[d][c]
self.generation += 1
Once the game is ready and the genetic algorithm is set, all the software has to do is repeating the play-evaluate-mutate cycle and observe wether the algorithm improves the way it plays the game.
game = Game()
game.generatePopulation()
game.update_score()
tk.update_idletasks()
tk.update()
time.sleep(1)
game.play()
while True:
game.mutatePopulation()
game.play()
The algorithm is able to improve remarkably its score: in most of the cases, and in relatively few generations, it becomes capable of surviving at least five cycles. Moreover, it can be noticed that there is a tendency of selecting layouts where the cells are grouped closer to each other.
However, in the simulations I have run, the algorithm has never found a layout able to survive forever or to cause a drastic increase in the score between two generations: the score tends to stagnate after a while. In addiction, it should be considered that the software ignores the layouts that remain still as time goes on (and that would survive forever), since the algorithm may get stuck in solutions that are not that interesting.