Vier gewinnt
Vier gewinnt ist ein Spiel, bei dem zwei Spieler abwechselnd unterschiedlich farbige Spielsteine in ein festes Raster werfen. Gewonnen hat der Spieler der zuerst mit seinen Spielsteinen ein Muster erreicht, bei dem vier Steine in einer Reihe sind. Ist das ganze Spielfeld voll und es wurde kein entsprechendes Muster erreicht ist das Spiel unentschieden.
In diesem Artikel geht es darum mittels Reinforcment Learning einen Computergegner zu erstellen.
Inhaltsverzeichnis
SS 2011
In der Version des Sommersemester 2011 von Daniel Wehring ist folgendes implementiert:
- GUI
- Spielen zweier menschlicher Spieler
- Spielen gegen einen Computergegner der zufällige Aktionen ausführt
- Agenten erstellt unter Verwendung des Reinforcment Learning-Frameworks von Patrick Boekhoven[1] mit JADE.
- Q Learning
- Sarsa
- Sarsa Lambda
WS 2011/2012
Bearbeitung in diesem Semester durch: Robin C. Ladiges
Noch zu machen:
- einbetten des erstellten Agenten / weiterentwickeln
- Ausprobieren Neuronale Netze dafür einzusetzen
zu KW42
geplant: SourceCode verstehen / ausführen, über Neuronale Netze informieren
Pakete angeguckt:
- vierGewinntGui
- vierGewinntGui.enums
- vierGewinntGui.view
- vierGewinntKI
Offen:
- Agent
Ausgeführt und etwas player vs maschine (Randomgegner) gespielt (possible Bug: Gegner wirft nie in die Reihe in die man grad geworfen hat).
maschine vs maschine ist in der GUI nicht nachvollziehbar, da das ganze Spiel sofort durchläuft und keine Pausen drin sind.
RL Learning verwendet laut SourceCode JADE, führt aber noch zu Exceptions beim Versuch es zu starten, da irgendeine Datei nicht gefunden werden kann. FIXED 17.10.: Argumente für JADE-Aufruf fehlerhaft (evtl. aufgrund von unterschiedlichen JADE Versionen), Aufruf führt nun nicht mehr zu einer Exception, und der Computer spielt gegen sich selbst.
Kapitel 14 "Neural Networks" in AI for game developers von D. M. Bourg und G. Seemann gelesen bis zum Source Code.
mögliche Optimierungen
- GamePanel.java : GUI mit Backbuffer arbeiten lassen (kein Flackern mehr)
- GamePanel.java::paintComponent(Graphics g) blauen Hintregrund einmal, statt 42 mal zeichnen.
- GamePanel.java::paintComponent(Graphics g) Referenzaufruf von ctrl.getModel().getMatrix() cachen
- Model.java : spielZuende() Ergebnis cachen, statt jedes mal neu aufzurufen in steinEinwerfenIn(int reihe)
- VG_Umwelt : doppelter Code zu Model.java
- VG_GUI : doppelter Code zu GamePanel.java
zu KW43
geplant: Optimierungen umsetzen, und offenes Modul angucken.
umgesetzt, dabei bemerkt, dass die Umsetzung des Spielstates der Felder bei mensch vs mensch, mensch vs maschine und maschine vs maschine auf Enumerated Integers, und bei RL Learning auf einfachen Integern basiert (weswegen die selben Methoden doppelt implementiert wurden). Immo durch eine Umwandlung vor der neuen gemeinsamen Methode umgesetzt, aber es wäre gut, wenn das im ganzem Programm einheitlich mit normalen Integers wäre.
Die Änderungen müssten noch ins SVN (IDE einrichten).
Das Agenten Modul ist schwer verständlich, da es kaum kommentiert und sehr umfangreich ist.
zu KW44
geplant: Vortrag über bisherigen Projektstand, vereinheitlichen der Spielfelder auf int, restlichen SourceCode begutachten
Extra Aufgabe: Laufzeitmessung um die bisherigen Optimierungen zu messen
Laufzeitmessung
Gemessen wurde die Zeit in VG_Umwelt.java::setup() die bei der Endlosschleife für das Sende_Reward Behavior benötigt wird (dieses Behavior verwendet die optimierte berechne_Reward() Methode). Die optimierten Teile der GUI zu messen macht keinen Sinn, da die Laufzeit sich hier nur minimal verbessert (oder sogar etwas verschlechtert) haben kann, und ein Unterschied hier auch sehr leicht an einem Messfehler liegen kann.
Gemessen wurde mit folgendem Code:
long a = System.currentTimeMillis();
seq.addSubBehaviour(new Sende_Reward(VG_Agenten.NAME_AGENT_1));
long b = System.currentTimeMillis()-a;
msall+=b;
msn++;
System.out.println("Durchschnittszeit: "+Double.toString((double)msall/(double)msn));
Gemessen wurde über einen Gesamtzeitraum von etwa 15 Minuten auf dem selben System (meinem Laptop) die Durchschnittszeit.
| Ergebnis | Durchschnittslaufzeit |
|---|---|
| alte Version | 19,287 ms |
| neue Version | 5,800 ms |
Also benötigt die neue Version zur Belohnungsberechnung nur noch etwa 30% der Zeit die Vorher benötigt wurde (etwa 70% schneller).
zu KW45
geplant: VG_Situation::definiere_ID() von long auf BigInteger ändern um Zustände eindeutig zu identifizieren.
Bugfix
possible Bug aus KW42, das der Random-Gegner nie in das eigene Feld wirft gefixt. Das Problem lag an der ComputerPlayerRandom::makeMove() Methode, die bei den zufälligen Zügen jene verwerfen sollte, bei denen die Reihe schon voll ist. Statt das oberste Feld zu prüfen ob es frei ist, wurde das unterste Feld überprüft (Offenbar Array-Index 0 mit 5 verwechselt...), wodurch der Computergegner nicht in Reihen werfen konnte, in die schon geworfen wurde. Das dies nicht früher aufgefallen ist, lag an einem Workaround, der bis zu 1000 mal (fehlerhaft) guckt ob die zufällig gewählte Reihe voll ist, und dann abbricht, um die letzte (womöglich eine wirklich volle Reihe) zu wählen.
Zustandsidentifizierung
VierGewinnt mit einem 7x6-Feld kennt 4,531 * 1012 Zustände [2], ein Integer mit 232 = 4,294 * 109 reicht da nicht aus. Ein Long mit 264 = 1,845 * 1019 würde dafür ausreichen. Das Problem ist der verwendete Algorithmus, der illegale Spielzustände die nicht erreicht werden können auch abbildet, so wird für das Spielfeld 342 = 1,094 * 1020 benötigt, was nicht in einen Long passt (mal davon abgesehen, das long in Java signed und nicht unsigned ist...). Es wäre für den Algorithmus mindestens eine Variable mit 67 bit nötig, um alle möglichen Zustände die das Spielfeld haben kann (nicht die die das Spiel haben kann) abzubilden. Von daher wird es auf BigInteger geändert, was einfacher ist, als sich einen komplexen Algorithmus zu überlegen um Zustände bijektiv auf Long-Zahlen abzubilden (rausfiltern von illegalen Zuständen in der Nummerierung).
zu KW46
geplant: krank
Zustandsidentifizierung 2
Statt BigInteger wird nun doch ein komplexerer Algorithmus implementiert.
Der Algorithmus erstellt eine Bit-Codierung, so dass für jede Reihe in 3 Bit (23 = 8, eine Reihe hat 6 Felder) festgehalten wird wieviele Spielfelder durch Spielsteine belegt sind, und für jede Reihe in 6 Bit ob das Feld mit einem Roten(Bit=0) oder einem Gelben(Bit=1) Stein belegt ist. Die Bits für die leeren Felder werden nicht beliebig mit 0 oder 1 belegt, da wir sonst unterschiedliche Long-Zahlen für ein und die selben Zustände hätten, deshalb wird sich auf 0 geeinigt. Die 0 hat dann zwar eine doppelt Belegung mit entweder Roten Steinen oder Leeren Feldern, aber dadurch das wir die Anzahl der belegten Steine speichern lässt sich dies unterscheiden.
Wir profitieren hierbei von der Eigenschaft, das wir pro Reihe nun nicht mehr 36 = 729 Zustände benötigen sondern nur noch 26 * 23 = 29 = 512, weil die Zustände mit Lücken zwischen Spielsteinen und Spielsteine die "in der Luft schweben" nicht mehr vorhanden sind. Genau genommen haben wir nur 26 * 6 = 384 mögliche Zustände pro Reihe, die zusätzlichen Zustände kommen von der Tatsache das wir Binär für die Zahl 6 mindestens 3 Bit benötigen (2 Bit mit maximum 4 reicht nicht aus).
Dadurch brauchen wir bei 7 Reihen (Spalten) lediglich (3+6) * 7 = 9 * 7 = 63 Bit für das gesamte Spielfeld. Da ein long in Java 64 bit hat, und ein Zeichen für das Vorzeichen reserviert ist (64 - 1 = 63), passt das genau hin.
Eine variable Länge der 6 Bits für die Belegung wäre zwar auch denkbar, aber dadurch ersparen wir letzendlich nichts im Vergleich zur festen Länge ein, da wir vom Schlimmsten Fall ausgehen müssen, das alle Felder belegt sind und wir die ganzen 63 Bit benötigen. Dieser Ansatz könnte in anderen Fällen, in denen z.B. eine ganze Reihe von Spielzuständen in eine Datei gespeichert oder ein einzelner Zustand übers Netzwerk übertragen werden soll, von Vorteil sein.
Zum Vergleich: der bisher implementierte Algorithmus errechnete Zahlen von 0 bis 342 = 1,094 * 1020 und der neue Algorithmus nur Zahlen von 0 bis (26 * 23)7 = (29)7 = 263 = 9,223 * 1018.
Beispiel für den Algorithmus
Folgender Spielzustand:
| Reihe (v.L.n.R.) | Anzahl Steine | Belegung (v.O.n.U., Frei, Gelb, Rot) | Binär (F=0, G=1, R=0) |
| 1 | 6 | GRGRGR | 110101010 |
| 2 | 5 | FGRGGG | 101010111 |
| 3 | 4 | FFRRRR | 100000000 |
| 4 | 6 | RGRRGG | 110010011 |
| 5 | 3 | FFFGRG | 011000101 |
| 6 | 3 | FFFRGR | 011000010 |
| 7 | 6 | RGGRRG | 110011001 |
Was zu der binären 64 Bit Zahl 0110101010101010111100000000110010011011000101011000010110011001 führt, was dezimal die 7.686.219.650.993.325.465 ist.
zu KW47
geplant: (1) Reinforcment Learning GUI Darstellung von JList zu JTable ändern (Werte in JTable updaten, statt immer die ganze JList neu zu erstellen wenn sich etwas ändert). (2) Nur die Zustände/Aktionen speichern, die durch den Lernalgorithmus einen vom Default 0 verschiedenen Wert bekommen.
zu KW48
geplant: Framework erweitern, um eine Factory zu übergeben um Situations_Aktionen zu erstellen.
Dadurch ist es möglich Situations_Aktionen selbst zu definieren, und so die hashCode und equals Methoden zu überschreiben.
Dies wird konkret verwendet, um aus den Q-Werten, mit denen das Framework arbeitet, V-Werte zu machen. Dadurch ist bei Vier Gewinnt eine Situations_Aktion definiert durch den Zustand in den man gelangt wenn man die Aktion in dem aktuellem Zustand ausführt.
zu KW49
geplant: entdeckten Fehler finden und beseitigen.
Der Fehler äußerte sich wenn eine verbotene Aktion auftritt, das man in der Ausgabe sehen konnte, das der Agent bereits von einer anderen Situation ausgeht, und nicht mehr von der, bei der die verbotene Aktion ausgeführt wurde.
Die Fehlerursache lag an dem von mir implementierten Factory aus der vorigen Woche, konkret in den Methoden um die Folgezustände zu berechnen. Hier habe ich fehlerhaft angenommen, das ein byte[][] Parameter in Java Call by Value ist, was aber in wirklichkeit Call by Reference ist, was dazu führte das bei jeder Berechnung einer Situations_Aktion die Aktion destruktiv verändert wurde.
Das desturktive Verändern von Situationen war aber an anderer Stelle auch schon vorhanden, wo mit einem Setter ein Situationsobjekt verändert wurde, was nun auch gefixt ist. Setter die nicht benötigt werden, und destruktiv die Frameworklogik verändern wurden entfernt.
zu KW50
geplant: Framework kommentieren, Lernalgorithmus und Parameter in GUI auswähl-/bestimmbar
zu KW51
geplant: Anwendung kommentieren, Lernalgorithmen auf Korrektheit prüfen und kommentieren.
zu KW02
geplant: Belohnungs-Verteilung überarbeiten und UML-Diagramme zeichnen.
UML-Sequenzdiagramm
Folgendes Diagramm zeigt die Kommunikation zwischen Umwelt und Agenten.
Im Code zu finden unter Agent_Frame.java (Kommunikationselement) und A_Umwelt.java (Kommunikation).
UML-Klassendiagramm
Folgendes Diagramm zeigt die Architektur des Frameworks und die Vererbung der Anwendungs-Klassen.
In der Mitte des Bilder ist die Klasse Agent von JADE, von der A_Umwelt und Agent_Frame erben. Beides sind also Agenten, und JADE ist für das Starten, Beenden, Sheduling und Nachrichten zwischen Umwelt und Agenten zuständig.
Ein Agent_Frame hat ein Lernelement (der Algorithmus der verwendet wird), Leistungselement (merken der Ergebnisse des Algorithmus, und basierend davon die beste Aktion auswählen) und Problemgenerator (zufällig Explorieren: etwas anderes ausprobieren, abhängig von der Wahrscheinlichkeit epsilon). Jedes Objekt der Klasse Agent_Frame hat ein eigenes JFrame zur Anzeige dessen Wertetabelle des Leistungselements. Welches Lernelement verwendet werden soll, und mit welchen Parametern, lässt sich in der von Agent_Frame erbenden Klasse steuern (konkret: VG_Agent_Frame).
Die Umwelt hält die Referenz auf die aktuelle Situation und ändert diese bei Aktionen der Agenten, sowie ein Objekt der abstrakten Klasse A_Uebergabe, über die Startparameter übergeben werden (Startsituation, mögliche Aktionen, etc). Die A_Uebergabe Klasse hat auch die optionale Möglichkeit eine andere Factory zu verwenden, mit der aus Situationen (A_Situation) und Aktionen (A_Aktion) Situations-Aktions Paare (A_Situation_Aktion) erstellt werden, dies ist z.B. bei Vier Gewinnt der Fall, in dem Situations-Aktions-Paare die zum gleichen Folgezustand führen als Äquivalent gelten.
Im Falle von Vier Gewinnt enthält die VG_Umwelt auch noch ein JFrame um das Spielfeld darzustellen. VG_Umwelt implementiert die abstrakten Methoden um die Bewertung für einen bestimmten Agenten zu bestimmen, sowie um zu prüfen ob eine Aktion erlaubt ist.
Die Klassen A_Situation und A_Aktion müssen (ebenso wie VG_Umwelt und VG_Agent_Frame) von der Anwendung realisiert werden. Sie benötigen die Implementation der Methode um eine eindeutige ID zu berechnen (siehe auch KW45/46), sowie im Falle von A_Aktion die Methode um aus einer gegebenen Situation bei der jeweiligen Aktion den Folgezustand zu berechnen.
zu KW03
geplant: Präsentationsfolien erstellen und UML-Klassendiagramm textuell ergänzen.
Quellen
- ↑ Patrick Boekhoven, Entwicklung eines Reinforcement Learning Frameworks auf Basis eines Agentensystems, 2011, Hamburg - URL http://edoc.sub.uni-hamburg.de/haw/volltexte/2011/1269/
- ↑ http://homepages.cwi.nl/~tromp/c4/c4.html
