Gibt es mehr Schachspiele mit 40 Zügen als Atome im Universum?

Es gibt weitaus mehr 40-Zug-Schachspiele als Atome im sichtbaren Universum, was wir weiter unten beweisen werden. Aber zuerst eine Klarstellung:

• Frühere Beiträge erwähnen die Shannon-Zahl , die seine Schätzung für die Spielbaumkomplexität des Schachs ist (dh die Anzahl möglicher Partien ). Shannon gab die Schätzung 10 ¹²⁰ als Bemerkung in "Programming a Computer for Playing Chess" an. Eine andere Schätzung von Victor Allis war 10 ¹²³ (dies wird in seiner Doktorarbeit erwähnt, die von der Wikipedia-Seite verlinkt ist ). Er schreibt:

Die Spielbaumkomplexität von Schach 10 ¹²³ basiert auf einem durchschnittlichen Verzweigungsfaktor von 35 und einer durchschnittlichen Spiellänge von 80"

(Tatsächlich gibt es unendlich viele mögliche Schachpartien, vorausgesetzt, kein Spieler behauptet ein Remis durch Wiederholung oder die 50-Züge-Regel. Die obigen Schätzungen basieren auf praktischeren Zahlen.)

• Das Obige scheint mit der Zustandsraumkomplexität verwechselt zu werden , dh der Anzahl möglicher legaler und erreichbarer Positionen auf einem Schachbrett (die eine drastisch andere Zahl ist als in der Frage gefordert). Tatsächlich wurde von Allis (op. cit.) eine strenge Obergrenze von 5 * 10 ⁵² abgeleitet , was weit weniger ist als die Anzahl der Atome im sichtbaren Universum (geschätzt auf 10 ⁸⁰ ; vgl. Wikipedia ).

Notation : Ein Schachzug besteht aus zwei Lagen , einer Lage mit Weiß und einer Lage mit Schwarz. Somit haben wir das „ Zwei-Zug -Matt“ (1. f3 e5 2. g4 Dh4#). Die hier verwendete Notation ist die algebraische Notation .

Wir werden einen konstruktiven Beweis liefern, dass es im sichtbaren Universum mehr Schachspiele mit 40 Zügen als Atome gibt. Betrachten Sie die folgende Reihe möglicher Schachpartien mit 40 Zügen, beginnend mit:

1. e4 e5
2. d4 d5
3. c3 c6

Nun kann Weiß für den Rest der Partie einen der folgenden Züge machen:

• Der weißfeldrige Läufer kann auf jedes Feld auf der Diagonale f1-a6 ziehen (6 Felder => 5 mögliche Züge).
• Der weiß-schwarzfeldrige Läufer kann auf jedes Feld auf der Diagonale c1-h6 ziehen (6 Felder => 5 mögliche Züge).
• Die weiße Dame kann auf jedes Feld auf der Diagonalen d1-a4 ziehen (4 Felder => 3 mögliche Züge).
• Der weiße Springer auf g1 kann auf jedes Feld in der Menge {g1,f3} ziehen (2 Felder => 1 möglicher Zug).

Die schwarzen Steine ​​sind symmetrisch begrenzt. Setzen Sie dies für die nächsten 74 Lagen fort. Dann gibt der weiße Spieler auf.

Das beobachten wir:

• Die Teile behindern sich nie gegenseitig. Captures werden nie gemacht. Überprüfung findet nie statt. Daher gibt es für jede Lage 14 legale Züge.

• Wir haben nur sehr wenige der tatsächlich möglichen Züge verwendet, die uns zur Verfügung stehen. Es wird weitaus mehr mögliche 40-Züge-Partien geben als in dieser Klasse.

• Diese Spiele dauern genau 40 Züge. (Wenn Sie das Aufgeben als eine Schicht zählen, können Sie Schwarz auf die vorherige Schicht aufgeben lassen.)

Daher haben wir einen Satz von 14 ⁷⁴ unterschiedlichen Schachpartien mit 40 Zügen konstruiert. Außerdem ist 14 ⁷⁴ > 10 ⁸⁴ , während 10 ⁸⁰ eine Schätzung der Anzahl der Atome im beobachtbaren Universum ist .

Einige Kommentare:

• Beim Schach können Spieler ein Remis durch die „ Drei-Zug-Regel “ beanspruchen, obwohl sie dazu nicht verpflichtet sind. (Dies führt zu Fällen, in denen Spieler auf unbestimmte Zeit weiterspielen, manchmal verursacht durch Schachtrainer, die darauf bestehen, dass ihre Schüler kein Remis akzeptieren oder anbieten, manchmal verursacht durch Spieler, die die Regeln nicht kennen.) Außerdem wird die Drei-Zug-Regel normalerweise theoretisch ignoriert Studien.

• Diese Positionen enden mit dem Rücktritt eines Spielers, aber sie könnten wahrscheinlich geändert werden, um bei Bedarf in einem Helfer zu enden. Dies würde jedoch die Gesamtzahl verringern (und Sie müssen wahrscheinlich ein clevereres Argument verwenden).

• Es gibt wahrscheinlich bessere Konstruktionen als die, die ich hier gebe.

Edit 2019-01: Die Beantwortung dieser Frage läuft darauf hinaus, zu wissen, wie viele Möglichkeiten es gibt, Schachpartien mit 40 Zügen zu spielen, und wie viele Atome es im Universum gibt. Letzteres ist bekannt, und alle diese Antworten zitieren letztendlich Schachexperten, die sich nur in der Interpretation ihrer Zahlen unterscheiden.

Die Antwort von Douglas S. Stones gefällt mir am besten, da sie die originellste ist. Es konstruiert einen Bewegungsbaum, der allein die Anzahl der Atome im Universum übersteigt, und beantwortet so direkt die Frage.

DavePhD hat auch die Zitate am deutlichsten dargestellt, was zeigt, dass mein Vertrauen in die Wolfram-Site falsch war.

Bearbeiten: Ich werde das Original so lassen, wie es ist, möchte aber dank Mike Dunlaveys Kommentar eine Korrektur hinzufügen. Ich habe die Frage falsch verstanden und wenn die Frage tatsächlich lautet, ob Spiele mit 40 Zügen oder weniger (ich lese 40 Züge oder mehr) größer ist als die Anzahl der Atome im Universum, ändere ich meine Antwort, um nicht zuzustimmen. Die Zahlen sind unten alle vorhanden, aber jetzt vergleichen wir 10^80 (Anzahl der Atome) mit 10^43 (Anzahl von 40 Zügen oder weniger Schachpartien). Die Zahl der Atome ist also größer.

Ich würde zustimmen.

Erstens liefert Wiki diese Zahl zur Anzahl der Atome im Universum:

Zwei ungefähre Berechnungen ergeben, dass die Anzahl der Atome im beobachtbaren Universum nahe bei 10^80 liegt.

Als nächstes stellt Wiki die Shannon-Zahl als Anzahl möglicher Schachpartien bereit, die gespielt werden können:

Die Spielbaumkomplexität des Schachs wurde zuerst von Claude Shannon als 10^120 berechnet, eine Zahl, die als Shannon-Zahl bekannt ist.

Schließlich liefert Wolfram Mathworld eine Zahl für die Anzahl der Partien mit weniger als 40 Zügen :

Die Anzahl möglicher Partien mit 40 Zügen oder weniger P(40) beträgt ungefähr 10^40 (Beeler et al. 1972) ...Shannon (1950) gab die Schätzung an: P(40) = 64! / (32! * 8!^2 * 2!^6) = 10^43.

Ich sehe, dass einige andere Antworten eingegangen sind, während ich geschrieben habe. Sie scheinen die insgesamt möglichen Spiele (10^120) mit der Anzahl der Atome im Universum (10^80) zu vergleichen, aber Sie suchen nach der Anzahl der Atome im Vergleich zu Spielen mit mehr als 40 Zügen . In diesem Fall betrachten wir:

10^80 vs. 10^120 - 10^43 (um konservativ zu sein)

Um fair zu sein, die eigene Antwort des Posters (@Vian) ist richtig, da 10 ^ 43 nicht einmal 10 ^ 120 verbeult und daher im Wesentlichen immer noch 10 ^ 80 und 10 ^ 120 vergleicht. Ich wollte nur erklären, warum ich denke, dass die Frage etwas anders ist, als nur die Anzahl der Atome und die Anzahl aller möglichen Schachspiele zu vergleichen.

Die akzeptierte Antwort ist falsch, da der Irrtum besteht, einen Link zu einer anderen Website als Wahrheit zu akzeptieren, anstatt tatsächlich zu rechnen.

Insbesondere die Seite http://mathworld.wolfram.com/Chess.html verwechselte die Anzahl der Stellungen mit der Anzahl der Partien mit 40 Zügen.

Obwohl Mathworld sagt

Die Anzahl möglicher Partien mit 40 Zügen oder weniger P(40) beträgt ungefähr 10^(40) (Beeler et al. 1972)

Die Beeler-Referenz selbst ist sehr klar, dass es sich um Positionen handelt, nicht um Spiele:

Es gibt ungefähr 10^40 mögliche Positionen

und obwohl mathworld sagt

Shannon (1950) gab die Schätzung an ... 10^43

Shannon schrieb wirklich im XXII. Programmieren eines Computers zum Spielen von Schach Philosophical Magazine , Ser.7, Vol. 7, No. 41, Nr. 314 - März 1950 :

In typischen Schachstellungen gibt es in der Größenordnung von 30 legalen Zügen. Die Zahl bleibt ziemlich konstant, bis das Spiel fast beendet ist, wie in Abb. 1 gezeigt. 1. Dieses Diagramm wurde aus Daten von De Groot erstellt, der die Anzahl der legalen Züge in einer großen Anzahl von Meisterpartien mittelte ( De Groot, 1946, a ). Somit ergibt ein Zug für Weiß und dann einer für Schwarz ungefähr 1000 Möglichkeiten . Eine typische Partie dauert etwa 40 Züge bis zur Aufgabe einer Partei. Dies ist für unsere Berechnung konservativ, da die Maschine mit Schachmatt rechnen würde, nicht mit Resignation. Aber selbst bei dieser Zahl müssen 10^120 Abweichungen von der Anfangsposition berechnet werden.

...

Eine andere (ebenso unpraktische) Methode besteht darin, ein "Wörterbuch" aller möglichen Positionen der Schachfiguren zu haben. Für jede mögliche Position gibt es einen Eintrag, der den korrekten Zug angibt (entweder durch den obigen Prozess berechnet oder von einem Schachmeister bereitgestellt). Wenn die Maschine an der Reihe ist, um sich zu bewegen, sucht sie lediglich die Position nach und führt den angezeigten Zug aus. Die Anzahl der möglichen Positionen in der allgemeinen Größenordnung von 64! / 32!(8!)^2(2!)^6, oder ungefähr 10^43

Beim Schach bedeutet „40-Züge-Spiel“, dass jeder Spieler eine Figur 40 Mal bewegt: 80-fache oder 80 halbe Züge.

In der Standard-Schachterminologie besteht ein Zug aus einem Zug jedes Spielers ; daher ist eine Lage im Schach ein halber Zug. Somit sind nach 20 Zügen in einem Schachspiel 40 Lagen fertig – 20 von Weiß und 20 von Schwarz.

Wenn also für ein Spiel mit 40 Zügen angenähert wird, dass es eine konstante (c) Anzahl von legalen Halbzügen gibt, hat die Annäherung der Anzahl von Spielen mit 40 Zügen die folgende Form:

c ^ 80

Solange also „c“ größer als 10 ist, ist die Anzahl der 40 Zugspiele größer als die Anzahl der Atome im Universum.

Zum Beispiel gibt es 20 mögliche erste Halbzüge (16 Bauernzüge und 4 Springerzüge) und 20 mögliche zweite Halbzüge.

Shannon verwendet also unter Berufung auf De Groot die Schätzung von "30" für "c" und daher:

30^80 = ~1,5 x 10^118

Also, ja, es gibt mehr Spiele mit 40 Zügen (80 halbe Züge) als die Anzahl der Atome im Universum .

Nach etwas besserer Suche habe ich das hier gefunden:

Die Shannon-Zahl

Allis schätzte auch die Komplexität des Spielbaums auf mindestens 10 ^ 123, "basierend auf einem durchschnittlichen Verzweigungsfaktor von 35 und einer durchschnittlichen Spiellänge von 80". Zum Vergleich: Die Anzahl der Atome im beobachtbaren Universum, mit dem es oft verglichen wird, wird auf 4×10^79 bis 10^81 geschätzt.

http://en.wikipedia.org/wiki/Shannon_number

Hier ist auch jemand, der versucht, es klarer zu erklären .

Eine kleine Google-Suche ergibt diese Schätzungen:

Atome im Universum: 10^80

Schachpartien mit 40 Zügen: 10^40

Geben oder nehmen Sie ein paar Nullen.