AlphaZero verstehen

29

Kürzlich wurde bekannt, dass das DeepMind-Forschungsteam von Alphabet seine Engine für maschinelles Lernen erweitert hat, um sowohl Shogi als auch Schach zu spielen. Offensichtlich hat seine Leistung im Schach nach nur wenigen Stunden des Selbstlernens, dh wenn man nur gegen sich selbst spielt, die Regeln der Spiele befolgt, die der aktuellen Top-Engines wie Stockfish 8 bereits übertroffen. Ich persönlich weiß noch nicht, wie genau die Matches eingestellt wurden, da Stockfish bei begrenzten Berechnungszeiten eine sehr schlechte Leistung bringen kann. In jedem Fall ist dies eine sehr beeindruckende Leistung, denn selbst wenn sich herausstellt, dass man Stockfish mit wenigen zusätzlichen Trainingsstunden optimaler hätte einrichten können, würde AlphaZero das Spielniveau erneut übertreffen, was bedeutet, dass AlphaZero von Grund auf stärker ist als jede andere Strömung Standard-Schachengine basierend auf heuristischen Auswertungsfunktionen.

Angesichts dieser Neuigkeiten wäre es großartig, wenn jemand auf die Hauptunterschiede bei der Funktionsweise einer maschinengelernten Schachmaschine im Vergleich zu den Standardmaschinen eingehen könnte, die wir alle gewohnt sind. Genauer gesagt:

  1. Ist die Evaluierungsfunktion, die AlphaZero verwendet und die mit maschinellen Lernmethoden trainiert wurde, am Ende nicht nur eine weitere heuristische Evaluierungsfunktion? Wenn ja, wäre es fair zu sagen, dass der grundlegende Unterschied zwischen den Bewertungsfunktionen der beiden Motoren darin besteht, dass Stockfish eine von Menschen handabgestimmte optimierte Bewertungsfunktion hat, was bedeutet, dass die Definition der zu optimierenden Funktion festgelegt ist, während z AlphaZero, die Zielbewertungsfunktion wird durch zusätzliches Training (zum Beispiel durch Selbstspiel) ständig neu definiert? Letzteres zu einer weitaus dynamischeren Herangehensweise machen.
  2. Letztendlich wendet ein Motor wie Stockfish seine Bewertungsfunktion auf den Baum möglicher Bewegungen an und entscheidet, welche Zweige behalten und welche fallen gelassen werden sollen, und geht dann durch einen tieferen BetonBei der Analyse jedes Zweigs wird anhand seiner Bewertungsfunktion herausgefunden, welcher Zweig den höchsten Wert ergab, und dies wird zur Hauptvariante (natürlich gibt es viele fortgeschrittene Techniken, um diesen großen Baum effizient zu beschneiden). Das heißt, für jede Position muss diese äußerst konkrete Routine wiederholt werden, damit Stockfish eine Entscheidung trifft. Ich stelle mir dagegen vor, AlphaZero macht etwas ganz anderes: Es basiert nicht auf einer konkreten Analyse des Baums möglicher Bewegungen an einer bestimmten Position, sondern weist dieser Position durch seine Bewertungsfunktion im Wesentlichen einen Wert zu (was intuitiv dem Putten ähnlich ist die aktuelle Position in Analogie zu allen anderen Positionen, für die sie trainiert wurde, ohne jemals konkret arbeiten zu müssenAnalyse wie Stockfish oder sogar ein menschlicher Spieler. Ist dies überhaupt ein gutes Bild der Funktionsweise von AlphaZero oder ähnlich ausgebildeten Maschinenlernmaschinen?

  3. Wir wissen, dass der Raum von Schachpositionen groß genug ist, dass jeder Versuch, alle Positionen darin abzutasten, im Prinzip sogar völlig vergeblich wäre (EXPTIME-Komplexität), was nahelegt, dass kein Umfang an Training durch Selbstspiel ausreichen würde Haben Sie alle Positionen erkundet? Wie kann das Endergebnis dann gut sein, obwohl Sie möglicherweise einen kleinen Bruchteil der Positionen des Raums im Selbstspiel erkundet haben? Was ist die Schlüsselidee hier im Spiel?

  4. Ich vermute, AlphaZero hat eine sehr optimale Möglichkeit, eine bestimmte Position, auch wenn sie neu ist, mit einer zuvor besuchten Position in seinem Trainingssatz zu vergleichen. Je näher der Vergleich ist, desto aussagekräftiger ist die Bewertung, die man aus dem Vergleich ziehen kann. Wenn es zum Beispiel in Spiel 5 den Zug Bg5 gespielt hat , muss es während des Trainings eine ähnliche Struktur untersucht haben, dh es kann erkennen, dass diese Position im Wesentlichen einer (möglicherweise völlig) anderen entspricht, die es in seinem Training gelernt hat Analogie dazu, wie die Gesichtserkennung durch maschinelles Lernen erreicht wird, und als Ergebnis gelangt man zu dem Schluss, dass Bg5 der beste Zug sein sollte, genau wie in dieser (oder diesen) anderen ähnlichen Positionen. Ist das überhaupt eine richtige Vermutung? Ich habe keine Ahnung wie dieser Vergleich aussieht Dies ist erledigt, da es sicherlich nicht möglich ist, alle trainierten Positionen zu speichern und jedes Mal zu analysieren.

Dies ist lediglich ein Versuch, einen Einblick in die Funktionsweise von AlphaZero und die Frage zu erhalten, wie es zu einer Entscheidung kommt, die eine bestimmte Position einnimmt.

user929304
quelle

Antworten:

18
  • Wie wählt AlphaZero einen Zug in der Suche aus?

Dies ist aus dem Papier sehr offensichtlich.

Jede Simulation wird fortgesetzt, indem in jedem Zustand ein Zug mit einer geringen Anzahl von Besuchen, einer hohen Zugwahrscheinlichkeit und einer hohen Wertauswahl ausgewählt wird.

Was bedeutet das? AlphaZero hat Wahrscheinlichkeiten für jede Bewegung (Ende von Seite 2 im Artikel) aus einem tiefen neuronalen Netzwerk trainiert. Während der Suche werden eine Bewegung proportional zu dieser Wahrscheinlichkeit sowie Knoten mit geringer Anzahl ausgewählt (um sicherzustellen, dass der Abtastraum untersucht wird). Dies ist kein neues Konzept. Die Monte-Carlo-Baumsuche war bereits in der Literatur enthalten, bevor es Google gab.

------ (Sehr) grobes Beispiel ------

Wir haben eine Position und wir haben zwei rechtliche Schritte.

  • Zug 1 ist gut und vernünftig
  • Zug 2 bringt deinen eigenen König in Gefahr, ohne Entschädigung

Dem Papier zufolge könnte ein trainiertes Tiefenmodell die Wahrscheinlichkeiten auf (0,90, 0,10) schätzen. Angenommen, AlphaZero verwendet 4 Iterationen in Monte Carlo. Die Iterationen könnten so aussehen:

Iteration 1 : Wähle Zug 1, weil er die höchste Wahrscheinlichkeit hat. Führen Sie eine Simulation ab Zug 1 durch. Iteration 2 : Wählen Sie Zug 1 aus, da dies die höchste Wahrscheinlichkeit hat. Führen Sie eine Simulation ab Zug 1 durch. Iteration 3 : Wählen Sie Zug 1 aus, da dies die höchste Wahrscheinlichkeit hat. Mach eine Simulation ab Zug 1.

Jetzt sind wir bei Iteration 4. Obwohl Zug 1 die höhere geschätzte Wahrscheinlichkeit hat, aber Zug 2 nicht durchsucht wurde ("niedrige Besucherzahl" in der Zeitung), würde AlphaZero jetzt Zug 2 auswählen und eine Simulation durchführen.

Beide Schritte würden in Betracht gezogen, aber AlphaZero würde in Schritt 1 mehr Rechenressourcen einsetzen (eine gute Sache).

AlphaZero würde dann den Zug mit dem besten erwarteten Ergebnis auswählen.

------------------ Deine Fragen: ------------------

Ist die Evaluierungsfunktion, die AlphaZero verwendet und die mit maschinellen Lernmethoden trainiert wurde, am Ende nicht nur eine weitere heuristische Evaluierungsfunktion?

Die trainierte Bewertungsfunktion ist ein tiefes neuronales Netzwerk. Es handelt sich nicht um heuristische Regeln, wie Sie sie in Stockfish sehen. Niemand versteht (auch nicht das Google-Team) das geschulte Netzwerk, es funktioniert einfach. So funktioniert NN im Allgemeinen.

Während für AlphaZero die Zielbewertungsfunktion durch die Zielbewertungsfunktion ständig neu definiert wird, wird sie durch zusätzliches Training ständig neu definiert.

Die Bewertungsfunktion in AlphaZero besteht aus einer Reihe trainierter Neuronen (Bias + Gewichte). Das Google-Team verwendete sehr leistungsfähige Maschinen, um die Parameter zu trainieren. Je mehr Ressourcen Sie in die Schulung eines Deep-Learning-Modells investieren können, desto bessere Parameter erhalten Sie im Allgemeinen.

(2).

Stockfish verwendet Alpha-Beta, während AlphaZero Monte-Carlo verwendet. Das sind zwei sehr unterschiedliche Algorithmen. Der Alpha-Beta-Algorithmus nimmt eine Unter- / Obergrenze an, während Monte-Carlo Simulationen von der Wurzel bis zum Blatt erstellt.

Wenn Sie alle Positionen erkundet haben, wie kann das Endergebnis dann gut sein, obwohl Sie möglicherweise einen kleinen Bruchteil der Positionen des Raums im Selbstspiel erkundet haben? Was ist die Schlüsselidee hier im Spiel?

Google behauptete nicht, sie hätten Schach gelöst, und nicht einmal ihre leistungsstarken Maschinen könnten möglicherweise alle Schachpositionen auflisten. Aber sie mussten nicht ... das ist der Punkt für maschinelles Lernen, das Modell "lernt" aus dem Trainingssatz. In diesem Fall stammt das Trainingsset aus dem Selbstspiel. Die Schlüsselidee ist es, so viele hochwertige Spiele wie möglich und schnell gegen sich selbst zu spielen.

Wenn es zum Beispiel in Spiel 5 den Zug Lg5 gespielt hat, muss es während seines Trainings eine ähnliche Struktur erkundet haben.

Ich glaube nicht, dass AlphaZero in den Trainingsspielen auf genau dieselbe Position gestoßen ist. Ich denke, ein kurzes Lesen von Monte-Carlo ist eine gute Idee:

https://chessprogramming.wikispaces.com/Monte-Carlo+Tree+Search

AlphaZero konnte den Zug durch Erreichen einer ausreichenden Tiefe spielen. Der Algorithmus schätzt die erwartete Gewinnwahrscheinlichkeit für jeden Zug. Offensichtlich ergab der Zug Bg5 die höchste erwartete Wahrscheinlichkeit.

Sie können sich vorstellen, dass AlphaGo so gut suchen konnte, dass die Gewinnwahrscheinlichkeit nach Lg5 am höchsten war, während Stockfish den Zug nicht ernsthaft in Betracht zog (und somit verlor).

Kleinschach
quelle
2
"Monte-Carlo-
Baumsuche
2
@CodesInChaos MCTS ist keine neue Technik. Google hat Monte Carlo mit Sicherheit nicht erfunden.
SmallChess
4
Brügmann 1993 ist eindeutig nur MC. MC Go Dev. (2003) kombiniert MC und Bäume auf primitive Weise. Chang (2005) ist ziemlich nah dran, aber in einem anderen Kontext und ich denke, es fehlt immer noch die richtige Wahl des Knotens, um Schätzungen zu erweitern und zu verbreiten. Effiziente Selektivitäts- und Sicherungsoperatoren in MCTS Remi Coulom (2006) ist meines Erachtens das erste richtige MCTS.
CodesInChaos
1
@SmallChess Teile Ihrer Antwort scheinen widersprüchlich zu sein: "Jetzt würde AlphaZero Zug 2 auswählen und eine Simulation durchführen. Beide Züge würden in Betracht gezogen, aber AlphaZero würde mehr Rechenressourcen für Zug 1 einsetzen (eine gute Sache)." widerspricht der Aussage. Jede Simulation fährt fort, indem in jedem Zustand eine Bewegung mit geringer Anzahl von Besuchen ausgewählt wird ... wie in Ihrem Beispiel 2 statt 1. Um ehrlich zu sein, enthält das Papier keine nützlichen Informationen für die Verständnis, da sie keine Möglichkeit zeigen, das Experiment zu reproduzieren oder einen Einblick in die tatsächliche Art und Weise zu geben, wie sie die Netzwerke trainieren.
Gented
1
Was sie tun, ist im Wesentlichen die Aussage "Wir haben Algorithmus X verwendet und er funktioniert" - was wenig bis gar kein Verständnis für die Methoden selbst bietet, sodass ich mich nicht zu sehr auf das Papier selbst konzentrieren würde, um herauszufinden, was es wirklich tut.
Gented
0

Ich denke, meine Frage wäre, wie das neuronale Netz "lernt", was zu tun ist, an einer Position, die es nicht angetroffen hat. Wenn die tatsächliche AZ ein MCTS unter Verwendung der Bias + -Gewichte aus dem trainierten neuronalen Netz ausführt, wird es nur einen Schritt zurückgeschoben, um zu ermitteln, wie das neuronale Netz diese Werte berechnet. Wenn es durch zufälliges Selbstspiel ohne menschliches Wissen geschehen ist, wie entscheidet es dann, wie eine Position gewichtet wird, die es noch nie gesehen hat?

Roy Koczela
quelle
1
Ich glaube, ich kann Ihnen vielleicht antworten, aber nicht hier. Bitte starte eine neue Frage.
SmallChess