{"id":23826,"date":"2023-03-06T06:22:55","date_gmt":"2023-03-06T05:22:55","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=23826"},"modified":"2023-05-04T07:18:11","modified_gmt":"2023-05-04T05:18:11","slug":"ki-reinforcement-learning-2","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2023\/03\/ki-reinforcement-learning-2.htm","title":{"rendered":"KI: Reinforcement Learning 2"},"content":{"rendered":"
(3 Kommentare.<\/a>)<\/small> <\/div>\n

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

Mit Reinforcement Learning kann sich eine selbst\u00e4ndig agierende KI, auch Agent<\/em> genannt, zum Beispiel beibringen, ein Spiel zu spielen, Pacman oder Space Invaders oder Pong oder Super Mario World oder ein Autorennspiel, oder gleich Auto zu fahren. Die Schwierigkeiten werden dabei allerdings immer gr\u00f6\u00dfer, und f\u00fcr die Schule wird man sich auf einfache F\u00e4lle beschr\u00e4nken m\u00fcssen.<\/p>\n\n\n\n

Ich will mich dem Konzept in zwei Schrittten n\u00e4hern. In diesem Blogeintrag geht es um den ersten davon: Aufschreiben, welche Entscheidungen direkt zu Erfolg und welche direkt zu Misserfolg gef\u00fchrt haben. Sp\u00e4ter dann die erfolgreichen verwenden, duh!<\/strong> Auch wenn dieser Blogeintrag sehr lang ist, geht es gar nicht um mehr als das; ich zeige das nur an etlichen Beispielen.<\/p>\n\n\n\n

Das Prinzip ist noch ganz einfach: Wenn eine Entscheidung in einer bestimmten Situation zu Erfolg, zum Beispiel Sieg in einem Spiel, gef\u00fchrt hat, merke ich mir das. Und wenn sie in einer bestimmten Situation zu Misserfolg, einer Niederlage in einem Spiel, gef\u00fchrt hat, merke ich mir das auch, Das Merken geschieht in einer Tabelle, die Q-Tabelle hei\u00dft. Das Q steht f\u00fcr Qualit\u00e4t, weil in der Tabelle die Qualit\u00e4t der Entscheidungen festgehalten wird, die Wertigkeit. <\/p>\n\n\n\n

Beispiel 1: Mau-Mau<\/h3>\n\n\n\n

Spielerin 1 denkt sich eine Ablageregel f\u00fcr Spielkarten aus, zum Beispiel eine vereinfachte Mau-Mau-Regel: man darf immer ablegen, wenn die eigene Karte den gleichen Wert oder die gleiche Farbe hat, sonst nicht. Spielerin 1 legt eine zuf\u00e4llige Karte ab, der Agent (Spieler 2) soll die geheime Regel herausfinden oder jedenfalls alle Karten legal zu spielen. Beim induktiven Kartenspiel Eleusis<\/strong>, hier oft genug thematisiert, geht es \u00fcbrigens genau darum, dass eine Person sich eine solche Regel ausdenkt und die anderen versuchen m\u00fcssen, ihre Karten passend auszuspielen.<\/p>\n\n\n\n

Nun schreibt man ein Programm, dass den Agenten ein paar Runden spielen l\u00e4sst und alles m\u00f6gliche ausprobieren l\u00e4sst. Er soll am Anfang wirklich zuf\u00e4llig Karten ausw\u00e4hlen und sich merken, ob der Zug gut war oder nicht. Wenn der Agent eine g\u00fcltige Karte ausgew\u00e4hlt hat, tr\u00e4gt er sich das in eine Tabelle ein, und wenn der Agent eine ung\u00fcltige Karte gespielt hat, ebenfalls. Schon recht bald hat sich der Agent diese Tabelle angelegt, wobei in der ersten Spalte jeweils der vorgefundene Zustand steht, also die oben liegende Karte, und in den folgenden Spalten die m\u00f6glichen Spieloptionen:<\/p>\n\n\n\n

<\/td>♥<\/font>A<\/td>♥<\/font>2<\/td>♥<\/font>3<\/td>♠A<\/td>♠2<\/td>♠3<\/td><\/tr>
♥<\/font>A<\/td>gut<\/td>gut<\/td>gut<\/td>gut<\/td>nicht gut<\/td>nicht gut<\/td><\/tr>
♥<\/font>2<\/td>gut<\/td>gut<\/td>gut<\/td>nicht gut<\/td>gut<\/td>nicht gut<\/td><\/tr>
♥<\/font>3<\/td>gut<\/td>gut<\/td>gut<\/td>nicht gut<\/td>nicht gut<\/td>gut<\/td><\/tr>
♠A<\/td>gut<\/td>nicht gut<\/td>nicht gut<\/td>gut<\/td>gut<\/td>gut<\/td><\/tr>
♠2<\/td>nicht gut<\/td>gut<\/td>nicht gut<\/td>gut<\/td>gut<\/td>gut<\/td><\/tr>
♠3<\/td>nicht gut<\/td>nicht gut<\/td>gut<\/td>gut<\/td>gut<\/td>gut<\/td><\/tr><\/tbody><\/table>
(Nur Ausschnitt der Tabelle, sie m\u00fcste breiter und l\u00e4nger sein, klar.)<\/figcaption><\/figure>\n\n\n\n

Wenn die Tabelle auf Basis der R\u00fcckmeldungen erstellt worden ist, wird der Agent keine falsche Karte mehr spielen. Kann man sagen, dass der Agent die geheime Regel kennt?<\/em> Vermutlich nicht. Das System funktioniert nat\u00fcrlich auch bei beliebig komplizierten Ablageregeln, sofern die nur von der oben liegenden Karte abh\u00e4ngen. Das Spiel Eleusis wird dadurch spannend, dass man nur eine begrenzte Anzahl an Versuchen hat, auf die Regel zu kommen, weil das durch schlichtes Ausprobieren ja sonst leicht ist.<\/p>\n\n\n\n

Neu eingef\u00fchrt in diesem Beispiel: <\/font><\/strong>Die Q-Tabelle.<\/p>\n\n\n\n

Ausblick auf ein sp\u00e4teres Problem: <\/strong>Wenn der Agent gerade noch am Lernen ist und die Tabelle so weit aufgebaut hat:<\/p>\n\n\n\n

<\/td>♥<\/font>A<\/td>♥<\/font>2<\/td>♥<\/font>3<\/td>♠A<\/td>♠2<\/td>♠3<\/td><\/tr>
♥<\/font>A<\/td>gut<\/td>gut<\/td>gut<\/td>gut<\/td>nicht gut<\/td>nicht gut<\/td><\/tr>
♥<\/font>2<\/td>gut<\/td><\/td><\/td>nicht gut<\/td>gut<\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

und wenn dann eine ♥<\/font>2 oben liegt, was soll der Agent dann machen? Sicher nicht die als „nicht gut“ \u00fcberpr\u00fcften und verworfenen Z\u00fcge, aber soll er die unbekannten ausprobieren oder sich auf die bereits gefundenen L\u00f6sungen verlassen? Bei diesem einfachen Spiel macht das keinen gro\u00dfen Unterschied, sp\u00e4ter wird das aber wichtiger werden. Exploration<\/em> hei\u00dft das Verhalten, auch mal riskantere Dinge auszuprobieren. Im Moment probiert unser Agent einfach willk\u00fcrlich alles aus, und wenn er fertig trainiert ist, nimmt er eine der guten M\u00f6glichkeiten.<\/p>\n\n\n\n

Beispiel 2: Monty Hall\/Das Ziegenproblem<\/h3>\n\n\n\n

Dieses Beispiel ist benannt nach dem Gastgeber und Produzenten der Show Let\u2018s Make A Deal<\/em>. (Auf Deutsch hei\u00dft das \u00c4quivalent Ziegenproblem, zuerst begegnet bei Gero von Randow.) Es gibt in der Show 3 geschlossene T\u00fcren, hinter einer ist der zu gewinnende Preis. Der Kandidat oder die Kandidatin w\u00e4hlt zuerst eine T\u00fcr, Monty Hall \u00f6ffnet eine andere T\u00fcr, hinter der garantiert kein Preis ist. (Das geht, weil Monty wei\u00df, wo der Preis ist.) Danach bietet Monty an, die Entscheidung zu wechseln auf die andere weiterhin geschlossene T\u00fcr. Soll man wechseln, soll man nicht wechseln, oder spielt es keine Rolle?<\/p>\n\n\n\n

Die L\u00f6sung herauszufinden ist f\u00fcr einen Menschen wohl nicht ganz einfach, deshalb wird dieses Problem auch gerne als Denksportaufgabe oder in B\u00fcchern \u00fcber Intuition und Wahrscheinlichkeit verwendet. Wenn man sich l\u00e4nger damit besch\u00e4ftigt oder das mal selbst programmiert hat, verschwindet die Verwirrung. Ich m\u00f6chte das als n\u00e4chstes Beispiel verwenden, eben weil die L\u00f6sung nicht ganz so offensichtlich ist.<\/p>\n\n\n\n

Neu sind aber zwei Dinge. Erstens, das Spiel besteht jetzt aus zwei Z\u00fcgen. In Zug 1 entscheidet man sich f\u00fcr T\u00fcr 1, 2 oder 3, in Zug 2 entscheidet man sich f\u00fcr oder gegen einen Wechsel zur von Monty angebotenen T\u00fcr. Nur der zweite Zug spielt eine Rolle, der erste ist v\u00f6llig egal, deshalb ist dieser Unterschied hier nicht wichtig. Zweitens jedoch ist das Spiel jetzt nicht mehr deterministisch. Egal ob sich der Wechsel von der Wahrscheinlichkeit her lohnt oder nicht, man kann mit jeder Entscheidung gewinnen oder verlieren. Ein blo\u00dfes gut\/nicht gut in der Q-Tabelle reicht also nicht. Wir schreiben stattdessen in die Tabelle die Anzahl der Erfolgsf\u00e4lle, z\u00e4hlen also schlicht mit, wie oft in einem bestimmten Spiel-Zustand die Entscheidung zu Erfolg gef\u00fchrt hat oder nicht. Der Spielzustand ist hier zum Beispiel mit dem kryptischen ?-1-2-0 notiert. Das ist so zu lesen: ? ist die unbekannte Gewinnt\u00fcr, die erste 1 die erste Entscheidung der Kandidatin, die 2 das Wechselangebot von Monty, und die letzte Ziffer die endg\u00fcltige Entscheidung der Kandidatin – hier eben noch nicht ausgef\u00fchrt. Bei 1000 Zufallsdurchg\u00e4ngen kamen folgende H\u00e4ufigkeiten von zum Gewinn f\u00fchrenden Z\u00fcgen heraus:<\/p>\n\n\n\n

Zustand<\/td>T\u00fcr 1<\/td>T\u00fcr 2<\/td>T\u00fcr 3<\/td><\/tr>
?-1-2-0<\/td>26.0<\/td>50.0<\/td>x<\/td><\/tr>
?-1-3-0<\/td>26.0<\/td>x<\/td>46.0<\/td><\/tr>
?-2-1-0<\/td>60.0<\/td>36.0<\/td>x<\/td><\/tr>
?-2-3-0<\/td>x<\/td>17.0<\/td>46.0<\/td><\/tr>
?-3-1-0<\/td>50.0<\/td>x<\/td>27.0<\/td><\/tr>
?-3-2-0<\/td>x<\/td>59.0<\/td>26.0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Man sieht: In jeder Zeile gibt es eine Entscheidung, die etwa doppelt so oft zu einem Gewinn gef\u00fchrt hat. Mehr wei\u00df die Tabelle auch nicht, der trainierte Agent w\u00e4hlt am Ende halt immer das mit der h\u00f6chsten Wertung aus. Nur der Mensch kann das Muster dahinter erkennen: Wechseln erh\u00f6ht die Chance auf einen Sieg immer!<\/p>\n\n\n\n

Daf\u00fcr brauche ich eigentlich kein Reinforcement Learning, das kann ich auch durch einfaches zuf\u00e4lliges Ausprobieren und Mitz\u00e4hlen herauskriegen. Aber ist nicht genau das, was unser Reinforcement Learning bis jetzt ohnehin ist?<\/p>\n\n\n\n

(Fu\u00dfnote zur Programmierung, weil ich das erst sp\u00e4ter gemerkt habe: Wenn auch Monty Hall durch einen zustandabh\u00e4ngigen Agenten gespielt wird, m\u00fcssen f\u00fcr den andere Zust\u00e4nde ausgegeben werden als f\u00fcr den Kandidaten.)<\/small><\/p>\n\n\n\n

Neu eingef\u00fchrt in diesem Beispiel:<\/font><\/strong> In der Q-Tabelle stehen jetzt Zahlenwerte, die sich \u00e4ndern k\u00f6nnen. Das ist hier n\u00f6tig, weil das Spiel ein Zufallselement enth\u00e4lt, Das er\u00f6ffnet sp\u00e4ter aber auch bei deterministischen Spielen neue M\u00f6glichkeiten, deshalb bleiben wir dabei.<\/p>\n\n\n\n

Beispiel 3: Schlag den Roboter<\/h3>\n\n\n\n

Dieses Beispiel wird in der Informatikdidaktik viel verwendet: Das kann man sch\u00f6n mit farbigen Schokolinsen und enaktiv umsetzen. Hier verwende ich das Material von Stefan Seegerer dazu, verlinkt ganz unten.<\/p>\n\n\n\n

Das Spiel ist eine Art Mini-Schach auf einem 3×3-Spielfeld, mit drei Bauern auf jeder Seite. Oben die Affen der menschlichen Spielerin, unten die Roboter (oder, in anderen Fassungen, Krokodile) des KI-Agenten.<\/p>\n\n\n\n

\"\"
Bild von hier: https:\/\/computingeducation.de\/proj-schlag-das-kroko\/<\/figcaption><\/figure>\n\n\n\n

Gezogen wird wie im Schach, gewonnen hat man, wenn man (1) die gegen\u00fcberliegende Seite mit einer Figur erreicht hat oder (2) alle gegnerischen Figuren geschlagen hat oder (3) der Gegner keinen Zug mehr machen kann,<\/p>\n\n\n\n

Die menschliche Spielerin 1 beginnt immer mit einem Zug der Affen. Der Agent ist immer Spieler 2, der mit den Robotern oder Krokodilen. Bei optimaler Strategie gewinnt Spieler 2 immer. Das ist am Anfang aber noch nicht offensichtlich, etwa wenn sich Sch\u00fclerinnen und Sch\u00fcler enaktiv als KI-Agent versuchen, dem Schokolinsen-Algorithmus folgend.<\/p>\n\n\n\n

Es insgesamt 37 verschiedene Spielzust\u00e4nde, denen der Agent begegnen kann, wovon 18 spiegelsymmetrische Varianten anderer Zust\u00e4nde sind. Am Ende sollte der Agent also eine Tabelle mit 37 gef\u00fcllten Zeilen erstellt haben. Zugm\u00f6glichkeiten gibt es mehr, n\u00e4mlich in meiner Schreibweise 14, wobei nicht alle Z\u00fcge in jedem Spielzustand legal m\u00f6glich sind; je nach Zustand stehen n\u00e4mlich maximal 4 zur Auswahl, meist sind es 2 oder 3. Wenn man eine Q-Tabelle verwendet, braucht man also 14 Spalten f\u00fcr die Werte. <\/p>\n\n\n\n

Wenn der Agent in einem dieser Zust\u00e4nde einen Zug ausprobiert, und danach gewonnen hat, wird der Wert in der Q-Tabelle f\u00fcr diesen Zug um eins heraufgesetzt. (Eine zus\u00e4tzliche Schokolinse inder Farbe des Zuges hingelegt.) Wenn der Agent in einem dieser Zust\u00e4nde ausprobiert und nach dem Zug von Spielerin 1 verloren hat, wird der entsprechende Wert in der Q-Tabelle um eins verringert. (Eine Schokolinse der passenden Farbe entfernt, etwa durch Aufessen.) Der Startwert f\u00fcr jeden Eintrag in der Q-Tabelle betr\u00e4gt, anders als beim vorherigen Beispiel 1 – letztlich weil man nur dann mit Schokolinsen arbeiten kann.<\/p>\n\n\n\n

Wenn der Agent mit seinem Zug weder unmittelbar gewonnen noch verloren hat, \u00e4ndert sich am Q-Wert in der Tabelle nichts. (Ein Ausblick: Das wird sich im n\u00e4chsten Blogeintrag \u00e4ndern.) <\/p>\n\n\n\n

Wenn man den Agenten 100000 mal gegen eine Zufallsspielerin spielen l\u00e4sst, ist danach eine Q-Tabelle entstanden, die f\u00fcr jeden Zustand und jeden in diesem Zustand m\u00f6glichen Zug Buch gef\u00fchrt hat, wie oft der Zug zu einem Sieg oder einer Niederlage gef\u00fchrt hat und wie oft nicht.<\/p>\n\n\n\n

Schauen wir uns ein paar Zust\u00e4nde an, hier der, den ich willk\u00fcrlich Zustand 1 genannt gabe, und zwar mit der Bewertung der Z\u00fcge am Anfang des Spiels. Es gibt drei m\u00f6gliche Z\u00fcge f\u00fcr Agent\/Roboter\/Krokodil, alle mit einem Schokoteil gleich hoch bewertet: <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Nach ein paar Runden hat sich die Bewertung aber ge\u00e4ndert. Man liest das so: 1 bedeutet einen Affen, 2 ein Krokodil oder einen Roboter, Move 63 bedeutet einen Zug von Zelle 6 nach Zelle 3. Die Zellen sind nummeriert von links oben 0 bis rechts unten 8.<\/p>\n\n\n\n

1      1|1|0     Move 63 (-3750.0)\n       0|0|1     Move 74 (-5645.0)\n       2|2|2     Move 75 (1.0) <\/code><\/pre>\n\n\n\n
In Schokoladenschreibweise:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Die drei m\u00f6glichen Z\u00fcge f\u00fcr den Agenten haben jetzt teilweise andere Werte. 7-4, also von unten mittig nach Mitte, hat einen negativen Wert; kein Wunder, mit diesem Zug verliert der Agent anschlie\u00dfend in einem von zwei m\u00f6glichen F\u00e4llen, weil Spielerin 1 einen Siegzug machen kann. Bei vielen Wahlen dieses Zuges wurde der Q-Wert beziehungsweise die Anzahl der Schokolinsen der entsprechenden Farbe um 1 verringert. (Es sind keine mehr da.) Der Wert von 6-3, also von unten links nach mittig links, ist ebenfalls niedrig, weil Spielerin 1 danach drei Optionen hat, von denen eine zur unmittelbaren Niederlage f\u00fcr den Agenten f\u00fchrt. Der Wert ist also oft verringert worden, aber nicht immer; erh\u00f6ht wurde er nie, weil er nie zu einem unmittelbaren Sieg f\u00fchrt. (Schokolinsen sind keine mehr da.) Und der Zug 7-5 hat noch die urspr\u00fcngliche Bewertung, da er weder unmittelbar zu einem Sieg f\u00fchrt noch  unmittelbar zu einer Niederlage f\u00fchren kann. (Die eine Schokolinse vom Anfang liegt weiter da.)<\/p>\n\n\n\n
\u00c4hnlich ist Zustand 4:<\/p>\n\n\n\n
4      1|0|0     Move 74 (-572.0)\n       1|0|1     Move 73 (1192.0)\n       0|2|2     Move 75 (-1253.0) <\/code><\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
In dieser Situation gibt es drei legale Z\u00fcge, 7-3 ist hoch bewertet, er f\u00fchrt ja auch zum unmittelbaren Sieg. (Spielerin 1 kann dann nicht mehr ziehen.) 7-5 ist sehr niedrig bewertet, er f\u00fchrt stets zur Niederlage. (Spielerin 1 kann dann nur einen Zug machen, einen Gewinnzug.) Und 7-4 ist nicht ganz so niedrig bewertet, er f\u00fchrt nicht automatisch, aber eben doch mit einer Chance von 50% zu einem unmittelbaren. Gewinnzug von Spielerin 1. (Im Schokolinsenmodell ist 7-3 heraufgesetzt, die anderen Z\u00fcge haben keine Linsen mehr; der Unterschied zwischen 7-4 und 7-5 kann mit den Schokolinsen nicht modelliert werden.)<\/p>\n\n\n\n
Auf andere Art interessant ist Zustand 34:<\/p>\n\n\n\n
34     0|0|0     Move 84 (-1212.0)\n       1|1|1\n       0|0|2 <\/code><\/pre>\n\n\n\n
Alle M\u00f6glichkeiten (okay, es gibt nur eine) haben einen stark negativen Wert. Das hei\u00dft, in diesem Zustand gibt es keine M\u00f6glichkeit mehr, zu gewinnen. Es m\u00fcsste also eigentlich Folgendes geschehen: Der vorhergehende<\/em> Zug des Agenten, der dazu f\u00fchrt, dass Spielerin 1 den Agenten mit ihrem Zug \u00fcberhaupt erst in diese bl\u00f6de Situation  Nummer 34 bringen kann, m\u00fcsste negativ bewertet sein. Aber das geht nicht, weil ja nur unmittelbare Sieg- oder Niederlage-Z\u00fcge bewertet werden und nicht mittelbare.<\/p>\n\n\n\n
Ein solcher Zustand, der theoretisch zu Nummer 34 f\u00fchren kann, ist Nummer 13:<\/p>\n\n\n\n
13     0|1|0     Move 64 (-1875.0)\n       1|1|0     Move 85 (-1222.0)\n       2|0|2     Move 84 (1899.0) <\/code><\/pre>\n\n\n\n
Der bietet Move 8-4, der zu unmittelbarem Sieg f\u00fchrt (Spielerin 1 kann dann nicht mehr ziehen und verliert deswegen); Move 6-4, der zu unmittelbarer Niederlage f\u00fchrt (Spielerin 1 hat dann nur eine legale Zugm\u00f6glichkeit, die ihr dann den Gewinn bringt); und Move 8-5, der deshalb niedrig bepunktet ist, weil er zu unmittelbarer Niederlage f\u00fchren kann<\/em>, und nicht<\/em> deshalb, weil er auch im anderen Fall im \u00fcbern\u00e4chsten Zug garantiert<\/em> zur Niederlage in Form von Zustand 34 f\u00fchren wird. Im Idealfall h\u00e4tte  8-5 einen \u00e4hnlich hohen Negativwert wie 6-4, weil er ebenso alternativlos zu einer Niederlage f\u00fchrt, nur halt teilweise erst sp\u00e4ter. – Im Minischach spielt das keine gro\u00dfe Rolle, weil alle Z\u00fcge, die zu Nummer 34 f\u00fchren k\u00f6nnen, aus anderen Gr\u00fcnden niedrig bewertet sind. Im n\u00e4chsten Beispiel wird das schon anders sein.<\/p>\n\n\n\n
Mein kleiner Vorbehalt gegen\u00fcber der enaktiven Schokolinsenversion: Man vollzieht dabei Schritt f\u00fcr Schritt nach, was der Algorithmus macht, hat aber vielleicht keinen Blick auf das Prinzip dahinter: alles ausprobieren, sich Gewinn- und vor allem Niederlagenz\u00fcge merken und das beim n\u00e4chsten Mal im gleichen Zustand ber\u00fccksichtigen. <\/p>\n\n\n\n
Neu eingef\u00fchrt in diesem Beispiel:<\/font><\/strong> Ein erster Hinweis darauf, dass Sackgassen-Z\u00fcge nicht erkannt werden, also Z\u00fcge, die mittelbar immer zu einer Niederlage f\u00fchren.<\/p>\n\n\n\n
Beispiel 4: Tic-Tac-Toe<\/h3>\n\n\n\n
Bei diesem Beispiel wird das Problem, das im Minischach noch wenig wichtig war, deutlicher. Tic-Tac-Toe, das ist das hier:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Die neun bespielbaren K\u00e4stchen habe ich wieder von 0 bis 8 durchnummeriert.  Eine „1“ in einem K\u00e4stchen bedeutet Spielerin 1, eine „2“ Spieler 2, eine „0“, dass es leer ist. Die gezeichnete Situation oben sieht f\u00fcr den Rechner also eher so aus wie das hier:<\/p>\n\n\n\n
1|2|2\n2|1|1\n2|2|1<\/code><\/pre>\n\n\n\n
Bei diesem Spiel soll der Agent lernen, vor dem Menschen drei in eine Reihe zu bringen. Das Prinzip ist wieder das gleiche: Aus allen legalen Z\u00fcgen w\u00e4hlt der Agent erst einmal willk\u00fcrlich einen aus; wenn der Agent danach gewonnen hat, gut; wenn er verloren hat, nicht gut. Es gibt jetzt allerdings viel mehr zu ber\u00fccksichtigende Zust\u00e4nde, n\u00e4mlich 2097 – 9 davon mit 8 Zugm\u00f6glichkeiten (n\u00e4mlich der erste Zug des Agenten in der Rolle von Spieler 2), die anderen 7 bis 1. Viele davon sind symmetrische Varianten anderer Zust\u00e4nde. Das kann man nicht mehr gut in einer Tabelle aufschreiben, aber f\u00fcr einen Computer ist die Verwaltung solch einer Tabelle immer noch sehr leicht.<\/p>\n\n\n\n
Der Startwert f\u00fcr jeden Zug ist wieder 1,0 wie im letzten Beispiel. Ohne Schokolinsenz\u00e4hlung w\u00e4re ein Startwert von 0,0 naheliegender, so wie bei Monty Hall \u00fcbrigens, aber ich habe das mal so gelassen, der Einfachheit halber.<\/p>\n\n\n\n
Wenn man den Agenten 200000 mal Tic-Tac-Toe gehen Zufallsspielerin 1 spielen l\u00e4sst (weniger w\u00e4re sicher auch okay), dann kommt am Ende eine Q-Tabelle heraus, die aus Zeilen wie dieser besteht, hier lesbar aufbereitet:<\/p>\n\n\n\n
0|0|0     Move 0 (-15.0)
1|2|2     Move 1 (-13.0)
0|1|1     Move 2 (-5.0)
          Move 6 (1.0)<\/code><\/pre>\n\n\n\n
Das liest man wieder so: Beim angegebenen Spielstand hat Move 0 (eine 2 links oben setzen) den Wert -15, Move 1 (eine 2 oben mittig) den Wert -13, auch Move 2 (oben rechts) ist negativ. Das liegt jeweils daran, dass diese Z\u00fcge \u00f6fter zu einer unmittelbaren Niederlage als zu einem unmittelbaren Sieg gef\u00fchrt haben. Genauer gesagt, sie haben niemals zu einem unmittelbaren Sieg gef\u00fchrt, und manchmal zu einer unmittelbaren Niederlage. Nur manchmal, weil die Zufallsspielerin 1 ja manchmal \u00fcbersieht, dass sie eine Siegm\u00f6glichkeit hat. Move 6 dagegen hat eine Quality von 1,0, das ist der unver\u00e4nderte Startwert, weil dieser Zug nie zu einem unmittelbaren Sieg oder einer unmittelbaren Niederlage gef\u00fchrt hat. Kann er ja auch gar nicht.<\/p>\n\n\n\n
Ein zweiter Tabelleneintrag; <\/p>\n\n\n\n
1|0|2     Move 1 (86.0)\n0|2|1     Move 3 (1.0)\n1|2|1<\/code><\/pre>\n\n\n\n
Hier gibt es nur zwei legale Zugm\u00f6glichkeiten, die eine hat 85 mal zum Sieg gef\u00fchrt, die andere hat nie zu Sieg oder Niederlage gef\u00fchrt – kein Wunder, die f\u00fchrt immer zu unentschieden.<\/p>\n\n\n\n
Die Frage, f\u00fcr welchen Zug man sich entscheiden soll, wenn mehrere nicht offensichtlich unsinnige zur Auswahl stehen, bleibt weiterhin erst einmal akademisch. Der Agent kann weniger oder mehr explorativ vorgehen, und entweder den jeweils bisher am h\u00f6chsten bewerteten Zug w\u00e4hlen, oder auch einmal einem anderen eine Chance geben. Beim aktuellen Spiel macht das keinen Unterschied, aber das wird sich noch einmal \u00e4ndern.<\/p>\n\n\n\n
Das kleine Problem vom letzten Beispiel versch\u00e4rft sich:<\/strong><\/p>\n\n\n\n
1|0|0     Move 1 (1.0)\n0|0|0     Move 2 (1.0)\n0|0|0     Move 3 (1.0)\n          Move 4 (1.0)\n          Move 5 (1.0)\n          Move 6 (1.0)\n          Move 7 (1.0)\n          Move 8 (1.0)<\/code><\/pre>\n\n\n\n
Wenn Spielerin 1 ihr erstes Kreuz links oben macht, sind f\u00fcr den Agenten alle Zugm\u00f6glichkeiten von der gleichen Qualit\u00e4t. Keiner f\u00fchrt n\u00e4mlich unmittelbar zu Sieg oder Niederlage, deshalb \u00e4ndert sich die Bewertung nie, da mag der Agent so viel trainiert haben, wie er m\u00f6chte. Aber erfahrene Spieler wissen: Fast alle Z\u00fcge f\u00fchren in dieser Situation zwar nicht automatisch, aber doch bei einer einigerma\u00dfen gewitzten Gegenspielerin im \u00fcber-\u00fcbern\u00e4chsten Zug zu einer Niederlage, sind also ein Fehler. Nur Move 4 ist sinnvoll. Unser Agent hat bislang keine Chance, das zu lernen, weil der Q-Tabellen-Eintrag bislang immer nur vom unmittelbaren folgenden Feedback abh\u00e4ngt.<\/p>\n\n\n\n
Hier eine Grafik, die das Problem noch einmal auf andere Weise darstellt. Die gelb markierten Z\u00fcge sind die, die in der Situation zu einer gleich folgenden Niederlage gef\u00fchrt haben; die werden herabgestuft. Die orange markierten Z\u00fcge sind die, die mittelbar<\/em> zu einer Niederlage f\u00fchren; ihr Wert bleibt nach dem bisherigen System leider unver\u00e4ndert:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Neu eingef\u00fchrt in diesem Beispiel:<\/font><\/strong> Nichts, aber das Problem der Sackgassenz\u00fcge wird deutlicher.<\/p>\n\n\n\n
Beispiel 5: Nim<\/h3>\n\n\n\n
Lasse ich weg, es gilt daf\u00fcr das gleiche wie f\u00fcr Tic-Tac-Toe.<\/p>\n\n\n\n
Beispiel 6: Breakout<\/h3>\n\n\n\n
In Breakout prallt ein Ball von allen W\u00e4nden und dem Schl\u00e4ger ab; der Agent soll lernen, den Schl\u00e4ger so zu steuern, dass der Ball erreicht wird. Ber\u00fchrt der Schl\u00e4ger den Ball, z\u00e4hlt das als Sieg; ber\u00fchrt der Ball den Boden, z\u00e4hlt das als Niederlage. Man l\u00e4sst den Agenten eine Zeitlang spielen und alles ausprobieren und eine Q-Tabelle anlegen.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Die erste Frage, die man sich stellt: <\/strong>Welche Zust\u00e4nde sollen in die Q-Tabelle eingetragen werden? Relevant sind m\u00f6glicherweise die x- und y-Position des Balls, die x-Position der Schl\u00e4gers, die Geschwindigkeit des Balls (falls es da Unterschiede gibt) und sein Drehwinkel. Selbst wenn man gro\u00dfz\u00fcgig rundet und das nicht pixelgenau misst, sonder gruppiert, landet man schnell bei 27000 Zust\u00e4nden (experimentell herausgefunden bei den Dimensionen meines Spieles), die verwaltet werden wollen. Dazu aber mehr im n\u00e4chsten Beitrag. Vorab: Wenn man schon wei\u00df, welcher Faktor oder welche Faktoren wirklich relevant sind f\u00fcr die L\u00f6sung des Problem, kann man sich darauf beschr\u00e4nken. Und beim einfachen Breakout oben reicht die Differenz der x-Positionen von Kugel und Schl\u00e4ger. <\/em>Alles  andere ist vorerst egal. Dann gibt es je nach Spielfeldgr\u00f6\u00dfe und eventueller Pixel-Zusammenlegung nur ein paar Dutzend Zust\u00e4nde. – Die Anzahl der m\u00f6glichen Entscheidung ist bei jedem Zustand ohnehin klein: Der Agent kann den Schl\u00e4ger nach links, nach rechts, oder gar nicht bewegen, abgek\u00fcrzt L, R, N.<\/p>\n\n\n\n
Die zweite Frage, die man sich stellt: <\/strong>Was soll als Sieg oder Niederlage gelten? Im n\u00e4chsten Blogeintrag wird das differenzierter, aber f\u00fcr jetzt gilt einfach: Den Ball mit dem Schl\u00e4ger zu ber\u00fchren z\u00e4hlt als Sieg, der Ball an der Unterkante des Spielfelds z\u00e4hlt als Niederlage.<\/p>\n\n\n\n
Wird das reichen, um erfolgreich spielen zu lernen, oder werden wir wie bei Tic-Tac-Toe keinen Erfolg haben?<\/p>\n\n\n\n
Nehmen wir an, wir haben den Zustand -12 oder +12. Der Schl\u00e4ger ist im einen Fall deutlich links vom Ball, im anderen weit rechts davon:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Wenn der Ball weit oben ist, wird sich die Q-Tabelle nicht \u00e4ndern, weil unmittelbar weder Sieg noch Niederlage folgen. Wenn der Ball weit unten ist wie im Bild,  f\u00fchren weder L noch R noch N zu einem Erfolg, sondern alle zu einer Niederlage. Die Q-Werte werden demnach nach Durchf\u00fchrung der Bewegung herabgesetzt, aber im Mittel alle gleich viel. Es gibt mittelfristig keinen Favoriten. Zustand -12 oder +12 sagen dem System letztlich beide gar nichts. <\/p>\n\n\n\n
Nehmen wir jetzt an, das Spiel ist im Zustand -7 oder +7 und gleichzeitig ist der Ball weit unten, so wie in diesem Bild:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Dann ist der Schl\u00e4ger knapp links oder rechts vom Ball, und jetzt f\u00fchrt die eine Entscheidung zu Sieg und die andere nicht. Es wird also in diesem Zustand jeweils der Wert der entsprechenden Entscheidung heraufgesetzt. (Und die Zust\u00e4nde -6 bis +6 f\u00fchren ohnehin nie zu einer Niederlage, und wenn der Ball weit unten ist, sogar zu einem Erfolg.)<\/p>\n\n\n\n
Die KI kann also lernen, in einigen wenigen Grenzsituationen das richtige zu tun, in allen anderen F\u00e4llen wird sie zuf\u00e4llig agieren. Reicht das?<\/p>\n\n\n\n
Ja, das reicht tats\u00e4chlich, um dieses simple Breakout spielen zu k\u00f6nnen. H\u00e4tte ich nicht gedacht! Warum klappt das da und bei Tic-Tac-Toe nicht? Bei Tic-Tac-Toe kommt der Agent nicht umhin, in einen bl\u00f6den Zustand zu kommen, wo man schon verloren hat, es aber noch nicht wei\u00df.  Bei Breakout ist es so, dass der Agent fr\u00fcher oder sp\u00e4ter in einen aus einer kleinen Menge von erfolgreichen Zust\u00e4nden kommt und sich immer nur innerhalb dieser Menge von Zust\u00e4nden bewegt. Klarer wird das vielleicht im Video:<\/p>\n\n\n\n