Shannon-Zahl: Wie viele Schachpartien sind denkbar?

Gern zitiert man die Shannon-Zahl, um die Vielfalt des Schachspiels greifbar zu machen. Außerdem eignet sie sich bestens, um Zehnerpotenzen, die wissenschaftliche Schreibweise und Größenordnungen zu üben, und zwar von der Sekundarstufe I bis in die Oberstufe. Wichtig ist aber, die Herkunft zu kennen und zu wissen, was sie genau misst und was nicht.

Shannon-Zahl

Vorsichtige Schätzung von etwa 10¹²⁰ möglichen Schachpartien, vorgelegt vom US-amerikanischen Mathematiker und Ingenieur Claude Shannon im Beitrag „Programming a Computer for Playing Chess“, erschienen 1950 im Philosophical Magazine.

Die Shannon-Zahl: Wie kommt die Rechnung zustande?

Claude Shannon (1916–2001) gilt als Wegbereiter der Informationstheorie. Im Jahr 1950 erschien eine seiner ersten Arbeiten zur Frage, wie ein Computer Schach spielen kann. Um deutlich zu machen, dass eine Maschine nicht sämtliche Zugfolgen durchrechnen kann, stellte er eine grobe Überschlagsrechnung an:

1. Eine typische Stellung bietet ungefähr 30 erlaubte Züge. Dieser Wert bleibt über weite Strecken einer Partie annähernd gleich.
2. Ein Zug von Weiß mit der Antwort von Schwarz führt damit auf etwa 30 × 30 = 900 Varianten, die Shannon zu 10³ aufrundet.
3. Eine durchschnittliche Partie umfasst rund 40 Züge (je 40 Züge für beide Seiten), ehe jemand aufgibt.
4. Somit ergeben sich ungefähr (10³)⁴⁰ = 10¹²⁰ Zugfolgen.

Shannon merkt außerdem an, dass ein Rechner, der pro Mikrosekunde eine Variante prüft, mehr als 10⁹⁰ Jahre benötigen würde, um den ersten Zug zu berechnen. Daraus schließt er, dass ein Schachprogramm Stellungen bewerten und die zu untersuchenden Varianten gezielt auswählen muss, ähnlich wie ein menschlicher Spieler.

Partien und Stellungen: zwei Zahlen, die nicht dasselbe meinen

Die Anzahl der Partien (Zugfolgen) sollte man nicht mit der Anzahl der Stellungen (Figurenanordnungen auf dem Brett) verwechseln. Ein und dieselbe Stellung lässt sich über Millionen unterschiedlicher Partien erreichen.

Shannon ermittelte die Zahl der Stellungen mit dem Ausdruck 64! / (32! × 8!² × 2!⁶), der abzählt, auf wie viele Arten sich die 32 Ausgangsfiguren auf die 64 Felder verteilen lassen. Das Ergebnis liegt bei etwa 4,6 × 10⁴², was er auf „rund 10⁴³“ aufrundete. Die neuere Schätzung von John Tromp, (4,82 ± 0,03) × 10⁴⁴ legale Stellungen, entstand auf anderem Weg: Er zog zufällig zwei Millionen Stellungen aus einer Menge mit bekanntem Umfang und prüfte dann, welche davon tatsächlich in einer Partie vorkommen können. Bei der computergestützten Auswertung half Peter Österlund.

Die ersten Züge, Schritt für Schritt abgezählt

Am Anfang einer Partie lässt sich genau nachzählen. Weiß hat 20 mögliche Züge (16 Bauernzüge und 4 Springerzüge), Schwarz ebenso. Daraus ergibt sich:

Mit einem Programm ab der Ausgangsstellung neu berechnete Werte (Zählung aller legalen Zugfolgen).

Schon nach jeweils zwei Zügen beider Seiten sind über 197 000 Zugfolgen erreicht. Danach wächst der Faktor weiter, weil die Figuren ins Spiel kommen und mehr Wahlmöglichkeiten entstehen. Damit ist die Annahme von rund dreißig Zügen pro Stellung gut begründet.

Wo kommt die Angabe 10¹²³ her?

Im Jahr 1994 wiederholte der niederländische Forscher Victor Allis die Rechnung mit anderen Annahmen: rund 35 Züge pro Stellung und Partien von 80 Halbzügen (40 Züge pro Seite). Dies ergibt 35⁸⁰. Um es als Zehnerpotenz auszudrücken, nutzt man den dekadischen Logarithmus: 80 × log(35) ≈ 80 × 1,544 ≈ 123,5, was die Größenordnung 10¹²³ liefert. Das Verfahren entspricht dem Shannons, nur die Parameter sind andere, und genau daran zeigt sich, wie stark das Ergebnis von den Annahmen abhängt.

Übrigens: Mit Shannons genaueren Parametern ergibt 900⁴⁰ etwa 10¹¹⁸ statt 10¹²⁰. Die Aufrundung 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 behandelt

Die Shannon-Zahl eignet sich hervorragend, um mit Zehnerpotenzen zu arbeiten, die in Österreich ebenso wie in Frankreich im Lehrplan der 8. Schulstufe (4^e) stehen. Einige Ideen:

• Die Zahl ausschreiben: 10¹²⁰ entspricht einer 1 mit 120 Nullen. Man kann die Schülerinnen und Schüler die Zahl an der Tafel ausschreiben lassen und dabei die benötigte Zeit messen.
• Mit Potenzen rechnen: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ ist eine unmittelbare Anwendung der Regel (a^m)ⁿ = a^{m × n}.
• Größenordnungen gegenüberstellen: 10¹²⁰ geteilt durch 10⁸⁰ ergibt 10⁴⁰. Selbst wenn jedes Atom des Universums ein Computer wäre, müsste jeder davon noch immer 10⁴⁰ Partien berechnen.
• Die Annahmen besprechen: 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 Zahl der Weizenkörner auf dem Schachbrett des Sissa, rund 1,8 × 10¹⁹, wirkt daneben winzig. Der Vergleich beider Zahlen ist eine gute Übung. Siehe die Berechnung zum Schachbrett des Sissa.

Lässt sich Schach „lösen“?

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

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

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