AlphaZeros Suchverfahren

6

Mir sind verwandte Fragen und gute Antworten zum gleichen Thema bekannt, z. B. AlphaZero verstehen . Meine Fragen beziehen sich auf die folgende Abbildung zum Suchverfahren von AlphaZero

Geben Sie hier die Bildbeschreibung ein

Diese Abbildung stammt aus dem Wissenschaftspapier zu AlphaZero (Abb. 4, Seite 4). Die Suche wird nach einer Position aus dem sehr schönen Spiel 1 AlphaZero (weiß) und Stockfish (schwarz) nach 29 dargestellt. ... Df8. Der Rest der Anmerkung der Figur ist wie folgt

Der interne Zustand von AlphaZeros MCTS wird nach 10 ^ 2, ..., 10 ^ 6 Simulationen zusammengefasst. Jede Zusammenfassung zeigt die 10 am häufigsten besuchten Staaten. Der geschätzte Wert wird in jedem Zustand aus der Sicht von Weiß angezeigt und auf den Bereich [0, 100] skaliert. Die Anzahl der Besuche jedes Zustands im Verhältnis zum Stammzustand dieses Baums ist proportional zur Dicke des Grenzkreises. AlphaZero berücksichtigt 30.c6, spielt aber schließlich 30.d5.

Ich würde mich über einige Einblicke in die folgenden Fragen freuen. (Wichtig zu beachten, dass ich nur ein Schachspieler ohne Kenntnisse der Informatik bin. Ich finde das immer noch faszinierend.)

  1. Was repräsentiert die 10 ^ 2, ..., 10 ^ 6 Simulationen? Ich bin sehr verwirrt, weil sie im ergänzenden Material feststellen, dass "während des Trainings jedes MCTS 800 Simulationen verwendet hat".
  2. Was bedeutet es, dass jedes MCTS 800 Simulationen verwendet hat?
  3. Ich gehe davon aus, dass der Wert von 60 im roten Kreis in den 10 ^ 2-Simulationen eine erwartete Punktzahl von 60% für Weiß darstellt, was der Durchschnitt aller Positionsbewertungen ist. Der einfache Durchschnitt der 9 gezeigten Züge beträgt jedoch 61,2. Ich denke, dass auch andere Bewegungen berücksichtigt und simuliert wurden. Bin ich hier richtig
  4. Ich gehe davon aus, dass sie für die Simulationen 10 ^ 3 bis 10 ^ 6 nur eine veranschaulichende Stichprobe der Zweige darstellen. Die Simulation 10 ^ 5 wird nach 34.Tce1 nicht angezeigt oder nach 34.Tce1 gestoppt? Ich denke, dass jede Simulation bis zu einer erwarteten Punktzahl von 100% geht.
Kortchnoi
quelle

Antworten:

5

Das Diagramm zeigt die 10 am häufigsten besuchten Spielzustände / Positionen, die AlphaZero berechnet hat. Es werden tatsächlich Tausende von Positionen betrachtet, aber es werden nur die 10 Positionen angezeigt, auf die am meisten zurückgegriffen wird. Für Ihre Fragen:

1) Der Suchalgorithmus von AlphaZero heißt Monte Carlo Tree Search (MCTS). Die Grundlagen, wie es funktioniert, wenn man in einem bestimmten Spielzustand denkt:

  • Wähle einen Zug. Die Art und Weise, wie dieser Zug ausgewählt wird, basiert auf einem Algorithmus, der Folgendes bevorzugt:
    • Wie gut ein Zug in früheren Zufallssimulationen davon war.
    • Wie selten wurde es ausgewählt (ein Zug, der weniger gespielt wurde ==> wünschenswerter).
  • Folgen Sie diesem Zug in einen neuen Spielzustand (dh die Position, die entsteht, wenn Sie den Zug spielen).
  • Wiederholen Sie Schritt 1 für einige Zeit oder Tiefenbegrenzung.

Der Zug, der in allen Playouts die beste durchschnittliche Punktzahl aufweist, wird von AlphaZero ausgewählt. Es geht um mehr als das, aber das Obige ist die allgemeine Idee von MCTS. So etwas wie 10 ^ 2-Simulationen für den Wurzelknoten bedeutet, dass AlphaZero den obigen Algorithmus 10 ^ 2 Mal für diese Position ausgeführt hat.

Der Teil, in dem "800 Simulationen" erwähnt wurden, bezieht sich auf den Zeitpunkt, an dem AlphaZero lernte ( vor seinen Spielen mit Stockfish). AlphaZero lernt Heuristiken selbstständig (wodurch Positionen genau bewertet werden können), indem es sich immer wieder selbst spielt. Ich gehe davon aus, dass sie bedeuten, dass in dieser Phase des Spielens jedes Mal, wenn überlegt wurde, was in einer Position gespielt werden soll, nur 800 Simulationen von einer Position aus durchgeführt wurden. Der Grund dafür war wahrscheinlich, Zeit zu haben, um mehr Übungsspiele zu spielen. Gegen Stockfish ist es nicht notwendig, extrem schnell zu spielen, und AlphaZero kann auch die Zeit nutzen, die ihm für das Ausspielen von mehr solcher Simulationen zur Verfügung steht.

2) Oben erklärt.

3) Ja, Tausende anderer Züge werden ebenfalls berücksichtigt. Sie werden im Diagramm einfach nicht angezeigt. Auch wenn die 10 angezeigten Zustände die einzigen erreichten, die erreicht wurden, konnte man ihre Punktzahlen nicht einfach herausrechnen. Der Grund ist, dass einige Spielzustände häufiger erreicht werden als andere und daher in der Durchschnittsberechnung ein höheres Gewicht haben.

  • Nehmen Sie zur Veranschaulichung an, Sie hätten zu Beginn eines Spiels nur zwei mögliche Züge gespielt: 1.e4 und 1.h4. Rückblickend auf den von mir skizzierten MCTS-Algorithmus würden Playouts / Simulationen auf 1.e4 häufiger auftreten, da 1.e4 eine bessere Leistung erbringt. 1.h4 wird jedoch auch gelegentlich ausgewählt, da Sie es nur selten betrachten. Vielleicht machst du 9 Playouts auf 1.e4 und bekommst eine Punktzahl von 60%, während du 1 Playout auf 1.h4 machst und eine Punktzahl von 0% bekommst. Ihre Gewinnchancen von der Startposition aus sind nicht (60% + 0%) / 2 = 30%, sondern (60% * 9 + 0% * 1) / 10 = 54%.

4) Ja, es wird nur ein veranschaulichendes Beispiel gezeigt, da nur die 10 am häufigsten besuchten Spielzustände angezeigt werden sollen. Ich bin sicher, AlphaZero hat den MCTS-Algorithmus weit über 34.Tce1 hinaus fortgesetzt.

Trägheitsunwissenheit
quelle
Vielen Dank! Gute Antwort. Ok, ich verstehe, dass AZ während der Spiele gegen SF 10 ^ 6 Simulationen pro gespielter Position / Zustand durchgeführt hat, z. B. nach 29 ... Df8 ... In Bezug auf Q1 ist für mich 1 / "Pick a move" unklar. ist ein MCTS und "Schritt 1 wiederholen" ist ein anderes MCTS oder 2 / ist Ihr Beispiel nur ein MCTS?
Kortchnoi
Genauer gesagt im 2. Fall: Ist Ihr Beispiel ein MCTS mit 2 Simulationen?
Kortchnoi
1
@Kortchnoi Das MCTS ist ein rekursiver Algorithmus. Dies bedeutet, dass es sich zum Ausführen X-mal selbst nennt (wobei X angibt, wie tief die Playout-Simulation von der Startposition aus ausgeführt wird). Die Schritte, die ich von "Pick a Move" bis "Repeat Step 1" aufgeführt habe, sind alle Teil einer MCTS-Simulation, unabhängig davon, wie oft der Algorithmus den Spielbaum rekursiv durchläuft. Eine weitere Simulation wird erst gestartet, wenn der Algorithmus die Suche beendet hat, und eine neue Wiedergabesimulation beginnt erneut von der Startposition aus.
Trägheitsunwissenheit
1
Stellen Sie sich das so vor. Sie möchten wissen, was Sie im ersten Zug spielen sollen. Sie wählen 1.e4 über den Algorithmus aus, da es in der Vergangenheit in den Simulationen, die Sie mental durchgeführt haben, gut funktioniert hat und Sie gleichzeitig nicht zu viele Simulationen durchgeführt haben. Jetzt in der neuen Position nach 1.e4 müssen Sie einen Zug auswählen, damit Schwarz spielen kann. Sie machen den gleichen Algorithmus und nehmen an, Sie erhalten 1 ... c5. Jetzt ist Weiß an der Reihe zu spielen, also machen Sie den gleichen Algorithmus. Usw., bis Sie ein Tiefenlimit erreichen oder jemand das Spiel gewinnt (oder zieht). Dies ist alles eine Simulation von der Startposition.
Trägheitsunwissenheit
1
Ja genau. Jedes MCTS ist nur eine Ansammlung dieser Simulationen, die von der Position aus ausgeführt werden, an die Sie denken.
Trägheitsunwissenheit