Ho provato a realizzare un programma in Python che applichi algoritmi genetici al Game of Life di Conway.
Il Game of Life, semplificando un po', è un modello che simula la sopravvivenza e l'evolversi di entità sulla base di alcune regole. Il gioco si svolge su una griglia di infinite celle quadrate, ognuna delle quali può avere due stati: Vivo / Morto (o Popolato / Vuoto).
All'inizio viene definito uno stato di partenza: viene deciso quante sono le caselle in vita e dove sono. Successivamente, con ogni unità di tempo trascorso si passa allo stato successivo seguendo queste quattro regole:
Il programma deve essere in grado di trovare lo stato iniziale che sopravviva il più a lungo possibile.
Per scrivere il programma ho usato il modulo tkinter, con cui si può gestire agilmente la finestra e gli elementi grafici.
Il gioco è completamente gestito dalla classe Game, che per ora contiene:
L'applicazione delle tre regole:
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
La popolazione iniziale del gioco sarà un gruppo di 100 diverse disposizioni casuali delle entità iniziali nel grid. Ogni disposizione comprenderà 10 entità.
La popolazione iniziale:
...
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))
Viene eseguito il gioco su tutte le disposizioni della popolazione iniziale, e a ciascuna viene assegnato un punteggio, sulla base di: quanti giorni è sopravvissuta, quante celle erano vive al ciclo precedente la morte, quante celle erano isolate all'inizio e il numero di celle iniziali.
La funzione fitness che ho impostato è:
self.fitness[popolazione] = day + (count_alive/(self.pop_size * 1.0)) - (alone_first_day/(self.pop_size * 100.0))
Le mutazioni sono probabilmente la parte più delicata dell'algoritmo: bisogna decidere quali disposizioni della popolazione scartare, quali invece conservare e come farli mutare così da ottenere la nuova popolazione.
Ho deciso di conservare la disposizione migliore della popolazione, ovvero quella che ha il punteggio fitness maggiore. Le disposizioni della nuova popolazione avranno il 10% di probabilità per ogni singola coordinata delle sue entità di mutare, ovvero di essere sostituiti da una coordinata casuale, e il 90% di rimanere uguale a quella della migliore disposizione.
La funzione che gestisce la mutazione:
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
Una volta completato il gioco e impostato l'algoritmo genetico, non resta altro che far ripetere al programma un gran numero di cicli gioco-valutazione-mutazione e osservare se con le generazioni il punteggio migliora.
game = Game()
game.generatePopulation()
game.update_score()
tk.update_idletasks()
tk.update()
time.sleep(1)
game.play()
while True:
game.mutatePopulation()
game.play()
Il programma riesce, nella maggior parte dei casi e nel giro di relativamente poche generazioni, a migliorare notevolmente il proprio punteggio, arrivando a sopravvivere intorno ai 5 giorni. Si può notare fin dall'inizio la tendenza a privilegiare disposizioni dove le celle sono raggruppate e vicine.
Tuttavia, nelle simulazioni da me svolte, non è mai stata raggiunta una disposizione che portasse a un aumento drastico del punteggio da una generazione all'altra; così come non sono mai state raggiunte disposizioni che sopravvivessero all'infinito, anche se va considerato che il programma ignora le disposizioni che restano costanti nel tempo, perchè bloccherebbero il programma in soluzioni poco interessanti.