Monte Carlo statt Alpha-Beta?

von Stephan Oliver Platz
16.01.2019 – Bisher arbeiteten Schachprogramme zumeist nach der so genannten Alpha-Beta-Methode. Das spektakuläre Google Projekt Alpha Zero basiert indes auf dem "Monte Carlo"-Ansatz. Auch die Komodo-Entwickler setzen jetzt mehr und mehr auf diese Methode - mit Erfolg. Stephan Oliver Platz erklärt den Unterschied und zeigt die Fortschritte.

ChessBase 15 - Megapaket ChessBase 15 - Megapaket

Kombinieren Sie richtig! ChessBase 15 Programm + neue Mega Database 2019 mit 7,4 Mio. Partien und über 70.000 Meisteranalysen. Dazu ChessBase Magazin (DVD + Heft) und CB Premium Mitgliedschaft für ein Jahr!

Mehr...

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

 




Stephan Oliver Platz (Jahrgang 1963) ist ein leidenschaftlicher Sammler von Schachbüchern und spielt seit Jahrzehnten erfolgreich in der mittelfränkischen Bezirksliga. Der ehemalige Musiker und Kabarettist arbeitet als freier Journalist und Autor in Hilpoltstein und Berlin.
Discussion and Feedback Join the public discussion or submit your feedback to the editors


Diskutieren

Regeln für Leserkommentare

 
 

Noch kein Benutzer? Registrieren

gerreg gerreg 18.01.2019 11:22
Hier zu Ergänzung das Ergebnis der gerade beendeten 14. TCEC Premier Division:
1. Stockfish 181224 29 Punkte
2. LCZero v20rc2 24
3. Komodo 2227.00 24
4. Houdini 6.03 23,5
5. Fire 7.1 17,5
6. KomodoMCTS 2227 17,5
7. Andsacs 095 16,5
8. Ethereal 11.14 16

Im Finale stehen damit Stockfish und LCZero.

LCZero ist ein bemerkenswertes, erst ein Jahr altes, OpenSource-Projekt eines Stockfish-Entwicklers. Hier wird ebenfalls MCTS eingesetzt. Mit großem Erfolg, wie man sieht.
DoktorM DoktorM 17.01.2019 09:24
MCTS kann Vorteile haben, aber nur, wenn man sich auf wenige Züge konzentrieren kann und es keine Zugfolge gibt, die außerhalb der betrachteten Züge zum Nachteil führt. Müssen viele Züge betrachtet werden, so kann eine Methode Vorteile haben, der mehr Schachwissen besitzt als MCTS. Aber auch dann wird man immer Beispiele finden, die mal die eine oder die andere Methode bevorteilen. Es gewinnt dann der, der weniger im Nebel herumstochert. Ein Vorteil hat die MCTS: Es wird jedem klar, dass man keine wundersame KI benötigt, um sehr gut ein Spiel zu spielen. Daher sind Spiele auch kein gutes Beispiel für die Leistungsfähigkeit von KI. Es gibt weitaus interessantere Probleme (automatische Beweiser, ...), bei der die KI-Forschung nicht einmal ansatzweise irgendetwas schafft, das man als Intelligenz bezeichnen könnte. Die KI verspricht viel und hält vergleichsweise wenig.
gerreg gerreg 17.01.2019 01:56
@GlockiGlockson: Die Werbung steht doch sogar explizit im Beitrag und wird implizit durch die Wahl der Adjektive verstärkt. Schaut man sich z.B. die Berichterstattung über die Top Chess Engine Championships (TCEC) an, erkennt man ein klares Muster: Schneiden in der Hauptrunde Komodo oder Houdini gut ab, wird ausführlich berichtet. Auch wenn sie hinter z.B. Stockfish landen. Das wird dann relativiert und der direkte Vergleich hinzugezogen. Im Sinne von: Gegen Stockfish gab es keine Niederlage o.ä. Über das Superfinale (die zwei stärksten Programme der Hauptrunde spielen gegeneinander ein ganz langes Match) gab es in der Vergangenheit dann keinen ausführlichen Bericht mehr, manchmal noch nicht einmal eine Meldung. Das wundert mich nicht, denn die über chessbase vertriebenen Programme verloren mehr als deutlich gegen Stockfish. *g*

Ich möchte nicht falsch verstanden werden: Ich habe nichts gegen Werbung. Sie sollte nur als solche klar gekennzeichnet werden. Sonst hat das Ganze, wohl nicht nur bei mir, ein "Geschmäckle".

Chessbase bietet m.E. auch im Mittel hervorragende Artikel, es ist eine tolle Seite. Da fallen solche "Tricks" halt besonders negativ auf.
GlockiGlocksen GlockiGlocksen 17.01.2019 12:46
Ich finde den Artikel sehr interessant und gut geschrieben. Schachfreund gerreg erscheint mir mit seinem Urteil viel zu streng. Wo soll das bitte ein Werbeartikel sein...
gerreg gerreg 17.01.2019 07:02
Mit Artikeln wie diesen sorgt Chessbase dafür, an Glaubwürdigkeit zu verlieren. Es ist ein reiner Werbeartikel, vermeintlich subtil hinter einer aktuellen Fragestellung der Schachwelt versteckt. Inhaltlich ist der Artikel schwach, sogar teilweise falsch. Nur einige Beispiele:

Im Abschnitt "Eine taktische Meisterleistung" steht "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..." Natürlich eine schöne Partie, nur findet meine alte Stockfish Version auch sämtliche Gewinnzüge, auch h4. Was soll die Partie dann? Komodo MCTS findet auch Züge, die jedes andere "normale" Schachprogramm auch findet?

Der Monte Carlo Tree Search wird ungenau erklärt. Der entscheidende Aspekt fehlt: Der Zufall! Die Monte Carlo Methode stammt aus der Stochastik. Von einer Stellung aus werden nicht, wie der Autor schreibt, alle möglichen Züge ausprobiert , sondern es werden legale Züge per Zufall ermittelt. Dabei können u.U. relevante nicht gewählt werden. Auch, wenn viele Male ein Zug "ausgelost" wird.

Der Abschnitt "Alpha-Beta Suche bald ausgereizt?" ist absurd! Man kann die Qualität einer Methodik nicht an relativen(!) ELO-Zahl-Entwicklungen ablesen. Nach dieser Logik wäre ein Algorithmus eines Schachprogramms, welches einen Sprung von ELO 1500 auf ELO 1800 gemacht hat, "besser" als der eines anderen Programms, was von ELO 3400 auf ELO 3405 kletterte.

Mit solchen Artikeln tut sich Chessbase m.E. keinen Gefallen. Niveauvoller Schachjournalismus sieht anders aus, ganz anders!
schablonenhaft schablonenhaft 16.01.2019 12:45
Mir scheint der Autor wirft Montecarlo und Neuronale Netze durcheinander. Es ist richtig, dass Montecarlo kein Vorwissen benötigt, ein neuronales Netz aber 9 Stunden bei Google oder Jahre auf einem normalen PC. Ich warte auf den Zeitpunkt, dass Montecarlo Stockfish schlägt...
1