Reinforcement Learning in Snap!

SnAIp ist ein Framework und Curriculum zur konstruktionistischen Vermittlung von maschinellem Lernen für den Unterricht. Part A beschäftigt sich mit einem der drei Paradigmen maschinellen Lernens, Reinforcement Learning:

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

Lernziele

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
• 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

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.

Aufgabe: Ordne den Begriffen aus dem Schaubild die passenden Elemente aus dem Spiel zu.

Wichtige Begriffe:

• Agent: Als Agent bezeichnet man ein Computerprogramm, oder einen Teil eines Computerprogramms, das zu einem gewissen Grad zu “autonomen” Verhalten fähig ist. In unserem Schaubild stellt der Roboter den Agenten dar. Im Schachspiel sind die Krokodile die Agenten.
• Zustand: Der Zustand ist eine Beschreibung der relevanten Umwelt des Agenten. In unserem Schaubild wird der Zustand durch den Wachstumsstand der Blumen dargestellt. Im Schachspiel ist die aktuelle Situation des Spielfelds der Zustand.
• Aktionen: 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. In unserem Schaubild hat der Agent zwei mögliche Aktionen: gießen oder mit dem Spaten pflanzen. Im Schachspiel kann jeweils vorwärts gezogen werden oder diagonal geschlagen.
• 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. In unserem Schaubild wird die Belohnung in Form von Münzen dargestellt. Im Schachspiel wird dies durch das Hinzufügen oder Entfernen der Schokolinsen belohnt oder bestraft.
• Strategie: Aufgrund der Belohnung, bzw. Bestrafung für bestimmte Aktionen in bestimmten Zuständen “lernt” der Agent gewisse Verhaltensmuster. Das Ziel des Agenten ist hierbei stets, die maximale Belohnung zu erhalten. Durch wiederholtes Durchlaufen dieses Zyklus wird die Strategie des Agenten nach und nach optimiert.
• 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. In unserem Schaubild stellt das Regal das Modell dar. Im Schachspiel ist

Materialien:

• Krokodilschach
• Rollenkarten
• Beschreibung bei AI-Unplugged

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.

Materialien:

• Vorlage Bananenjagd
• Lösung Bananenjagd

3. Pimp my Game

Im nächsten Schritt sollen nun eigene Spiele um Reinforcement Learning erweitert werden. 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.

Materialien:

• Vorlage Pong (Deutsch)
• Vorlage Pong (Englisch)
• Lösung Pong
• Lösung Breakout
• Lösung Space Invaders
• SnAIp-Cards

Regeln für die Findung geeigneter Unterrichtsbeispiele:

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: 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, um schnelle Lernerfolge zu erzielen. Das bedeutet für den Benutzer: bereits nach kurzer Zeit ist eine Verbesserung der Verhaltens des Agenten beobachtbar. 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. Das Problem wird in diesem Beispiel durch eine Einschränkung der Zustände gelöst - indem die Koordinaten der Aliens nicht exakt, sondern nur in bestimmten Intervallen abgefragt werden. 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: Im Idealfall hat ein Beispiel von vornherein eine relativ begrenzte Anzahl an Zuständen, wie etwa Pong oder die Bananenjagd. 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. 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, Explorationsrate 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 (Explorationsrate 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 (Explorationsfaktor) 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

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:

• MarI/O (genetic algorithms)
• AI learns to play the World’s hardest game (genetic algorithms)
• Google DeepMind’s Deep Q-learning playing Atari Breakout (Deep-Q-Learning)
• AI playing Super Mario World with Deep Reinforcement Learning (Deep Reinforcement Learning)
• StarCraft II Deep Reinforcement Learning Agent (Deep Reinforcement Learning)
• Deep Neural Networks playing FIFA 18 (Deep Neural Networks)

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. Natürlich ist Q-Learning nicht auf Snap! beschränkt. Das Prinzip eignet sich auch, um auf Processing, Java oder Stride übertragen zu 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 hier 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.

Material

• Krokodilschach & Rollenkarten
• Bananenjagd Vorlage & Lösung
• Pong Vorlage (Deutsch) & Pong Vorlage (Englisch)
• Pong Lösung
• Breakout Lösung
• Space Invaders Lösung
• SnAIp-Cards
• Vorlage SnAIp-Blöcke

Weiterführende Links

• Gym ist eine Python-Bibliothek zur Entwicklung und zum Vergleich von Reinforcement Learning Algorithmen. Hiermit können rechenintensivere Verfahren ausprobiert werden.