Shannon-Zahl: Wie viele Schachpartien sind möglich?

Die Shannon-Zahl wird häufig angeführt, um den Reichtum des Schachspiels zu veranschaulichen. Sie eignet sich außerdem hervorragend, um Zehnerpotenzen, wissenschaftliche Schreibweise und Größenordnungen zu üben, von der Sekundarstufe I bis zur Oberstufe. Man sollte aber wissen, woher sie stammt, was sie genau misst und was nicht.

Shannon-Zahl

Vorsichtige Schätzung, etwa 10¹²⁰, der möglichen Schachpartien, vorgeschlagen vom amerikanischen Mathematiker und Ingenieur Claude Shannon im Aufsatz „Programming a Computer for Playing Chess“, veröffentlicht 1950 in der Zeitschrift Philosophical Magazine.

Die Shannon-Zahl: Woher stammt die Rechnung?

Claude Shannon (1916–2001) gilt als Begründer der Informationstheorie. 1950 veröffentlichte er einen der ersten Aufsätze über die Programmierung eines Computers zum Schachspielen. Um zu zeigen, dass eine Maschine nicht einfach alle Zugfolgen berechnen kann, nahm er eine grobe Abschätzung vor:

1. In einer typischen Stellung gibt es etwa 30 legale Züge. Diese Zahl bleibt während eines großen Teils der Partie ungefähr konstant.
2. Ein weißer Zug gefolgt von einem schwarzen Zug ergibt daher etwa 30 × 30 = 900 Möglichkeiten, die Shannon auf 10³ aufrundet.
3. Eine typische Partie dauert etwa 40 Züge (40 weiße und 40 schwarze Züge), bis ein Spieler aufgibt.
4. Die Zahl der Zugfolgen beträgt somit etwa (10³)⁴⁰ = 10¹²⁰.

Shannon fügt hinzu, dass eine Maschine, die pro Mikrosekunde eine Variante untersuchte, mehr als 10⁹⁰ Jahre bräuchte, um ihren ersten Zug zu berechnen. Daraus folgert er, dass ein Schachprogramm Stellungen bewerten und die zu untersuchenden Varianten auswählen muss, so wie es ein menschlicher Spieler tut.

Partien und Stellungen: zwei verschiedene Zahlen

Man sollte die Anzahl der Partien (Zugfolgen) nicht mit der Anzahl der Stellungen (Anordnungen der Figuren auf dem Brett) verwechseln. Ein und dieselbe Stellung kann durch Millionen verschiedener Partien erreicht werden.

Shannon schätzte die Anzahl der Stellungen mit der Formel 64! / (32! × 8!² × 2!⁶), die zählt, auf wie viele Arten sich die 32 Ausgangsfiguren auf die 64 Felder verteilen lassen; das Ergebnis beträgt etwa 4,6 × 10⁴², was er zu „etwa 10⁴³“ rundete. Die moderne Schätzung von John Tromp, (4,82 ± 0,03) × 10⁴⁴ legale Stellungen, wurde auf andere Weise gewonnen: Er zog zufällig zwei Millionen Stellungen aus einer Menge, deren Umfang man kennt, und prüfte dann, welche davon tatsächlich in einer Partie erreichbar sind, unterstützt von Peter Österlund bei der computergestützten Analyse.

Die ersten Züge: eine exakte Zählung

Zu Beginn der Partie lässt sich exakt zählen. Weiß hat 20 mögliche Züge (16 Bauernzüge und 4 Springerzüge). Schwarz ebenso. Man erhält:

Durch Programm aus der Ausgangsstellung neu berechnete Werte (Zählung aller legalen Zugfolgen).

Nach nur zwei Zügen jeder Seite werden bereits über 197 000 mögliche Zugfolgen erreicht. Der Multiplikationsfaktor steigt danach weiter an, weil die Figuren ins Spiel kommen und mehr Auswahl haben: Das rechtfertigt die Annahme von etwa dreißig Zügen pro Stellung.

Woher stammt die Schätzung von 10¹²³?

1994 hat der niederländische Forscher Victor Allis die Rechnung mit anderen Annahmen wiederholt: etwa 35 mögliche Züge pro Stellung und Partien von 80 Halbzügen (40 Züge jeder Seite). Man erhält 35⁸⁰. Um dies als Zehnerpotenz zu schreiben, verwendet man den dekadischen Logarithmus: 80 × log(35) ≈ 80 × 1,544 ≈ 123,5. Daraus ergibt sich die Größenordnung 10¹²³. Die Methode ist genau die von Shannon, nur die Parameter ändern sich, was zeigt, wie sehr das Ergebnis von den Annahmen abhängt.

Mit Shannons genauen Parametern ergibt 900⁴⁰ übrigens etwa 10¹¹⁸ statt 10¹²⁰: Die Rundung von 900 auf 1 000 liefert die runde Zahl. Bei einer so gewaltigen Größenordnung spielt der Unterschied für die Praxis keine Rolle.

Wie man sie im Unterricht erklärt

Die Shannon-Zahl eignet sich hervorragend zum Üben von Zehnerpotenzen, einem Thema des Lehrplans der 4^e. Einige Ansätze:

• Die Zahl schreiben: 10¹²⁰ wird als eine 1 gefolgt von 120 Nullen geschrieben. Man kann die Schülerinnen und Schüler das an der Tafel ausschreiben lassen … und dabei die nötige Zeit messen.
• Mit Potenzen rechnen: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ ist eine direkte Anwendung der Regel (a^m)ⁿ = a^{m × n}.
• Größenordnungen vergleichen: 10¹²⁰ geteilt durch 10⁸⁰ ergibt 10⁴⁰. Selbst wenn jedes Atom des Universums ein Computer wäre, müsste jeder dieser Computer noch immer 10⁴⁰ Partien berechnen.
• Die Annahmen diskutieren: Warum 30 Züge pro Stellung? Warum 40 Züge pro Partie? Was ändert sich bei einer Partie mit 60 Zügen? (Antwort: (10³)⁶⁰ = 10¹⁸⁰.)

Die Anzahl der Weizenkörner auf dem Schachbrett des Sissa, etwa 1,8 × 10¹⁹, wirkt daneben winzig: Der Vergleich beider Zahlen ist eine gute Übung. Siehe die Berechnung zum Schachbrett des Sissa.

Kann man Schach „lösen“?

Ein Spiel zu lösen bedeutet, mit Sicherheit zu wissen, welches Ergebnis (Sieg für Weiß, Sieg für Schwarz oder Remis) bei perfektem Spiel beider Seiten herauskommt. Die Shannon-Zahl zeigt, dass dies nicht durch das Durchprobieren aller Partien gelingt. Computer haben jedoch alle Stellungen mit wenigen Figuren gelöst, mithilfe von Endspieltabellen. Um zu erfahren, wie weit die Frage gediehen ist, hat sich der Palais des Échecs gefragt, ob Schach eines Tages gelöst werden kann.

Die Shannon-Zahl und andere große Zahlen des Schachbretts

Das Schachbrett ist eine kleine Fabrik für große Zahlen: 2⁶⁴ − 1 Weizenkörner des Sissa, über 26 000 Milliarden geschlossene Springerrundreisen, 92 Lösungen des Achtdamenproblems, 204 Quadrate … Finden Sie sie auf unserer Seite die großen Denksportaufgaben des Schachbretts.