{"id":23788,"date":"2023-03-09T08:30:47","date_gmt":"2023-03-09T07:30:47","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=23788"},"modified":"2026-02-09T09:44:00","modified_gmt":"2026-02-09T08:44:00","slug":"ki-reinforcement-learning-3","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2023\/03\/ki-reinforcement-learning-3.htm","title":{"rendered":"KI: Reinforcement Learning 3"},"content":{"rendered":"
(1 Kommentare.<\/a>)<\/small> <\/div>\n

(Fortsetzung von hier.<\/a>)<\/p>\n\n\n\n

Die L\u00f6sung des Problems, grunds\u00e4tzlich<\/h3>\n\n\n\n

Das Problem vom letzten Mal war: Wenn man nur den Zug vor Sieg oder Niederlage bewertet, dann gibt es eben nur eine Lernm\u00f6glichkeit unmittelbar vor Sieg oder Niederlage und sonst nicht. Wenn man das Problem so formuliert, ist die L\u00f6sung einfach: Man bewertet nicht nur den letzten gemachten Zug, sondern jeden Zug, jedesmal.<\/strong> Es gilt dabei weiter: wenn ein Zug zu einer Niederlage f\u00fchrt, wird er herab-, wenn er zu einem Sieg f\u00fchrt, heraufgewertet. Neu ist: wenn ein Zug zu einer Situation f\u00fchrt, wo es nur schlechte <\/em>Folgez\u00fcge gibt, dann wird er ebenfalls herabgewertet – hier ein Tic-Tac-Toe-Beispiel, Spieler 2 am Zug, alle Z\u00fcge in dieser Situation f\u00fchren zu einer Niederlage (so dass die KI lernen muss, diese Situation zu vermeiden):<\/p>\n\n\n\n

1|2|0     Move 2 (-15.0)\n2|0|0     Move 4 (-13.0)\n1|0|1     Move 5 (-11.0)\n          Move 7 (-15.0)<\/code><\/pre>\n\n\n\n
Und wenn andersherum ein Zug zu einer Situation f\u00fchrt, in der es mindestens einen sehr guten Zug gibt, dann wird die Bewertung des ersten Zugs heraufgesetzt.<\/p>\n\n\n\n
Kurz: Bei jedem Durchgang wird der letzte Zug im vorhergehenden Zustand bewertet, und zwar abh\u00e4ngig von der Bewertung der M\u00f6glichkeiten im aktuellen <\/em>Zustand (oder eben Sieg\/Niederlage). <\/p>\n\n\n\n
Reihenfolge:<\/p>\n\n\n\n
    \n
  1. Die KI befragt die Q-Tabelle nach der besten Entscheidung in der aktuellen Situation.<\/li>\n\n\n\n
  2. Diese Entscheidung wird durchgef\u00fchrt; damit \u00e4ndert sich die Situation.<\/li>\n\n\n\n
  3. Das Spiel meldet der KI Erfolg oder Misserfolg oder eine andere Bewertung der Situation zur\u00fcck.<\/li>\n\n\n\n
  4. Die KI \u00e4ndert den Eintrag in der Q-Tabelle f\u00fcr die alte, urspr\u00fcngliche Situation, und zwar in Abh\u00e4ngigkeit von der Bewertung  des bestm\u00f6glichen Zugs in der jetzigen Situation. Wenn es in der neuen Situation einen tollen Zug gibt, wird der Wert der alten Zug-Situation-Kombination heraufgesetzt. Wenn es in der neuen Situation nur schlechte Z\u00fcge gibt, wird der Wert der alten Zug-Situation-Kombination herabgesetzt.  <\/li>\n<\/ol>\n\n\n\n
    Die konkrete Belohnungsfunktion, mit Lernrate und Diskontierung<\/h3>\n\n\n\n
    Beim letzten Mal habe ich zwei Fragen vorgestellt, die man sich bei jedem solchen Spiel\/Projekt stellt: Was w\u00e4hlt man als Zustand, und was z\u00e4hlt als Gewinn\/Niederlage? Die vorl\u00e4ufigen Antworten waren: als Zustand nehmen wir bei Breakout die Differenz in der x-Position von Ball und Schl\u00e4ger, und Gewinn\/Niederlage ist das Treffen oder Verfehlen des Balles mit dem Schl\u00e4ger. Wir bleiben vorerst bei diesen beiden Antworten, werden sp\u00e4ter aber etwas daran \u00e4ndern m\u00fcssen.<\/p>\n\n\n\n
    Bi der Funktion, mit der man den neuen Q-Wert f\u00fcr einen Zustand stateOld<\/code> und einen Zug move<\/code> berechnet, spielen neben dem aktuellen Zustand stateNew<\/code> noch zwei Faktoren eine Rolle, deren Wert unterschiedlich eingestellt werden kann, der aber konstant bleibt: Diskontierungsfaktor\/gamma und Lernrate\/learning rate. <\/p>\n\n\n\n
    Diskontierungsfaktor\/gamma:<\/strong> Kommt von discount\/Nachlass\/Erm\u00e4\u00dfigung\/Skonto. Ist ein Wert zwischen 0 und 1 und bestimmt, wie sehr der h\u00f6chstm\u00f6gliche zuk\u00fcnftige Wert ber\u00fccksichtigt werden soll. Vorschlagswert: 0.5<\/p>\n\n\n\n
    Lernrate:<\/strong> Ist ein Wert zwischen 0 und 1 und bestimmt, wie sehr der neue Wert (aus Erwartung und Belohnung zusammengesetzt) gegen\u00fcber dem alten dominiert. Vorschlagswert: 0.75<\/p>\n\n\n\n
    Dann sieht die Funktion so aus (reward<\/code> ist die Belohnung\/Bestrafung f\u00fcr Treffen\/Ball im Aus\/sonstwas):<\/p>\n\n\n\n
    public void update(String stateOld, String stateNew, double reward, int move)\n{\n  \/\/ (1) increase reward by (discounted) highest value in new state\n  reward = reward + gamma * getHighestValue(stateNew);\n\n  \/\/ (2) reduce reward by old value\n  reward = reward - getValue(stateOld, move);\n\n  \/\/ (3) apply learning rate to modified reward\n  double change = reward * learningRate;\n\n  \/\/ (4) increase value by calculated change\n  increaseValue(stateOld, move, change);\n}<\/code><\/pre>\n\n\n\n
    Man kann es auch so sehen, dass der alte Wert erh\u00f6ht wird um:<\/em>
    lernfaktor * (Belohnung + diskontierter Bestwert - alter Wert)<\/code><\/p>\n\n\n\n
    Meist sieht man die Formel f\u00fcr den neuen Wert so, was aber genau das gleiche ist:<\/p>\n\n\n\n
    neuerWertf\u00fcr Entscheidung e in Zustand z<\/sub> = \n(1-lernrate) * alterWertf\u00fcr Entscheidung e in Zustand z<\/sub> + \nlernrate * (belohnung + gamma * h\u00f6chstwertf\u00fcr eine Entscheidung in Zustand z+1<\/sub><\/code><\/pre>\n\n\n\n
    Wenn der Lernfaktor 0 ist, \u00e4ndert sich gar nichts. Wenn der Lernfaktor 1 ist, wird der neue Wert ganz auf die Belohnung plus diskontierter Bestwert gesetzt, der alte Wert spielt keine Rolle dabei. Bei den Werten dazwischen gilt: Wenn die Summe aus Belohnung f\u00fcr den gemachten Zug und diskontiertem Bestwert im neuen Zustand gr\u00f6\u00dfer ist als der alte Wert, dann erh\u00f6ht sich dieser; wenn sie kleiner ist, verringt er sich.<\/p>\n\n\n\n
    Wenn der Discount-Faktor 0 ist, geht es einfach nur um die Belohnung, der Bestwert im neuen Zustand spielt keine Rolle. Wenn der Discount-Faktor 1 ist, spielt der Bestwert im neuen Zustand eine gr\u00f6\u00dfere Rolle.<\/p>\n\n\n\n
    Die Formel kann man nat\u00fcrlich vereinfachen, dann geht das Berechnen vielleicht schneller. Sie reicht bereits, um etwa Nim oder Tic-Tac-Toe und nat\u00fcrlich auch Breakout spielen zu lernen (aber letzteres ging ja bereits halbwegs). Wenn es in Zustand 3 nur Z\u00fcge gibt, die zur Niederlage f\u00fchren, wird der Wert f\u00fcr die Entscheidung, die von Situation 2 zur Zustand 3 gef\u00fchrt hat, verringert. Und wenn es in Zustand 2 dann irgendwann einmal auch sonst nur niedrig bewertete Z\u00fcge gibt, wird auch die Bewertung von einem Zug in Zustand 1, wenn er zu Zustand 2 f\u00fchrt, verringert. Sackgassen sprechen sich sozusagen nach und nach herum, und Strecken, die zum Ziel f\u00fchren, ebenso. Wenn es viele Zust\u00e4nde gibt, dauert das aber sehr, sehr, sehr lange.<\/p>\n\n\n\n
    Funktioniert das? <\/h4>\n\n\n\n
    Bei Breakout hat das ja schon im einfachen System geklappt, aber jetzt kann die KI eben auch Tic-Tac-Toe und Nim spielen lenen. Nur l\u00e4sst sich das nicht so gut in einem Bild oder Film zeigen. Ich verspreche aber, dass diese neuen Bewertungen errechnet worden sind:<\/p>\n\n\n\n
    1|0|0     Move 1 (-0.0776515946578002)\n0|0|0     Move 2 (-0.09491143167204687)\n0|0|0     Move 3 (-0.08783116090423461)\n          Move 4 (2.1469792068679446E-6)\n          Move 5 (-0.09086642291797421)\n          Move 6 (-0.1026154061878333)\n          Move 7 (-0.09468690776157813)\n          Move 8 (-0.09604017243001356)<\/code><\/pre>\n\n\n\n
    Zug 4 hat keine sehr hohe Bewertung, aber die einzige nichtnegative. Es ist der einzige Zug, der auf diese Er\u00f6ffnung hin bei einer versierten Spielerin 1 nicht zur sp\u00e4teren Niederlage von Agent 2 f\u00fchrt (aber vermutlich auch nicht oft zu einem Sieg, sondern eher zu unentschieden). Die ganz oben gezeigte Situation 120-200-101 wird also nach dem Training nicht mehr entstehen.<\/p>\n\n\n\n
    Neu eingef\u00fchrt:<\/font><\/strong> Lernrate, Diskontierungsfaktor<\/p>\n\n\n\n
    Eine wichtige Entscheidung: Das Belohnungssystem<\/h3>\n\n\n\n
    Das bisherige Belohnungssystem war sehr streng: Pluspunkte f\u00fcr Treffer, Minuspunkte f\u00fcr Aus, und sonst nichts. Ein anderes Belohnungssystem k\u00f6nnte dar\u00fcber hinaus die Erg\u00e4nzung haben: je gr\u00f6\u00dfer die Entfernung Schl\u00e4ger-Kugel, desto gr\u00f6\u00dfer f\u00e4llt die negative Belohnung aus. Das motiviert, diese Entfernung gering zu halten. Damit ist der Agent noch viel schneller trainiert. Aber, finde ich, er ist dann nicht darauf trainiert, Breakout zu spielen, sondern darauf, den Schl\u00e4ger m\u00f6glichst nah am Ball zu halten. Und das ist eine viel leichtere Aufgabe. Wenn man schon wei\u00df, was die L\u00f6sung ist, kann man das Erlernen dieser L\u00f6sung beschleunigen.<\/p>\n\n\n\n
    Die zweite wichtige Entscheidung: Wie die Wahl der Zust\u00e4nde das Ergebnis beeinflusst<\/h3>\n\n\n\n
    Bisher gab es bei Breakout nur ein paar Dutzend Zust\u00e4nde, die deswegen leicht zu verarbeiten waren; sie kamen immer wieder vor und hatten deshalb reichlich Gelegenheit, sich bei der Bewertung ihrer m\u00f6glichen Z\u00fcge zu wandeln und zu optimieren. Wenn es mehr Zust\u00e4nd gibt, wird das schwieriger. Die Zust\u00e4nde hingen bisher ab von der Differenz in den x-Positionen von Schl\u00e4ger und Ball. <\/p>\n\n\n\n
    Ich finde das ein bisschen geschummelt. Wenn ich eh schon wei\u00df, dass die Differenz in den x-Positionen wichtig ist und sonst nichts, dann habe ich der KI schon eine Menge Arbeit abgenommen. Wenn ich dagegen nichts vorgebe und als Zustand anbiete: die x-Positionen, aber auch die y-Position des Balls, und seine Flugrichtung noch dazu, dann habe ich, selbst bei grober Zusammenfassung (wo ich etwa nur 12 verschiedene m\u00f6gliche y-Zust\u00e4nde f\u00fcr den Ball ber\u00fccksichtige) immer noch knapp 14000 Zust\u00e4nde, und da dauert es lange, bis die sich oft genug wiederholt haben. Die KI findet dann zwar eine brauchbare L\u00f6sung, es dauert nur deutlich l\u00e4nger. <\/p>\n\n\n\n
    Die gefundene L\u00f6sung sieht dann aber auch anders aus, unsicherer, wackeliger: Beim einfachen Zustandssystem besteht sie darin, den Schl\u00e4ger immer parallel zum Ball zu f\u00fchren, also die Differenz zwischen den x-Positionen klein zu halten. Beim komplexen Zustandssystem ist das wie im folgenden kurzen Film: Meistens ist es egal, wie der Schl\u00e4ger ein bisschen zappelt, aber wenn der Ball unten ist, wird der Schl\u00e4ger hektisch:<\/p>\n\n\n\n
    \"\"<\/figure>\n\n\n\n
    (Warum \u00e4ndert sich oben nichts sondern alles bleibt bei 0? Weil der Startwert 0 ist, und wenn die Belohnung auch 0 ist, \u00e4ndert sich selten etwas. Mit 1 als Startwert sieht man zwar st\u00e4ndige Ver\u00e4nderung, der Agent findet aber keine L\u00f6sung.)<\/p>\n\n\n\n
    \u00dcberblick \u00fcber die ausprobierten Varianten<\/h3>\n\n\n\n
    Ich habe verschiedene Kombinationen ausprobiert. Da ist einmal die Unterscheidung zwischen der einmaligen R\u00fcckmeldung vom letzten Blogeintrag (funktioniert nicht bei Tic-Tac-Toe, Nim, \u00fcberhaupt allen schwierigeren Spielen) und der kontinuierlichen R\u00fcckmeldung aus diesem Beitrag. Zweitens kann ich die Berechnung der Belohnung streng halten oder bereits Wissen einflie\u00dfen lassen. Drittens kann ich bei der Wahl der zust\u00e4nde bereits Wissen einflie\u00dfen lassen oder nicht.<\/p>\n\n\n\n
    F\u00fcr Breakout sieht der Unterschied beim Lernen so aus:<\/p>\n\n\n\n
    System der R\u00fcckmeldung<\/th>Berechnung der Belohnung via<\/th>Zustand:einfach
    (x-Differenz)<\/th>    		Zustand:schwierig
    (alle Daten)<\/th><\/tr><\/thead>
    Einmalig<\/td>x-Differenz
    (sehr leicht)<\/td>    		lernt schnell<\/em><\/td>spielt nach Lernphase nur rudiment\u00e4r (au\u00dfer bei gro\u00dfem Schl\u00e4ger)<\/em><\/td><\/tr>
    Einmalig<\/td>Abstand zum Ball
    (leicht)<\/td>    		lernt schnell<\/em><\/td>spielt nach Lernphase allenfalls rudiment\u00e4r (au\u00dfer bei gro\u00dfem Schl\u00e4ger)<\/em><\/em><\/td><\/tr>
    Einmalig<\/td>nur Sieg\/Niederlage
    (schwer)<\/td>    		lernt schnell<\/em><\/td>spielt nach Lernphase allenfalls rudiment\u00e4r (au\u00dfer bei gro\u00dfem Schl\u00e4ger)<\/em><\/em><\/td><\/tr>
    Kontinuierlich<\/td>x-Differenz
    (sehr leicht)<\/td>    		lernt schnell<\/em><\/td>lernt schnell<\/em><\/td><\/tr>
    Kontinuierlich<\/td>Abstand zum Ball
    (leicht)<\/td>    		lernt schnell<\/em><\/td>lernt einigerma\u00dfen<\/em><\/td><\/tr>
    Kontinuierlich<\/td>nur Sieg\/Niederlage
    (schwer)<\/td>    		lernt schnell<\/em><\/td>lernt langsam, aber lernt<\/em><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    Und noch gar nicht herumgespielt habe ich mit unterschiedlichen Werten f\u00fcr Lernrate oder Diskontierung.<\/p>\n\n\n\n
    Eine kleinere Neuerung: Exploration<\/h3>\n\n\n\n
    Das ist einfach! Normalerweise w\u00e4hlt der Agent in einem Zustand nicht einen zuf\u00e4lligen, sondern den qualitativ besten Zug, den mit dem h\u00f6chsten Q-Wert laut Tabelle. Manchmal will man aber, dass der Agent abenteuerlustiger ist. Eine Explorationsrate von 0,05 besagt, dass in 5% aller F\u00e4lle stattdessen ein ganz zuf\u00e4llig ausgew\u00e4hlter Zug gew\u00e4hlt wird. Der Vorteil: Der Agent probiert auch mal etwas aus, das nicht erfolgsversprechend aussieht, und st\u00f6\u00dft so m\u00f6glicherweise auf unerwartete L\u00f6sungen. Dieses explorative Verhalten kann man losgel\u00f6st von allen anderen Neuerungen betrachten.<\/p>\n\n\n\n
    int decideOnMove(String state) {\n if (Math.random()<explorationRate) { \n  return pickRandomMove(state);\n }\n else {\n  return pickBestMove(state);\n }\n}<\/code><\/pre>\n\n\n\n
    Neu eingef\u00fchrt:<\/font><\/strong> Die Explorationsrate.<\/p>\n\n\n\n
    Ausblick auf ein Problem<\/h3>\n\n\n\n
    Wenn die Anzahl der Zust\u00e4nde zu hoch wird, st\u00f6\u00dft man mit einer Q-Tabelle an technische Grenzen. Schon die 14000 Zust\u00e4nde beim vereinfachten Breakout sind eigentlich zu viel. Vielleicht sind ja manche Elemente, die den aktuellen Spielzustand ausmachen, manchmal<\/em> weniger relevant als andere und k\u00f6nnen je nach den anderen Elementen ignoriert werden? Dann benutzt man keine Q-Tabelle mehr, sondern ein Neuronales Netz – die Eingangswerte beschreiben den Zustand, die Ausgangswerte die m\u00f6glichen Z\u00fcge in diesem Zustand. Zu Erkl\u00e4rung und Beispiel werde ich aber wohl nicht mehr kommen, aber weiter unten sind ein paar Videos dazu verlinkt.<\/p>\n\n\n\n
    Ausblick: Alternativen zu Reinforcement Learning<\/h3>\n\n\n\n
    Wenn ich die L\u00f6sung eh schon wei\u00df, wei\u00df ich brauche ich keine Q-Tabelle, insbesondere, wenn ich den besten Zug aus den gegebenen Variablen mit einer einfachen Formel berechnen kann. Bei dem Breakout-Spiel geht das zum Beispiel leicht, ich muss einfach schreiben: wenn x-Position von Schl\u00e4ger gr\u00f6\u00dfer als x-Position der Kugel, dann gehe nach links, sonst nach rechts. Die Leistung der KI ist hier also nicht, auf eine L\u00f6sung zu kommen, die uns schwerer gefallen w\u00e4re.<\/p>\n\n\n\n
    Bei Tic-Tac-Toe ist das schon schwieriger. Auch da k\u00f6nnte ich mir vorher alle Z\u00fcge selber \u00fcberlegen und knackige Strategien formulieren. Au\u00dferdem es einfachere Algorithmen, dort auf eine L\u00f6sung zu kommen, etwa Minimax. Allerdings erfordert Minimax eine f\u00fcr jedes Spiel individuelle Bewertungsfunktion, das hei\u00dft, man muss sich als Mensch vorher mehr Gedanken gemacht haben, was eine gute Position und was eine schlechte ist – bei Maschinellem lernen findet das die KI selber heraus. Oder man macht das mit Brute Force durch Ausprobieren und Streichen von schlechten Z\u00fcgen und rekursivem Streichen weiterer Zust\u00e4nde\u2026 aber sind wir damit nicht doch wieder bei unserer ganz einfachen Form von Reinforcement Learning?<\/p>\n\n\n\n
    Bei einem Spiel, wo ein Auto einen fixen Parcour entlang fahren soll, gibt es schnell viele Zust\u00e4nde und keine einfache oder offensichtliche Formel, was in welchem Zustand zu tun ist. Statt da m\u00fchsam von Hand zu \u00fcberlegen, was in jedem Zustand das beste ist (links, rechts, geradeaus, bremsen, beschleunigen), l\u00e4sst man den Agenten das einfach durch Ausprobieren und Belohnen lernen. <\/p>\n\n\n\n
    Fu\u00dfnote: Unerwartetes Verhalten<\/h3>\n\n\n\n
    Die KI versucht ihr Verhalten zu optimieren angesichts der Vorgaben bei der Programmierung. Manchmal passen diese Vorgaben aber nicht zum programmierten System und zeugen so Verhalten, das man so nicht gewollt hat. Von Beispielen hatte ich immer wieder gelesen, aber jetzt hatte ich selber solche F\u00e4lle. Hintergrund: Mein Breakout hatte urspr\u00fcnglich einen Bug: Wenn der Schl\u00e4ger den Ball an einer bestimmten Position erwischte, irgendwo am Eck, dann rollte der Ball den Schl\u00e4ger entlang und prallte erst am anderen Ende des Schl\u00e4gers wieder ab. Das war nur manchmal so und hatte bei meinem urspr\u00fcnglichen Breakout-Projekt, in dem es noch gar nicht um Maschinelles Lernen ging, keine gro\u00dfen Auswirkungen, so dass ich mich nie darum gek\u00fcmmert hatte, das mal zu beheben.<\/p>\n\n\n\n
    Die KI, mit dem Auftrag, Punkte zu machen, und das n\u00e4mlich durch Ber\u00fchren des Balls mit dem Schl\u00e4ger, hat den Bug und sp\u00e4ter eine L\u00fccke im ersten L\u00f6sungsversuch gleich entdeckt und ausgenutzt. <\/p>\n\n\n\n