Verstärkendes Lernen

"Schlag den Computer!"


Das Verstärkende Lernen ist ein von der Psychologie inspiriertes Paradigma des maschinellen Lernens: Der Computer lernt durch Belohnung und Bestrafung in Interaktion mit seiner Umgebung eine Aufgabe zu meistern, indem er versucht, die mögliche Belohnung zu maximieren.
Anhand eines Mini-Schachspiels wollen wir hier, die den Algorithmen des Verstärkenden Lernens zugrunde liegenden Ideen erfahrbar machen. 

Viel Spaß dabei! 

Das Spiel:

Jede Spielfigur bewegt sich wie ein Bauer beim normalen Schach, d. h. sie kann nur vorwärts gehen und gegnerische Figuren nur diagonal schlagen. Eine Seite hat gewonnen, wenn sie es schafft

  • eine eigene Spielfigur an das andere Ende des Spielfeldes zu führen,
  • alle gegnerischen Figuren zu schlagen,
  • oder dafür zu sorgen, dass der Gegner in der nächsten Runde keinen Spielzug mehr ausführen kann.

MiniSchach Spielfeld

Die menschliche Spielerin bzw. der menschliche Spieler beginnt und kann sich entsprechend der Spielregeln frei bewegen. Anschließend ist der Computer an der Reihe: Er analysiert das aktuelle Spielfeld, prüft die möglichen Züge und wählt aus den verfügbaren Optionen die passende Spielsituation aus.


Regeln

Im Anschluss zieht der Computer zufällig eines der farbigen Tokens, die sich neben der jeweiligen Spielsituation befinden. Die Farbe des Tokens bestimmt, welcher Zug ausgeführt wird. Wird beispielsweise ein rotes Token gezogen, wird der Roboter dem roten Pfeil folgend bewegt.

Dieses Vorgehen wird solange wiederholt, bis ein Gewinner feststeht. Bevor eine neue Runde gespielt wird, passt der Computer nun seine Strategie wie folgt an:

  1. Computer hat gewonnen: Ein Token in der Farbe des letzten Spielzugs, der zum Sieg geführt hat, wird zusätzlich auf das Feld dieses Spielzugs gelegt.
  2. Mensch hat gewonnen: Das Token, das den letzten Zug des Computers bestimmt hat, wird aus dem Feld des jeweiligen Spielzugs entfernt.
Zunächst wird der Computer kaum eine Chance haben zu gewinnen, da er seine Bewegungen zufällig wählt (indem ein Token gezogen wird). Je mehr Spiele der Computer beendet, desto besser wird er: Er „lernt”, welche Züge ihm zum Sieg verhelfen und welche er vermeiden sollte, da sie in der Vergangenheit in einer Niederlage endeten. So wird die Strategie des Computers schrittweise verfeinert. Da der Computer für das Verlieren bestraft und für das Gewinnen belohnt wird, sprechen wir auch von verstärkendem Lernen (Reinforcement Learning) – ein Lernen durch Belohnung und Bestrafung:

    Bestrafung = Wegnehmen eines Tokens bei einem Spielzug, der zur Niederlage führte
    Verstärkung = Hinzufügen eines Tokens bei einem Spielzug, der zum Sieg führte

Durch dieses Vorgehen werden bei den jeweiligen Spielzügen diejenigen Züge „aussortiert”, die Niederlagen zur Folge hatten, sodass irgendwann nur noch „gute” Züge übrig bleiben.

Der vorgestellte Algorithmus dient dazu, das Prinzip des Verstärkenden Lernens zu erkunden. In der Praxis würde man bspw. Strategien, die nicht zum Erfolg führen, nicht sofort eliminieren, sondern nur die Wahrscheinlichkeit ihres Auftretens verringern. So lernt der KI-Agent nach und nach, welche Aktionen in welcher Situation wohl am besten geeignetsten ist, schließt aber Züge nicht sofort vollständig aus, die einmal nicht zum Erfolg geführt haben.


!   Spielen Sie im Folgenden das Spiel: Schlag den Computer!