Navigation

SnAIp Part A – Reinforcement Learning

SnAIp Part A – Reinforcement Learning

entwickelt von Sven Jatzlau, Tilman Michaeli und Stefan Seegerer

Reinforcement Learning (Verstärkendes Lernen) ist ein Paradigma des maschinellen Lernens. Reinforcement Learning ist dabei von der Psychologie inspiriert: Der Agent lernt durch Belohnung und Bestrafung. Er lernt damit durch Interaktion mit seiner Umwelt selbstständig eine gewisse Aufgabe zu meistern.

Darum geht’s

Die Schülerinnen und Schüler …

  • … erklären, dass KI-Systeme die Welt über Sensoren wahrnehmen.
  • …identifizieren und beschreiben die wesentlichen Bestandteile/Elemente von RL (Zustand, Umwelt, Agent, …)
  • … erläutern, wie Agenten durch Reinforcement Learning lernen.
  • … verwenden RL Algorithmen, um bestimmte Spiele in Snap! um selbstlernende Agenten zu erweitern.
  • …vergleichen unterschiedliche Belohnungsfunktionen miteinander und treffen eine reflektierte Wahl
  • …analysieren, wie der Lernvorgang auf technischer Ebene mit Hilfe von Q-Learning realisiert werden kann

Ablauf

  1. Was ist Reinforcement Learning (RL)
  2. Einstieg in RL in Snap!
  3. Pimp my Game
  4. Blick hinter die Kulissen
  5. Ausblick

1. Was ist Reinforcement Learning

Zur Einführung  von Reinforcement Learning ganz ohne PC bietet sich  die Aktivität “Krokodil-Schach” aus der Sammlung “AI Unplugged” an. Für weitere Informationen verweisen wir Sie auf AI Unplugged (deutschsprachig) bzw. CS4Fun (englischsprachig).

Nun gilt es, das Grundprinzip von Reinforcement Learning zu verdeutlichen. Den  Schülerinnen und Schülern wird dafür die folgende Skizze präsentiert.

Möglicher Arbeitsauftrag:
Ordne den Begriffen aus dem Schaubild die passenden Elemente aus dem Spiel zu.

Die Idee von Reinforcement Learning ist, dass ein Agent aus seiner Umgebung lernt, indem er mit ihr interagiert und Belohnungen für durchgeführte Aktionen erhält. Die wichtigsten Begriffe sind in der unten stehenden Box zusammengefasst.

  • Agent: Als Agent bezeichnet man ein Computerprogramm, oder einen Teil eines Computerprogramms, das zu einem gewissen Grad zu “autonomen” Verhalten fähig ist.
  • Aktion: Als Aktion wird die Interaktion des Agenten mit seiner Umwelt bezeichnet. Je nach Zustand seiner Umwelt, wählt der Agent aus einer Menge verfügbarer Aktionen, wodurch er in einen Folgezustand gelangt und belohnt oder bestraft wird.
  • Belohnung: Die Belohnung ermöglicht es dem Agenten, zu lernen, indem erwünschtes Verhalten belohnt (positiv verstärkt) bzw. unerwünschtes Verhalten bestraft (negativ verstärkt) wird.

Eine wichtige Ergänzung zu unserem vorherigen Lernalgorithmus stellt der Interpreter dar. Dieser legt zwei wichtige Dinge fest: 

  1. Beobachtung: Was der Agent sehen, bzw. worauf er reagieren soll. 
  2. Belohnung: Abhängig vom vergangenen Zustand, dem neuen Zustand, und der durchgeführten Aktion des Agenten wird dieser belohnt, bzw. bestraft.
  • Zustand: Der Zustand ist eine Beschreibung der relevanten Umwelt des Agenten. 
  • Modell: Das Modell ist das “Gehirn” des Agenten. In ihm werden Zustände, Aktionen und gelernte Assoziationen gespeichert. Wird vom Lernvorgang des Agenten gesprochen, ist damit eine Anpassung des Modells gemeint.

2. Einstieg in RL in Snap!

Im nächsten Schritt gilt es nun, einen “Affen”-Agenten lernen zu lassen und ihn so bei der Bananenjagd zu unterstützen!

Ziel des Äffchens ist es, über das Fass zu springen

Aufgabe 1: Die Schülerinnen und Schüler erhalten eine Vorlage (Musterlösung) für das Spiel “Bananenjagd”. Dort sind alle Blöcke, die für den selbstlernenden Agenten von Relevanz sind, enthalten –  allerdings nicht in der richtigen Reihenfolge. Die Aufgabe der Schülerinnen und Schüler ist es, diese in die richtige Reihenfolge zu bringen. Als Hilfestellung dient die obige Skizze.

Aufgabe 2: Die Schülerinnen und Schüler erhalten Beobachtungsaufträge: Sie sollen zunächst beschreiben, wie sie das Lernen beschreiben würden. Dabei stellen Sie fest, dass das Verhalten zunächst zufällig erscheint, der Agent im Anschluss lernt länger auf dem Boden zu bleiben, allerdings rennt das Äffchen trotzdem hin und wieder ins Fass hinein und auch der Doppelsprung ist noch ein Problem.

Weitere Aufgabe zur Binnendifferenzierung: Für schnelle Schülerinnen und Schüler kann die Aufgabe bereits weitergesponnen werden. Ihre Aufgabe ist es, das Spiel so zu verändern, dass die Fässer zwei verschiedene Größen annehmen können (Hinweis: zweites Kostüm!) und das Lernverhalten des Agenten so verbessern, dass es trotzdem alle Fässer meistern kann. Hierbei muss zum ersten Mal der Zustand angepasst werden.

Optional kann die Snap-Vorlage um ein Skript erweitert werden, das auf Tastendruck ein Fass spawnt. Damit wird das Spiel für die Schülerinnen und Schülern interaktiver.

Wir erweitern unsere eigenen Spiele in Snap!

Im nächsten Schritt sollen nun eigene Spiele um Reinforcement Learning erweitert werden.  

Pimp my Game

Prinzipiell lässt sich Reinforcement Learning auf jedes beliebige Spiel übertragen. Für die Auswahl eines Unterrichtsbeispiels mit SnAIp gelten jedoch einige Regeln und Einschränkungen, die weiter unten aufgeführt werden. 

Aufgabe 1: Die Schülerinnen und Schüler implementieren ihr eigenes Spiel  oder ihnen wird ein bereits fertig implementiertes Spiel zur Verfügung gestellt. Dieses wird nun erweitert  und “gepimpt”. Dazu sollen die Schülerinnen und Schüler zunächst folgende Bestandteile modellieren  und anschließend umsetzen:

  • mögliche Aktionen
  • Belohnungsfunktion
  • Erfassung des Zustands

Aufgabe 2: Die Schülerinnen und Schüler erhalten die Aufgabe, mit verschiedenen Belohnungsfunktionen und Zuständen zu experimentieren und deren Effekte auf das Lernverhalten zu beschreiben.

Geeignete Unterrichtsbeispiele:

Hier einige Beispiele, die sich besonders gut für den Unterrichtseinsatz eignen (zunächst inklusive Lösung):

  • Breakout ist ein Einzelspieler Arcade Spiel, in dem mit einem Schläger der Ball auf eine Steinwand geschossen wird.
  • Virtuelles Tischtennis in Form von Pong ist ein Klassiker unter den Arcade-Games. In diesem Beispiel kann zudem ein lernender einem nicht lernenden Agenten gegenübergestellt werden. 
  • (Simple) Space Invaders (Achtung Snap!5)
  • Flappy Bird

Drei Regeln für die Findung geeigneter Unterrichtsbeispiele:

Der Q-Learning Algorithmus ist prinzipiell auf jedes Spiel übertragbar. Die Geschwindigkeit, mit der der jeweilige Agent das erwünschte Verhalten erlernt, steht und fällt jedoch mit der Anzahl der unterschiedlichen möglichen Zustände. 

Es folgen drei Extrembeispiele zur Verdeutlichung:

  1. Bananenjagd/Pong: Hier werden die Zustände ausschließlich durch die Entfernung zum Fass, bzw. die Koordinaten des Balls bestimmt. Durch die Größe der Leinwand ergibt sich daher eine begrenzte Anzahl möglicher Zustände, was auch die Anzahl Zeilen der Tabelle niedrig genug hält, um schnelle Lernerfolge zu erzielen. Das bedeutet für den Benutzer: bereits nach kurzer Zeit ist eine Verbesserung der Verhaltens des Agenten beobachtbar.
  2. Space Invaders: In diesem Beispiel bestimmen die Positionen der angreifenden Aliens und die Position des Raumschiffs die möglichen Zustände. Verglichen mit Bananenjagd, bzw. Pong treten hier bereits deutlich mehr Zustände auf, was sich in Form eines langsameren Lernvorgangs bemerkbar macht. Aus diesem Grund ist dieses Beispiel u. U. weniger ideal für den Unterricht. Eine mögliche Lösung für dieses Problem wäre eine Einschränkung der Zustände – beispielsweise könnten die Koordinaten der Aliens nur in bestimmten Bereichen abgefragt werden.
  3. Bomberman: In diesem Spiel wäre die Anzahl der Zustände, die für einen sinnvollen Lernvorgang benötigt wären, viel zu groß: die eigene Position, die der gegnerischen Bomber, die Stärke der Explosion, die Anzahl verfügbarer Bomben, die Positionen der einzelnen Mauern, usw. Da ein einziger Fehler zum sofortigen Spielende führen würde, lässt sich auch keiner dieser Parameter sinnvoll einschränken, bzw. begrenzen. Aus diesem Grund ist dieses Beispiel nicht für den Unterrichtseinsatz geeignet.

Zusammenfassend bestimmt also die Anzahl möglicher Zustände die Dauer des Lernvorgangs. Daraus leiten sich drei Regeln für die Auswahl eines geeigneten (Bei-)Spiels für den Unterricht ab:

  1. Im Idealfall hat ein Beispiel von vornherein eine relativ begrenzte Anzahl an Zuständen, wie etwa Pong oder die Bananenjagd.
  2. Für komplexere Beispiele, wie etwa Space Invaders, sollte versucht werden, die Anzahl an Zuständen “von Hand” zu begrenzen – das könnte hier etwa bedeuten, dass die Koordinaten der Aliens nur in Bereichen abgefragt werden.
  3. Treffen auf ein Beispiel weder 1) noch 2) zu, d.h. es gibt zu viele mögliche Zustände, die nicht sinnvoll zu begrenzen sind, ist das Beispiel für den Unterrichtseinsatz nicht geeignet, da der Lernvorgang zu lange andauern würde.

Zukunft und Vergangenheit:

Möglicherweise sind die Schülerinnen und Schüler zu diesem Zeitpunkt bereits auf folgendes Problem gestoßen:

“Wird nicht manchmal das “richtige” Verhalten bestraft? Also z.B. wenn der Schläger sich nach unten bewegt, aber den Ball trotzdem nicht erreicht?” (vgl. Abbildungen)

Tatsächlich hilft es bei solchen Beispielen dem Agenten nicht, wenn erst in dem Moment gelernt wird, in dem der Ball berührt wird. Wichtig sind die vorherigen Aktionen, die zu dieser Berührung geführt haben, da diese verstärkt oder bestraft werden müssen. 
Es müssen also die vorherigen Situationen, nicht nur die aktuelle, in den Lernvorgang mit einbezogen werden (“zu welchem Zeitpunkt sollte ich springen, um das Fass nicht zu berühren?”). Damit bezieht der Agent nicht nur die kurzfristige Belohnung dieser Situation in seine Entscheidung mit ein, sondern maximiert seine Belohnung langfristig

4. Blick hinter die Kulissen

Im Folgenden soll nun betrachtet werden, wie das Konzept RL in diesem Fall auf Technologie-Ebene realisiert wird: Das verwendete Verfahren nennt sich Q-Learning und arbeitet mit Tabellen als Datenstruktur. Daneben gibt es weitere, komplexere Verfahren, die beispielsweise auf neuronale Netze als Datenstruktur setzen.

Q-Learning:

Q-Learning ist ein Algorithmus, der eine Q-Tabelle erzeugt, mit der ein Agent die beste Aktion für einen Zustand findet. Der Q-Wert in der Q-Tabelle gibt an, welche Belohnung bei Durchführung dieser Aktion in der aktuellen Situation zu erwarten ist. Durch die Assoziation eines bestimmten Zustands mit einer bestimmten Belohnung lernt der Agent (= die Wahrscheinlichkeit dieses Verhalten erneut zu zeigen steigt). 

Aufgabe 1: Die Schülerinnen und Schüler erhalten den Auftrag die Tabelle, die als Datenstruktur das Modell repräsentiert, anzusehen. Dies kann mit dem Block Element 1 von <model> erreicht werden.   (Tipp: Doppelklick auf die erscheinende Tabelle fixiert diese.)

Die Schülerinnen und Schüler werden ermutigt, den Schritt- für-Schritt Debugger zu verwenden und zu beobachten, wie sich die Werte nach jedem Schritt ändern.

Aufgabe 2:Die Schülerinnen und Schüler erhalten die Aufgabe den Einfluss der Parameter Lernrate, Zufall und Discountfaktor auf den Lernprozess zu untersuchen. Dazu variieren Sie einzelne Parameter und beobachten den Effekt. 

Mögliche Ideen sind

  • den Discountfaktor auf 0 zu setzen, dies resultiert in einem Lernen lediglich aus der aktuellen Situation
  • sehr hohe und sehr niedrige Werte für die Lernrate vergleichen und dabei die Zeit messen bis ein stabiles Verhalten erworben wird.
  • keine zufällige Wahl der Aktionen mehr zulassen (Zufall auf 0; 0,5 und 1 setzen).

Hinweise zu den Methoden

Ermittlung der Q-Werte

Der Algorithmus iteriert über die Zeilen der Tabelle und überprüft, ob irgendeine Zeile der Tabelle = dem neuen Zustand ist. Falls, ja wird diese Zeile zurückgegeben. Ansonsten wird eine neue Zeile für den Zustand erstellt, und seine Q-Werte mit 0 initialisiert. Schließlich wird die neue Zeile in die Q-Tabelle eingefügt und zurückgegeben.

Ermittlung der besten Aktion

Q-Werte für aktuellen Zustand werden abgerufen. Mit einer gewisser Wahrscheinlichkeit (Zufallsfaktor) wird eine zufällige Aktion ausgeführt, d.h. ein zufälliges Element der wird zurückgegeben. In allen anderen Fällen wird der Eintrag der Zeile mit dem höchsten Wert gesucht. Dieser Eintrag repräsentiert die am positivsten bewertete Aktion für diesen Zustand. Ist das Maximum 0, so wird zufälliges Verhalten gezeigt, d.h. eine zufällige Aktion ausgeführt und diese zurückgegeben.

Aktualisierung der Tabelle

Quelle: Q-learning
Von Wikipedia, der freien Enzyklopädie (https://en.wikipedia.org/wiki/Q-learning)
  • Q-Tabelle: Verwaltet alle bereits bekannten Zustände und die erwarteten Belohnung bei Durchführung einer bestimmten Aktion in einem Zustand
  • Lernrate: Bestimmt, wie schnell neues Verhalten gelernt wird
  • Discountfaktor: Bestimmt, wie stark zukünftiges Verhalten gewichtet wird

Diese Formel ist im Block <update model> umgesetzt:

5. Ausblick

Das System mit Tabellen ist ganz schön smart, nicht wahr? Mit relativ einfachen Mitteln wurde den Sprites “Intelligenz” eingehaucht.

Lässt sich das jetzt einfach auf FIFA, Super Mario usw. übertragen?

Ja! Während es aber bei Spielen wie Pong oder Breakout noch möglich ist, eine Tabelle aller Zustände zu führen, ist dies bei komplexeren Spielen, aber auch in der realen Welt kaum mehr möglich. Bei Tic Tac Toe wären bereits 19,683 verschiedene Zustände nötig und bei Spielen wie Fifa oder League of Legends würde die Tabelle mehrere Millionen Zeilen enthalten und wäre damit so groß, dass das Training ewig dauern würde.

Solche Situationen erfordern etwas, das auch verallgemeinert und nicht mehr jede einzelne Situation lernt. An dieser Stelle kommen beispielsweise neuronale Netze als Datenstruktur ins Spiel, die etwa auch bei der Bilderkennung zum Einsatz kommen (Deep Q-Learning). Für jeden Zustand approximiert das Netz den Q-Wert für jede mögliche Aktion. Bestimmte Arten von Netzen sind zudem sehr gut darin mit Bildern umzugehen, weshalb es in diesen Fällen nicht nur möglich ist, eine Zustandsbeschreibung als Eingabe für den Algorithmus zu verwenden, sondern auch das Eingabebild, das menschliche Spieler sehen. 

Mit Pixeln ist man sogar noch spieleunabhängiger, denn dann ist der Zustand bei allen Spielen gleichartig – nämlich eine zweidimensionale Sammlung von Pixeln.

Videos mit weiteren Beispielen zu Machine Learning in Videospielen:

Material

Hinweise für Lehrkräfte

Warum Q-Learning?

Der Vorteil von Q-Learning ist vor allem, dass das Training bei kleinen Problemräumen sehr schnell gehen kann: Je nach gewählter Zustandsbeschreibung sind Effekte in unter drei Minuten sichtbar. Zudem kann der Q-Learning Algorithmus durch Nutzung einer Tabelle, in der Zustände und die Q-Werte für die jeweiligen Aktionen gespeichert sind, nicht nur leicht verstanden und visualisiert, sondern auch von Schülerinnen und Schülern selbst implementiert werden.

Wie wähle ich passende Parameter?

Tatsächlich gibt es kein richtig oder falsch für die Wahl von Lernrate, Discountfaktor, Zustand oder Belohnung. Die Schülerinnen und Schüler sind hierbei ein Stück weit gefordert, darüber nachzudenken, welche Informationen in ihrer Situation wichtig sind und welche Aspekte die Höhe der Belohnung bzw. Bestrafung bestimmen. Und trotz aller Überlegungen ist das Umsetzen eines Lernalgorithmus auch immer mit Experimentieren verbunden.