Ein Reinforcement-Learning Agent lernt den Spieleklassiker Snake 🐍

Snake der Spieleklassiker der Millennials, auf jedem alten Nokia Handy vorhanden, begeisterte die kleine Apfel fressende Schlange Jung und Alt. Ziel des Spiel ist es die Schlange durch geschickten Input die zufĂ€llig erscheinenden Äpfel fressen zu lassen. BerĂŒhrt die Schlange die Wand oder ihren eigenen Schwanz ist das Spiel vorbei. Dieses simple aber im spĂ€teren Verlauf doch anspruchsvolle Spiel bietet sich aufgrund der steigenden KomplexitĂ€t gut fĂŒr den Reinforcement-Learning Ansatz an.

In diesem Projekt wird ein Agent entwickelt, welcher mit Hilfe von Reinforcement-Learning das Spiel Snake spielen lernen soll. Hierzu wurde ein neuronales Netz bestehend aus drei Convolutional-Layern und 2 Dense-Layern entwickelt. Die Architektur des Netzes ist in Abbildung 1 zu sehen. Als Aktivierungsfunktion wurde ReLU verwendet.

Abb 1. Die einzelnen Verarbeitungsschritte der Bilder innerhalb des Netzes zum Errechnen des nÀchsten Spielzuges

Das Snake-Spiel

Das Snake-Spiel selbst wurde mit Hilfe der Bibliothek PyGame realisiert. Es besitzt eine 250 x 250 Pixel große SpieloberflĂ€che. Der Apfel ist 25 x 25 Pixel groß und rot. Die Schlange ist blau, initial 25 x 50 Pixel groß und wĂ€chst mit jedem gefressenen Apfel um einen 25 x 25 Pixel Block.

WĂ€hrend eines Spielschrittes kann sich die Schlange in vier unterschiedliche Richtungen bewegen: oben(0), unten(3), links(1), rechts(2). Dies kann der Agent tun, indem er der play_step(self,action) Methode eine entsprechenden Wert ĂŒbergibt. Anschließend wird mit Hilfe der _move() Methode die Schlange in die entsprechende Richtung bewegt.

def play_step(self, action):
   final_move = [0,0,0,0]
   final_move[action] = 1
   self.frame_iteration += 1
   self._move(final_move) 
   self.snake.insert(0, self.head)
Bewegen der Schlange in eine Richtung

Im Anschluss wird ĂŒberprĂŒft, ob eine Kollision stattgefunden hat, ist dies der Fall, wird folgendes zurĂŒck gegeben:

  • der negative Reward
  • der neue Status des Spiels als Screenshot
  • der boolÂŽsche Wert "true", um anzuzeigen, dass das Spiel beendet ist
  • die aktuell erreichte Punktzahl
if self.is_collision() or self.frame_iteration > 100*len(self.snake):
       game_over = True
       reward = -1
       return self.get_last_frames(self.screenshot()), reward,
       game_over, self.score
ÜberprĂŒfung auf Kollision innerhalb der play_step Methode

Wurde keine Kollision festgestellt, wird falls nötig ein neuer Apfel an einer zufĂ€lligen Stelle platziert. Wurde kein Apfel gefressen, wird der letzte Block der Schlange entfernt. Dadurch erscheint es dem Nutzer, als ob sich die Schlange vorwĂ€rts bewegt. Die Übergabewerte in diesem Fall unterscheiden sich lediglich in dem boolÂŽschen Wert, da das Spiel nicht beendet wurde.

  if self.head == self.food:
       self.score += 1
       reward = 2
       self._place_food()
   else:
       self.snake.pop()
Neusetzen des Apfels/ entfernen des letzten Elementes

Der Agent erhÀlt "Augen"

Der Agent “sieht” mit Hilfe von Bildern der SpieloberflĂ€che, welche er an das Netz ĂŒbergibt. Da jedoch aus einem einzelnen Bild keine Informationen zu Bewegungsrichtungen gewinnen lassen, ist es nötig, dass mehrere aufeinander folgende Bilder ĂŒbergeben werden. Diese werden zunĂ€chst in Graustufen und anschließend in Matrizen umgewandelt. Diese können nun an das Netz ĂŒbergeben werden, welches die neuen Bewegungsrichtungen berechnet. Die Schlange wird sich in Richtung der am höchsten bewerteten Richtung bewegen.

Damit der Agent den Lernprozess schneller bewĂ€ltigen kann, wurde sich fĂŒr ein Spielfeld der GrĂ¶ĂŸe 250 x 250 Pixel entschieden. Dieses Feld wird mit Hilfe der screenshot() Methode verarbeitet und als Matrix zurĂŒckgegeben. Zu dem Verarbeitungsprozess gehören eine GraufĂ€rbung, sowie das zuschneiden des Originalbildes auf 84 x 84 Pixel. Durch diesen Prozess kann die zu verarbeitende Datenmenge weiter reduziert werden. In Abbildung 2. ist ein solch bearbeitetes Bild zu sehen. Dabei gilt es zu beachten, dass diese Verarbeitung nicht fĂŒr jeden Use-Case pauschalisiert werden kann. Die EinfĂ€rbung in Graustufen ist nur möglich, da die Farben keine Rolle in Snake spielen. Auch bei dem zuschneiden der Bilder muss gewĂ€hrleistet werden, dass dem Netz beziehungsweise dem Agent genug Bildinformationen ĂŒbergeben werden.

Abb 2. Screenshot der SpieloberflÀche nach der Verarbeitung: umgewandelt in Graustufen und skaliert auf 84x84 Pixel
def screenshot(self):
   data = pygame.image.tostring(self.display, 'RGB') 
   image = Image.frombytes('RGB', (250, 250), data)
   image = image.convert('L')  
   image = image.resize((84, 84))
   matrix = np.asarray(image.getdata(), dtype=np.uint8)
   matrix = (matrix - 128)/(128 - 1)  
   return matrix.reshape(image.size[0], image.size[1])
Die screenshot Methode im Detail

Diese Bildinformationen werden in der get_last_frames(screenshot) Methode zu einem Stapel von vier Matrizen zusammengesetzt und als “State” zurĂŒckgegeben. Dabei sorgt eine sogenannte “deque” dafĂŒr, dass dieser Stapel auch genau vier Matrizen enthĂ€lt. Der “State” ist dementsprechend das was das Agent “sieht” und wodurch die folgenden Aktionen berechnet werden können.

def get_last_frames(self, screenshot):
   frame = observation
   if self._frames is None:
       self._frames = deque([frame] * self._num_last_frames)
   else:
       self._frames.append(frame)
       self._frames.popleft()
   state = np.asarray(self.frames) 
return state
Die get_last_frames Methode im Detail

Der Agent ĂŒbergibt den State an das Neuronale Netz, wodurch die nachfolgenden Aktionen berechnet werden. Der Input des Netzes setzt sich hierbei aus der besagten 4 x 84 x 84 großen Matrix zusammen.


Oh a piece of Candy

Damit der Agent ĂŒberhaupt lernen kann, ist im Reinforcement-Learning ein sogenannter Reward (Belohnung) notwendig. Simpel dargestellt wird der Agent fĂŒr eine “gute” Aktion belohnt, er bekommt ein virtuelles Bonbon. Der Reward ist die wichtigste RĂŒckmeldung an den Agenten. Diese Belohnung steuert den gesamten Lernprozess und die zukĂŒnftigen Aktionen des Agenten.

Die Folgenden Rewards kann der Agent fĂŒr seine Aktionen erhalten:

  • Findet der Agent den Apfel, so erhĂ€lt er einen positiven Reward von 2.
  • Findet eine Kollision statt (entweder mit der Mauer, oder der Schlange selbst)   ist das Spiel vorbei und der Agent erhĂ€lt einen negativen Reward von -1.
  • Ebenso gibt es eine Abbruchbedingung fĂŒr den Fall, dass lĂ€ngere Zeit kein Apfel gefunden wurde. Dies soll verhindern, dass der Agent eine Strategie wĂ€hlt, welche die Schlange nur am Rand des Spielfeldes kreisen lĂ€sst. In diesem Fall wird das Spiel neu gestartet und ein negativer Reward von -1 an den Agenten ĂŒbergeben
  • Um dem Agenten einen grĂ¶ĂŸeren Anreiz zu geben, sich schneller zu einem Apfel zu begeben wurde ein weiterer negativer Reward von -0,02 eingefĂŒhrt. Dieser Reward wird fĂŒr jede weitere ausgefĂŒhrte Aktion an den Agenten ĂŒbergeben. Dabei gilt es zu beachten, dass der Reward nicht zu klein gewĂ€hlt wird, da es dem Agenten ansonsten klĂŒger erscheinen könnte, die Anzahl an Aktionen zu verringern, indem er das Spiel durch eine Kollision beendet.
reward = -0.02
game_over = False
if self.is_collision() or self.frame_iteration > 100*len(self.snake):
   game_over = True
   reward = -1
   return self.get_last_frames(self.screenshot()), reward,
game_over, self.score

if self.head == self.food:
   self.score += 1
   reward = 2
   self._place_food()
else:
   self.snake.pop()
self._update_ui()
self.clock.tick()
return self.get_last_frames(self.screenshot()), reward, game_over, self.score
Die Implementierung des Rewardsystems

Das GedÀchtnis und der Lernprozess des Agenten

Das Training der Netze geschieht mit Hilfe einer deque, in welcher fĂŒr jeden Schritt die folgenden Daten gespeichert werden:

  • die Ausgangsposition
  • die aktuell vorgenommene Aktion
  • die nachfolge Position
  • der erhaltene Reward

Da dies sehr speicherintensiv ist, muss hier auf die zu VerfĂŒgung stehenden Ressourcen geachtet werden, da ansonsten ein Overflow oder ein Absturz droht. Aus diesem Grund wurde die GrĂ¶ĂŸe in der Implementierung auf 40.000 EintrĂ€ge festgelegt. Dies lastet eine Grafikkarte mit 10 Gigabyte Speicher gĂ€nzlich aus. Ist diese Zahl von EintrĂ€gen erreicht, wird bei dem nĂ€chsten Eintrag der Ă€lteste nach dem "Pop-left" Prinzip gelöscht.

Die Aktionsauswahl wÀhrend des Lernprozesses wird in Exploration und Exploitation unterteilt. WÀhrend des Lernvorganges werden ZufÀllig 32 dieser EintrÀge zu einem Batch zusammengefasst und mit den Netzen eine Aktion berechnet.  Anhand der errechneten Aktionen werden im Anschluss die beiden Netze trainiert. Dazu werden die Q-values und der Loss berechnet.

    def learn(self):
    
        if self.curr_step % self.sync_every == 0:
            self.sync_Q_target()

        if self.curr_step % self.save_every == 0:
            self.save()

        if self.curr_step < self.steps_before_learning:
            return None, None

        if self.curr_step % self.learn_every != 0:
            return None, None

        # Get Samples from memory
        state, next_state, action, reward, done = self.recall()

        # Get Estimate Q-value
        estimate =self.net(state, model=NetMode.TRAINING)[np.arange(0, self.batch_size), action]

        # Get next Q-value for loss
        nextQ = self.calc_next_Q(reward, next_state, done)

        loss = self.update_Q_training(estimate, nextQ)

        return (estimate.mean().item(), loss)

Exploration vs Exploitation

Die Schlange beziehungsweise der Agent steht vor einem typischen Dilemma. Soll er seine Strategie weiter beibehalten (Exploitation), oder soll eine gÀnzlich neue gewÀhlt werden (Exploration), um schneller ans Ziel zu gelangen.

Um dieses Dilemma zu lösen, gibt es verschiedene Methoden, wie beispielsweise das "Epsilon-greedy-Prinzip", welches auch in diesem Ansatz implementiert wurde.

Bei der Aktionsauswahl nach dem "Epsilon-greedy-Prinzip" nutzt der Agent sowohl Exploitation, um sich Vorwissen zunutze zu machen, als auch Exploration, um nach neuen Strategien zu suchen. Das "Epsilon-greedy-Prinzip" wÀhlt die meiste Zeit die Aktion mit der höchsten errechneten Belohnung. Ziel des Prinzips ist es, ein Gleichgewicht zwischen Exploration und Exploitation herzustellen. Zu beginn des Lernprozesses ist der Anteil an zufÀlligen Aktionen noch sehr hoch, wohingegen die berechneten Aktionen mit steigender Erfahrung des Agenten zunehmen.

    def get_action(self, state):
        # EXPLORE (AusfĂŒhren zufĂ€lliger Actionen)
        if np.random.rand() < self.exploration_rate:
            action_idx = np.random.randint(self.action_dim)
            self.random += 1

        # EXPLOIT (verwendet Voraussage der KI)
        else:
            state = torch.FloatTensor(state).cuda() if self.use_cuda
            else torch.FloatTensor(state)
            state = state.unsqueeze(0)
            action_values = self.net(state, model=NetMode.TRAINING)
            action_idx = torch.argmax(action_values).item()
            self.calc +=1
        # verringern der exploration_rate
        self.exploration_rate *= self.exploration_rate_decay
        self.exploration_rate = max(self.exploration_rate_min, self.exploration_rate)

        self.curr_step += 1
        return action_idx, self.calc, self.random
Implementierung des Epsilon-greedy-Prinzip



Die beiden GehirnhÀlften

Da der Ansatz des traditionellen Q-Learning oftmals dazu neigt die Zustand-Aktions paare deutlich zu ĂŒberschĂ€tzen, wurde der Ansatz des Double Q-Learning verfolgt und implementiert.

FĂŒr das Double Q-Learning werden zwei Netze initialisiert das Target- sowie das Training-Netz. WĂ€hrend des Lernvorgangs wird das Trainings-Netzwerk verwendet, um eine Aktion vorauszusagen, wĂ€hrend das Target-Netzwerk dazu verwendet wird, um diese zu evaluieren.

Hierbei wird bei jedem Training Schritt das Trainings-Netzwerk aktualisiert. Alle 10.000 Schritte kommt es zu einer Synchronisation der beiden Netzwerke: Dabei wird das sogenannte "State-dictionary", welches die Gewichte der Netze enthÀlt, kopiert.

Die Auswahl welches Netz verwendet werden soll, wird durch ein Enum getroffen:

def forward(self, input, model):
   if model == NetMode.TRAINING:
       return self.trainingNet(input)
   elif model == NetMode.TARGET:
       return self.targetNet(input)
Die Auswahl des beiden Netze
 @torch.no_grad()
    def calc_next_Q(self, reward, next_state, done):
        next_state_Q = self.net(next_state, model=NetMode.TRAINING)
        best_action = torch.argmax(next_state_Q, axis=1)
        next_Q = self.net(next_state, model=NetMode.TARGET)[np.arange(0, self.batch_size), best_action]
        return (reward + (1 - done.float()) * self.gamma * next_Q).float()
Die Berechnung des Q-values
    def update_Q_training(self, current_Q, next_Q) :
        loss = self.loss_function(current_Q, next_Q)
        self.optimizer.zero_grad()
        loss.backward()
        self.optimizer.step()
        return loss.item()
Update des Training-Netzes
	def sync_Q_target(self):
    	self.net.targetNet.load_state_dict(self.net.trainingNet.state_dict())
Synchronisation der des Training- und des Target-Netzes

Schlusswort

Abschließend gilt es zu sagen, dass in diesem Projekt ein Agent entwickelt wurde, welcher schon nach 24 Stunden Training in der Lage war, eine maximale Punktanzahl von 26 zu erreichen.

Als Training Hardware wurde eine Google-Cloud-VM Instanz verwendet:

  • n1-highmem-2
  • Tesla K 80 GPU

Der komplette Code ist in diesem Github-Repository zu finden.

Quellen