AlphaGo Zero: tut es $Q(s_t, a)$ dominieren $U(s_t, a)$ in schwierigen Spielzuständen?

Dec 03 2020

AlphaGo Zero

AlphaGo Zero verwendet eine Monte-Carlo-Baumsuche, bei der die Auswahlphase von gesteuert wird $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, wo:

Der Exploitation-Parameter ist $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (dh der Mittelwert der Werte $v_i$ aller Simulationen, die durch die Kante gehen $(s_t, a)$)
Der Explorationsparameter ist $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (dh die vorherige Wahrscheinlichkeit $P(s_t, a)$, gewichtet mit der Konstante $c_{puct}$, die Anzahl der Simulationen, die durchlaufen werden $(s_t, a)$sowie die Anzahl der Simulationen, die durchlaufen werden $s_t$).

Die vorherige Wahrscheinlichkeit $P(s_t, a)$ und Simulationswert $v_i$ werden beide vom tiefen neuronalen Netzwerk ausgegeben $f_{\theta}(s_t)$::

Dieses neuronale Netzwerk nimmt als Eingabe die Rohplatinen-Darstellung s der Position und ihrer Geschichte und gibt sowohl Bewegungswahrscheinlichkeiten als auch einen Wert (p, v) = fθ (s) aus. Der Vektor der Bewegungswahrscheinlichkeiten p repräsentiert die Wahrscheinlichkeit der Auswahl jeder Bewegung a (einschließlich Durchlauf), pa = Pr (a | s). Der Wert v ist eine skalare Bewertung, die die Wahrscheinlichkeit des Gewinns des aktuellen Spielers von Position s aus schätzt.

Meine Verwirrung

Meine Verwirrung ist das $P(s_t, a)$ und $v_i$ sind Wahrscheinlichkeiten, die auf verschiedene Verteilungen normalisiert sind, was zu $v_i$ etwa 80x größer als $P(s_t,a)$ im Durchschnitt.

Das neuronale Netzwerk wird ausgegeben $(p, v)$, wo $p$ ist ein gegebener Wahrscheinlichkeitsvektor $s_t$, normalisiert über alle möglichen Aktionen in dieser Runde. $p_a = P(s_t, a)$ ist die Wahrscheinlichkeit, eine Aktion zu wählen $a$ gegebener Zustand $s_t$. Ein Go-Spiel hat ungefähr 250 Züge pro Runde, daher hat jeder Zug im Durchschnitt eine Wahrscheinlichkeit$\frac{1}{250}$dh $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

Andererseits, $v$ ist die Wahrscheinlichkeit, einen bestimmten Zustand zu gewinnen $s_t$, normalisiert über alle möglichen Endspielbedingungen (Gewinn / Unentschieden / Verlust). Nehmen wir der Einfachheit halber an$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, wo das Spiel zufällig gespielt wird und jedes Ergebnis gleich wahrscheinlich ist.

Dies bedeutet, dass der erwartete Wert von $v_i$ ist mindestens 80x größer als der erwartete Wert von $P(s_t, a)$. Die Folge davon ist, dass$Q(s_t, a)$ ist mindestens 80x größer als $U(s_t, a)$ im Durchschnitt.

Wenn das oben Gesagte zutrifft, wird die Auswahlphase von der dominiert $Q(s_t, a)$ Daher sollte AlphaGo Zero dazu neigen, Kanten ohne Simulationen zu vermeiden (Kanten, bei denen $Q(s_t, a) = 0$) sofern nicht alle vorhanden sind $Q(s_t, a)$ Begriffe sind extrem klein ($< \frac{1}{250}$), oder das MCTS enthält so viele Simulationen, dass das $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ Begriff in $U(s_t, a)$gleicht die Größen der beiden Begriffe aus. Letzteres wird wahrscheinlich nicht passieren, da ich glaube, dass AlphaGo Zero nur verwendet$1,600$ Simluationen pro Zug, also $\sqrt{\sum_b N(s_t, b)}$ Kappen bei $40$.

Nur tragfähige Züge auswählen

Im Idealfall sollte MCTS nicht jede mögliche Bewegung auswählen, die erforscht werden soll. Es sollte nur tragfähige Züge in einem bestimmten Zustand auswählen$s_t$und ignoriere alle schlechten Züge. Lassen$m_t$ ist die Anzahl der realisierbaren Bewegungen für den Staat $s_t$, und lass $P(s_t, a)$ = 0 für alle Züge $a$das sind nicht lebensfähig. Nehmen wir außerdem an, dass das MCTS niemals einen Zug auswählt, der nicht realisierbar ist.

Dann wird der vorige Abschnitt teilweise gelindert, weil jetzt $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. Als Ergebnis,$Q(s_T, a)$ sollte nur sein $\frac{m_t}{3}$ mal größer als $U(s_t, a)$im Durchschnitt . Vorausgesetzt$m_t \le 6$Dann sollte es kein allzu großes Problem geben

Dies bedeutet jedoch, dass AlphaGo Zero nur dann ideal funktioniert, wenn die Anzahl der realisierbaren Züge gering ist. In einem Spielzustand$s_t$ wo es viele realisierbare Bewegungen gibt ($>30$) (z. B. eine schwierige Wendung mit vielen möglichen Auswahlmöglichkeiten), wird sich die Auswahlphase des MCTS wie im vorherigen Abschnitt beschrieben verschlechtern.

Fragen

Ich denke meine Fragen sind:

Ist mein Verständnis korrekt oder habe ich irgendwo Fehler gemacht?
Tut $Q(s_t, a)$ in der Regel dominieren $U(s_t, a)$um so viel in der Praxis, wenn der Spielzustand viele tragfähige Züge hat? Wird die Auswahlphase normalerweise dominiert von$Q(s_t, a)$ während dieser Spielzustände?
Tut die Tatsache, dass $Q(s_t, a)$ und $U(s_t, a)$ Wenn Sie sich in so unterschiedlichen Größenordnungen befinden (wenn der Spielstatus viele realisierbare Bewegungen aufweist), wirkt sich dies auf die Qualität des MCTS-Algorithmus aus. Ist MCTS in diesem Sinne robust und erstellt dennoch Richtlinien von hoher Qualität?
Wie häufig hat ein Spielstatus in Go viele realisierbare Züge (> 30)?

Antworten

2 DennisSoemers Dec 05 2020 at 03:08

Ich glaube nicht, dass Sie unbedingt echte Fehler in Ihren Berechnungen oder Ähnlichem gemacht haben, das scheint alles korrekt zu sein. Ich kann Ihre Fragen zu "Kommt X normalerweise vor?" Nicht wirklich sicher beantworten. oder "Wie häufig ist X?" müsste experimentieren, um dies sicherzustellen. Ich denke, wir können die Frage, ob MCTS robust ist und dennoch qualitativ hochwertige Richtlinien erstellen kann, auch sofort mit "Ja" beantworten, da wir bei einer Reihe von Spielen mit diesen Techniken hochmoderne Ergebnisse auf dem neuesten Stand der Technik gesehen haben .