MemBrain Neural Network Editor + Simulator User Forum

Hallo zusammen,
erst einmal ich bin komplett neu bei KNN.
Kurz zur Schilderung des Projekts:
Ziel ist es ein KNN zu entwerfen und zu trainieren, welches ein Brettspiel möglichst gut spielt. Also praktische eine Spiele KI.
Es handelt sich bei dem Spiel um das Spiel "Manhattan". Das ganze gibt es für den PC und ist hier http://www.informatik.uni-kiel.de/softw ... /download/ zu downloaden (Server GUI). Falls ihr es euch nicht kurz anschauen wollt kann ich auch kurz die Regeln erklären.
Dazu die ersten Fragen. Ist es sinnvoll hier ein neuronales Netz zu verwenden? Lohnt es sich vom Aufwand her im Vergleich zu einer anderen Spiele KI Methode?

Mein Plan sah so aus, dass ich mehrere Neuronale Netze entwerfe und diese dann ständig gegeneinander spielen lasse. Ich weiß nicht mehr wo, aber ich habe gelesen, dass es möglich sei das Netz minimal zu verändern und je nach Ergebnis die Änderungen zu speichern oder zu verwerfen. Die Netze sollen also beide minimal verändert werden gegeneinander Spielen und je nach Sieg oder Niederlage dann die Änderungen behalten oder wieder löschen.
Aber dazu später mehr.
Ersteinmal wäre mir wichtig ob das ganze Projekt überhaupt Sinn macht oder ob ich es lieber lassen sollte.
Vielen Dank
Gambo

Hallo und herzlich Willkommen im Forum!

meiner Einschätzung nach lohnt sich das Projekt schon, allerdings nicht in der einfachen Form mit ausschließlich überwachtem Lernen.

Übergeordnet zu einem KNN benötigt man für eine erfolgreiche Spielerealisierung eine Verhaltens- und Lernlogik, es handelt sich bei dem beschriebenen Problem um ein klassisches Reinforcement Learning (RL) Problem.

RL hier im Detail zu beschrieben würde den Rahmen bei weitem sprengen. Ein ausgezeichnetes Buch dazu (leider nur Englisch verfügbar):
http://www.amazon.de/Reinforcement-Lear ... 411&sr=8-1

Kurz gesagt handelt es sich beim klassischen RL-Ansatz um einen Agenten ('Agent'), der in einer Umgebung ('Environment') je nach seinem momentanen Zustand ('State') Aktionen ('Actions') auswählt und durchführt.
Nach jeder Aktion erhält der Agent von der Umgebung eine Belohnung ('Reward'). Der Reward is eine slakare Größe und kann auch negativ sein (dann als Bedeutung 'Bestrafung').
RL Algorithmen sind so gestaltet, dass die langfristige Gesamtbelohnung ('Return') maximiert wird.

Die Grundidee ist, dass der Agent eine Funktion erlernt, die jeder möglichen Aktion in jedem möglichen Zustand eine Bewertung zuweist. Der Agent wählt dann aus den möglichen Aktionen eines Zustands diejenige aus, die nach dieser erlernten Funktion den größtmöglichen Wert hat. Dies nennt man 'Exploration', d.h., der Agent wählt gierig ('greedy') die momentan als höchstwertig geschätzte Aktion aus. Ab und zu wählt der Agent jedoch auch eine Aktion zufällig ('Exploration'), er probiert also augenscheinlich minderwertige Aktionen aus, um zum einen Neues zu lernen , und um sich zum anderen stets flexibel an eine sich evtl. verändernde Umwelt anzupassen. So verbessert sich die Wertefunktion der Aktionen beständig, bis der Agent irgendwann ganz genau weiß, welche Aktion in einem bestimmten Zustand auf langfristige Sicht den höchten Gesamtgewinn erzielt.

So, um nun endlich zu den KNN bei der Sache zu kommen: Für kleine Probleme mit wenigen States und Aktionen eignen sich tabellarische Ansätze zur Abbildeung der Aktions-Zustands-Wertefunktion. Sehr schnell wächst bei solchen Problemen aber in der Praxis die Anzahl der möglichen Permutattionen von Zustanden und Aktionen so immens an, dass der tabellarische Ansatz nicht mehr handhabbar ist und man über Funktionsapproximation gehen muss. Genau da kommen die überwachten Lernalgorithmen der KNN zum tragen: Ein KNN bekommt als Inputs den momentanen Zustand des Agenten und des Environments sowie eine Aktion (beides muss man natürlich geeignet kodieren). Am Ausgang gibt das Netz den geschätzten Wert der Zustands-/Aktionskombination aus. Alle möglichen Aktionen werden im momentanen Zustand nacheinander an das Netz angelegt und deren Wert als Ausgangssignal des Netzes berechnet. So gelangt man zu einer Aussage, was sie höchstwertige Aktion ist und führt diese aus (immer wenn sich der Agent 'greedy' verhalten soll).

Aus den erhaltenen Rewards, die nach jeder ausgeführten Aktion vom Environment vergeben werden bildet der Agent dann die Lernmuster (Pattern) zum Training des KNN. Dieses Training wird permanent während des gesamten Verhaltens des Agenten immer wieder durchgeführt, so dass der Agent seine Abbildungsfunktion stets verbessert bzw. auch welchselnden Umgebungsbedingungen anpasst.

Ein sehr reizvoller Gedanke an RL-Implementierungen von Spielen ist die Tatsache, dass man die Trainingsmuster für das KNN nicht von Hand erzeugen muss. Man teilt also dem Agenten nicht mit, wie man gut spielt. Man belohnt ihn lediglich für's Gewinnen und bestraft ihn für's Verlieren. Daraus bildet er die notwendigen Lernmuster für sein KNN von selbst.
Man kann sogar so weit gehen, dass man zwei RL.Agenten, die zu Anfang völlig 'dumm' sind, gegeneinander antreten lässt. Diese zwei Agenten spielen also permanent in rasender Geschwindigkeit gegeneinander und lernen dabei ganz von selbst, wie man das Spiel gut spielt. Und das ganz ohne dass man ihnen sagt, was sie tun sollen, es ist wirklich faszinierend.

So, jetzt muss ich erst einmal Schluss machen. Ich empfehle das erwähnte Buch wärmstens, es ist faszinierend und man lernt ungeheuer viel dabei!

Viele Grüße und viel Erfolg!

Dankeschön für diesen doch recht ausführlichen Beitrag und entschuldige bitte das ich mich jetzt erst wieder melden kann.

Vom Prinzip her meinte ich genau das was du geschrieben hast, konnte mich nur nicht richtig ausdrücken. Ich habe mir mal das Buch im Internet angesehen und denke ich werde gleich mal anfangen es zu lesen.
Was mir gerade noch unklar ist ist folgendes: Ich müsste das KNN ja jeden Spielzug bewerten lassen, und den besten dann ausführen. Wenn ich den Clienten, damit er lernt, bestrafen oder belohnen möchte dann kann ich das ja erst am Ende des Spiels tun, wenn ich weiß wer gewinnt und wer verliert. So bewerte ich ja aber immer nur 24 Züge auf einmal. Funktioniert es trotzdem, dass der Client da einen Sinnvollen Lerneffekt daraus zieht?

Ich hoffe ich hab mich diesmal verständlicher ausgedrückt.

Gambo wrote:Wenn ich den Clienten, damit er lernt, bestrafen oder belohnen möchte dann kann ich das ja erst am Ende des Spiels tun, wenn ich weiß wer gewinnt und wer verliert. So bewerte ich ja aber immer nur 24 Züge auf einmal. Funktioniert es trotzdem, dass der Client da einen Sinnvollen Lerneffekt daraus zieht?

Ja, es funktioniert trotzdem. Das liegt daran, dass nach einer Aktion nicht nur die momentane Belohnung zur Anpassung des Wertes des State/Action Paares genommen wird, sondern auch ein gewisser Anteil des Wertes aus den möglichen zukünftigen Aktionen, die dieser Aktion folgen könnten.
Dadurch propagiert sich eine Belohnung, die am Ende einer Aktionskette vergeben wird, Schritt für Schritt nach 'hinten' durch die Aktionskette fort. Mit jedem Erreichen eines Zustands wird also der Vorgängerzustand in seinem Wert angepasst.

Am besten einfach mal durch das Buch lesen, dann wird das alles klar, denke ich.

Es ist keine leichte Kost, es lohnt sich aber, denke ich.

Viele Grüße

So inzwischen bin ich ein wenig weiter denke ich.
Ich habe mir diverse Bücher und Scripte zum Thema angesehen und teilweise gelesen.

Leider bin ich im Moment noch Schüler und sobald es in diesen Büchern an die, zu mindestens für mich, höhere Mathematik geht kostet es doch sehr viel Zeit mir diese zu erarbeiten. Ich frage mich wie weit ich wirklich die vorkommenden Algorithmen komplett verstanden haben muss um mein Ziel zu erreichen.
Natürlich weiß ich, dass es sinnvoll und nützlich ist es zu verstehen und ich finde es an den meisten Stellen auch ziemlich interessant, doch dafür habe ich im Moment leider nicht die Kapazitäten.

Deshalb: Denkst du, dass es für mich wirklich unumgehbar ist mir dies alles anzueignen?

Die nächste Frage wäre, ob ich mit meinem folgendem Gedankengang auf dem richtigem Weg bin.
- Der Agent ruf das Netz auf und verändert die Gewichte.
- Er legt für jede Mögliche Aktion den Input an und holt sich aus dem Netz den Output.
- Die Aktion mit dem höchsten Output wird ausgeführt.
- Erhält der Agent von seiner Umgebung eine Positive Rückmeldung behält er die Änderungen oder verwirft sie wenn er eine Negative erhält.
- Ein Zeitschritt ist abgeschlossen und es geht von Vorne los.

Ich würde nur gern wissen ob ich vom Prinzip verstanden habe oder einfach überhaupt nicht.

Freundlichen Gruß
Gambo

Gambo wrote:Deshalb: Denkst du, dass es für mich wirklich unumgehbar ist mir dies alles anzueignen?

Nein, das denke ich nicht. Du kannst bestimmt auch ohne allzu viel Mathe-Overhead voran kommen.

Gambo wrote:Die nächste Frage wäre, ob ich mit meinem folgendem Gedankengang auf dem richtigem Weg bin.
- Der Agent ruf das Netz auf und verändert die Gewichte.
- Er legt für jede Mögliche Aktion den Input an und holt sich aus dem Netz den Output.
- Die Aktion mit dem höchsten Output wird ausgeführt.
- Erhält der Agent von seiner Umgebung eine Positive Rückmeldung behält er die Änderungen oder verwirft sie wenn er eine Negative erhält.
- Ein Zeitschritt ist abgeschlossen und es geht von Vorne los.

Nicht ganz, Du bist aber nah dran. Ich würde die Sache so beschreiben
- Der Agent legt für jede mögliche Aktion den Input (Input = Aktion + momentaner Zustand) an und holt sich aus dem Netz den Output.
- Mit einer hohen Wahrscheinlichkeit (z.B. 90 % ) führt der Agent die Aktion mit dem höchsten Output aus. Mit einer geringeren Wahrscheinlichkeit (10 %) führt der Agent eine zufällig gewählte Aktion aus.
- Die Belohnung der Aktion wird 'gemerkt' (= r). Achtung: 'Belohnung' kann auch ein negativer Wert sein.
- Der Agent legt im neu erreichten Zustand wieder für jede mögliche Aktion den Input (Input = Aktion + momentaner Zustand) an und holt sich aus dem Netz den Output.
- Der Wert der höchstwertigen Aktion wird sich gemerkt (= r')
- Ein neues Trainingsmuster wird abgelegt und zwar für Inputs = [alter Zustand + durchgeführte Aktion], Output = [r + Gamma * r'], wobei Gamma zwischen 0 und 1 gewählt wird
- Das neue Trainingsmuster wird dem bereits erarbeiteten Fundus von Trainingsmustern hinzugefügt und über alle Trainingsmuster ein Trainingsschritt durchgeführt (= 1x Teach Lesson)
- Ist die maximale Größe des Trainingssatzes erreicht (z.B. 50000 Muster), dann wird das älteste Muster vom Trainingssatz gelöscht.
- Das Ganze beginnt von vorne

Der Faktor 'Gamma' führt dazu, dass der Agent nicht nur den erzielten momentanen Gewinn erlernt, sondern auch noch den (geschätzten) nächsten zu erreichenden Gewinn mit einbezieht. So pflanzt sich erzielter Gewinn durch die Zustands-/Aktionspaare zurück fort. Ein höherer Wert von Gamma (Richtung 1) macht den Agenten 'weitsichtiger'. Ein niedriger Wert von Gamma führt dazu, dass der Agent mehr auf kurzfristige Gewinnerzielung trainiert wird.
Das Verhältnis 90% / 10 % im Beispiel oben bezeichnet man als das Verhältnis von Exploitation zu Exploration. Zu Beginn des Trainings sollte viel Exploration (also 'ausprobieren') stehen. Je schlauer der Agent wird, um so mehr kann man auf Exploitation (also Ausnutzung von erlerntem Wissen) umsatteln.

Hoffe, Dir etwas weiter geholfen zu haben...

Viele Grüße