L'obiettivo di questo progetto è di realizzare un programma in Python capace di imparare autonomamente a giocare a Flappy Bird utilizzando una forma semplice di neuroevoluzione simile a quella usata nel progetto Percorso a Ostacoli, ma non identica, in quanto questa si basa su un approccio più simile ai Greedy Algorithms.
L'idea del gioco è abbastanza semplice: il quadratino rosso (nella versione originale un uccellino), deve passare attraverso le aperture tra coppie di tubi verdi che si avvicinano posizionate a altezze variabili e sopravvivere il più a lungo possibile. Il quadrato è soggetto alla forza di gravità, e come l'uccellino può darsi una spinta verso l'alto come con un battito d'ali.
Uno dei primi tentativi dell'algoritmo:
Per creare il gioco ho usato il modulo tkinter, con cui è possibile gestire agilmente gli elementi grafici.
I tubi vengono generati ad altezze variabili sul bordo destro della finestra e si avvicinano con una determinata velocità verso sinistra, mentre il quadratino parte a metà altezza della finestra ed è costantemente soggetto alla forza di gravità. Il quadratino muore quando o si scontra con i tubi o tocca il terreno, mentre non muore se raggiunge il limite superiore della finestra, così come nel gioco originale.
Il gioco è completamente gestito dalla classe Game, che contiene diverse funzioni, tra cui:
La funzione move_bird:
def move_bird(self):
if self.jump_triggered == True and self.bird_speed_y < 0: #inizio nuovo salto
self.time_count=0
self.bird_speed_y = 10 #cambio la velocità verticale con una positiva
self.bird_speed_y0 = self.bird_speed_y
self.bird_y0 = self.bird_y #posizione verticale iniziale
self.jump_triggered = False
else: #è già in un salto
self.jump_triggered = False
self.bird_speed_y -= 0.4 #considero accelerazione verso il basso di 0.8m/s^2
self.new_y = self.bird_y0 - self.bird_speed_y0 * self.time_count + 0.2 * self.time_count * self.time_count
if self.new_y <= 90:
self.new_y = 90
self.movement_y = self.new_y - self.bird_y
self.w.move(self.bird, 0, self.movement_y)
self.bird_y = self.new_y
self.time_count+=1
Una volta pronto il gioco, il programma deve imparare a giocare. L'algoritmo avrà accesso a due informazioni: la distanza orizzontale che separa il quadratino dai tubi successivi e la distanza verticale dall'apertura. Usando queste informazioni, l'algoritmo dovrà decidere se battere le ali oppure no. Queste informazioni verranno interpretate da reti neurali strutturate in questo modo:
L'algoritmo che ho scritto è una sorta di Greedy Algorithm applicato ai pesi e ai bias delle reti neurali considerate. Il programma inizia a giocare con una rete neurale inizializzata randomicamente, la utilizza su un numero fissato di partite, ad esempio 100, e le assegna come punteggio la media del tempo sopravvissuto in queste partite.
Il programma, dopo aver testato la prima rete, ne crea una copia leggermente mutata e esegue il medesimo test sullo stesso numero di partite. Se il punteggio di questa rete è migliore di quello precedente, la nuova rete neurale prende il posto della prima e verrà usata per le successive mutazioni.
I metodi di Game che gestiscono l'approccio greedy del programma:
def check_score(self):
if self.num_move % 1 == 0:
txt_for_print = "G: " + str(self.num_move) + " BEST: " + str(round((self.best_score), 4)) + " | " + str(round((self.last_score), 4))
print(txt_for_print)
if self.last_score >= self.best_score:
self.best_score = self.last_score
self.accept_move()
self.propose_move()
else:
self.move_attempt += 1
self.propose_move()
def accept_move(self):
self.move_attempt = 0
self.config.set_weights_as(self.config_test)
def propose_move(self):
self.num_move += 1
mutation_rate = 0.02
self.config_test.set_mutation_of(self.config, rate=mutation_rate)
Le reti neurali sono gestite da una classe apposita NeuralNetwork che, oltre a gestire i Layer, i Neuroni e il calcolo degli output, contiene alcuni metodi dedicati sia all'approccio Greedy che all'approccio degli Algoritmi Genetici. Per esempio:
La funzione set_mutation_of():
def set_mutation_of(self, other, rate=0.10):
if not isinstance(other, NeuralNetwork) or not np.all(self.layers_sizes == other.layers_sizes):
raise Exception("This works only with another NN of same size")
self.set_weights_as(other)
for l in range(self.n_layers-1):
random_ws = np.random.rand(self.layers_sizes[l], self.layers_sizes[l+1]) * 2 - 1
mask_w = np.random.rand(self.layers_sizes[l], self.layers_sizes[l+1]) < rate
self.weights[l][mask_w] = random_ws[mask_w]
random_bs = np.random.rand(self.layers_sizes[l+1]) * 2 - 1
mask_b = np.random.rand(self.layers_sizes[l+1]) < rate
self.biases[l][mask_b] = random_bs[mask_b]
La realizzazione di questo progetto è durata, nel complesso, quasi due anni. A causa di vari cambi di approccio, continue interruzioni, bug individuati solo dopo mesi e precedenze date ad altri progetti. Finalmente posso essere soddisfatto: nella sua versione finale, il programma riesce a migliorare drasticamente e rapidamente il proprio punteggio. Alcune delle reti neurali trovate potrebbero potenzialmente sopravvivere all'infinito. Di seguito alcune statistiche.
Il miglioramento dei punteggi medi, minimi e massimi nelle partite di test in un breve allenamento di esempio:
Una rete neurale che ha raggiunto punteggi estremamente alti (circa 500 tubi superati) trovata in sole 74 iterazioni:
