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
