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.

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 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 * 10¹² Zustände , ein Integer mit 2³² = 4,294 * 10⁹ reicht da nicht aus. Ein Long mit 2⁶⁴ = 1,845 * 10¹⁹ 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 3⁴² = 1,094 * 10²⁰ 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 (2³ = 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 3⁶ = 729 Zustände benötigen sondern nur noch 2⁶ * 2³ = 2⁹ = 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 2⁶ * 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 3⁴² = 1,094 * 10²⁰ und der neue Algorithmus nur Zahlen von 0 bis (2⁶ * 2³)⁷ = (2⁹)⁷ = 2⁶³ = 9,223 * 10¹⁸.

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.