Komodo MCTS glänzt mit Alpha-Zero-Techniken
Vor etwas mehr als einem Jahr machte das Schachprogramm Alpha Zero Schlagzeilen, indem es auf sensationelle Weise Stockfish 8 besiegte. In den veröffentlichten Partien beeindruckte die an Anderssen und Morphy erinnernde Spielweise mit Opfern von Bauern und Figuren "auf Position". Viele Schachfreunde würden sich gerne Alpha Zero zulegen, wenn es denn erhältlich wäre und auf herkömmlichen Rechnern betrieben werden könnte. All das ist bekanntlich nicht der Fall. Doch glücklicherweise gibt es mit Komodo MCTS ein für einen erschwinglichen Preis erhältliches Schachprogramm, das ähnliche Techniken wie Alpha Zero einsetzt und auf herkömmlichen Rechnern installiert werden kann. Diese Version macht seit ihrem ersten Erscheinen große Fortschritte, wie nicht zuletzt zwei bemerkenswerte, im Dezember 2018 gespielte Partien zeigen.
Eine taktische Meisterleistung
In der Auftaktrunde der Division 2 des laufenden TCEC 14-Turniers, das von vielen als die eigentliche, wenn auch inoffizielle Schachcomputerweltmeisterschaft angesehen wird, besiegte Komodo MCTS auf spektakuläre Weise Nirvana 2.4. Erst opfert Komodo mit Weiß einen Bauern, dann die Qualität und schließlich auch noch einen Läufer, doch schon nach der Annahme des Bauernopfers steht Schwarz auf verlorenem Posten:
In dieser Partie beeindruckt besonders die unvoreingenommene Herangehensweise, die wohl auch mit der von Komodo MCTS angewandten Monte Carlo-Suchmethode zusammenhängt.
Monte Carlo tree search (MCTS) - was ist das?
Im Gegensatz zur herkömmlichen Alpha-Beta-Suche wird in diesem Verfahren keinerlei Schachwissen vorausgesetzt, abgesehen von den Spielregeln und den möglichen Ausgängen einer Schachpartie: Sieg, Niederlage oder Remis. Grob gesprochen läuft die Sache so ab: In einer gegebenen Stellung werden die möglichen Züge ausprobiert, indem das Programm gegen sich selbst spielt, bis ein Ergebnis erzielt ist: 1, 0 oder 1/2. Wie der Zug aussieht, der das beste Ergebnis erzielt, spielt keine Rolle. Ob der Zug einen Bauern, eine Figur oder die Dame preisgibt, einen Doppel- oder Tripelbauern zulässt, gegen irgendwelche ehernen Spielgrundsätze verstößt, ist ganz und gar unerheblich, solange er erfolgreich ist. Man könnte das eine unvoreingenommene Herangehensweise nennen. Durch eine große Anzahl an zu Ende gespielten Partien werden Rückschlüsse gezogen auf die besten Züge in einer bestimmten Stellung. Mit den erfolgreichsten Fortsetzungen beschäftigt sich das Programm ausführlicher als mit den erfolglosen. So entsteht ein "Suchbaum", der zum Schluss eine Zugwahl zulässt, die rein ergebnisorentiert ist.
Bekanntlich hat Alpha Zero neun Stunden lang gegen sich selbst zahllose Partien gespielt und aus den Ergebnissen gelernt, wofür allerdings gewaltige Rechenkapazitäten bereitgestellt wurden, denn sonst hätten neun Stunden wohl kaum ausgereicht. Anschließend jedoch war Alpha Zero in der Lage, es mit Stockfish 8, einem der besten Schachprogramme der Welt, aufzunehmen. Auf einen Nenner gebracht, bedeutet das: KI (künstliche Intelligenz) lernt durch Ausprobieren rein aus der Erfahrung heraus.
Wirksam = ästhetisch schön?
In diesem Zusammenhang sei an die einst zwischen Weltmeister Dr. Emanuel Lasker und seinem Erzrivalen Dr. Siegbert Tarrasch geführte Diskussion um den "ästhetischen" Wert eines Zuges erinnert. Lasker schrieb dazu vor Beginn seines WM-Kampfes gegen Tarrasch im Jahre 1908 folgendes:
"Dr. Tarrasch ist ein Denker, der tiefe und vielschichtige Überlegungen liebt. Er ist bereit, die Effektivität und Zweckmäßigkeit eines Zuges anzuerkennen, wenn er ihn gleichzeitig als schön und als theoretisch korrekt betrachtet. Aber ich akzeptiere diese Art von Schönheit nur, falls und wenn sie gerade zweckmäßig ist. Er bewundert eine Idee um ihrer Tiefgründigkeit willen, ich bewundere sie wegen ihrer Wirksamkeit. Mein Gegner glaubt an Schönheit, ich an Stärke. Ich finde, daß ein Zug dadurch, daß er kraftvoll ist, auch schön ist." (a)
Daraus wird deutlich, dass Weltmeister Dr. Emanuel Lasker am Schachbrett rein ergebnisorentiert dachte. Ganz genau diesen Ansatz verfolgt auch Komodo MCTS.
Alpha-Beta Suche bald ausgereizt?
In einem im Dezember 2018 veröffentlichten Interview stellte Komodo-Entwickler IGM Larry Kaufman fest, dass Komodo MCTS zehnmal so schnelle Fortschritte mache wie die "normale" Komodo-Version, die bekanntlich auf die bewährte Alpha-Beta-Suche setzt. (b) Stark vereinfacht kann man dazu folgendes feststellen:
Bei der Alpha-Beta-Suche geht es darum, möglichst viele Züge und Varianten von vornherein auszuschließen, weil ihr Ergebnis offenkundig ungünstig ist. Der Alpha-Wert gibt dabei an, wieviel Spieler A mindestens erreichen wird, wenn ein bestimmter Zug gespielt wird. Der Beta-Wert beschreibt hingegen, wieviel in diesem Falle Spieler B durch seinen besten Gegenzug höchstens erreichen wird. Wenn ich also einen Zug prüfe, der einen Springer gewinnt und feststelle, dass der Gegner durch seinen besten Gegenzug höchstens einen Bauern dafür bekommt, so könnte ich dieser Fortsetzung bei sonst gleichen Bedingungen einen Wert von +2.00 zuweisen. Nun sehe ich mir einen anderen Zug in derselben Ausgangsstellung an und stelle fest, dass ich damit zwar einen gegnerischen Turm schlagen kann, mein Gegner bei bestem Gegenspiel aber dafür mindestens meine Dame und drei Bauern bekommt, so dass das Endergebnis bei -7.00 liegt.
Auf diese Weise bekommen alle möglichen Züge in einer Stellung Werte zugewiesen. Diejenigen Züge mit den besten Werten kommen ganz nach oben und werden sofort näher und tiefer untersucht, während diejenigen mit den schlechtesten Werten als letzte drankommen und gewöhnlich auch bei größerer Suchtiefe keine besseren Ergebnisse liefern. Sollte dieser Fall dennoch eintreten, so findet unverzüglich eine Neubewertung statt, und ein bisher beispielsweise mit -2.55 bewerteter Zug rückt plötzlich mit einem Pluswert an die erste, zweite oder dritte Stelle. Die Stellungen werden im Gegensatz zum Monte Carlo-Verfahren jedoch nicht ausgespielt (es sei denn, dass ein Matt gefunden wird), sondern bis zu einer mit der Zeit immer größer werdenden Suchtiefe weiterverfolgt und die entstehenden Stellungen nach vorher genau festgesetzten Gesichtspunkten bewertet. Hierbei spielt nicht nur der Wert der Figuren und Bauern eine Rolle, sondern auch positionelle Faktoren wie z. B. Königssicherheit, Bauernschwächen, offene Linien, Raumvorteil, Zentrumsbeherrschung usw.
Dieses geniale Verfahren wurde in den letzten Jahren immer mehr verfeinert und hat sich als außerordentlich erfolgreich erwiesen. Dennoch könnte es sein, dass der Spielraum für Spielstärkesteigerungen irgendwann ausgeschöpft ist. Zu denken gibt, dass die neueste Stockfish-Version 10, in welche die Programmierer und ihre zahllosen freiwilligen Tester etwa zehn Monate Entwicklungsarbeit investierten, um gerade mal 15 ELO-Punkte im Vergleich zu ihrer Vorgängerversion Stockfish 9 zulegen konnte (64-bit, 1CPU, laut CCRL-ELO-Liste 40/40 vom 12. Januar 2019). (c)
Vergleichen wir damit die drei Vorgängerversionen: Stockfish 7 erschien am 2. Januar 2016 und hat eine ELO-Zahl von 3246. Stockfish 8 vom 1./2. November 2016, also nur 10 Monate später, machte einen Sprung auf 3301 ELO, steigerte sich also um 55 ELO-Punkte. Das entspricht einem Zuwachs von 5,5 ELO je Entwicklungsmonat. Stockfish 9 vom 30. /31. Januar 2018 kam etwa 15 Monate später heraus und bringt mit 3367 ELO 66 mehr als die Vorgängerversion auf die Waage, was 4,4 ELO Steigerung je Entwicklungsmonat bedeutet. Nun gingen 10 Monate ins Land, bevor die neueste Version Stockfish 10 fertig war. Diese erschien am 30. November 2018 und bringt 3382 ELO auf die Waage, also nur noch 15 ELO-Punkte mehr als Stockfish 9. Daran sieht man, dass die Kurve mit nur noch 1,5 ELO Zuwachs je Entwicklungsmonat plötzlich stark abflacht.
Diese Beobachtungen könnten darauf hindeuten, dass das Entwicklungspotential bei den Schachprogrammen mit den herkömmlichen Alpha-Beta-Suchmustern tatsächlich bereits weitgehend ausgeschöpft ist. Aber natürlich sollte man nicht vorschnell urteilen. Warten wir daher Stockfish 11 ab, erst dann wissen wir mehr, ob dieser Trend sich verfestigt oder nicht. Jedenfalls wird aus dem oben Gesagten deutlich, warum die Komodo-Entwickler Larry Kaufman und Mark Lefler die größten Fortschritte ihrer MCTS-Version zutrauen. Im laufenden TCEC-Wettbewerb (TCEC 14) konnte sich Komodo MCTS bereits sensationell bis in die „Premier League“, und damit in die Klasse der besten 8 Schachprogramme vorarbeiten.
Komodos positionelles Meisterstück
Dass das neuartige Programm mit der Monte Carlo-Suchtechnik bereits jetzt in einzelnen Partien einen Giganten wie Stockfish 10 besiegen kann, ist bemerkenswert. Die folgende Partie wurde am 21. Dezember 2018 mit einer Bedenkzeit von 40 Minuten je 40 Züge ausgetragen. Beide Programme liefen dabei auf je vier Prozessoren. Durch ein überraschendes Bauernopfer gelingt es Komodo MCTS, seinen formidablen Gegner positionell an die Wand zu spielen. Bemerkenswert ist, dass nach dem 26. Zuge von Weiß alle drei auf dem Brett vorhandenen Springer auf Randfeldern stehen:
Komodo MCTS gibt es zusammen mit der herkömmlichen Komodo-Version für 89,90 Euro im ChessBase Shop. Der Vorteil dabei besteht darin, dass der Anwender von der Monte Carlo-Methode Gebrauch machen kann, ohne dafür auf die bewährte Alpha-Beta-Methode verzichten zu müssen. Die abwechselnde Verwendung der beiden Suchtechniken ermöglicht tiefere Einblicke in komplizierte Stellungen, was sowohl beim Analysieren von Partien, als auch bei der Vorbereitung von Eröffnungsvarianten mit Hilfe des Computers nützlich sein kann.
Komodo 12
Komodo gibt Gas! Die neue Version des mehrfachen Weltmeisterprogramms spielt nicht nur stärker als jemals zuvor. Mit ihrer neuen "Monte-Carlo" Version - basierend auf KI-Techniken - spielt sie auch deutlich aggressiver.
Mehr...
Quellen:
(a) Zitiert nach Harold C. Schonberg, "Die Großmeister des Schach", S. 119
(b) http://www.chessdom.com/komodo-mcts-monte-carlo-tree-search-is-the-new-star-of-tcec/
(c) http://computerchess.org.uk/ccrl/4040/cgi/compare_engines.cgi?class=Single-CPU+engines&print=Rating+list&print=Results+table&print=LOS+table&table_size=12&cross_tables_for_best_versions_only=1
