Schach hat eine Antwort – aber niemand kennt sie

Spieltheorie, Teil 2 von 9

Am 24. November spielen Gukesh und Javokhir Sindarov in Cologny bei Genf die erste Partie ihres Weltmeisterschaftskampfs. Beide bereiten sich seit Monaten mit Teams von Sekundanten und den stärksten Schachprogrammen vor. Und doch kennt keiner von ihnen die Antwort auf die einfachste Frage über Schach: Wer gewinnt, wenn beide Seiten perfekt spielen?

Noch seltsamer ist etwas anderes. Mathematiker haben vor über hundert Jahren gezeigt, dass es diese Antwort gibt. Sie steht so fest wie das Ergebnis von 2 + 2. Nur hat sie noch nie jemand gesehen.

Was Zermelo zeigte

Im ersten Teil der Reihe haben wir das Streichholzspiel gelöst, indem wir vom Ende zum Anfang gedacht haben. Der deutsche Mathematiker Ernst Zermelo – heute vor allem für seine Arbeiten zur Mengenlehre bekannt – wandte 1913 in einem Aufsatz eine ähnliche Überlegung auf das Schach an.

Schach ist ein Zwei-Personen-Spiel mit vollkommener Information, ganz ohne Zufall. Die Zahl der Stellungen ist endlich, und die Regeln verhindern, dass eine Partie ewig dauert. Für solche Spiele gilt genau eine von drei Aussagen:

1. Weiß kann den Sieg erzwingen, wie auch immer Schwarz sich verteidigt.
2. Schwarz kann den Sieg erzwingen, wie auch immer Weiß spielt.
3. Jede Seite kann sich mindestens ein Remis sichern.

Das ist „die Antwort des Schachs“. Welche der drei Aussagen stimmt, weiß niemand.

Eine kleine historische Anmerkung. Zermelo stellte eigentlich eine engere Frage als die, die man ihm meist zuschreibt: Kann eine Seite mit Gewinnstellung den Sieg erzwingen, und in wie vielen Zügen? Die vertraute Formulierung mit drei Möglichkeiten und die ausdrücklich formulierte Rückwärtsinduktion kamen später, in Arbeiten der ungarischen Mathematiker Dénes Kőnig (1927) und László Kalmár (1928). Die Spieltheorie-Historiker Ulrich Schwalbe und Paul Walker haben diese Verwechslung ausführlich aufgearbeitet. Der „Satz von Zermelo“ ist also eher das Werk mehrerer Menschen, benannt nach dem ersten von ihnen.

Drei Stufen von „gelöst“

Wenn es heißt, ein Spiel sei „gelöst“, kann Dreierlei gemeint sein:

• ultraschwach gelöst – man weiß, wie das Spiel bei perfektem Spiel endet, aber nicht, wie man das erreicht;
• schwach gelöst – man kennt das Ergebnis und eine Strategie, die es aus der Ausgangsstellung sichert;
• stark gelöst – man kennt den richtigen Zug in jeder Stellung, die entstehen kann.

Das Streichholzspiel aus Teil 1 ist stark gelöst: Wir haben eine Regel für jede beliebige Zahl von Hölzern. So sieht es bei einigen echten Spielen aus:

Achten Sie auf die Formulierung beim Damespiel. Das Ergebnis gilt für eine bestimmte Variante: Einfache Steine ziehen nur vorwärts, die Dame zieht ein Feld in jede diagonale Richtung, und Schlagen ist Pflicht. Für andere Varianten – etwa internationale Dame auf 10×10 oder Varianten, in denen die Dame über mehrere Felder zieht – gilt es nicht.

Dame: achtzehn Jahre Rechenarbeit

Das Team von Jonathan Schaeffer an der University of Alberta in Kanada begann 1989 mit der Berechnung. Auf dem Höhepunkt, 1992, arbeiteten mehr als 200 Prozessoren daran. Allein die Endspieldatenbank – alle Stellungen mit zehn oder weniger Steinen – umfasst rund 39 Billionen Stellungen. Insgesamt hat Dame auf 8×8 etwa 5 × 10²⁰ mögliche Stellungen.

Im September 2007 veröffentlichte die Zeitschrift Science das Ergebnis: Bei perfektem Spiel beider Seiten endet Dame remis. Interessant ist, dass der Beweis nicht jede Stellung prüfen musste. Es genügte zu zeigen, dass keine Seite mit Vorteil von den Remislinien abweichen kann.

Warum sich Schach nicht genauso durchrechnen lässt

1950 schätzte Claude Shannon, der Begründer der Informationstheorie, die Zahl möglicher Schachstellungen auf etwa 10⁴³ und die Zahl möglicher Partien auf etwa 10¹²⁰. Er rechnete aus, dass eine Maschine, die eine Variante pro Mikrosekunde prüft, über 10⁹⁰ Jahre bräuchte, um ihren ersten Zug zu wählen.

Eine neuere Schätzung von John Tromp liegt noch höher: etwa 4,8 × 10⁴⁴ legale Stellungen. Das Damespiel hat im Vergleich etwa 5 × 10²⁰. Schach ist also nicht „doppelt so schwer“ wie Dame – der Unterschied liegt in der Größenordnung einer Billion Billionen.

Mathematiker nennen die Lösung des Schachs nicht unmöglich. Wie beim Damespiel müsste man für den Beweis eines Sieges oder Remis nicht jede Stellung untersuchen. Doch Jonathan Schaeffer, der den Dame-Beweis leitete, sagte selbst, man bräuchte einen technologischen Durchbruch – etwa Quantencomputer –, bevor man sich überhaupt an Schach wagen könne.

Wo die Antwort schon bekannt ist

Es gibt einen Teil des Schachs, in dem die Antwort vollständig gefunden ist: das Endspiel. Computer haben alle Stellungen mit bis zu sieben Steinen auf dem Brett berechnet, Könige eingeschlossen. Diese Tabellen – man nennt sie Tablebases – kennen für jede Stellung das genaue Ergebnis und den kürzesten Weg dorthin. Manche dieser Gewinne dauern über fünfhundert Züge, und kein Mensch könnte ihre Logik erklären.

Schauen wir, was die Tabellen über eine der berühmtesten Studien der Schachgeschichte sagen.

Die Saavedra-Stellung

Weiß: König b6, Bauer c6. Schwarz: König a1, Turm d5. Weiß am Zug.

FEN: 8/8/1KP5/3r4/8/8/8/k7 w - - 0 1

Die Geschichte begann 1895 in der Schachspalte der Zeitung Glasgow Weekly Citizen. Ihr Redakteur Barbier veröffentlichte eine ähnliche Stellung und hielt sie bei richtigem Spiel von Schwarz für remis. Die Lösung, die die Studie berühmt machte, fand ein Leser: Fernando Saavedra, ein spanischer Priester, der in Glasgow lebte.

Was fast alle sehen. Der Bauer steht einen Schritt vor der Umwandlung. Der schwarze Turm gibt Schach, der weiße König flieht davor. Der natürliche Plan: den Schachs entkommen und eine Dame holen.

1.c7 Td6+ 2.Kb5 Td5+ 3.Kb4 Td4+ 4.Kb3 Td3+ 5.Kc2 Td4!

Schwarz kann kein Schach mehr geben, spielt aber listig. Jetzt scheint 6.c8=D mühelos zu gewinnen. Doch nach 6...Tc4+! 7.Dxc4 hat der schwarze König keinen legalen Zug mehr. Das ist Patt – remis. Weiß kann das Schlagen auch nicht ablehnen: Nach jedem Königsrückzug nimmt Schwarz die Dame mit ...Txc8, und plötzlich spielt Schwarz auf Gewinn.

Was übersehen wird. 6.c8=T!! Ein Turm setzt nicht patt, weil er die Diagonale nicht kontrolliert, die der schwarze König braucht. Weiß droht ein Schach von a8, nach dem Schwarz nichts mehr hilft. Die zäheste Verteidigung ist 6...Ta4 (nur 6...Td2+ hält ebenso lange), und dann 7.Kb3! Jetzt droht Weiß zugleich, den Turm auf a4 zu schlagen und mit Tc1 mattzusetzen. Beides kann Schwarz nicht abwehren.

Was die Tabellen hinzufügten. Die Tablebase bestätigt das Wesentliche: 1.c7 ist der einzige gewinnende erste Zug, und 6.c8=D führt wirklich nur zum Remis. Sie zeigt aber auch etwas, das die klassische Analyse nicht sichtbar macht. Im sechsten Zug gewinnt nicht nur 6.c8=T, sondern auch 6.Kb3 und 6.Kc3. Der Weg zum Matt ist dort etwa dreimal so lang und längst nicht so schön. Die Unterverwandlung ist der kürzeste Gewinn, aber nicht der einzige.

Was das für Spielerinnen und Spieler bedeutet

Eine Tablebase denkt nicht in „schönen“ und „schlechten“ Zügen. Sie denkt in drei Kategorien: Gewinn, Remis, Verlust. Jeder Zug, der die Kategorie erhält, ist in gewissem Sinn richtig. 6.Kb3 ist richtig. 6.c8=D ist ein Fehler, obwohl es der natürlichste Zug auf dem Brett ist: Er verwandelt einen Gewinn in ein Remis.

Daraus folgt ein praktisches Prinzip. Vor einem Zug, der offensichtlich wirkt, lohnt sich nicht die Frage „Ist das der beste Zug?“, sondern „Ändert er das Ergebnis?“. Patt, Dauerschach, ein verlorener Bauer – so werden aus Gewinnstellungen Remisstellungen.

Doch das Prinzip hat eine Grenze. Im Mittelspiel weiß niemand, in welcher Kategorie eine Stellung liegt: Tabellen für 32 Steine gibt es nicht, und es wird sie in absehbarer Zeit auch nicht geben. Dort müssen Menschen und Programme die Stellung näherungsweise bewerten und den Zug suchen, der gegen die stärkste Antwort des Gegners am besten ist. Diese Idee – Minimax – ist Thema des nächsten Teils der Reihe.

Und der Wettkampf in Genf ist gerade deshalb spannend, weil Gukesh und Sindarov nicht perfekt spielen. Sie spielen ein Spiel, dessen Antwort niemand kennt.

Übung

1. Finden Sie in der Stellung nach 6.c8=T Ta4 den Gewinnzug für Weiß und erklären Sie, warum er gewinnt.
2. Warum muss Weiß nach 6.c8=D Tc4+ den Turm schlagen, obwohl das Patt ist?
3. Zu welcher Stufe von „gelöst“ gehört Schere, Stein, Papier aus Teil 1? Kann man überhaupt sagen, wer bei perfektem Spiel gewinnt?

Die Antworten stehen am Ende.

Fragen zur Diskussion

• Wenn morgen verkündet würde, dass Schach bei perfektem Spiel remis ist – würde sich für Sie etwas am Spiel ändern?
• Was hilft beim Lernen mehr: den perfekten Zug aus einer Tabelle zu kennen oder zu verstehen, warum ein Zug funktioniert – auch wenn es schnellere gibt?
• Saavedra fand einen Zug, den der Autor der Studie übersehen hatte. Haben Sie schon einmal eine Lösung gesehen, die erfahreneren Leuten entgangen war?

Als Nächstes in der Reihe: „Minimax: Wie ein Gegner denkt, der Ihnen das Schlechteste wünscht“, über den Satz von von Neumann und darüber, wie Schachprogramme „denken“.

Antworten. 1) 7.Kb3! – laut Tablebase der einzige Gewinnzug. Weiß greift den Turm auf a4 an und droht zugleich Matt mit Tc1. 2) Nach jedem Königsrückzug nimmt Schwarz die Dame mit ...Txc8 und behält einen Turm gegen den nackten König. 3) Die Züge erfolgen gleichzeitig, deshalb gibt es keinen einzelnen „richtigen Zug“. Die perfekte Strategie besteht darin, jede Option zufällig mit Wahrscheinlichkeit 1/3 zu wählen. Dann gewinnt im Schnitt niemand, wie auch immer der Gegner spielt. Solchen gemischten Strategien widmet die Reihe einen eigenen Artikel.