Dann saß ich einfach da und bewunderte AlphaZero gegen Stockfish . Und jetzt bin ich auf das Thema im Zusammenhang mit der Optimierung neuronaler Netze zurückgekommen, die manchmal bei der Arbeit durchgeführt werden muss (leider weniger, als wir möchten). Es scheint mir, dass diese Aufgaben eng miteinander verbunden sein könnten, deshalb wollte ich meine Ideen irgendwie systematisieren.
Schach ist ein Spiel mit vollständigen Informationen, die auf einer Aufzählung von Optionen basieren (sowie Dame, Los usw.).
Das Problem ist jedoch, dass der Variationsbaum im Schach ziemlich schnell wächst (obwohl deutlich langsamer als in Go). Zum Beispiel hat jede Seite mit einem vollen Brett aus Teilen in einer ruhigen Position ungefähr 10 vernünftige Fortsetzungen. Somit können wir in nur 3 Schwarz-Weiß-Zügen (6 halbe Züge) eine Million Positionen von diesem erhalten. Berücksichtigen wir auch, dass das durchschnittliche Spiel zwischen Personen 40-50 Züge dauert (zwischen Computern - 80-100). Wir werden daher zu dem Schluss kommen, dass eine vollständige Berechnung des Variantenbaums für die meisten Positionen unmöglich ist, was bedeutet, dass wir uns auf das teilweise Schneiden des Suchbaums sowohl in der Breite als auch in der Tiefe konzentrieren müssen. Nun wollen wir sehen, wie Menschen und Maschinen mit diesem Problem umgegangen sind. Ich beginne mit einem kleinen historischen Überblick.
"Proteinschach".
Schach ist seit ungefähr 1400 Jahren bekannt, aber die ersten großen Turniere fanden Mitte des 19. Jahrhunderts statt. Es war eine Zeit offener und romantischer Schlachten. Die Gegner versuchten, schnell Teile in den Kampf einzuführen, die Position zu öffnen und einen Angriff auf den König zu starten. Niemand hat materielle und positionelle Zugeständnisse besonders berücksichtigt. Überraschenderweise wurde der Antagonist des romantischen Schachs, Wilhelm Steinitz, der erste offizielle Weltmeister .
Er legte den Grundstein für das Positionsspiel . Vor allem dank Steinitz haben wir begonnen, mit Konzepten wie „Bauernstruktur“, „starken und schwachen Quadraten“, „guten und schlechten Stücken“ zu arbeiten. Dies ist es, was das Element der Strategie, das auf langfristigen Vorteilen basiert, in das Schach eingeführt hat. Steinitz entwickelte einen Positionsansatz und bestrafte seine Gegner unerbittlich für materielle Opfer und Positionsfehler. Emmanuel Lasker , der ihn auf dem Schachthron ersetzte, sprach sehr gut über den ersten Champion : " Steinitz 'Talent als praktischer Spieler war geringer als das Talent von Blackburn oder Zukertort, den er dennoch besiegte, weil er ein großer Denker war, und sie waren es nicht ."Steinitz formulierte die Grundprinzipien der Positionsbewertung und die daraus resultierenden Spielpläne in einer Hochsprache (in diesem Fall Deutsch).
Dementsprechend stellte er sie anderen Menschen zum Studium zur Verfügung . Dies hat die menschliche Herangehensweise an Schach geprägt. Wir nehmen es sehr ernst, den Variationsbaum im Schach nach Positionsprinzipien zu beschneiden. Einige Züge werden verworfen, weil sie zu einer schlechten Position am berechneten Horizont führen. Einige, weil sie zu langfristigen Zugeständnissen führen, andere, weil sie ziellos sind. Infolgedessen berechnen wir einen sehr kleinen Teil der möglichen Optionen.
Das weitere Verständnis von Schach war im Wesentlichen eine Weiterentwicklung der vom ersten Champion aufgestellten Ideen. Konzepte wie Blockade, Prävention, Herrschaft tauchten auf. Schachspieler begannen, die Prinzipien des Spielens typischer Positionen zu studieren, die sich aus verschiedenen Eröffnungen ergaben (geschlossene Ketten, ein isolierter Bauer usw.). Auf die eine oder andere Weise wurden Positionen nahe der Materialbilanz untersucht. Es gab aber auch Ausnahmen - zum Beispiel spielte der junge Mikhail Tal in einem anderen Stil. Er schuf scharfe unausgeglichene Positionen mit einer Verletzung des Materialverhältnisses (später demonstrierte auch Garry Kasparov ein ähnliches Spiel). Die Gegner waren an ein solches Spiel nicht gewöhnt und gingen nacheinander vorbei. Tal wurde 1960 Weltmeister, verlor aber ein Jahr später den Rückkampf. In der zweiten Hälfte des 20. Jahrhunderts verlagerte sich der Forschungsschwerpunkt auf den Beginn des Spiels - die Eröffnung. Mit der leichten Hand von Mikhail Botvinnik (6. Weltmeister) und Garry Kasparov (13.) widmeten die Schachspieler den Löwenanteil ihrer Zeit der Ausarbeitung spezifischer Eröffnungsvarianten. Zunehmend Computer in diesem Prozess verwenden. Infolgedessen werden viele Variationen der populären Eröffnungen bis zu Positionen entwickelt, an denen das Ergebnis des Spiels vorbestimmt ist. Dies führt zu einer gewissen Entmannung des Schachs sowie zu der Notwendigkeit, sich eine Vielzahl von Variationen zu merken, um nicht bereits in der Eröffnung besiegt zu werden. Es überrascht nicht, dass das Pendel in letzter Zeit in die entgegengesetzte Richtung geschwungen ist. Der aktuelle WeltmeisterMagnus Carlsen ist eher bestrebt, am Ende der Eröffnung keinen Vorteil zu erzielen, sondern eine Spielposition, die von Computer-Engines nicht „abgedroschen“ wird. Die Schwere des Kampfes wird auf die späteren Phasen des Spiels (Mittelspiel, Endspiel) übertragen.
"Silikonschach".
Nach dem treffenden Ausdruck von Alexander Kronrod ist Schach die „Fruchtfliege“ der künstlichen Intelligenz. Ihre Studie begann mit dem Aufkommen der ersten Computer und zog Pioniere wie Alan Turing und Claude Shannon an.... Es war Shannon, der die erste Schätzung des Wertes der Schachfiguren "König = 200, Königin = 9, Turm = 5, Bischof = 3, Ritter = 3, Bauer = 1" vorlegte. Seltsamerweise war es diese einfache Einschätzung, die die Entwicklung der Schachprogrammierung für die nächsten 70 Jahre bestimmte. Shannon sagte auch die Aufteilung der Schachprogramme in "schnell" (Brute Force) und "klug" (klug) voraus. "Schnelle" Programme durchlaufen alle möglichen Optionen bis zu einer bestimmten Tiefe vollständig, bewerten die Position mit einer einfachen Bewertungsfunktion (wie dem Materialverhältnis) und wählen den besten Zug nach dem Minimax-Prinzip aus... "Intelligente" Programme verwenden komplexere Algorithmen und variieren die Suchtiefe ähnlich wie ein Mensch. Der 6. Weltmeister Mikhail Botvinnik war in den letzten Jahren seines Lebens an der Entwicklung eines solchen Algorithmus beteiligt. Allerdings ohne großen Erfolg, wie viele andere Entwickler von "intelligenten" Programmen. Denn in seiner dritten Vorhersage war Shannon falsch - "intelligente" Programme scheiterten ständig im Kampf gegen "schnelle". Der Grund ist, dass Brute Force sehr gut parallelisiert und optimiert ist. Und Shannons einfache Schätzung erwies sich als ziemlich stabil und robust. Denn wie Schachspieler wissen, verwandelt sich jeder Positionsvorteil früher oder später in einen materiellen. Während sich die Prinzipien der Positionsbewertung für eine viel schlechtere Formalisierung eignen.
Sie erfordern umständliche sequentielle Berechnungen und sind schlecht optimiert. Infolgedessen begannen mit zunehmender Computerleistung "schnelle" Programme zu dominieren. Auf diese Weise wurde der Mainstream des Computerschachs gebildet, der sich deutlich vom menschlichen Schach unterscheidet - bis zu einer bestimmten Tiefe durch Alpha-Beta-Clipping (und einige andere Heuristiken) und Positionsschätzung nach Shannon. Außerdem begannen die Programme, aktiv (wenn das Spiel noch nicht weit von der Ausgangsposition entfernt ist) und Endspiel (wenn die Anzahl der Teile klein ist und der Variationsbaum vollständig berechnet werden kann) Basen zu entwickeln und zu verwenden. Und die Leistung von Computern wuchs ständig, und die Programmierer saßen auch nicht untätig und optimierten ständig die Motoren. Am 11. Mai 1997 ereignete sich ein MeilensteinDeep Blue Computer besiegte Weltmeister Garry Kasparov in einem 6-Spiele-Match.
Unmittelbar danach hat IBM dieses nie billige Projekt eingestellt. Chips, die Schachberechnungen beschleunigen, wurden speziell für Deep Blue entwickelt ! Aber auch ohne sie war die Überlegenheit eines Computers gegenüber einer Person bereits offensichtlich. Deep Fritz , Deep Junior , Rybka , Komodo und Stockfish begannen, die führenden Großmeister gnadenlos zu zerschlagen und ihnen sogar Material voraus zu geben ... Sie spielten jedoch mit unterschiedlichem Erfolg - die Ergebnisse der Weltmeisterschaften unter den Programmen finden Sie hier .
Alles änderte sich, als die Macher von AlphaZero, nachdem sie den Weltmeister im Spiel gegen Li Sedol besiegt hatten , endlich Schach spielten. Das Ergebnis war phänomenal - nach 4 Stunden mit mir selbst zu spielenAlphaZero besiegte StockFish, indem es 28 Spiele gewann und 72 zog. Nach einem Jahr führte DeepMind ein saubereres Experiment durch , bei dem Stockfish die Eröffnungs- und Endspielbücher verwenden konnte. Das Ergebnis +155 -6 = 839 lässt jedoch keinen Zweifel daran, wer derzeit der stärkste Spieler der Welt ist.
Lassen Sie uns verstehen, wie dieses neue Wunder arrangiert wurde . (Es gibt bereits ein ganzes Buch für diejenigen, die tiefer in Python-Skripte eintauchen möchten ). Der Hauptalgorithmus ist die Monte-Carlo-Baumsuche... Dies ist natürlich ein Overkill, wodurch AlphaZero anderen Schachprogrammen ähnelt. Aber das Wort Monte Carlo sollte nicht irreführend sein - die Suche wird von einem neuronalen Netzwerk gesteuert (für Go war es 80-lagig, ich weiß nicht, welches hier) und ist eng ausgerichtet. AlphaZero schneidet den Brute-Force-Baum aus Positionsgründen ab, genau wie ein Mensch! Im Vergleich zu Stockfish hat Alphazero fast 1000-mal weniger Optionen... Sie schaufelt viel weniger "Müll", berechnet aber die wahrscheinlich stärksten Optionen tiefer und genauer. Daher gewinnt es auch mit weniger Zeit oder auf schwächerer Hardware. Und das Wichtigste ist, dass AlphaZero Schach ausschließlich nach "ihrer eigenen Erfahrung" "studiert" hat. Sie hatte keine a priori Informationen. Ihr "Verständnis" wird durch die "Shannon-Einschätzung" nicht beeinträchtigt. Sie hat ihr eigenes einzigartiges Verständnis der Vision von Schach und des Spielstils, das oft die materielle Balance ignoriert (wie der junge Tal!).
Welche Schlussfolgerungen können wir aus diesem wunderbaren Experiment ziehen?
- Er widerlegt entschieden alle Überlegungen zur Entmannung des Schachs. Das Aussehen eines Spielers, der in einem noch nie dagewesenen Stil spielt und eine völlige Überlegenheit gegenüber Wettbewerbern zeigt, zeigt, dass die Möglichkeiten des Spiels noch lange nicht ausgeschöpft sind.
- . 4 (« ») ! – ( -) . . . AlphaZero () .
- – ? – , , .. , . AlphaZero – – –. ? , , . , . . . . SkyNet wird ein bisschen weniger distanziert und ein bisschen finsterer ... In der Zwischenzeit wäre ich dankbar für Links, Artikel und Ideen, wie man dieses Problem angehen kann.
PS. Aber du wirst die Spiele sehen . Ich habe ein unvergleichliches Vergnügen.