Was war die Quelle der Zufälligkeit im Match Alpha Zero gegen Stockfish?

7

Mein Verständnis ist, dass der Algorithmus von Alpha Zero nach der "Lern" -Phase behoben wurde. Würde er also für jede Position den gleichen Zug ergeben? War die Variabilität des Spiels vollständig auf eine Stockfisch-Einstellung zurückzuführen, oder zeigte Alpha Zero auch ein zufälliges Element in seiner Zugauswahl an?

Firtydank
quelle
2
Die von Alpha-Null verwendete Monte-Carlo-Baumsuche klingt ziemlich zufällig.
Hoacin
1
Monte Carlo ist kein deterministischer Algorithmus.
SmallChess
Meines Wissens nach wurde der mcst in der "Lern" -Phase verwendet, um das neuronale Netz zu trainieren, während der Algorithmus für die tatsächliche Übereinstimmung festgelegt wurde. Scheint, als würde mir ein Trick fehlen.
Firtydank
3
Ich denke, mcts wurde die ganze Zeit benutzt.
Hoacin
Eine andere mögliche, wenn auch unwahrscheinliche Quelle für Abweichungen ist die Zeit. Während die gleiche Zeit für den gleichen Zug verwendet werden kann, gibt es immer die Möglichkeit, eine andere Zeit in Anspruch zu nehmen, um einige Berechnungen durchzuführen. Daher lief sie möglicherweise ein bisschen schneller als die andere, und je schneller die Zeit kam, desto besser antworte, weil es weiter ging als die langsamere Zeit.
Benji Altman

Antworten:

6

Ich habe bemerkt, dass AlphaZero 1.d4 und 1.Sf3 in http://www.chessgames.com/perl/chess.pl?tid=91944&crosstable=1 gespielt hat . Möglichkeiten:

  • Mutlithreading (jeder Softwareentwickler kann Ihnen sagen, dass es nicht deterministisch ist)
  • Monte-Carlo-Baumsuche (der Algorithmus zeichnet zufällige Pfade, kann also nicht deterministisch sein)

Bitte beachten Sie, dass die Parameter des Modells möglicherweise "fest" sind (Ihre eigenen Wörter), die tatsächliche Bewegung jedoch möglicherweise anders ist. Wir haben keinen Quellcode für AlphaZero, aber Multithreading und MCTS sind wahrscheinlich zwei Hauptursachen.

SmallChess
quelle
1
Was meinst du, Multithreading ist nicht deterministisch? Ist das nicht abhängig davon, wie es verwendet wird. Wir wissen vielleicht nicht, welcher Thread zuerst beendet wird, aber zum größten Teil neigen die Leute dazu (oder versuchen es zumindest), darauf zu achten, dass Inkonsistenzen mit der Reihenfolge, in der die Dinge ausgeführt werden, das Endergebnis des Programms nicht beeinflussen.
Benji Altman
@ BenjiAltman Ich schrieb, wir haben keinen Quellcode. Sie können gerne zu Ihrer eigenen Antwort beitragen.
SmallChess
3
Multithreading in Schachengines ist fast nie deterministisch.
SmallChess
1
@ BenjiAltman Threads können die Verarbeitung zu unterschiedlichen Zeiten beenden. Wenn das Programm nicht irgendwie darauf wartet, dass jeder Thread beendet wird, und sie deterministisch zurückgibt, kann das tatsächliche Ergebnis davon abhängen, welchem ​​Thread vom Scheduler eine höhere Priorität zugewiesen wird.
1
@rec Richtig. Hochleistungsanwendungen wie Schach warten nicht auf das Ende der Threads (sie sind keine Geschäftsanwendungen!) Und sind daher deterministisch. Zum Beispiel ist Stockfish, der auf Multi-Core läuft, zu 100% nicht deterministisch.
SmallChess
5

Die LC0-Autoren haben das AlphaZero-Papier sehr sorgfältig studiert, eigene Experimente durchgeführt und sind zu folgendem Ergebnis gekommen. Obwohl AlphaZero seinen Algorithmus Monte-Carlo-Baumsuche nennt (alle Monte-Carlo-Methoden sind per Definition explizit zufällig), verwendet AlphaZero nach einer bestimmten Anzahl von Zügen keinen expliziten Nichtdeterminismus (ich glaube, das sind 15 Züge).

MCTS besteht aus zwei verschiedenen Teilen, die Zufälligkeiten in die Bewegungsauswahl einbringen können.

  1. Während der Suchphase weist AlphaZero Gewichte zu, anhand derer Bewegungen untersucht werden sollen, basierend auf zwei Faktoren: der vom neuronalen Netzwerk ausgewerteten Gewinnwahrscheinlichkeit sowie einigen Teilbaumgrößenstatistiken der übergeordneten und untergeordneten Bewegungsunterbäume. Der erste Faktor stellt sicher, dass zuerst vielversprechendere Zeilen bewertet werden, und der zweite Faktor stellt sicher, dass weniger vielversprechende Zeilen schließlich durchsucht werden. In einer natürlichen Implementierung von MCTS würde es gewichtete zufällige Entscheidungen zwischen diesen gewichteten Möglichkeiten verwenden. In der Realität wählt AlphaZero völlig deterministisch zwischen diesen aus, indem jedes Mal nur das maximale Gewicht ausgewählt wird. Dies geschieht, weil sich die Zufälligkeit in diesem Schritt nicht als hilfreich herausstellt und den Motor im Durchschnitt nur von den wichtigeren Variationen ablenkt.

  2. Während der Verschiebungsphase kann eine gewichtete Auswahl zwischen Verschiebungskandidaten getroffen werden, die bereits tiefe und genaue Bewertungen haben, die von der Suchphase berechnet wurden. Die Idee ist, leicht suboptimale Bewegungen zu machen, um zu versuchen, Vielfalt in sein Spiel einzuführen, damit es nicht jedes Mal das gleiche Spiel spielt. Dies ist besonders wichtig während des Trainings, führt aber auch zu interessanteren Spielergebnissen. Es stellt sich heraus, dass AlphaZero dies nur für die ersten 15 Züge oder so tut, danach wählt es immer den besten Zug. Dieser Determinismus erweist sich als wesentlich für sein äußerst genaues Endspiel, bei dem sich winzige Unterschiede in der Bewertung als Unterschied zwischen Unentschieden und Gewinnen herausstellen.

Dies gilt sowohl während des Trainings als auch während der Evaluierung.

Mit anderen Worten, sobald es aus der Öffnung heraus ist, ist sein Spiel so deterministisch wie ein traditioneller Motor.

Beachten Sie jedoch, dass es dieselbe Art von Multithreading- und Zeitsteuerungs-Nichtdeterminismus wie herkömmliche Engines gibt.

Benjamin
quelle