Ist die Anzahl der möglichen Schachpartien unendlich?

15

Diese Frage hat etwas mit der Frage zu tun. Kann die Gesamtzahl der möglichen Gewinne / Unentschieden / Verluste berechnet werden? , aber etwas anders.

Es gibt kürzlich eine Folge einer Fernsehsendung, in der behauptet wird, es gebe "mehr mögliche Schachpartien als Atome im Universum". Sie machen weiter: "Jeder mögliche Zug repräsentiert ein anderes Spiel, ein anderes Universum [..]." "Im zweiten Zug gibt es 72084 mögliche Spiele, im dritten - 9 Millionen, im vierten - 318 Millionen".

Ist die Gesamtzahl der Schachpartien für alle praktischen Zwecke unbegrenzt, wenn die menschlichen und technologischen Einschränkungen gegeben sind? Und halten die oben genannten Zahlen tatsächlich der Prüfung stand? (dh was sind die geschätzten möglichen Spiele bis zum zehnten Zug?)

Merkwürdigerweise scheint Wikipedia darauf hinzudeuten, dass die Anzahl der Spiele geschätzt werden kann:

Die Anzahl der möglichen Partien [in Go] ist enorm (10 761 im Vergleich zu 10 120 im Schach).

theory statistics game-complexity Landroni
quelle
3
Wenn Sie ein "Spiel" als die Geschichte von Zügen definieren, hat jedes Spiel, das Wiederholungen zulässt, unendlich viele mögliche Spiele. Schlangen und Leitern hat unendlich viele mögliche "Spiele". Wenn Sie an der Komplexität des Lösens eines Spiels interessiert sind, ignorieren Sie die
Zughistorie
3
Hinweis: Informatiker würden sich sofort dagegen aussprechen, "für alle praktischen Zwecke unendlich" zu sein. Es ist bemerkenswert gefährlich, auf Unendlich aufzurunden. Im Allgemeinen bricht jemand, wenn er den Fehler macht, schnell seinen Algorithmus, indem er zeigt, dass es nicht wirklich eine Unendlichkeit ist, mit der er es zu tun hat. Bei der Verschlüsselung ist es nicht ungewöhnlich, dass Algorithmen, die "bis zum Tod des Universums unzerbrechlich" schienen, aufgrund einiger Tricks, die die Problemgröße um 10 ^ 80 oder mehr verringerten, zerstört wurden.
Cort Ammon - Reinstate Monica
2
Wenn ich mich nicht irre, beziehen Sie sich auf die TV-Show Person von Interesse, oder? Wenn Sie die nächsten möglichen Schritte vorhersehen, müssen Sie einen Entscheidungsbaum erstellen, um alle Möglichkeiten zu berechnen. Wenn Harold sich auf den "zweiten Zug" bezieht, meint er, zwei Züge vorauszusehen (Ihren und den des Gegners; in der Informatik ist dies die 2. Ebene der Tiefe des Baums). Ohne die Berechnungen zu machen, glaube ich, könnte es richtig sein. Zumindest muss es eine riesige Zahl sein.
CMPSoares
Möglicherweise finden Sie dieses Video interessant. youtu.be/Km024eldY1A
Jivan Scarano

Antworten:

17

Die maximale Anzahl von Zügen in einem Schachspiel ist nicht unendlich, es sind 11797 Lagen = 5898 Züge und eine halbe. Dies liegt an der Fünfzig-Züge-Regel.

Also nein, die Anzahl der möglichen Schachpartien ist nicht unendlich.

Die maximale Anzahl legaler Züge in einer Position ist 218. Eine grobe Obergrenze für die Anzahl möglicher Schachpartien ist also 218 ^ 11797 = 10 ^ 27586

Warten Sie, tatsächlich können die Spieler nach fünfzig Zügen ohne Eroberungs- oder Bauernbewegung weiterspielen, ohne die Auslosung in Anspruch zu nehmen ...

Artikel 9.3 des FIDE-Schachgesetzes bestimmt:

9.3

Das Spiel wird nach einem korrekten Anspruch eines Spielers gezogen, der den Zug ausgeführt hat, wenn:

  • er schreibt seinen Zug, der nicht geändert werden kann, auf sein Spielberichtsblatt und erklärt dem Schiedsrichter, dass er diesen Zug ausführen möchte, wodurch die letzten 50 Züge jedes Spielers ohne die Bewegung eines Bauern und ohne Gefangennahme ausgeführt werden, oder
  • Die letzten 50 Züge jedes Spielers wurden ohne Bewegung eines Bauern und ohne Gefangennahme ausgeführt.

Ich denke also, die Anzahl der möglichen Schachpartien könnte dann als unendlich angesehen werden ...

Wenn Sie sich jedoch nicht für die vorherigen theoretischen Zahlen interessieren:
Die durchschnittliche Anzahl der legalen Züge in einer Position beträgt ungefähr 35, und die durchschnittliche Länge einer Schachpartie beträgt ungefähr 40 Züge = 80 Züge. Rationale "Schachpartien sind 35 ^ 80 = 10 ^ 123.
Die Gesamtzahl der legalen Positionen liegt irgendwo zwischen 10 ^ 40 und 10 ^ 50.

Schicksal
quelle
Das Problem der Wiederholung kann gelöst werden, indem die Frage so angepasst wird, dass es sich nicht um Züge, sondern um Zustände handelt. Wie viele verschiedene mögliche Konfigurationen eines Schachbretts sind möglich? Das ist die interessante Frage aus der Sicht der Komplexität. Wiederholung spielt keine Rolle, sie wiederholt den gleichen Zustand. Viele Staaten sind entweder nicht zu erreichen, weil sie mehr als 50 Züge benötigen, oder weil die Bewegung von Figuren (insbesondere von Bauern) eingeschränkt ist.
Schwern
3
@ Tony Ennis: Ich habe bearbeitet. Aber eigentlich nein, die 50-Züge-Regel garantiert nicht, dass das Spiel endet, da die Spieler auch entscheiden können, die Auslosung nicht zu beanspruchen.
Schicksal
2
Könnten Sie bitte Ihre Antwort so bearbeiten, dass sie als Antwort und nicht als Diskussion mit Ihnen selbst angezeigt wird? Sie beginnen mit der falschen Behauptung, die Anzahl der Spiele sei endlich, und korrigieren sich dann. Stellen Sie einfach zuerst die richtige Behauptung auf. wenn du dann sagen willst "Aber wenn die Spieler immer ein Unentschieden machen, sobald sie dazu berechtigt sind, dann ...", ist das in Ordnung.
David Richerby
11
Tatsächlich gibt es seit Juli letzten Jahres eine 75-Punkte-Regel, die verbindlich ist. Die 50-Züge-Regel garantiert also kein Spielende, die 75-Züge-Regel jedoch, obwohl das längste Spiel auf 17.697 Züge ansteigt. Bei einem durchschnittlichen Verzweigungsfaktor von 35 könnte man die mögliche Anzahl von Spielen auf 35 ^ 17697 oder ungefähr 10 ^ 27000 schätzen.
Deedlit
1
Selbst wenn wir sowohl die 50- als auch die 75-Züge-Regel missachten, muss irgendwann eine dreifache Wiederholung stattfinden, wenn die Spieler weiterspielen, ohne ein Unentschieden zu fordern. Ich weiß nicht, ob hier ein Unentschieden erforderlich ist, aber ich würde zum Zweck dieser Frage eine endliche Anzahl unterschiedlicher Spiele mit unendlichen Möglichkeiten in Betracht ziehen, eine endliche Anzahl möglicher Spiele zu wiederholen.
11684
6

Q1: ja Die Gesamtzahl der Schachpartien kann für alle praktischen Zwecke als unendlich angesehen werden. Wir haben nicht die Technologie, um in den ersten 13 Zügen von der Ausgangsposition aus Gewalt anzuwenden.

F2: Die tatsächlichen Zahlen bis zur Tiefe 13 sind bekannt. Die genaue Anzahl der möglichen Positionen für den 10. Zug beträgt 69.352.859.712.417. Lesen Sie diesen Wikipedia-Artikel für weitere Details.

Es gibt einen Versuch für Tiefe 14, aber bisher läuft die Berechnung nach Monaten und Monaten noch.

Kleinschach
quelle
Ja, beeindruckende Zahlen. Komischerweise können wir nicht mehr als 14 Züge berechnen ... Ich frage mich, wie viele Züge für Go ... Three berechnet werden können. :)
landroni
Es muss nicht "für alle praktischen Zwecke als unendlich angesehen werden", da es tatsächlich unendlich ist. Obwohl die Regeln für 50 Züge und die dreifache Wiederholung es jedem Spieler erlauben , ein Unentschieden zu fordern, beenden sie das Spiel nicht automatisch .
David Richerby
1
@landroni Go ist wahrscheinlich einfacher zu berechnen als Schach. Es gibt 361 Spiele mit einem Zug, 361 * 360 Spiele mit zwei Zügen und 361 * 360 * 359 Spiele mit drei Zügen. Die Anzahl der Vier-Züge-Spiele hängt davon ab, ob Selbstmord erlaubt ist. Wenn ja, dann gibt es 358 mögliche vierte Züge, es sei denn, die ersten beiden Steine ​​von Schwarz nehmen den ersten Stein von Weiß in die Ecke. In diesem Fall gibt es 359. Also 361 * 360 * 359 * 358 + 8 Vier-Züge-Spiele. Wenn Selbstmord nicht erlaubt ist, gibt es 361 * 360 * 359 * 358 - 8 * 358 Vier-Züge-Spiele. Sie können auf diese Weise fortfahren und die Fälle aufteilen - 14 Züge sind wahrscheinlich mit Computeraufwand machbar.
Deedlit
4
Beachten Sie, dass dies 13 Halb -moves oder Lage - sieben Züge von weißen und sechs von Schwarz.
RemcoGerlich
2
@DavidRicherby: Die 75-Punkte-Regel (neu seit Juli 2014) ist jedoch obligatorisch.
RemcoGerlich
2

Irgendwann gehen Ihnen die Kombinationen aus. Die Antwort lautet also im Grunde nein.

Nuach
quelle
1

Nach meinen Berechnungen handelt es sich um ca. 10 ^ 134 verschiedene Varianten des Spiels http://jknow.republika.pl/chessexplorer/szachy.html

Jan Nowakowski
quelle
4
Können Sie hier einen Überblick über die Methodik geben?
Landroni
1

Ein einfaches Argument dafür, dass die Anzahl der Schachpartien endlich ist, könnte sein:

Aufgrund der 50-Züge-Regel enthält jede 50-Züge-Folge eines bestimmten Schachspiels mindestens eine Gefangennahme oder einen Bauernzug. Da sich endlich viele Figuren auf dem Brett befinden und sich die Spielfiguren während einer Partie nur endlich oft bewegen können, ist die Anzahl der Züge in einer Schachpartie begrenzt. Da es in jedem Zug nur endlich viele Möglichkeiten gibt, ist die Anzahl aller Spiele endlich.

Beachten Sie, dass dieses Argument fast unbrauchbar ist, wenn man eine Schätzung der Anzahl möglicher Spiele erhalten möchte. Wenn nicht anders, ist das einzige, was ich oben benutze, die 50-Züge-Regel und wie sich die Figuren bewegen, so dass die Wiederholungen erlaubt sind (natürlich max. 50-fache Wiederholungen). Daher ist das Argument nur theoretisch und nicht praktisch.

Zvonimir
quelle
0

Die Regel mit 50 Zügen beinhaltet "bei korrektem Anspruch": Kein Anspruch, keine Implementierung der Regel. Gleiches gilt für Wiederholungen. Ergo unendlich.

Natürlich ohne vorgeschriebene maximale Anzahl von Zügen.

x1797n7917
quelle
4
Nicht länger. Die neuen FIDE-Schachgesetze haben eine Regel mit 75 Zügen und einer automatischen Ziehung. Siehe fide.com/fide/handbook.html?id=171&view=article $ 9.6.
Dag Oskar Madsen
0

Zum Verständnis der FIDE-Gesetze - Erstens sind sie für das Turnierspiel bestimmt -. Wenn Sie also wissen, wie sich die FIDE-Gesetze nicht auf zwei Freunde beziehen, die sich zum Spielen entschließen? Für zwei Freunde, die sich nur auf zwei Könige beschränken, können sie sich beliebig oft gegenseitig um das Brett jagen. (Plausibel-nicht wirklich, möglich-ja)

Nach FIDE-Gesetz 9.2 müssen 50 aufeinanderfolgende Züge ausgeführt werden, bei denen kein Bauer bewegt und keine Eroberung vorgenommen wurde. Dies wäre offensichtlich kein "Spiel mit 50 Zügen".

Nach FIDE-Gesetz 9.6 - 75 aufeinanderfolgende Züge ... Gleiche Begründung, dass dies kein 75-Züge-Spiel ist.

Einer der ersten Beweise für ein aufgezeichnetes Spiel waren 14 Züge hintereinander (1. e4 b6 2. d4 b7 3. dd3 f5 4. ef5 bg2 5. dh5 g6 6. fg6 sf6 7. gh7 nh5). Wenn der Gewinner sich entschieden hätte, kein Schachmatt zu setzen, hätte er noch 75 weitere Züge benötigt, um die Auslosung gemäß FIDE-Gesetz 9.6 zu erklären (mit 12 verbliebenen Bauern - ich bezweifle, dass dies in 75 Zügen geschehen wäre).

Mit freundlichen Grüßen CFC

Clayton Currier
quelle
2
Nun, wenn zwei Freunde, denen offizielle Regeln egal sind, ein Unsinnspiel spielen und es Schach nennen möchten, können sie es! Aber sollten wir es für die Zwecke dieser Site Schach nennen? Eine Position mit nur zwei Königen ist eine sofortige Auslosung.
RemcoGerlich
0

Da andere Antworten hier auf Wiederholung oder ähnliches verweisen, möchte ich Ihre Frage dahingehend modifizieren, dass die Anzahl der möglichen Schachstellungen unendlich ist. Die Antwort lautet "Nein". Die Summe ist jedoch sehr groß und wird auf ungefähr 10 bis 120 geschätzt Es wird angenommen, dass die Gesamtzahl der Atome im Universum nur 10 nach der 80. Potenz ist.

Die von einem vorherigen Responder angegebene Zahl 10 nach der 134. Potenz ist möglicherweise korrekt.

Das chinesische Spiel "Go" ist noch abwechslungsreicher als Schach (aber langweilig im Vergleich, da Schachfiguren mit unterschiedlichen Fähigkeiten haben, während in Go alle Figuren gleich sind).

markbolles44
quelle
0

Ich sehe das vielleicht zu simpel, aber es scheint mir, dass die Zahl endlich sein muss. Wenn wir uns das Spielbrett und die Figuren ansehen und nicht das Schachspiel, sondern die Anzahl der möglichen Variationen berechnen, erhalten wir eine Antwort, die endlich ist. Verblüffend groß, aber endlich. Da in einer Schachpartie nicht alle Kombinationen möglich sind, muss die Anzahl der Kombinationen in einer Schachpartie kleiner sein als diese endliche Zahl und daher eine endliche Zahl selbst.

Justin
quelle