Netzwerkarchitektur für Trumpfquartett-KI

[sandroid]

Hallo MemBrain-Community,

ich bin ziemlich neu in der Thematik neuronaler Netze und bin bei meiner Recherche auf MemBrain als ein dafür passender, weitgehend intuitiv zu bedienender Simulator gestoßen. Vielen Dank, für dieses unkomplizierte, aber mächtige Werkzeug! Zur Einarbeitung stellte ich mir die Aufgabe, eine künstliche Intelligenz für das bekannte Trumpf-Quartett (Andere Bezeichnungen: Supertrumpf; Leben und Tod; etc...) zu entwerfen. Für dieses existieren verschiedene Kartendecks mit je 32 Karten, die man überall erwerben kann. Falls jemand die Regeln nicht kennt, hier ein grober Umriss: http://de.wikipedia.org/wiki/Supertrumpf

Ich hätte mein neuronales Netzwerk gerne in verschiedenen Etappen konstruiert:

Etappe 1:

Das neuronale Netzwerk kommt nur dann zum Einsatz, wenn der künstliche Spieler "am Zug" ist, da er andernfalls laut Regelwerk sowieso keine Möglichkeit hat, den Spielverlauf zu beeinflussen. Bei einem Zug werden dem neuronalen Netzwerk die Eigenschaftswerte der aktuellen Trumpfkarte vorgelegt. Es entscheidet dann lediglich, welcher dieser Werte angesagt wird. Lernen sollte das neuronale Netzwerk dabei "durch Erfahrung". Bei jeder Spielaktion bekommt es das "Feedback", ob der Zug erfolgreich war, d.h. eine Karte des Gegners gewonnen wurde, oder aber verlustreich, da eine Karte verloren wurde und der Spielzug abgegeben wurde. Ggf. könnte man noch die Pattoption als Feedback einführen. Lernen könnte das Netzwerk sehr schnell, wenn es gegen sich selbst spielt, also selbst sowohl die Züge des einen Spielers als auch die des anderen bestimmt. Die Lernregel müsste die Optimierung des Feedbacks als Ziel besitzen.

Ich vermute, dass ein solches neuronales Netzwerk nicht allzu schwer zu erstellen sein dürfte. Aber welche Lernregel muss ich anwenden? Wie funktioniert diese? Mein intuitiver Entwurf eines neuronalen Netzwerkes sähe nun so aus:
- 5 Inputneuronen für die 5 Eigenschaftswerte, mit einer Normalisierung auf eine Skala von 0 bis 1 (0 = Kleinster vorkommender Wert; 1 = Größter vorkommender Wert)
- 5 Hiddenneuronen, jeder mit allen Inputneuronen verbunden.
- Hier ggf. noch eine Schicht genauso wie die erste. Macht das Sinn oder nicht?
- 1 Output-Neuron, der mit allen 5 Hiddenneuronen der vorherigen Schicht verbunden ist und 1...5 zeigt je nach ausgewählter Eigenschaft.
Ist solch ein Entwurf denkbar?

Etappe 2:

Erst einmal wäre ich glücklich, wenn ich mit Etappe 1 Erfolg haben würde. Dann habe ich mir als Ausblick gedacht, die Intelligenz des Netzes noch weiter zu verbessern, indem sich das Netz "merkt", welche Karten in der Vergangenheit von wem ausgespielt wurden und wer diese bekam. Dann kennt die KI unter Umständen die Werte schon und kann darauf besser eingehen. Ich denke, dass hier irgendwie eine Rückkopplung der Informationen aus bereits gespielten Karten vonnöten wäre. Jeglicher Entwurf hierzu fehlt mir noch. Aber wie schon geschrieben, liegt mein Hauptaugenmerk zunächst auf Etappe 1.

Für jegliche Hilfe bin ich sehr dankbar!

Gruß
sandroid

[TJetter]

Hallo und herzlich Willkommen im Forum!

Der Dreh- und Angelpunkt der Überlegungen muss folgendes sein:
Soll die KI über eine gut/schlecht-Bewertung selbst lernen? In diesem Fall muss Reinforcement-Learning (RL) zum Einsatz kommen. Das ist ein ungeheuer spannendes und lohnendes Thema, aber nichts, was man 'mal schnell' macht. Dazu ist eine gewisse Portion Einarbeitung und Einlesen notwendig. Ein neuronales Netz wird da zwar auch verwendet, das ist aber bei Weitem nicht alles. RL ist keine Lernregel im Sinne von NN, sondern ein 'Ablaufstrickmuster' für eine gewisse Art der KI. Ein guter Startpunkt ist dieser Thread im Forum hier:
viewtopic.php?f=5&t=231
Bei RL geht es darum, selbstlernende Agenten zu entwickeln, die zum Beispiel Spiele erlernen, wie im Kniffel-Beispiel aus dem Thread oben. RL erlaubt es dabei dem Agenten, optimale Strategien auch über längere Spielverläufe hinweg zu erlernen. Das NN bei RL-Implementierungen sagt nicht direkt Aktionen voraus, sondern erlernt die Wertigkeit von Aktionen in bestimmten Spielzuständen vorherzusagen. Eine übergeordnete Spiel-Logik benutzt das NN dazu, herauszufinden, welche Spielaktionen welche Wertigkeiten in bestimmten Spielzuständen haben, führt diese Aktionen dann aus und erzeugt neue Trainingsdaten bzgl. der tatsächlich sich ergebenden Wertigkeiten dieser Aktionen. Das NN in einer RL-Implementierung hat deshalb IMMER GENAU EINEN Output, dieser repräsentiert die Wertigkeit.

Wenn man ein NN nutzen möchte, um direkt eine durchzuführende Aktion auszugeben (z.B. welches Markmal beim Trumpfquartett ausgewählt werden soll), dann muss man dem Netz ausschlielich RICHTIGE inputs/Output Paare zum Training vorlegen. D.h., eine Aussage, ob die letzte Auswahl gut oder schlecht war, führt nicht zum Ziel, denn: Wie sollte daraus der zu erlernende Output des Netzes bestimmt werden? Vielmehr muss man - wenn man nicht so etwas wie RL implementieren möchte - dem Netz nach jedem Schritt sagen können, was die richtige Entscheidung gewesen wäre und diese als neuen/zusätzlichen Trainingsdatensatz aufnehmen.

Konkret beim Quartett-Spiel: Immer wenn alle Mitspieler ihre Karten auf den Tisch gelegt haben, muss eine übergeordnete Programnlogik folgendes durchführen:
Wenn die KI den Stich gewonnen hat, dann einen neuen Datensatz zum Training bestimmen mit:
- Inputs: alle Kartenmerkmale
- Output: Ausgewähltes Merkmal
Wenn die KI den Stich verloren hat, dann einen neuen Datensatz zum Training bestimmen mit:
- Inputs: alle Kartenmerkmale
- Output: Merkmal, das ausgewählt hätte werden müssen, um den Stich zu machen.
Natürlich können im letzteren Fall keine oder sogar mehrere Auswahlen richtig sein, man könnte für alle, die gewonnen hätten, einen Datensatz zerzeugen und der Trainingsmenge hinzufügen.
Ebenso könnte man im Falle des Gewinnens neben dem 'Gewinnsatz' noch weitere hinzufügen, die ebenfalls zum Gewinn geführt hätten.

Bedingung ist hierfür, dass man die Karten der anderen nach jedem Spielzug einsehen darf und deren Merkmale miteinender vergleichen darf. Ansonsten kann man eben immer nur aus gewonnenen Zügen lernen.

Die Codierung der Auswahl würde ich als getrennte Neuronen umsetzen, also ein Output-Neuron für jedes Merkmal (in den Trainingsdatensätzen wird immer nur eines davon auf '1' gesetzt, alle anderen auf 0).

Die Normalisierung der Eingänge kann MemBrain übrigens selbst übernehmen, man gibt einfach für jedes Input-Neuron in dessen Eigenschaften den geeigneten Normalisierungsbereich an.

Eine prinzipielle Frage: In welcher Programmiersprache soll das Spiel denn implementiert werden? Ich nehme an, die MemBrain DLL soll zum Einsatz kommen?

Viele Grüße und viel Erfolg!

[sandroid]

Vielen Danke für die sehr schnelle und ausführliche Hilfestellung!

Wenn ich es richtig verstehe, dann müsste ich während dem Spiel nach jedem Zug einen neuen Lerndatensatz hinzufügen und anschließend jedes mal das NN noch einmal alle Lerndatensätze lernen lassen.

Folgender Ablauf also:

Initial: Lerndatensätze leer
Spiel beginnt.
Für jeden Spielzug, an dem die KI an der Reihe ist, wird folgendes ausgeführt:

1) An die 5 Eingänge des NN werden die 5 Eigenschaftswerte der aktuellen Karte angelegt.
2) Die Aktion wird durchgeführt, an deren Ausgang der höchste Wert von allen 5 Ausgangswerten anliegt (Zu Beginn rein zufällig also).
3) Die Karten beider Spieler werden aufgedeckt und verglichen
4) UNABHÄNGIG davon, ob der Stich gewonnen ist, wird ein Datensatz angelegt, der für jede der 5 möglichen Aktionen, die zum Gewinn geführt hätten, eine 1 enthält, und für die Verlustaktionen eine 0.
5) Lernen: Nun wird mittels Backpropagation (???) ein Lernen über alle Lerndatensätze durchgeführt. Wenn das Lernen nicht gegen eine "Abweichung" von 0 konvergiert, wird nach einem Timeout abgebrochen.

Falls die KI den Stich gewonnen hat, also laut Regelwerk immer noch am Zug ist, geht es gleich wieder weiter mit Schritt 1) . Ansonsten wird das Spiel fortgesetzt, bis irgendwann die KI wieder am Zug ist.
Die KI lernt nur anhand der einzelnen separaten Stiche. Das finale Spielergebnis (Spiel endet, wenn ein Spieler keine Karten mehr hat) hat auf das Lernen keinen Einfluss.
Somit kann ein Spiel auch beliebig beendet werden (Durch Spielende laut Regelwerk oder Spielabbruch) und neu gestartet werden, die KI lernt einfach weiter.

Die Lerndatensatztabelle hätte folgende Spalten:
MerkmalA; MerkmalB; MerkmalC; MerkmalD; MerkmalE; AGewinnt; BGewinnt; CGewinnt; DGewinnt; EGewinnt

Ist der Ablauf so umsetzbar? Oder habe ich das Reinforcement Leraning falsch verstanden?
Ansonsten wäre nun klar, wie viele Eingangs- und Ausgangsneuronen benötigt würden (Jeweils 5 bei 5 Merkmalen/Karte). Aber wie kann ich die optimale Anzahl Anzahl der Hidden-Neuronen-Schichten ermitteln. Gillt hier "Je mehr desto besser!" oder "Je weniger desto besser!"? Und wie viele Neuronen benötige ich pro Schicht?

@Plattform:
Grundsätzlich bin ich weitgehenst sprachunabhängig. Gibt es eine Sprache / Plattform, die sich für die MemBrain-DLL besonders gut eignet? Es existieren ja für gängige Plattformen Wrapper.
Trotzdem habe ich nun begonnen, von einer nativen VC++-Konsolenanwendung statisch gegen die Bibliothek zu linken. Mein Projekt dient auch nur meiner Neugier und ist nicht dem aktiven Einsatz als Computerspiel zum Zeitvertreib gedacht.

[sandroid]

@Plattform
Ich würde nun ggf. doch auf die .NET-Framework-Umgebung mit C# umschwenken, ganz einfach, weil die Entwicklung bei mir mit nativen VC++ weniger zeiteffizient ist.
Gibt es den .NET-Wrapper auch in einer Projektversion für Visual Studio 2013?

Muss ich dort irgendwelche besonderen Dinge beachten?

[TJetter]

@Plattform
Ich würde nun ggf. doch auf die .NET-Framework-Umgebung mit C# umschwenken, ganz einfach, weil die Entwicklung bei mir mit nativen VC++ weniger zeiteffizient ist.
Gibt es den .NET-Wrapper auch in einer Projektversion für Visual Studio 2013?

Wieso, gibt es Probleme mit dem Projekt unter VS2013?

Muss ich dort irgendwelche besonderen Dinge beachten?

Nein, die dll bindet sich ein wie jede andere native dll. Im Zweifelsfall die dll unter C:\Windows\SysWOW64 kopieren, dann sollte sie immer gefunden werden.

Wenn ich es richtig verstehe, dann müsste ich während dem Spiel nach jedem Zug einen neuen Lerndatensatz hinzufügen und anschließend jedes mal das NN noch einmal alle Lerndatensätze lernen lassen.

Korrekt. Wobei man auch der Effizienz halber nur nach dem Spielende trainieren kann. Dann wird neues eben erst nach jedem Spiel erlernt. Sonst kann - je nach wachsender Größe des Trainingsdatensatzes - das Spiel doch zäh werden.

Für jeden Spielzug, an dem die KI an der Reihe ist, wird folgendes ausgeführt:

1) An die 5 Eingänge des NN werden die 5 Eigenschaftswerte der aktuellen Karte angelegt.
2) Die Aktion wird durchgeführt, an deren Ausgang der höchste Wert von allen 5 Ausgangswerten anliegt (Zu Beginn rein zufällig also).
3) Die Karten beider Spieler werden aufgedeckt und verglichen
4) UNABHÄNGIG davon, ob der Stich gewonnen ist, wird ein Datensatz angelegt, der für jede der 5 möglichen Aktionen, die zum Gewinn geführt hätten, eine 1 enthält, und für die Verlustaktionen eine 0.
5) Lernen: Nun wird mittels Backpropagation (???) ein Lernen über alle Lerndatensätze durchgeführt. Wenn das Lernen nicht gegen eine "Abweichung" von 0 konvergiert, wird nach einem Timeout abgebrochen.

Zu Schritt 4:
Guter Punkt. Ich hätte für jede Aktion, die zum Gewinn geführt hätte, einen eigenen Trainingsdatensatz erzeugt. Auf die beschriebene Art müsste es aber auch funktionieren und es verkürzt das Training, da weniger Datensätze erzeugt werden. Klingt gut, ja.
Zu Schritt 5:
Mit einer festen Anzahl Trainingszyklen nach jedem Spieldurchlauf kommt man bestimmt schon hin. Eine Überwachung der Konvergenz ist hier nicht unbedingt nötig. Man kann sich die gesammelten Datensätze ja mal in MemBrain selbst zusammen mit dem Netz anschauen und sehen, wie sich die Trainingskonvergenz verhält.

Falls die KI den Stich gewonnen hat, also laut Regelwerk immer noch am Zug ist, geht es gleich wieder weiter mit Schritt 1) . Ansonsten wird das Spiel fortgesetzt, bis irgendwann die KI wieder am Zug ist.
Die KI lernt nur anhand der einzelnen separaten Stiche. Das finale Spielergebnis (Spiel endet, wenn ein Spieler keine Karten mehr hat) hat auf das Lernen keinen Einfluss.
Somit kann ein Spiel auch beliebig beendet werden (Durch Spielende laut Regelwerk oder Spielabbruch) und neu gestartet werden, die KI lernt einfach weiter.

Korrekt.

Die Lerndatensatztabelle hätte folgende Spalten:
MerkmalA; MerkmalB; MerkmalC; MerkmalD; MerkmalE; AGewinnt; BGewinnt; CGewinnt; DGewinnt; EGewinnt

Ebenfalls korrekt

Ist der Ablauf so umsetzbar?

Ich denke schon, ja.

Oder habe ich das Reinforcement Leraning falsch verstanden?

Wie gesagt, ist das KEIN Reinforcement Learning. Bei RL wird für jede Aktion ein Wert erlernt und es benötigt kein Wissen über das Spiel. Bei einer echten RL-Implementierung müsste man dem Netz nicht sagen, was die richtige Wahl gewesen wäre. Da wäre nur Gewinn oder Verlust (Belohnung bztw. Bestrafung) eingegangen. Im vorliegenden Fall scheint mir aber die beschriebene Implementierung ausreichend und als 'Einstieg' ist das definitiv geeigneter, als sich gleich mit RL auseinandersetzen zu müssen. In einem weiteren Schritt kann man dann ja eine echte RL Implementierung angehen, die funktioniert dann auch für Probleme, bei denen man nicht für jede Aktion gleich sagen kann, was stattdessen besser gewesen wäre.

Aber wie kann ich die optimale Anzahl Anzahl der Hidden-Neuronen-Schichten ermitteln. Gillt hier "Je mehr desto besser!" oder "Je weniger desto besser!"? Und wie viele Neuronen benötige ich pro Schicht?

Ich würde mit einer Hidden-Schicht und darin zwei bis drei Neuronen beginnen. Damit erst mal alles aufsetzen und testen. Optimieren kann man dann immer noch.

Viele Grüße