Verstärkendes Lernen erkunden

"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. 
Übrigens: Ein Programm, welches seine Umgebung wahrnimmt und mit ihr interagiert, um autonom Ziele zu verfolgen, wird auch als Agent bezeichnet.

Viel Spaß dabei! 

Das Spiel:

Jede Spielfigur bewegt sich wie ein Bauer, 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. Sie bzw. er kann sich frei gemäß der Spielregeln bewegen. Danach ist der Computer an der Reihe. Dieser vergleicht das aktuelle Spielfeld mit den Zugmöglichkeiten und wählt die passende Spielsituation aus den gegebenen Möglichkeiten 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, siegbringenden Spielzugs wird zusätzlich auf das Feld dieses Spielzugs gelegt.
  2. Mensch hat gewonnen: Das Token, das den letzten Zug der Computer-Spielerin bzw. des Computer-Spielers bestimmt hat, wird 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.

!   Hier geht es nun zum Spiel: Schlag den Computer!