Wie gehe ich mit ungültigen Zügen beim Lernen um?

Ich möchte eine KI erstellen, die Five-in-A-Row / Gomoku spielen kann. Wie ich bereits im Titel erwähnt habe, möchte ich dafür das verstärkende Lernen verwenden.

Ich verwende die Policy-Gradient- Methode, nämlich REINFORCE, mit Baseline. Für die Näherung von Wert und Richtlinienfunktion verwende ich ein neuronales Netz . Es hat Faltungsschichten und vollständig verbundene Schichten. Mit Ausnahme der Ausgabe werden alle Ebenen gemeinsam genutzt. Die Ausgabeebene der Richtlinie enthält die Ausgabeeinheit $8 \times 8=64$ (die Größe der Karte ) und den Softmax . Es ist also stochastisch. Was aber, wenn das Netzwerk eine sehr hohe Wahrscheinlichkeit für einen ungültigen Zug erzeugt? Ein ungültiger Zug liegt vor, wenn der Agent ein Feld mit einem "X" oder "O" überprüfen möchte. Ich denke, es kann in diesem Spielzustand stecken bleiben.

Könnten Sie eine Lösung für dieses Problem empfehlen?

Ich vermute, die Schauspieler-Kritik- Methode zu verwenden. Für einen ungültigen Zug sollten wir eine negative Belohnung geben und den Zug an den Gegner weitergeben.

Ignoriere einfach die ungültigen Züge.

Für die Erkundung ist es wahrscheinlich, dass Sie den Zug nicht nur mit der höchsten Wahrscheinlichkeit ausführen, sondern stattdessen Züge zufällig basierend auf der ausgegebenen Wahrscheinlichkeit auswählen. Wenn Sie nur illegale Züge bestrafen, behalten diese eine gewisse Wahrscheinlichkeit (wie gering sie auch sein mögen) und werden daher von Zeit zu Zeit (wie selten sie auch sein mögen) ausgeführt. So behalten Sie immer einen Agenten, der gelegentlich illegale Aktionen ausführt.

Für mich ist es sinnvoller, die Wahrscheinlichkeiten aller illegalen Züge auf Null zu setzen und den Ausgabevektor neu zu normalisieren, bevor Sie Ihren Zug wählen.

Normalerweise verwenden Softmax-Methoden in Policy-Gradienten-Methoden unter Verwendung der linearen Funktionsnäherung die folgende Formel, um die Wahrscheinlichkeit für die Auswahl der Aktion $a$ zu berechnen . Hier werden die Gewichte $\theta$ , und die Funktionen $\phi$ a in Abhängigkeit von dem aktuellen Zustand ist $s$ und eine Aktion aus der Menge von Aktionen $A$ .

Um illegale Aktionen zu eliminieren, würde man die Menge der Aktionen auf diejenigen beschränken, die legal waren, daher $Legal(A)$ .

Im Pseudocode kann die Formel so aussehen:

action_probs = Agent.getActionProbs(state)
legal_actions = filterLegalActions(state, action_probs)
best_legal_action = softmax(legal_actions)

Unabhängig davon, ob Sie eine lineare oder eine nichtlineare Funktionsnäherung (Ihr neuronales Netz) verwenden, sollten Sie bei der Berechnung Ihres Softmax nur die zulässigen Schritte verwenden. Diese Methode bedeutet, dass der Agent nur gültige Züge ausgibt. Dies ist gut, wenn Sie Ihr Spiel später ändern möchten, und dass der Agent den Wertunterschied zwischen der eingeschränkten Auswahl an Aktionen leichter erkennen kann. Es ist auch schneller, wenn die Anzahl der möglichen Aktionen abnimmt.

IMHO ist die Idee der ungültigen Bewegungen selbst ungültig. Stellen Sie sich vor, Sie platzieren ein "X" an den Koordinaten (9, 9). Sie könnten es als ungültigen Zug ansehen und es negativ belohnen. Absurd? Sicher!

Tatsächlich sind Ihre ungültigen Züge jedoch nur ein Relikt der Darstellung (die selbst einfach und in Ordnung ist). Die beste Behandlung von ihnen besteht darin, sie vollständig von jeder Berechnung auszuschließen.

Dies wird im Schach deutlicher:

• In einer Positionsdarstellung können Sie den Zug in Betracht ziehen a1-a8, der nur dann zum Spiel gehört, wenn sich ein Turm oder eine Königin im Spiel befindet a1(und einige andere Bedingungen erfüllt sind).

• In einer anderen Darstellung könnten Sie den Umzug in Betracht ziehen Qb2. Auch dies kann zum Spiel gehören oder nicht. Wenn der aktuelle Spieler keine Dame hat, dann hat er sicherlich keine.

Da die ungültigen Züge eher mit der Darstellung als mit dem Spiel zusammenhängen, sollten sie überhaupt nicht berücksichtigt werden.

Ich hatte kürzlich ein ähnliches Problem mit Minesweeper.

Die Art und Weise, wie ich es gelöst habe, war, die illegalen / ungültigen Züge vollständig zu ignorieren.

1. Verwenden Sie das Q-Netzwerk, um die Q-Werte für alle Ihre Aktionen (gültig und ungültig) vorherzusagen.
2. Verarbeiten Sie die Q-Werte vorab, indem Sie alle ungültigen Züge auf einen Q-Wert von Null / negative Zahl setzen (abhängig von Ihrem Szenario).
3. Verwenden Sie eine Richtlinie Ihrer Wahl, um eine Aktion aus den verfeinerten Q-Werten (dh gierig oder Boltzmann) auszuwählen.
4. Führen Sie die ausgewählte Aktion aus und setzen Sie Ihre DQN-Logik fort

Hoffe das hilft.