Warum dominiert NN + MCTS & AB + handschriftliche Auswertung das Maschinenschach?

Soweit ich weiß, können Suchmaschinen derzeit in vier Gruppen unterteilt werden: diejenigen, die Alpha-Beta (AB) + diejenigen, die Monte Carlo Tree Search (MCTS) für die Suche verwenden, und diejenigen, die handschriftliche Funktionen verwenden + diejenigen, die neuronale Netze für die Suche verwenden eval. Die zwei stärksten Motoren sind Leela und Stockfish. Leela verwendet MCTS + NN, während Stockfish AB + handschriftlich verwendet.

Warum diese beiden Kombinationen? Warum nicht NN + AB oder MCTS + handschriftlich? Wenn MCTS besser ist als AB, warum ist Komodo MCTS nicht stärker als Komodo AB? Wenn AB besser ist als MCTS, warum verwendet Leela dann nicht stattdessen AB?

Geschwindigkeit

Neuronale Netze arbeiten viel langsamer als handgefertigte Auswertungsfunktionen. Im TCEC Superfinal kann Leela Chess Zero auf zwei GPUs mit jeweils dedizierten Tensorkernen rund 60.000 Positionen pro Sekunde suchen. Im Gegensatz dazu durchsucht Stockfish auf einem einzelnen Kern meines PCs über 2 Millionen Positionen pro Sekunde.

Während moderne Motoren über eine große Auswahl an Techniken verfügen , um unnötige Äste abzuschneiden , ist die Alpha-Beta-Baumsuche immer noch eine Brute-Force-Technik, bei der eine große Anzahl von Positionen durchsucht werden muss, um gute Züge zu bestimmen.

Im Gegensatz dazu ist MCTS weitaus selektiver und erweitert seinen Suchbaum nur in Richtung der vielversprechendsten Schritte, sodass er die begrenzte Anzahl von Knoten, die durchsucht werden können, optimal nutzen kann.

Schlimmstes Verhalten

Eine der Hauptanforderungen der Bewertungsfunktion für eine Engine, die auf der Alpha-Beta-Suche basiert, ist ein gutes Worst-Case-Verhalten . Dies liegt daran, dass jeder große Fehler in der Auswertung, wie selten er auch sein mag, leicht auf die Wurzel übertragen werden kann und zu einem entsetzlich falschen Zug führt.

Neuronale Netze sind aufgrund ihrer Komplexität anfällig für Überanpassungen und können nur so gut sein wie die Daten, mit denen sie trainiert wurden. In Match 80 des Superfinales der TCEC-Saison 14 war Lc0 im 47. Zug anscheinend unbeeindruckt von Stockfishs zusätzlicher Königin und bewertete die Position als coole +0,77, während Stockfish (und die meisten anderen Motoren) eine Bewertung von +8,31 aufwies. Eine beliebte Erklärung dafür ist, dass Lc0 möglicherweise nicht viele Spiele mit mehreren Damen auf dem Brett in seinem Trainingsset hatte.

Neuronale Netze weisen daher ein schlechtes Worst-Case-Verhalten auf und können daher bei der Alpha-Beta-Suche schlecht abschneiden. Im Gegensatz dazu ermöglicht MCTS, dass eine einer Position zugewiesene falsche Punktzahl ausgeglichen wird, indem sie mit angemessenen Punktzahlen herausgemittelt wird, die Positionen in der Nähe der Suche zugewiesen werden.

Ruhe

Alle starken Alpha-Beta-Engines verwenden eine Technik namens Ruhesuche , eine eingeschränkte Form der Alpha-Beta-Suche, die an Blattknoten angewendet wird, um zu erkennen, dass ihre handgefertigten Bewertungsfunktionen nur in "ruhigen" Positionen gut funktionieren, in denen keine Erfassungen oder Überprüfungen anstehen .

Unmittelbar nach der ersten Hälfte eines Königintauschs kann eine handgefertigte Bewertungsfunktion Ihnen beispielsweise mitteilen, dass die Seite, deren Königin gerade genommen wurde, vollständig verloren ist, wohingegen ein neuronales Netzwerk möglicherweise verstehen kann, dass die Königin bald wiedererobert wird.

Dies macht handgefertigte Auswertungsfunktionen aufgrund des Fehlens einer Ruhesuche für MCTS ebenfalls ungeeignet, was dazu führt, dass die handgefertigten Funktionen die meiste Zeit eine schlechte Leistung erbringen (obwohl Komodo 12 MCTS diese Einschränkung umgeht, indem es ohnehin kurze Alpha-Beta-Suchen verwendet , um Ruhepositionen zu erhalten und Erlauben Sie daher der handgefertigten Bewertung, eine angemessene Punktzahl zu erhalten.

AB und MCTS sind nicht unbedingt für sich genommen besser als einander. Es ist nur so, dass es sich um verschiedene Suchalgorithmen handelt, die mit verschiedenen Stiftungen besser funktionieren. Für das NN funktioniert MCTS gut, da es dem Motor ermöglicht, Zweige zu erkunden, denen es besser geht. Dies gibt dem Motor mehr Freiheit zu sehen, was er "will".

Mittlerweile müssen bei AB grundsätzlich alle Branchen betrachtet werden. Dies liegt daran, dass die Engine auch bei einer iterativen Vertiefung in jeder Iteration nur auf jedem Zweig so weit schaut. Es weiß also nicht, ob ein Zweig tatsächlich für eine Seite gewinnt, auch wenn er in einer begrenzten Tiefe zu verlieren scheint.