spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo zusammen,

hier möchte ich euch mein aktuelles Projekt "LightBulb" vorstellen und den Thread als kleinen Entwlicklerblog nutzen. Da ich mich zur Zeit mit künstlichen Neuronalen Netzen und Evolutionären Algorithmen beschäftige und diese Themen sehr interessant finde, habe beschlossen dazu ein Framework zu schreiben.

Ziel

Das Ziel ist in erster Linie, dass ich mir dabei mehr Wissen über die oben genannten Themen aneigne (learning by doing ). Es wäre aber auch toll am Ende ein Framework zu haben, das vorzugsweise bei Spielen eingesetzt werden kann um z.B. KIs automatisch generieren zu lassen oder KIs zu verwenden die noch während dem Spielen weiterlernen und sich dem menschlichen Spieler anpassen.

Aktuell schon implementierte Features

• Backpropagation
  
• ResilientBackpropagation
  
• BackpropagationThroughTime
  
• TruncatedBackpropagationThroughTime
  
• CascadeCorrelation
  
• Hopfieldnetze
  
• Lernende Vektorquantisierung (LVQ1,LVQ2,LVQ3,OLVQ1)
  
• RBF-Netze
  
• RealTimeRecurrentLearning
  
• Self-organizing maps
  
• SchmidhuberLearning
  
• Evolution
  
• Coevolution
  

Dabei ist zu beachten, dass natürlich nicht alle der oben genannten Features perfekt für alle Anwendungsfälle getestet wurden. Meistens ging ich einfach so vor, dass ich nach der Implementierung die Lernregel mit zwei drei kleinen Beispielen getestet habe und bin dann falls das funktioniert hat zum nächsten Teilbereich übergegangen.

Technisches:

• Das Ganze ist in c++11 implementiert
  
• Als IDE verwende ich hauptsächlich VS, es läuft aber auch mit ein paar Anpassungen unter Eclipse&Linux
  
• Der Code is OpenSource und kann unter GitHub begutachtet werden
  
• Für graphische Darstellungen wird 'SFML' und als Lineare-Algebra Framework 'Eigen' verwendet
  

Todos:

• Aktuell bin ich dabei den Kern des Frameworks (Implementierung der Neuronalen Netze) zu überarbeiten (aus Performancegründen)
  
• Generieren von KIs durch Evolutionäre Algorithmen für einige weitere kleine Spiele wie Pong, 4-gewinnt...
  
• Entwicklung von Unit-Tests (Nutze dafür GoogleTest)
  
• Vereinfachung der Nutzung des Frameworks
  

Anwendungsbeispiele:

Das aktuell beeintruckendste und aufwändigste Beispiel ist die Entwicklung einer TicTacToe KI. Dabei wird durch Evolutionäre Algorithmen ein Neuronales Netz entwickelt das perfekt TicTacToe spielen kann. (Perfekt heißt hierbei, dass die KI nicht verlieren kann!) Dafür wird keine vorgegebene KI benötigt, sondern es wird vielmehr CoEvolution genutzt. Vereinfacht ausgedrückt, verbessern sich die NNs dabei schrittweiße indem sie gegen andere NNs aus der gleichen Population antreten. Danach werden die schlechtesten aussortiert... etc.

Falls ihr die finale KI einmal austesten wollt, könnt ihr das hier online tun:



Freue mich über Feedback und Fragen

Zitat von »anti-freak«

Wie einfach wäre es, dein Framework zu nutzen, statt sich selbst was eigenes zu bauen?

Das ist eigentlich ganz einfach:
Ich erkläre es mal an dem TicTacToe Beispiel.
Man muss eigentlich nur zwei Klassen erstellen: Eine EvolutionWorld-Klasse und eine EvolutionObject-Klasse.

Die EvolutionObject-Klasse (-> TicTacToeAI) stellt ein Individuum/eine KI dar und muss nur die Funktionen getNNInput() und interpretNNOutput() implementieren. Also in der Klasse muss festgelegt werden wie die NN-Eingaben bestimmt werden und wie die NN-Ausgaben interpretiert werden.

In TicTacToeAI wird in getNNInput() also die Eingabe aus dem aktuellen Spielfeld zusammengebastelt:
2 Eingaben pro Feld: 0 0 => frei, 1 0 => X, 0 1 => O Also insgesamt 18 Eingabewerte.
In interpretNNOutput() wird aus den 9 Ausgabewerten die erste Ausgabe mit Wert "1" gesucht und dann versucht das dementsprechende Feld für den aktuellen Spieler zu setzen.

Die EvolutionWorld-Klasse (-> TicTacToe) stellt die Umgebung der KIs dar und muss nur die Funktion simulateGame(obj1, obj2) implementieren. Sie muss also bestimmen können welches der beiden EvolutionObjects besser ist.

In TicTacToe wird in simulateGame() zuerst ein Spiel simuliert in dem die erste KI anfängt und dann ein Spiel in dem die zweite anfängt. So wird dann bestimmt welche KI besser ist bzw. ob beide gleich gut sind.

Das ist alles den Rest macht dann die Coevolution learningRule.

Zitat von »anti-freak«

Interessant, wie ließe sich das aber in einem etwas komplexerem Spiel, wie z.B. im Age of Empire Style (oder so eine Art Tower Defense) umsetzen?

Da liegt das einzige Problem. Je komplexer das Problem ist, desto größer muss das Neuronale Netz gewählt werden (Mehr Eingänge, Mehr Ausgänge, Mehr Hidden-Layers...) und desto größer wird der Suchraum. Es dauert also viel viel länger eine brauchbare KI zu entwickeln.
Wie genau sich dass jetzt bei anderen Spielen entwickelt, muss ich erst noch testen.
Beim TicTacToe Beispiel wurden zum Finden einer perfekten KI ~700 Generationen und 480 Millionen simulierte TicTacToe Partien benötigt. Das ganze dauerte bei meinem PC so ca. 2h.
Ich glaube aber, dass sich das noch drastisch verbessern lässt und so habe ich auch in nächster Zeit vor da noch ein bisschen an den Parametern zu drehen.

Zitat von »Koschi«

Gibt es schon irgend ein (Externes)System nach dem die Neuronen Spielregeln lernen können oder muss das alles Programmiert werden?

Ich weiß nicht genau, ob ich die Frage richtig verstanden habe. Vielleicht habe ich sie oben jetzt auch schon beantwortet, aber die spielregeln muss man den neuronen nicht extra "erklären". Man muss den Netzen nur ihre Eingabewerte liefern, was meistens der aktuelle Spielstand ist. Durch "survival of the fittest" wird dann nach einiger Zeit automatisch eine KI gefunden, die die Spielregeln beherrscht.

Zitat von »Koschi«

Und kann man einen Lernfortschritt abspeichern und wieder herstellen?

Aktuell noch nicht, ist aber ein Must-Have Feature, das ich auf jedenfall noch implementieren werde. Also sowohl das Speichern/Laden von Neuronalen Netzen, als auch von Lernfortschritten.
Das einzige das es aktuell in der Richtung gibt ist ein "SynapticExporter" der ein NN für Synaptic (ein JS-Framework für Neuronale Netze) exportiert. Das war für die kleine Online Simulation nötig

Ich hatte mich ehrlich gesagt bis jetzt noch nicht allzu sehr mit diesem Thema beschäftigt. Nach einigen Recherchen tendiere ich aber aktuell zur zlib/libpngLizenz.

Hallo zusammen,

es hat sich einiges getan in den letzten Monaten und ich dachte, ich teil euch hier mal die größten Änderungen mit

Überarbeitung der Repräsentation von Neuronalen Netzen:

Bisher hatte ich einen sehr Objektorientierten Ansatz. (Eigene Klassen für Neuron, Edge, Network...) Das ganze ist zwar toll wenn man seine Neuronalen Netze flexibel gestalten will, es ist aber auch ziemlich unperformant. Somit bin ich dann nach einigen Tests zur etwas üblicheren Repräsentation durch Vektoren und Matrizen gewechselt. Es werden nun also Gewichte und Aktivierungwerte von Neuronen layerweise durch Vektoren/Matrizen abgespeichert. Der große Vorteil ist dabei, dass nun die Berechnung der Netzausgänge um einiges schneller durch Matrix-Vektormultiplikation durchgeführt werden kann. (Um die ganze Lineare Algebra Rechnerei kümmert sich wie schon mal erwähnt das Framework Eigen, mit dem ich echt zufrieden bin)
Mein einziges Bedenken war damals, dass sich dieser Vorteil mit dem nun aufwändigeren Umbau der Netze wieder relativiert. Es hat sich aber später herausgestellt, dass die Berechnung der Netzausgänge viel öfter als eine Änderung der Topologie durchgeführt wird. Somit ist der zusätzliche Overhead (fast) egal.

Leider muss ich nun auch alle Lernregeln noch einmal überarbeiten, was sehr zeitaufwändig sein kann. Deswegen sind zur Zeit alle etwas unwichtigeren Lernregeln deaktiviert. Ich möchte mich jetzt erst mal auf Evolutionäre Optimierung konzentrieren.


Grafische Oberfläche:

Die meiste Zeit seit Januar ging für die grafische Darstellung drauf. Aber es hat sich gelohnt
Am Anfang wollte ich dazu ja weiterhin SFML verwenden. Habe für Textboxen und CO. dann auch SFGUI dazu geholt, aber mir war das ganze dann einfach zu wenig. Da fehlen einfach viele Sachen wie Listen oder Out-Of-The-Box MultiWindow Management. Ist halt doch eher für Spiele gedacht. Dann bin ich zu wxWidgets gewechselt und ich muss sagen ich bin echt begeistert. Eins der besten Frameworks die ich kenne. Hat so ziemlich jedes Feature das man sich nur vorstellen kann, ist Plattformunabhängig, nutzt die native Styles... Kann ich echt nur empfehlen.

Die GUI kann aktuell schon folgendes:

• Auflistung und Verwaltung von NeuralNetworks und TrainingPlans (Ein TrainingPlan ist einfach eine Beschreibung des Lernprozesses zu einem spezifischen Problem)
  
• Paralleles ausführen mehrerer TrainingPlans
  
• Konfiguration von TrainingPlans
  
• Anzeige der Netze mit allen Neuronen, Gewichten
  
• Zeichen von Datasets (Trainingerror, Netzgröße...) (Dazu nutze ich die Erweiterung wxFreeChart, auch sehr toll )
  
• Laden/Speichern von Netzen und TrainingPlans (Hier nutze ich das Framework cereal. Serialisierung ist zwar unter C++ manchmal etwas umständlich aber es läuft.)
  
• Anzeigen des Logs
  
• Ausführen von Berechnungen an einem Neuronalen Netz
  
• ...
  

Einfach dazu die Bilder im Anhang bewundern.


Aufteilung des Projekts:

Im Zuge der GUI Entwicklung habe ich das Projekt auch etwas besser aufgeteilt in:

• LightBulb (quasi die CoreLibrary)
  
• LightBulbApp (hier ist die GUI mit dabei)
  
• LightBulbExample (Eine Beispielanwendung, die aktuell 10 Example training plans enthält)
  

Strukturoptimierung:

Ja auch in dieses Gefilde hab ich mich gewagt. Die Topologie der Neuronalen Netze kann nun also auch während der Suche nach den besten Gewichten durch Evolution optimiert werden. Dazu habe ich u.a. das hier beschriebene Phased Searching eingebaut.


TicTacToe:

Hier habe ich noch etwas optimiert und konnte durch bessere Parameter die Zeit bis eine perfekte TicTacToe KI gefunden wird von mehreren Stunden auf 8min verkleinern. Dabei müssen 25 Millionen TicTacToe Spiele simuliert werden. Bei eingeschalteter Strukturoptimierung sind es leider etwas mehr (ca. 45-50 Millionen Spiele).


Sonstiges:

Ein paar kleinere Dinge haben sich noch getan. So hab ich die Unit Tests weiter ausgebaut und habe nun auch endlich angefangen LightBulb mit Pong zu testen. Das scheint auch sehr gut zu klappen, also anscheinend ist Pong einfacher zu lernen als TicTacToe (Aber dazu mehr demnächst)
Außerdem bin ich vor kurzen auf Reinforcment Learning gestoßen. Das scheint auch sehr interessant zu sein. Ich glaub das teste ich mal aus.

Danke

Ja aktuell werden alle Berechnungen über die CPU ausgeführt. Es wäre aber echt mal spannend da die GPU mit einzubinden. Hab nur keine Ahnung wie das geht. Da muss ich mich mal schlau machen Aber da könnte man wahrscheinlich echt noch einiges an Performance rausholen.