TicTacToe ANN und GA

[EinfachSö]

Auf Anraten von @ mache ich hierzu einen neuen Thread.

Mein Ziel ist es eine AI für TicTacToe zu "programmieren". Dabei soll die AI aus einem künstlichen neuronalen Netz bestehen und durch Training, in Form eines genetischen Algorithmus, verbessert werden.

Für mich erscheint TTT als ein nicht-komplexes aber auch nicht-lineare-separierbares Problem. Daher sollte ein mehrschichtiges 'Feedforward NN' ausreichen. Aktuell habe ich lediglich 3 Schichten (Input, Hidden und Output). Die Input Schicht besteht aus 10 nodes - 9 für jedes Feld und 1 für die Farbe( x oder o). Als Hidden Layer habe ich zwischen 7 und 15 nodes variiert. Der Output besteht aus 1 node.

Der Input ist diskret und kann nur 3 Zahlenwerte annehmen (-1, 0 und 1). Für die 9 Felderinputs gilt:

 Spoiler

-1 ≡ o
0 ≡ nicht besetzt
1 ≡ x

Das "Farbeninput" nimmt zwei Werte an (-1 oder 1), nach dem selben Schema wie eben.
Die Gewichte zwischen den nodes der Schichten variieren zwischen -40 und 40. Sie sind ziemlich hoch angesetzt, weil ich anfangs die Auswirkung testen wollte - im Nachhinein musste ich die Aktivierungsfunktionen anpassen
Für die Hiddenlayer nutze ich eine, an die Gewichte angepasste, TanH-Funktion:

 Spoiler

a(x) = 2/(1 + exp(-0.1 * x)) - 1

Dabei habe ich den Faktor 0.1 gewählt, damit beim ersten Zug alle Werte für a(x) realistisch sind. Beim ersten Zug sind die Felderinputs 0 und nur das Farbeninput bestimmt das Ergebnis der Akt.f. - also -40 < x < 40

Für die Outputlayer habe ich keine stetige Aktivierungsfunktion. Da der Output ja diskret sein soll (1-9) brauchte ich auch eine diskrete Funktion. Zudem soll jeder Wert mit der gleichen Wahrscheinlichkeit erscheinen. Die Summe der Signale von Hidden zu Output ist normalverteilt und demnach kommen die extremen Werte seltener vor:

 Spoiler

Woher der Sprung rechts kommt ist mir noch unklar. Ich habe die Werte gefittet und mit der Gausskurve konnte ich die Bereiche wählen, in denen die Zahlen 1-9 ausgegeben werden.

 Spoiler

Ich konnte eine einigermaßen gerechte Outputverteilung erstellen


Was den GA betrifft, kann man sich meinen Post im ChitChat anschauen
Kurz zusammengefasst:
-ca. 1000 Generationen
-Population von 100 Individuen
-jeder gegen jeden => 99*99 Spiele
-Fitnessfunktion noch unklar
-Mutationsrate von 0.01-0.05
-crossover 'tournament selection' oder 'roulette ...'
-ab und an ein neues ANN hinzufügen -> mehr Vielfalt


Das Problem ist die schnelle Konvergenz zu einem sehr unbefriedigenden Ergebnis. Das primäre Ziel ist es der AI beizubringen, nur erlaubte Züge zu machen.

[Shadow992]

So riesige Gewichte zu nehmen sind afaik der Tod für beinahe jedes NN. Da ist es kein Wunder, dass dein NN nicht oder nur miserabel konvergiert.
Aber das ist nicht das einzige Problem bei der ganzen Sache, ich zähl einfach einmal auf, was dich daran hindert bessere Ergebnisse zu bekommen:

1. Deine gewählte Aktivierungsfunktion ist sehr schlecht sowohl was Performanz angeht als auch was Konvergenz angeht (mal abgesehen davon, dass du nicht TanH benutzt sondern eine abgewandelte sigmoid ). Ich würde dir stattdessen empfehlen die ReLU-Funktion zu benutzen. Es ist nachgewiesen, dass diese Funktion schneller und besser konvergiert als TanH bzw. Sigmoid. (ReLU: https://en.wikipedia.org/wiki/Rectif...al_networks%29 )
2. Wie bereits erwähnt sind deine Gewichte richtiges Gift für NNs. Normalerweise will man Gewichte zwischen -1 und +1, nicht jedoch viel größer/kleiner.
3. Dein Input ist auch etwas "doof" gewählt. -1, 0 und 1 ist prinzipiell ok für x, unbesetzt und o. Aber dein zusätzliches Feld für "Welcher Spieler am Zug ist", macht es dem NN enorm schwer "Muster zu erkennen" bzw. dein benutztes NN ist definitiv nicht mächtig genug, um derartige Abhängigkeiten zu erkennen.
4. Was uns schon zum nächsten Punkt bringt: Dein Netz, wenn es "zusätzlich" erkennen soll was valide Züge sind und was nicht, underfitted die Daten jämmerlich. Sprich du brauchst mehr Schichten, ganz spontan würde ich zu Input-Layer mit 9 Units (oder alternativ 10) --> 3x3 Convolution (16 Filter) --> 128 Fully Connected --> 64 Fully Connected --> 9 Outputs raten.
5. So wie ich das sehe modelierst du dieses Problem als Regression-Task, sprich du willst eine konkrete Zahl haben (je nach Feld) als Ausgabe. Regression-Tasks sind aber IMMER schlechter in der Genauigkeit als äuqivalente Klassifikation-Tasks. Sprich was du machen solltest: 9 Output-Units erstellen, wobei jede einen Wert ausgibt und diejenige Unit mit dem höchsten Output-Wert ist dann das Feld, welches das beste zu setzende Feld ist (oder alternativ, welches ein valides feld ist).
6. Wie genau du deine NNs trainierst hab ich immer noch nicht verstanden. Wenn ich das richtig sehe trainierst du sie gar nicht, sondern erzeugst jedes mal komplett Neue. Das ist zwar möglich, aber alles andere als performant oder gar schnell. Ich würde also trotzdem zu einem Standard-Training ala SGD tendieren.

Eventuell bringt dir auch mein kleines E-Book dazu ein paar mehr Einblicke und Ideen bzw. Klärungen von Unklarheiten:
Ansonsten frag einfach, dann helf ich dir schon, notfalls mit Codes über skype o.ä.

[EinfachSö]

Originally Posted by Shadow992

So riesige Gewichte zu nehmen sind afaik der Tod für beinahe jedes NN. Da ist es kein Wunder, dass dein NN nicht oder nur miserabel konvergiert.
Aber das ist nicht das einzige Problem bei der ganzen Sache, ich zähl einfach einmal auf, was dich daran hindert bessere Ergebnisse zu bekommen:

1. Deine gewählte Aktivierungsfunktion ist sehr schlecht sowohl was Performanz angeht als auch was Konvergenz angeht (mal abgesehen davon, dass du nicht TanH benutzt sondern eine abgewandelte sigmoid ). Ich würde dir stattdessen empfehlen die ReLU-Funktion zu benutzen. Es ist nachgewiesen, dass diese Funktion schneller und besser konvergiert als TanH bzw. Sigmoid.
2. Wie bereits erwähnt sind deine Gewichte richtiges Gift für NNs. Normalerweise will man Gewichte zwischen -1 und +1, nicht jedoch viel größer/kleiner.
3. Dein Input ist auch etwas "doof" gewählt. -1, 0 und 1 ist prinzipiell ok für x, unbesetzt und o. Aber dein zusätzliches Feld für "Welcher Spieler am Zug ist", macht es dem NN enorm schwer "Muster zu erkennen" bzw. dein benutztes NN ist definitiv nicht mächtig genug, um derartige Abhängigkeiten zu erkennen.
4. Was uns schon zum nächsten Punkt bringt: Dein Netz, wenn es "zusätzlich" erkennen soll was valide Züge sind und was nicht, underfitted die Daten jämmerlich. Sprich du brauchst mehr Schichten, ganz spontan würde ich zu Input-Layer mit 9 Units (oder alternativ 10) --> 3x3 Convolution (16 Filter) --> 256 Fully Connected --> 64 Fully Connected --> 9 Outputs
5. So wie ich das sehe modelierst du dieses Problem als Regression-Task, sprich du willst eine konkrete Zahl haben (je nach Feld) als Ausgabe. Regression-Tasks sind aber IMMER schlechter in der Genauigkeit als äuqivalente Klassifikation-Tasks. Sprich was du machen solltest: 9 Output-Units erstellen, wobei jede einen Wert ausgibt und diejenige Unit mit dem höchsten Output-Wert ist dann das Feld, welches das beste zu setzende Feld ist (oder alternativ, welches ein valides feld ist).
6. Wie genau du deine NNs trainierst hab ich immer noch nicht verstanden. Wenn ich das richtig sehe trainierst du sie gar nicht, sondern erzeugst jedes mal komplett Neue. Das ist zwar möglich, aber alles andere als performant oder gar schnell. Ich würde also trotzdem zu einem Standard-Training ala SGD tendieren.

Eventuell bringt dir auch mein kleines E-Book dazu ein paar mehr Einblicke und Ideen bzw. Klärungen von Unklarheiten:

Vielen Dank für deine Zeit.

Zu deinen Punkten:

1. Sigmoid ist doch nur eine Art des tanh .
   Was bezweckt bei ReLU denn, dass man negative Werte ignoriert?
2. Ich hatte die Output Akt.f. halt schon angepasst und war dann zu faul das alles wieder zu ändern . Werde ich wohl machen, wenn ich deine Tipps umsetze.
3. siehe 4
4. Wie ist dann die Verbindung von Input zu 3x3 Conv? Jede Inputnode zu jeder Convnode? Und wie sieht es zwischen den Filtern aus?
5. Ich habe andauernd überlegt wie ich den Output gestalten soll. Das ist natürlich eine ansehnliche Lösung.
6. Ich trainiere sie nach einem simplen genetischen Algo. Ich lasse die Netzwerke ein paar Spiele machen und bewerte wie gut sie waren. Die besseren werden bei der Fortpflanzung bevorzugt. Die Gewichte zwischen den Layers bestimmen dabei das Genom und das Kind von zwei ANNs setzt sich aus den Gewichten der Eltern zusammen.

EDIT: Dein pdf könnte die Fragen bzgl. ConvNet beantworten.

[Shadow992]

Originally Posted by EinfachSö

Vielen Dank für deine Zeit.

Zu deinen Punkten:

1. Sigmoid ist doch nur eine Art des tanh .
   Was bezweckt bei ReLU denn, dass man negative Werte ignoriert?
2. Ich hatte die Output Akt.f. halt schon angepasst und war dann zu faul das alles wieder zu ändern . Werde ich wohl machen, wenn ich deine Tipps umsetze.
3. siehe 4
4. Wie ist dann die Verbindung von Input zu 3x3 Conv? Jede Inputnode zu jeder Convnode? Und wie sieht es zwischen den Filtern aus?
5. Ich habe andauernd überlegt wie ich den Output gestalten soll. Das ist natürlich eine ansehnliche Lösung.
6. Ich trainiere sie nach einem simplen genetischen Algo. Ich lasse die Netzwerke ein paar Spiele machen und bewerte wie gut sie waren. Die besseren werden bei der Fortpflanzung bevorzugt. Die Gewichte zwischen den Layers bestimmen dabei das Genom und das Kind von zwei ANNs setzt sich aus den Gewichten der Eltern zusammen.

EDIT: Dein pdf könnte die Fragen bzgl. ConvNet beantworten.

1. Ah jo mein Fehler meinte "Logistische Funktion": https://de.wikipedia.org/wiki/Logistische_Funktion
   Negative Werte bringen deinen Gradienten zum Explodieren. Da du nicht mit Gradienten arbeitest ist dieser Punkt gar nicht so wichtig (obwohl ich trotzdem noch einmal an deiner Stelle überlegen würde auf Gradientenabsteigsverfahren umzusteigen.).
2. Ist besser
3. Siehe 4
4. Das PDF dürfte die Fragen klären, wobei wenn deine Lib das nicht von Haus aus anbietet, reicht für Tests u.ä. auch die Conv-Schicht weg zu lassen.
5. Ja die richtige Output-Gestaltung ist mit das "wichtigste" beim Arbeiten mit NNs...
6. Das ist möglich, aber das Problem bei GAs als Optimierer bei NNs ist, dass zwei gute Eltern nur sehr selten ein gutes Kind erzeugen. NNs funktionieren halt nur so gut, weil das Zusammenspiel vieler kleiner "Arbeiter" harmoniert. Stell dir das wie in einer Firma vor. Es wird Fließband-Arbeit gemacht und jedes Neuron/jeder Arbeiter hat einen Bereich auf den er sich spezialisiert hat, wobei er immer das vorverarbeitete Produkt von Arbeiter X kriegt. Das heißt Firma X hat als Vorverarbeitung "Schrauben der Größe nach sortieren" und die Arbeiter danach (also Neuronen in tieferen Schichten) wissen: "Egal was ich mache, ich weiß die Schrauben kommen sortiert an". Jetzt haben wir eine Firma Y und die hat als Vorverarbeitung: "Schrauben der Farbe nach sortieren". Auch hier wissen die nächsten Arbeiter: "Die Schrauben sind immer der Farbe nach sortiert". Wenn man jetzt aber beide Firmen kreuzt, hat man plötzlich sowas wie: "Schicht 1: Alle Schrauben werden der Größe nach sortiert", "Schicht 2: Ich weiß egal was passiert, die Schrauben sind der Farbe nach sortiert". Das heißt Schicht 1 und Schicht 2 arbeiten total aneinander vorbei und werden nur in ganz wenigen Ausnahmefällen so gut sein wie die original Firmen. Das ist auch mit einer der Hauptgründe warum dein NN so dermaßen schnell konvergiert. Es hat eben einen Zustand gefunden, den man mit Duchmischen/kleinen Veränderunge nicht einfach so beheben kann, weil die "Anpassung der Neuronen aufeinander bzw. untereinander" einfach fehlt.