Hallo zusammen, tldr; Ich suche Ideen, Ansätze und Google-Stichworte zu neuronalen Netzen und nicht-überwachtem Trainieren. Mein Ziel ist es einen automatischen Spieler (Bot) zu programmieren, gegen den ich das Spiel Splix.io (http://www.splix.io) spielen kann. Splix.io ist kurzgesagt vergleichbar mit dem bekannten Spiel "Snake", nur ohne Früchte, dafür aber mit dem Ziel Flächen zu besetzen, die durch Umranden mit der Schlange erobert werden. Es dürfen viele Spieler gleichzeitig auf dem Spielfeld sein (Multiplayer; Multibots). Da ich keine Strategie einprogrammieren möchte, soll sich mein Bot das Spielen selbst beibringen. Hierfür eignen sich ja neuronale Netze. Das meiste, was ich so gefunden haben, waren Netze mit Backpropagation als Trainingsart. Ich glaube das hilft mir nicht weiter, da ich ja keine Trainingsdaten mit Erwartungswerten liefern kann, auf die das Netz hintrainieren könnte. Als Eingangsgröße ins neuronale Netz wollte ich ein "Pixelabbild" des Spiels verwenden (also so ca. 20x20Pixel). Als Ausgangsgröße erwarte ich eine dieser 3 Reaktionen: "links abbiegen", "rechts abbiegen", "nichts tun (=geradeaus weiterlaufen)". => 400 Eingangsneuronen, 1..2 hidden layers und der Ausgangslayer dann mit 3 Neuronen. Ich kann aber nicht nach jedem Zug/Schritt schon bewerten ("Fitnessfunktion"), ob die letzte Aktion gut oder schlecht war - weil das schlicht zu diesem Zeitpunkt noch nicht abschätzbar ist. Eigentlich müsste ich ca. 20..50 Aktionen/Schritte erstmal laufen lassen und dann erst bewerten. Macht man da so? Vermutlich gibt es aber aus den 3^50 (=10^24) Möglichkeiten dann nur eine handvoll gute Abfolgen/Kombinationen... Ok, angenommen das Problem der Bewertung sei gelöst (eine Fitnessfunktion sei verfügbar), wie trainiere ich dann die Kantengewichte und Biasse der Neuronen? Meiner Meinung nach bietet sich da ein genetischer/evolutionärer Ansatz an. D.h. ich beginne mit zufällig initialisiertem Netz und variiere die Kantengewichte evolutionär. Das kann ich mir noch so grob vorstellen. Aber dauert das dann nicht unendlich lange, bis da was gescheites rauskommt? Und wie kann ich steuern, dass da überhaupt irgendwas sinnvolles rauskommt? In welchem Wertebereich muss ich dann die Kantengewichte variieren? Kann man das praktisch irgendwie eingrenzen? (Bei Backpropagation pendelt sich der Wert ja quasi von selbst ein, da ja immer Deltas aufaddiert werden und so die Abweichung zum Endwert immer kleiner wird; bei evolutionär/genetisch muss ich ja selbst den Bereich vorgeben). Liegen die Kantengewichte immer bei -1..+1? Wie groß darf der Bias werden? Die ganzen Beispiele mit SuperMarI/O, Tetris, "Kreaturen lernen laufen" lassen sich damit meiner Meinung nach nicht vergleichen, weil diese unter einer volldeterministischen Umgebung ("alles ist in jeder Simulation immer gleich") ablaufen. Bei meinem Spiel treten ja unvorhersehbare Ereignisse/Störungen(?) durch menschliche Spieler ein - auf die soll das Netz ja gerade (auch) reagieren lernen. Übrigens: Das ganze soll mit Javascript, d.h. NodeJS für den Server (und die Bots) und Spieler-Anbindung an Webbrowser (JS + p5.js) umgesetzt werden. Ich möchte keinen Bot bauen, der sich mit Splix.io verbindet und dort mitspielt, sondern auf meinen eigenen "Splix"-Server (der läuft schon) antreten lassen. Freue mich über Stichworte, Links oder Hinweise, die mir sagen, wie man das eigentlich macht... :-) Danke.
Tja. ich wuerd einmal etwas herumspielen, und auf eine Idee zum Lernen warten. Irgendwie muss ja ein Feedback irgendwo her kommen. Wahrscheinlich kommt von selbst nichts. Denn fuer jede Entscheidung muss ja eine Bewerten da sein... Probier's doch mal mit einem normalen Systen.
Der eigentliche Ansatz bei solchen Problemen/Spielen ist, anstatt neuronale Netze sog. Reinforcement Learning einzusetzen. Es gibt etliche Beispiele, wo man 2D-Spiele mit RL-Methoden "gelöst" hat, Snake, Mario, einige Atari-Spiele, Backgammon usw. Deshalb versuche mal eher in Richtung Reinforcement Learning zu gehen anstatt neuronale Netze. Denn so wie du das Spiel beschreibst, klingt es nach den klassischen Voraussetzungen für das Reinforcement Learning: man hat einen Agenten (Spielfigur), seine Umgebung (Spielfeld), eine Menge von Aktionen (Spielzügen: gerade aus, hoch, runter, links, rechts) mit denen der Agent mit seiner Umgebung interagiert. Was dir noch fehlen sind eine sog. Belohnungsfunktion und eine Codierung der Zustände des Spielfelds. Das Ziel ist es, eine Strategie/Vorgehensweise (sog. policy) zu entwickeln/erlernen, die die Gesamtbelohnung maximiert, wobei sich diese aus der Summe der einzelnen Belohnungen zusammensetzt. Die policy gibt an, wann, d.h. in welchem Zustand man welchen Spielzug machen sollte. Die Belohnungsfunktion bewertet jeden Spielzug/Aktion. Eine einfache Belohnungsfunktion wäre zB wenn "nichts passiert" gibt die Belohnungsfunktion eine 0, wenn ein Gebiet erorbert wird dann liefert sie eine positive Zahl x, wenn man Gebiete verliert dann eine negative Zahl y. Die Zaheln x und y könntest du mit der Größe der Gebiete korrelieren. Ziel ist es, die Gesamtbelohnung zu maximieren, wobei sich diese aus der Summe der einzelnen Belohnungen zusammensetzt. Was problematischer wird, ist die Codierung der Zustände des Spielfelds. Denn nach jedem Zug ändert sich der Zustand und die Anzahl der Zustände ist riesig und man kann die Zustände nicht a priori bestimmen. D.h. man müsste die Zustände approximieren. Auf die Schnelle ist mir nichts eingefallen, wie man die Zustände bzw ihre Approximation modellieren kann. Auf ein ähnliches Problem (Approximation der Zustände) stößt du bei Snake auch. In dieser pdf wird deren Approximation vorgestellt http://cs229.stanford.edu/proj2016spr/report/060.pdf Was splix komplexer macht, ist, dass ein bereits besetztes Gebiet wieder zurückerobert werden kann. Wie das Spiel aber genau funktioniert, habe ich auf die Schnelle nicht verstanden. Vielleicht hilft dir der Ansatz trotzdem. Wie du schon festgestellt hast, ist die Aufgabe nicht so einfach.
Afu schrieb: > Da ich keine Strategie einprogrammieren möchte, soll sich mein Bot das > Spielen selbst beibringen. Hierfür eignen sich ja neuronale Netze. Ja, aber der Rechenaufwand, bist diese KI irgendwas sinnvolles liefert, ist enorm. Vergleiche mit einem Menschen: Bis der sich wie ein Erwachsener verhalten kann, muß er etliche Jahre zuerst intensivst gehätschelt werden und dabei laufend auf die Schnauze fallen. Im weiteren Verlauf nimmt dann zwar die Notwendigkeit zur Hätschelung immer weiter ab, die Notwendigkeit, dauernd auf die Schnauze zu fallen, bleibt aber bestehen. Ohne das: kein Lernfortschritt. D.h.: scheinbarer Mißerfolg ist immer vor allem eins: ein kleiner Schritt in die richtige Richtung. Wenn er denn zum Lernen verwendet wird... Übertragen auf dein konkretes Problem läuft das ungefähr so: Die "Hätschelphase": da bringst du dem System erstmal bei, was eigentlich das Optimierungsziel ist. Das kann NICHT automatisch erfolgen. Das Netz hat NIX, nichtmal die bedingten Reflexe und instinktiven Verhaltensweisen, mit denen ein Mensch praktischerweise bereits geboren wird und auf die sein Lernen aufbauen kann. Das ist ein sehr großes (und bisher für den allgemeinen Fall ungelöstes) Problem jeglicher KI! Erst die zweite Phase ist dann recht gut automatisierbar, aber auch nicht so einfach, wie du dir das vorstellst. Das Kernproblem hast du immerhin schon erkannt: Erst nach vielen Einzelentscheidungen wird der Erfolg der Gesamtstrategie überhaupt erst messbar. Das Problem ist nun: Wie kriege ich heraus, welche Einzelentscheidung(en) in dieser Historie Scheisse war? Antwort: nur dadurch, daß die Alternativen durchgespielt werden. Sprich: ein exponentielles Problem mit dem Potential, etliche Großrechner jahrelang zu beschäftigen... Und selbst dann, wenn das alles jederzeit zu einem schicken und überaus erfolgreichen Spiel in der Trainingsmenge führt, schützt es die KI nicht davor, bei einem bisher unbekannten Zug des "Gegners" erneut furchtbar auf die Schnauze zu fallen... So ist das nunmal mit der Intelligenz (ganz egal, ob künstlich oder natürlich)...
Reinforcement Learning schrieb: > anstatt neuronale Netze sog. Reinforcement Learning einzusetzen. Durch deinen Hinweis bin ich dem Thema mal näher nachgegangen. Ich habe nach ein paar Stunden Youtube-Vorlesungen, jetzt auch eine grobe Vorstellung von Reinforcement Learning (RL) insbesondere mit dem model-free Ansatz. Und das Beste ist, man kann den Lernfortschritt selbst noch beobachten/einschätzen und die internen Größen verstehen. Ganz im Gegensatz zu den unverstehbaren Kantengewichten bei den NNs. > Was dir noch fehlen sind eine sog. Belohnungsfunktion Das müsste doch einfach der Punktestand sein (Anzahl der eroberten Zellen). Ich muss ja nicht jeden Zug einzeln belohnen. Eine Belohnung am Ende reicht aus. Das propagiert sich dann durch das Verfahren auf umgekehrtem Wege zurück bis zum aktuellen Zustand. > und eine Codierung der Zustände des Spielfelds. Da war die erste Idee mit den 400 Eingangsgrößen eine ganz schlechte, weil die Anzahl der Zustände/Kombinationen unüberschaubar wird. Ich denke/hoffe, dass man als Eingangsgrößen auf ganz wenige Größen zurückgreifen kann. Also nicht die vielen Pixelzustände auswerten/lernen, sondern daraus schon vorher abstraktere Kenngrößen ("features") ermitteln, wie z.B. "Abstand zum Gegner", "Größe des (bald) eingekesselten Bereichs" usw.. Der Vorteil ist, dass es dann auch egal ist, ob sich das dann links oben im Feld oder links unten oder sonstwo abspielt. Hier beschreibt der Dozent, wie man bei der Berechnung der Q-Values vorgeht: https://www.youtube.com/watch?v=yNeSFbE1jdY (ab Minute 45). Ich glaube, dass das ein geeigneter Ansatz wäre - wenn(!) ich den dann mal besser überblicke. :-) > Was splix komplexer macht, ist, dass ein bereits besetztes Gebiet wieder > zurückerobert werden kann. Das will ich zunächst mal alles ignorieren. Vermutlich muss man verschiedene Spielphasen (neue Zellen erobern, eigene Zellen verteidigen, Gegner angreifen...) separat betrachten/lernen und dann im geeigneten Moment zwischen den einzeln gelernten Aktionen umschalten. Aber das ist ferne Zukunftsmusik. Ich bin schon zufrieden, wenn mein Bot Zellen einkesselt, ohne jedesmal selbst sofort gefressen zu werden. > Vielleicht hilft dir der Ansatz trotzdem. ja, sehr. Genau das hatte ich mir mit meinem Ausgangspost erhofft - ein Schubs in die richtige Richtung. Danke! :-)
Ich würde die KI so programmieren, dass sie genau das gleiche macht was der menschliche Spieler bzw. sein Gehirn machen würde. Dazu muss man sich irgendwie genau beobachten wie man das selber spielt. Das wird aber dann wohl auf normalen Code hinausgehen, das scheinbar komplexe neuronale Zeug interessiert mich aber doch irgendwie ...
Afu schrieb: > Reinforcement Learning schrieb: >> anstatt neuronale Netze sog. Reinforcement Learning einzusetzen. > Durch deinen Hinweis bin ich dem Thema mal näher nachgegangen. > Ich habe nach ein paar Stunden Youtube-Vorlesungen, jetzt auch eine > grobe Vorstellung von Reinforcement Learning (RL) insbesondere mit dem > model-free Ansatz. > Und das Beste ist, man kann den Lernfortschritt selbst noch > beobachten/einschätzen und die internen Größen verstehen. Ganz im > Gegensatz zu den unverstehbaren Kantengewichten bei den NNs. Wie du festgestellt hast, ist der model-free Ansatz der vielsprechendste. Und der Q-Learning-Algo beim RL ist von der Bedeutung her mit dem Backpropagation-Algorithmus bei kNN vergleichbar. >> Was dir noch fehlen sind eine sog. Belohnungsfunktion > Das müsste doch einfach der Punktestand sein (Anzahl der eroberten > Zellen). Ich muss ja nicht jeden Zug einzeln belohnen. Eine Belohnung > am Ende reicht aus. Das propagiert sich dann durch das Verfahren auf > umgekehrtem Wege zurück bis zum aktuellen Zustand. Naja du benötigst schon eine Belohnungsfunktion (reward) für jede Aktion/Zug. Der Reward ist ja das Kernstück von RL (daher kommt auch der Name reinforcement). In jeder Update-Regel (sei es das Update für Q oder auch für die Gewichte beim Approximieren der Q-Funktion mittels linearer Kombination von feature-Funktionen) kommt der Reward (es ist dieses kleine r in den Formeln) vor. >> und eine Codierung der Zustände des Spielfelds. > Da war die erste Idee mit den 400 Eingangsgrößen eine ganz schlechte, > weil die Anzahl der Zustände/Kombinationen unüberschaubar wird. > > Ich denke/hoffe, dass man als Eingangsgrößen auf ganz wenige Größen > zurückgreifen kann. Also nicht die vielen Pixelzustände > auswerten/lernen, sondern daraus schon vorher abstraktere Kenngrößen > ("features") ermitteln, wie z.B. "Abstand zum Gegner", "Größe des (bald) > eingekesselten Bereichs" usw.. Der Vorteil ist, dass es dann auch egal > ist, ob sich das dann links oben im Feld oder links unten oder sonstwo > abspielt. > Hier beschreibt der Dozent, wie man bei der Berechnung der Q-Values > vorgeht: Youtube-Video "Lecture 11: Reinforcement Learning II" (ab > Minute 45). > Ich glaube, dass das ein geeigneter Ansatz wäre - wenn(!) ich den dann > mal besser überblicke. :-) Die feature-extraction ist der Schlüssel und auch das schwierigste bei ML-Algorithmen. Ich weiß nicht, wie viel Background du im Bereich der kNN (und allgemein mit ML) hast, aber die Bestimmung der sog feature-Vektoren (bei kNN auch meist einfach als Input-Vektoren bezeichnet) ist der wichtigste/herausfordernste Teil, damit das neuronale Netz gute Ergebnisse liefert. Wenn man eine Lösung für ein spezifisches Problem sucht, dann versucht man meistens, manuell feature-Vektoren bzw. beim RL feature-Funktionen zu erstellen/definieren. Möchte man jedoch ein wenig verallgemeinern, dann versucht man ein Modell zu entwickeln, welches diese feature-extraction automatisch vornimmt. Das ist auch die Essenz von sog. Deep-Learning. Im Bereich der Bilderkennung zB erkennen die sog. Hidden-Layers eines deep neural networks (sog. convolutional neural networks) sog basis-features wie z.B. Kanten. Das Deep-Learning-Konzept kann man auch bei RL einsetzen, um die Q-Funktion zu approximieren, in dem Fall wird die Q-Funktion nicht mehr durch Linearkombination von Gewichten und feature-Funktionen approximiert, sondern es wird nichtlinear approximiert, wobei die approximierende nichtlineare Funktion das deepe-neuronale Netz ist. >> Was splix komplexer macht, ist, dass ein bereits besetztes Gebiet wieder >> zurückerobert werden kann. > Das will ich zunächst mal alles ignorieren. Vermutlich muss man > verschiedene Spielphasen (neue Zellen erobern, eigene Zellen > verteidigen, Gegner angreifen...) separat betrachten/lernen und dann im > geeigneten Moment zwischen den einzeln gelernten Aktionen umschalten. > Aber das ist ferne Zukunftsmusik. Ich bin schon zufrieden, wenn mein Bot > Zellen einkesselt, ohne jedesmal selbst sofort gefressen zu werden. > >> Vielleicht hilft dir der Ansatz trotzdem. > ja, sehr. Genau das hatte ich mir mit meinem Ausgangspost erhofft - ein > Schubs in die richtige Richtung. Danke! :-) Naja ich würde an deiner Stelle zunächst mal ein einfacheres Problem lösen um mit den Algorithmen vertraut zu werden. Ein Beispiel, das du durch den klassischen Q-Learning-Algorithmus lösen kannst, ist Tic-Tac-Toe (du hast weniger als 9^3 Zustände, d.h. deine Q-Werte kannst du in einem Array speichern) - auch die graphische Implementierung wäre recht einfach. Danach könntest du, wie in dem Video, Pacman nehmen - hierzu gibt es eine freie Python-Implementierung (einfach nach Python Pacman googlen).
Reinforcement Learning schrieb: > Tic-Tac-Toe (du hast weniger als 9^3 Zustände Kurzer Nachtrag: Meine Abschätzung war total daneben. Gemeint war eig, dass du deutlich weniger als 3^9=19683 Zustände hast. Du hast sogar weniger als 6050 Zustände. Nichtsdestotrotz kannst du die Q-Werte in einem Array speichern.
Kurzer Zwischenstand: Nachdem ich jetzt einige dieser Featurefunktionen aufgestellt habe, und deren Gewichtungsfaktoren einfach pi*Daumen vorgegeben habe, bewegt sich der Bot schon recht "interessant" übers Feld. Von Lernen kann noch keine Rede sein, weil ich das programmatische Variieren/Anpassen der Gewichtungsfaktoren noch nicht ganz durchschaut habe. Naja, gebe ich diese halt von Hand vor. Ist dann zwar nix mit Lernen, aber der Bot läuft trotzdem (wenn ich die Gewichte sinnvoll einstelle). Eine Featurefunktion z.B. bewertet die Entfernung zur Homebase. Eine andere ermittelt die Anzahl der potentiell einzukesselnden Zellen. Weitere kümmern sich darum, dass er keine 180°-Kehren macht (wenig sinnvoll, da vom Server sowieso ignoriert), und sich selbst nicht in die Spur beißt. Wieder andere belohnen das Weglaufen von der Homebase oder verhindern das Überfahren der Spielfeldbegrenzung. Läßt man den Bot jetzt loslaufen passieren höchst interessante Dinge. Ich hatte zunächst erwartet, dass er etwas in den freien Raum reinläuft (wird ja belohnt), dann irgendwie abbiegt und wieder zurück zur Homebase läuft (nämlich dann, wenn der erwartete Zellenzuwachs die Belohnung fürs Rauslaufen übersteigt). Naja, was ist statt dessen passiert? Er ist genau eine Zelle weit von der Homebase weggelaufen und hat die (anfangs quadratische) Homebase im Abstand von einer Zelle einmal umrundet. Naja, das gibt gefahrlos eine große Fläche, die er da einkesseln kann, aber viele Punkte bekommt er am Ende ja nicht, weil die meisten eingekesselten Zellen ja schon eingefärbt waren und somit nicht neu/doppelt gezählt werden. Hm, ich hatte ja nicht gesagt (bzw. in die Featurefunktion gepackt), dass nur neu eingefärbte Zellen zählen, also eindeutig mein Fehler - aber "kreativ" fand ich den Bot schon. :-) Wie gesagt alles ohne echtes ML. Dennoch entwickelt das Teil auch so ein "Eigenleben". Ich könnte dem Bot stundenlang zuschauen. Und da die Rechnungen ja alle ganz gut nachvollziehbar sind, läßt sich seine Reaktion auch immer schön erklären. Noch(!) habe ich das Feintunen der Gewichte im Griff. Aber so wirklich sinnvoll spielt er noch nicht und ich befürchte, dass mir der Überblick/Vorstellungskraft langsam verloren geht. Muss ich mich eben doch nochmal ausführlicher mit der Lernerei beschäftigen. Ich bin mal gespannt, wie das noch weitergeht...
Hallo, ich mach es mal kurz: Wenn es zu viele Spielstandsmöglichkeiten gibt und deiner RAM knapp werden könnte, macht das Q-Learning mit KNNs Sinn! Ansonsten kann der Q-Learner auch alle Kombinationen abspeichern. Evolution und Fitnessfunktion sind nette Spielzeuge. Q-Learning ist aber viel mächtiger. Bleib also dabei. Das ein Spielzug erst nach 20 Zügen ordentlich bewertet werden kann ist kein Problem. Lies unbedingt dieses Beispiel: http://outlace.com/Reinforcement-Learning-Part-3/ ... dann sollte eigentlich alles klar sein. Ich fande es jedenfalls sehr erleuchtend. VG Basti
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.