Spis treści:
- 1 Die Schönheit des Schachs
- 2 Schwierigkeitsgrad des Spiels? Schach ist wirklich für alle da
- 3 Computerschach
- 4 Stockfish-Programm und Elo-Schach-Ranking
- 5 Schach lösen, oder chess solving, und ob es überhaupt möglich ist
- 6 Der Schachalgorithmus - wie funktioniert er?
- 7 Supercomputer und Schach
- 8 Schach und künstliche Intelligenz, oder Deep Learning
- 9 Kann der Mensch mit dem Computer mithalten?
Philadelphia, USA, Pennsylvania, 1997: Die Welt sieht ungläubig zu, wie Großmeister Garry Kasparov, der wohl beste Schachspieler der Geschichte, nach seinen ersten Siegen eine Partie gegen den IBM Deep Blue Computer verliert. Die Ära der Schach-Engines beginnt und verändert das Bild dieses großartigen Spiels für immer.
Um mit einer Unterscheidung zu beginnen: Weisheit ist schwer zu definieren. Sie wird gemeinhin als die Fähigkeit angesehen, auf der Grundlage von Wissen und Erfahrung vernünftige Lebensentscheidungen zu treffen. Mit der Intelligenz ist es keineswegs einfacher – für viele ist “intelligent sein” eine hohle Phrase, andere suchen eine sichere Definition in der Unterscheidung zwischen verschiedenen Arten von Intelligenz. Wenn wir uns heute mit Intelligenz beschäftigen, dann auf jeden Fall in mathematischer und logischer Hinsicht. Auf solchen Fähigkeiten basiert das ultimative Schachspiel. Ein Spiel übrigens, mit dem viele Programmierer vertraut sind.
Jason Statham, Zitat aus dem fiktiven Buch "Fundamentals of Chess 1883", Ausschnitt aus dem Film Revolver (2005)
Minimax (manchmal auch minmax), die Methode der Minimierung des maximal möglichen Verlustes oder alternativ der Maximierung des minimal möglichen Gewinns (Maximin), ist einer der Eckpfeiler der Vorhersage im Schach und der Ausgangspunkt für die Konstruktion immer besserer Spieleralgorithmen. Sie leitet sich aus der Theorie des Nullsummenspiels ab und umfasst zwei “Organisationen” von Zügen: sowohl diejenige, bei der die Spieler abwechselnd Züge ausführen, als auch diejenige, bei der die Züge gleichzeitig ausgeführt werden. Heute wollen wir uns ansehen, wie Menschen im Vergleich zu Computern mit der Entscheidungsfindung angesichts von Unsicherheit umgehen. Wie viel “Intelligenz” haben wir als ihre Schöpfer ihnen bisher vermitteln können?
Die Schönheit des Schachs
Die ganze Welt hat von Schach gehört. Es ist wie Coca-Cola. Nach Angaben des Portals chess.com im Jahr 2020 spielen mehr als 600 Millionen Erwachsene regelmäßig Schach. Eine Zahl, die mit der von regulären Facebook-Nutzern vergleichbar ist. Laut The Encyclopedia of Chess Variants (2007) gibt es mehr als 2.000 Varianten des Spiels. Wir haben einmal gehört, dass sich Spiele wie Schach, Poker oder Bridge in einem wichtigen Punkt von modernen Brettspielen, Kartenspielen oder Battle Royale unterscheiden – letztere sind keine Spiele, die man die nächsten 50 Jahre seines Lebens spielen wird. Da ist etwas dran.
Schach ist ein Brettspiel, das in der Freizeit und im Wettkampf zwischen zwei Spielern gespielt wird. Es wird manchmal auch als westliches oder internationales Schach bezeichnet, um es von verwandten Spielen wie Xiangqi zu unterscheiden. Die heute gespielte Form des Schachspiels entstand in Südeuropa in der zweiten Hälfte des 15. Jahrhunderts, nachdem es sich aus ähnlichen, viel älteren Spielen indischen und persischen Ursprungs entwickelt hatte. Heute ist Schach eines der beliebtesten Spiele der Welt, das von Millionen von Menschen gespielt wird – zu Hause, in Vereinen, online, im Fernstudium und bei Turnieren.
Es handelt sich in erster Linie um ein abstraktes Strategiespiel ohne versteckte Informationen. Es gibt kein Rätselelement, kein Glücks- oder Pechelement, d.h. keinen Zufall – nur reines logisches Denkvermögen. Zu Beginn kontrolliert jeder Spieler, d. h. einer die weißen und der andere die schwarzen Figuren, sechzehn Schachfiguren. Es sind Lauffiguren und Bauern: ein König, eine Dame, zwei Türme, zwei Läufer Zwei Springer und acht Bauern. Es gibt auch eine schöne Botschaft: Ein Bauer, der über das gesamte Schachbrett marschiert und die letzte Linie erreicht, wird zur Königin oder zu einer Figur nach Wahl des Spielers.
Ziel des Spiels ist es, den gegnerischen König Schach und folglich Schachmatt zu setzen. Schachmatt ist eine Situation, in der der König sofort angegriffen wird (der König steht im Schach) und es gibt keine Möglichkeit, ihn im nächsten Zug vom angegriffenen Feld zu entfernen. Es gibt auch mehrere Möglichkeiten, das Spiel mit einem Unentschieden zu beenden. Diese kühl berechenbaren Eigenschaften machen das Schachspiel zu einem idealen Testfeld für die Algorithmik.
Schwierigkeitsgrad des Spiels? Schach ist wirklich für alle da
Vielleicht sollten wir eher sagen: die Komplexität des Spiels. Es kann schwierig sein, einen Gegner zu besiegen, denn die Schachregeln sind gar nicht so schwer zu begreifen. Es besteht jedoch ein erheblicher Unterschied zwischen der Kenntnis der Schachregeln und des einfach guten Schachspiels. So wie ein Texas-Hold’em-Pokerspieler bei einem Spiel mit einem zufälligen und strategischen Element die Wahrscheinlichkeit berechnet, ob eine fehlende Karte auf dem Tisch erscheint, kann ein Schachspieler nicht alle möglichen Varianten einer Schachpartie von Anfang bis Ende berücksichtigen. Aber er sollte es versuchen.
Im Folgenden finden Sie eine mögliche Anzahl von Fortsetzungsbewegungen, die uns eine Vorstellung von den Dimensionen geben, mit denen wir es hier zu tun haben:
♞♞♞ nach 3 Zügen (der letzte Zug von Weiß)
♞♞♞♞ nach 4 Zügen (der letzte Zug von Schwarz)
♞♞♞♞♞ nach 5 Zügen (der letzte Zug von Weiß)
♞♞♞♞♞♞ nach 6 Zügen (der letzte Zug von Schwarz)
♞♞♞♞♞♞♞ nach 7 Zügen (der letzte Zug von Weiß)
♞♞♞♞♞♞♞♞ nach 8 Zügen (der letzte Zug von Schwarz)
8902
197 281
4 865 609
119 060 324
3 195 901 860
84 998 978 956
Das bereitet um Kopfzerbrechen, nicht wahr? Nachdem jeder Spieler 5 Züge gemacht hat, gibt es 69.352.859.712.417 Spielmöglichkeiten, die gespielt werden könnten. Legt man die Berechnungen des amerikanischen Mathematikers Claude Shannon zugrunde und analysiert das Schachspiel im Hinblick auf die Anzahl der “vernünftigen” Partien, die gespielt werden können (ohne lächerliche, eindeutig spielverlierende Züge wie den Zug der Dame, die ohne Kompensation für einen Bauern geschlagen wird), so kommt man zu einem Ergebnis von ungefähr. 10^40 Parteien. Diese Schätzung basiert auf der Möglichkeit, etwa drei sinnvolle Züge zu wählen, und auf einer Spiellänge von 80 Zügen. Nun, mehr als 1.000 Spiele und Milliarden von Dollar aus der obigen Liste – den Rest der Berechnung überlassen wir Ihnen.
Computerschach
Computerschach umfasst sowohl die Hardware, d. h. die speziellen Computer, die dafür entwickelt wurden, als auch die Schachbots – die Software, die das Spiel möglich macht. Computerschach gibt Spielern die Möglichkeit, auch ohne menschliche Gegner zu üben, und bietet Analyse, Unterhaltung und Training. Es hat auch etwas Beruhigendes, gegen einen Computer zu spielen – manche Leute bevorzugen dies, als gegen einen menschlichen Gegner zu spielen, vor dem man sich lächerlich machen kann. Natürlich sollte dies niemanden zurückhalten, aber es sollte Anfängern auch keinen “Vorsprung” verschaffen. – Der Computer schenkt ihn schließlich niemandem.
Die ersten Maschinen der 1950er Jahre aus der Ära der Röhrencomputer spielten so schlecht, dass sie selbst von Anfängern geschlagen werden konnten, und die Schach-Engines der zweiten Hälfte der 1990er Jahre sind heute wirklich spezialisierte Geräte, wie Kasparows Partie gegen den IBM Deep Blue beweist, die in der Überschrift des Artikels zitiert wird. Computerschachanwendungen, die auf dem Niveau eines Schachmeisters oder höher spielen, sind auf Hardware verfügbar, die von Supercomputern bis zu Smartphones reicht. Es sind auch eigenständige Schachmaschinen erhältlich. Stockfish, GNU Chess, Fruit und andere freie Open-Source-Anwendungen sind für verschiedene Plattformen verfügbar. Schauen wir uns unseren Favoriten an – Stockfish.
Stockfish-Programm und Elo-Schach-Ranking
Stockfish ist eine freie, quelloffene Schach-Engine, die für verschiedene Desktop- und Mobilplattformen verfügbar ist. Neben den Vätern trägt auch eine große Gemeinschaft von Open-Source-Entwicklern zu den Fähigkeiten der Engine bei. Stockfish bleibt an der Spitze der meisten Ranglisten ähnlicher Software. Sie wird einhellig als die stärkste CPU-Schach-Engine angesehen. Stockfish gewann die inoffizielle Weltmeisterschaft im Computerschach in den Saisons 6 (2014), 9 (2016), 11 (2018), 12 (2018), 13 (2018), 14 (2019), 16 (2019), 18 (2020), 19 (2020) und 20 (2021) und wurde in den anderen Saisons jeweils Vizeweltmeister.
Stockfish kann bis zu 512 CPU-Threads auf Multiprozessorsystemen verwenden, implementiert eine erweiterte Alpha-Beta-Suche und verwendet Bit-Arrays. Im Vergleich zu anderen Suchmaschinen bietet sie eine noch bessere Suchtiefe, was teilweise auf eine aggressivere Spielweise zurückzuführen ist. Interessante Tatsache: Sie unterstützt auch eine stark randomisierte Variante von Chess960.
Ist Stockfish wirklich so gut? Sehen wir es einmal so: Zunächst brauchen wir eine Elo-Rangliste. Am Anfang wird ein Neuling wird nicht gewertet. Der Elo-Rang eines Spielers wird durch eine Zahl dargestellt, die sich je nach Ausgang der bewerteten Spiele ändern kann. Nach jedem Spiel nimmt der Gewinner dem Verlierer Punkte ab. Die Differenz zwischen der Bewertung des Gewinners und der des Verlierers bestimmt die Gesamtzahl der gewonnenen oder verlorenen Punkte nach dem Spiel. Wenn der Spieler mit der höheren Wertung gewinnt, werden dem Spieler mit der niedrigeren Wertung nur einige Punkte abgezogen.
Wenn der niedriger eingestufte Spieler gewinnt, wird eine Anzahl von Wertungspunkten übertragen.. Bei einem Unentschieden erhält der niedriger eingestufte Spieler auch einige Punkte vom höher eingestuften Spieler. Das bedeutet, dass dieses Bewertungssystem selbstkorrigierend ist. Spieler, deren Bewertung zu niedrig oder zu hoch ist, sollten langfristig besser oder schlechter abschneiden, als das Bewertungssystem vorhersagt, und somit Bewertungspunkte gewinnen oder verlieren, bis diese ihre wahre Stärke im Spiel widerspiegeln. Und so weiter und so fort. Die Rangliste hat viele Änderungen durchlaufen und ist nur eine vergleichende Klassifizierung für die Gruppe, in der sie erstellt wurde, aber sie ist immer noch die beste, offizielle und weit verbreitete Methode zur Bewertung von Schachspielern.
Werfen wir nun einen Blick auf die Zusammenfassung der ersten acht Plätze, die vom Internationalen Schachverband FIDE gegeben wird.
Die besten Spieler der Standardvariante laut FIDE, Stand April 2021
- Magnus Carlsen, Norwegen – Elo 2847
- Fabiano Caruana, USA – Elo 2820
- Liren Ding, China – Elo 2791
- Ian Nepomniachtchi, Russland – Elo 2789
- Levon Aronian, Armenien – Elo 2781
- Alexander Grischuk, Russland – Elo 2777
- Anish Giri, Niederlande – Elo 2776
- Shakhriyar Mamedyarov, Aserbaidschan – Elo 2770
Garri Kasparov prophezeite Carlsen, dass er die Zahl 2900 erreichen könne, wenn dieser nur “ernsthaft zu arbeiten” beginne. Nun, da wir wissen, wie die Elo-Rangliste aus dem vorherigen Absatz eingestuft wurde…. Stockfish steht auf Platz 3516, mehrere hundert Punkte höher als der derzeitige Weltgroßmeister und wohl der beste Spieler aller Zeiten.
Andere Spitzenschachprogramme, die in den letzten Jahren ihre Rechenkapazität erheblich ausgebaut haben, sind:
- Komodo (Elo +3400)
- Houdini 6 (Elo +3400)
- Fire 7.1 (Elo +3300)
- Deep Shredder (Elo +3200)
Heutzutage verbringen viele professionelle Schachspieler viel Zeit mit der Arbeit am Computer. Es ist anerkannt, dass jeder aufstrebende Spieler versuchen sollte, mit einer starken Schach-Engine zu spielen, und sei es nur aus dem Grund, dass sie es ermöglicht, die Partie aus jeder beliebigen Stellung zu beginnen, die besten Zugmöglichkeiten praktisch unbegrenzt zu lernen (das Leben ist zu kurz dafür) und eine Stagnation zu verhindern, wenn man nicht viele Spielpartner hat. Auf der anderen Seite können Faulheit und Missbrauch solcher Werkzeuge zum selben Ergebnis führen. Wenn man dem allgemeinen Feedback aus der Community Glauben schenken darf, gibt es eine wachsende Zahl von Amateurschachspielern, die nicht eigenständig über eine bestimmte Schachstellung nachdenken, sondern in erster Linie auf die Meinung der Maschine hören. Ist das bei Programmierern nicht eine ähnlich verhängnisvolle Angewohnheit?
Schach lösen, oder chess solving, und ob es überhaupt möglich ist
Überlegen wir einmal: Da es viele Spiele gibt, die lösbar sind und gelöst wurden, gibt es dann eine mathematische Lösung für Schach? Nun, mathematisch ist das durchaus möglich. Ein Beispiel für ein gelöstes Spiel ist Tic-Tac-Toe, bei dem es eine bewährte Methode gibt, zu gewinnen, wenn man zuerst spielt, oder jedes Mal unentschieden zu spielen, unabhängig davon, ob man als Erster oder Zweiter spielt.
Wäre es mit der gleichen Logik möglich, beim Schach eine bestimmte Zugfolge zu machen, die einen Sieg oder ein Unentschieden garantiert? Obwohl Schach weitaus komplizierter ist, als mit einem Stock Kreise und Kreuze auf einer Sandstraße zu setzen, und die Zahl der möglichen Spiele und Ergebnisse geradezu unfassbar groß ist, ist es dennoch ein endliches Spiel. Interessanterweise führen bei den FIDE-Weltmeisterschaften im Schachlösen seit 2009 Teams aus Polen die Mannschaftswertung an.
Die Teilnehmer müssen innerhalb einer bestimmten Zeit eine Reihe verschiedener Schachaufgaben lösen. Für richtige Lösungen in möglichst kurzer Zeit werden Punkte vergeben. Bringt es uns einer vollständigen Schachlösung näher – wahrscheinlich nicht, aber es ist eine ausgezeichnete Übung.
Der Schachalgorithmus - wie funktioniert er?
Warum sind diese Programme so clever? Oder, wie Sie es vorziehen: intelligent? Oder schließlich: Warum sind sie so tolle Buchhalter? Computerschachanwendungen, unabhängig davon, wie sie implementiert sind, verwenden ein anderes Zugauswahlparadigma als Menschen. Sie verwenden heuronistische Verfahren, um Baumstrukturen zu erstellen, zu suchen und zu bewerten, die Zugfolgen von der aktuellen Position aus darstellen, und versuchen, während des Spiels die beste Option zu wählen. Ist es möglich, die eine, die beste Option zu wählen, unabhängig davon, wie der Gegner wahrscheinlich reagieren wird? Es scheint so – eine der täglichen Übungen für Schachspieler, die in der beliebten kostenlosen Lichess-App angeboten werden, ist die Aufgabe, den besten Zug aus einer vordefinierten Stellung der Figuren zu wählen. Solche Entscheidungsbäume sind sehr groß. Sie reichen von Tausenden bis zu Millionen von Knotenpunkten.
Die Rechengeschwindigkeit heutiger Computer, die in der Lage sind, Zehntausende bis Hunderttausende von Knoten oder mehr pro Sekunde zu verarbeiten, kombiniert mit Expansions- und Reduktionsheuristiken, die den Baum auf die relevantesten Knoten eingrenzen, macht diesen Ansatz…. sehr effektiv, um selbst die besten Schachspieler zu überfordern.
Supercomputer und Schach
Mitte letzten Jahres stellte das japanische Unternehmen Fujitsu den Fugaku vor – den schnellsten Supercomputer der Welt für Forschungszwecke. Seine Leistung liegt bei bis zu 415,5 Petaflops (PFLOPS). Das Betriebssystem verwendet sowohl Linux als auch den leichtgewichtigen McKernel-Kern. In der ersten Version im Juni 2020 wurden 158.976 A64FX-Knoten für den Betrieb verwendet, wobei diese Zahl im Laufe der Zeit weiter erhöht wurde. Es wäre sicherlich äußerst faszinierend, Fugaku für Schachsimulationen zu verwenden. Deep Blue, der Kasparov 1996 und auch in späteren Jahren schlug, erreichte 11,38 Gigaflops (GFLOPS). Ein Gigaflop ist gleich 10^9 FLOPS oder 1 Milliarde FLOPS. Tatsächlich war Deep Blue in weniger als 30 Jahren etwa 81.666 Mal leistungsfähiger als der Apollo 11 AGC, der NASA-Computer, der 1969 die Apollo 11-Mondlandung unterstützte.
Die Entwicklungen im Bereich der Halbleitertechnologien führen dazu, dass die Rechenleistung aufeinanderfolgender Computergenerationen exponentiell zunimmt. Im Jahr 2020, 23 Jahre nach Deep Blue und 51 Jahre nach der Landung von Apollo 11, wird die Geschichte das iPhone-Smartphone für dieses Rennen melden. Am 13. Oktober 2020 veröffentlichte Apple Inc. seine neueste iPhone-Reihe, das iPhone 12. Nach Angaben des Unternehmens ist die neue Neural Engine in der Lage, 11 Billionen Rechenoperationen pro Sekunde (TFLOPS) durchzuführen. Damit ist er 967 Mal effizienter als Deep Blue und mehr als 890 Millionen Mal effizienter als der Apollo 11 AGC.
Schach und künstliche Intelligenz, oder Deep Learning
Deep Learning-Technologien für künstliche Intelligenz haben Schachspielern nicht weniger zu bieten. Da Schach ein endliches Spiel ist – kehren wir zu dieser These zurück – das bedeutet, dass wir das Schachspiel lösen könnten, wenn wir genügend Rechenleistung hätten. Jede Schachstellung ist entweder ein Sieg für Weiß, ein Sieg für Schwarz oder ein erzwungenes Unentschieden für beide Spieler. Dies kann durch eine Funktion mit rekursiven Regeln dargestellt werden.
Jede künstliche Schachintelligenz beginnt mit einer Funktion, die mit der Suche nach Positionen im Spielbaum verbunden ist. Alle Schach-KIs konzentrieren sich auf intelligente Suchalgorithmen, aber da die Anzahl der Positionen im Suchbaum exponentiell ansteigt, ist es in der Praxis unmöglich, tiefer als, sagen wir, 5-10 Positionen bis zu einem Dutzend Positionen vorauszugehen.
Kann der Mensch mit dem Computer mithalten?
Und inwieweit ist ein solcher Komparativismus überhaupt sinnvoll? Es ist schwierig, eine solche Frage mit der Wahrnehmung und Vorstellungskraft eines Durchschnittsmenschen zu beantworten. Auch das größte Genie kann sich nicht alles vorstellen – und auch nicht das Nichts, denn ein Vakuum ist bereits etwas. Und Größenordnungen im Schachspiel sind vor allem eine Frage der Berechnungsfähigkeiten unseres Gehirns. Vielleicht sollte man diese Probleme der Philosophie und ihren Zweigen wie der Ontologie überlassen.
Es macht immer Spaß, auf die Geschichte zurückzublicken und zu sehen, wie weit wir in der Computerwelt gekommen sind. Wir werden erleben, wie die Technologie, die auf dem Mond gelandet ist, zu der Technologie wird, die in Zukunft auf dem Mars und darüber hinaus landen wird. Außerdem sind die GSM-Technologien, die es uns ermöglichen, mit Freunden und Familie in Kontakt zu bleiben, weitaus leistungsfähiger, als man gemeinhin annimmt. Wir haben buchstäblich persönliche Supercomputer in unseren Taschen.
Wie geht es weiter mit dem Schachspiel, das im Altertum aus dem fernen Indien zu uns kam? Es gibt immer noch keine Technologie oder Rechenleistung, die die Komplexität und Schönheit dieses erstaunlichen alten Spiels in einen geschlossenen Pool von Aktivitäten einkapseln und in vorstellbaren Zahlen beschreiben kann. Großmeister Magnus Carlsen driftet auf die Laufstege der Welt ab, Kasparow ist nicht mehr dabei.
Allerdings scheint das Schach während der Pandemie und dank der Popularität der Queen’s Gambit-Serie eine weitere Renaissance vor sich zu haben. Außerdem: Sind strategische Planungsfähigkeiten jemals aus der Mode gekommen?
