Ist Schach ein gelöstes Spiel?

24

Schach ist ein Nullsummenspiel mit begrenzten Entscheidungen. Die Anzahl der möglichen Züge an einem bestimmten Punkt und die Anzahl der möglichen Zustände des Bretts sind alle endlich.

Tic-Tac-Toe ist eines der einfachsten Beispiele für ein gelöstes Spiel. Ich kann mich nicht erinnern, wie viele Jahre vergangen sind, seit ich das letzte Mal ein Tic-Tac-Toe-Match verloren habe. Gibt es eine solche "optimale Strategie" für Schach?

Gibt es eine Strategie, die garantiert, dass der Spieler einen Sieg oder schlimmstenfalls ein Unentschieden erzielt?

Wenn ja, werfen Sie bitte etwas Licht darauf.

Tobi Alafin
quelle

Antworten:

26

Aufgrund der Beobachtung Sie machen, dass der Baum der möglichen Spielpfade für Schach endlich ist, Schach ist in der Tat solv Lage , in genau der gleichen Sinne , dass Tic-Tac-Toe ist. Es gibt also optimale Strategien für Schach. Niemand hat jedoch eine Ahnung, was sie sind. Während Tic-Tac-Toe dank eines relativ kleinen Raums möglicher Spiele gelöst wird, ist Schach bei weitem nicht gelöst, da der Raum möglicher Spiele weit über dem liegt, was mit der aktuellen Computertechnologie erreicht werden könnte.

Wie in einer anderen Antwort angemerkt, weisen Endspiel-Tischbasen für alle Positionen mit einer begrenzten Anzahl von Stücken ein optimales Spiel auf. In diesen Situationen haben wir also Lösungen, die ebenso explizit und konkret sind wie die für Tic-Tac-Toe. Es ist jedoch wichtig zu beachten, dass man zwar leicht die optimale Strategie für Tic-Tac-Toe lehren / sich daran erinnern und schnell zu einem perfekten, nicht unterstützten Tic-Tac-Toe-Spieler werden kann, aber die Menge an Informationen hinter beispielsweise den 7-teiligen Lomonosov-Tischbasen , beträgt 140 Terabyte. Es gibt keine präzise Beschreibung der optimalen 7-Mann-Strategie, die man lernen / merken und dann ohne Hilfe perfekt spielen könnte.

ETD
quelle
5
Es kann hilfreich sein zu erwähnen, dass es keinen Konsens darüber gibt, ob die Ausgangsposition ein erzwungener Sieg für Weiß, ein Unentschieden oder sogar ein erzwungener Sieg für Schwarz (durch einen bizarr komplexen Zugzwang) ist. Dies bedeutet, dass wir nicht einmal wissen, ob das Spielen der optimalen Strategie ein Unentschieden garantieren kann.
Kevin
5
Es gibt keinen "Mangel an Konsens". Überwältigender Konsens ist "Unentschieden": en.wikipedia.org/wiki/First-move_advantage_in_chess .
Jeff Y
1
@JeffY Vielleicht besteht ein gewisser Konsens, aber wir können es nicht wissen, bis wir eine Tischbasis von 32 Männern haben.
24.
5
@ Jeffy, ich denke, dass Kevin anstatt des ablenkenden Satzes über "mangelnden Konsens" eigentlich nur darauf abzielen wollte, dass es einen "Mangel an Beweisen" gibt. Ich denke, wir sind uns alle einig, unabhängig von einem überwältigenden Meinungskonsens (und ich stimme Ihnen zu, dass die meisten davon ausgehen, dass das Spiel ein theoretisches Unentschieden ist), und unabhängig von empirischen Beweisen aus den vielen Spielen, die von Menschen und / oder Spielern gespielt werden. oder Engines (die beide suboptimal spielen), schließt keines der theoretischen Möglichkeiten für Schach (Sieg für Weiß / Unentschieden / Sieg für Schwarz) mit Sicherheit aus. .....
ETD
5
Kurz gesagt, ich denke, JeffY hat absolut Recht, dass es einen beträchtlichen Konsens in der Annahme gibt, dass Schach ein theoretisches Unentschieden ist, und das stimmt perfekt mit dem genauen Punkt von Kevin und 11684 überein, dass wir immer noch nicht wissen, ob Schach ein theoretisches Unentschieden ist oder nicht nicht. Ich denke, dass Sie alle wahrscheinlich mehr auf Augenhöhe sehen, als die obigen Kommentare auf den ersten Blick vermuten lassen.
ETD
8

Schachpartien mögen endlich sein, aber die Anzahl der möglichen Partien ist unvorstellbar.

Es ist keine Abfolge von Zügen bekannt, die beiden Seiten einen Sieg oder ein Unentschieden garantieren.

Tony Ennis
quelle
8

Schach ist noch nicht gelöst und wird es auch in den nächsten Jahrzehnten nicht sein (es sei denn, es wurden lächerliche Fortschritte beim Computing mit Quantencomputern oder solch drastischen Veränderungen erzielt).

Sie können den ersten Zug in Ihrem Kopf berechnen: Weiß hat 20 Optionen und Schwarz hat 20 Antworten; Wir haben bereits 400 mögliche Positionen. Diese Zahl wächst lächerlich schnell, die Anzahl der möglichen Positionen für ein Spiel mit 80 Zügen ist unvorstellbar groß.

Wenn Schach gelöst würde, wären Schachturniere und Meisterschaften im Grunde genommen Übungen zum Auswendiglernen, was es sinnlos macht. (EDIT: das ist eher übertrieben, siehe Kommentare.)

Derzeit ist Schach für jede Position mit gelöst sechssieben Stücke (einschließlich Könige). Die letzte Schätzung, für die ich gehört habe7 Männer8-Mann-Tischbasen waren irgendwo in den 2020er Jahren, und natürlich wächst die Zeit, die für ein zusätzliches Stück benötigt wird, exponentiell. Ich erwarte nicht , Schach überall zu sehen , in der Nähe gelöst in meinem Leben (wieder, abgesehen von wirklich außergewöhnlichen Rechenentwicklungen). (Gutschrift für Korrekturen an Tony Ennis.)

11684
quelle
Es gibt bereits 7-Mann-Tischgestelle.
Tony Ennis
"Ja wirklich?" Woher? Dann habe ich mich falsch erinnert, bitte ersetzen Sie 6 durch 7 und 7 durch 8. @TonyEnnis
11684
3
Laut ETDs Kommentar könnten sich die Menschen die Lösung selbst dann nicht merken , wenn das Schach gelöst wäre . Der Kommentar zu "sinnlos" ist also falsch.
Jeff Y
3
@ 11684 Wie geht das? Verändert es die Art des Endspielspiels in Turnieren drastisch, 7-teilige Tischbasen zu haben? Ich sehe es nicht
Jeff Y
1
@ 11684 Alles wahr. Aber wie würde das Turniere verändern ? Ich kann sehen, dass es viel mehr Eröffnungslinien öffnen kann (als Nicht-Verlierer), obwohl ich nicht sehen kann, dass ich mir weniger merken muss, um sie zu spielen. Und ich kann sehen, dass es Postmortems von Spielen sicherlich ändern würde. Aber ich sehe einfach keine signifikanten Auswirkungen auf Mensch-gegen-Mensch-Spiele, so wie 7-Teile-Endspiele nicht durch das Vorhandensein von 7-Teile-Tischbasen beeinflusst werden.
Jeff Y
4

Ein weiterer Punkt ist, dass das Schachspiel endlich ist, aber nur mit der 75-Züge-Regel (das Spiel wird gezogen, wenn es für 75 Züge keine Eroberungen oder Bauernzüge gibt). Zuvor erlaubte dies die Regel mit Unentschieden durch aufeinanderfolgende dreifache Wiederholung der Position, die sogenannte "Deutsche Regel", eine unendliche Anzahl von Spielen, wie von Max Euwe gezeigt .

Sylvain Julmy
quelle
3
Mit der Regel der dreifachen Position wäre das Spiel offensichtlich endlich. Denken Sie nur, dass es eine endliche Anzahl möglicher Positionen gibt und dass jede Position höchstens zweimal wiederholt werden kann. Der verlinkte Artikel zeigt, dass das Spiel unter der "deutschen Regel" unendlich sein kann, die verlangt, dass dieselbe Sequenz dreimal hintereinander
sharcashmo
Danke, ich habe meine Erklärung durcheinander gebracht, es ist dreimal die gleiche Abfolge von Zügen :).
Sylvain Julmy
3

Wir wissen, dass es eine optimale Strategie gibt, da, wenn es in einem Spiel eine begrenzte Anzahl von Spielern und eine begrenzte Anzahl von Strategien für jeden Spieler gibt, man nachweisen kann, dass ein Nash-Gleichgewicht existiert (also spielen Sie Ihre optimale Reaktion auf das Optimum des anderen Spielers Antwort und umgekehrt).

Die Sache ist, dass wir, selbst wenn wir wissen, dass eine solche Strategie existiert, aufgrund von Rechenbeschränkungen nicht genau wissen, um welche Strategie es sich handelt.

user10321
quelle
3

Hier ist eine Antwort, die ich ursprünglich unter /cstheory/6563/ geschrieben habe .

Ein perfekter Schachspieler wird immer einen Sieg erzwingen, wenn er einen Sieg erzwingen kann, und ein Unentschieden erzwingen, wenn er ein Unentschieden erzwingen kann. Natürlich können sie jederzeit ein Unentschieden erzwingen, wenn sie einen Sieg erzwingen können. Auch wenn ein Spieler keinen Sieg erzwingen kann, kann der andere Spieler ein Unentschieden erzwingen. Schach ohne die 50-Züge-Regel oder die 3-fache Wiederholungsregel ist möglicherweise nicht so schwer zu lösen, wie Sie denken. Es kann gezeigt werden, dass das Hinzufügen der 3-fachen Wiederholungsregel keinen Unterschied macht, ob ein Spieler einen Sieg oder ein Unentschieden erzwingen kann. Die Anzahl der möglichen Wege, die ein Spiel nach n Zügen gehen kann, wächst exponentiell mit n. Die Anzahl der Zustände, die nach n Zügen auftreten können, wächst andererseits nicht exponentiell weiter, da sie die Gesamtzahl der möglichen Zustände, die in einem legalen Spiel auftreten können, nicht überschreiten kann. Gemäßhttps://en.wikipedia.org/wiki/Game_complexity , es gibt ungefähr 10 ^ 47 Zustände, die in einem legalen Schachspiel auftreten können.

Schach kann wie folgt gelöst werden: Nehmen Sie eine Reihe von Zuständen, von denen wir beweisen können, dass sie alle Zustände enthalten, die in einem legalen Schachspiel ohne die 3-fache Wiederholungsregel oder die 50-Zug-Regel auftreten können. Zwei verschiedene Staaten könnten die gleiche Anordnung von Schachfiguren haben und sich unterscheiden, an wem sie an der Reihe sind, ob Sie das Recht haben, en passant zu fangen, und ob ein bestimmter König oder Turm das Recht hat, jemals wieder eine Burg zu errichten. Als nächstes nimmst du alle Zustände, in denen die minimale Anzahl von Zügen, die Weiß erzwingen kann, 1 ist, was in dem Zug von Weiß geschehen muss. Nehmen Sie als nächstes alle Zustände an, in denen die Mindestanzahl an Zügen, in denen Weiß einen Gewinn erzwingen kann, 2 ist. Dies bedeutet, dass Schwarz an der Reihe ist und unabhängig davon, welche Züge Weiß machen kann, in einem Zug einen Gewinn erzwingen kann. Nehmen Sie als nächstes alle Zustände, in denen die Mindestanzahl an Zügen, in denen Weiß einen Gewinn erzwingen kann, 3 ist. Dies bedeutet, dass Weiß einen Zug hat, der ihm in zwei Zügen einen erzwungenen Sieg beschert, aber in einem Zug keinen Sieg erzwingen kann. Nehmen Sie als nächstes alle Zustände an, in denen die Mindestanzahl an Zügen, in denen Weiß einen Gewinn erzwingen kann, 4 ist. Dies bedeutet, dass Schwarz an der Reihe ist und unabhängig davon, welchen Zug Weiß macht, in 3 Zügen einen Gewinn erzwingen kann, während Weiß derzeit keinen Gewinn erzwingen kann 2 Züge. Sobald wir eine Zahl erreicht haben, in der es keine Staaten gibt, in denen die Mindestanzahl von Zügen, in denen Weiß einen Sieg erzwingen kann, diese Zahl ist, haben wir bereits alle Staaten gefunden, in denen Weiß einen Sieg erzwingen kann. Wir können alle Staaten finden, in denen Weiß einen Sieg erzwingen kann Schwarz kann auf ähnliche Weise einen Sieg erzwingen. Alle übrigen Staaten sind solche, in denen beide Spieler ein Unentschieden erzwingen können. Dies bedeutet, dass Schwarz an der Reihe ist und unabhängig davon, welche Bewegung er ausführt, Weiß in drei Zügen einen Sieg erzwingen kann, während Weiß derzeit keinen Sieg in zwei Zügen erzwingen kann. Sobald wir eine Zahl erreicht haben, in der es keine Staaten gibt, in denen die Mindestanzahl von Zügen, in denen Weiß einen Sieg erzwingen kann, diese Zahl ist, haben wir bereits alle Staaten gefunden, in denen Weiß einen Sieg erzwingen kann. Wir können alle Staaten finden, in denen Weiß einen Sieg erzwingen kann Schwarz kann auf ähnliche Weise einen Sieg erzwingen. Alle übrigen Staaten sind solche, in denen beide Spieler ein Unentschieden erzwingen können. Dies bedeutet, dass Schwarz an der Reihe ist und unabhängig davon, welche Bewegung er ausführt, Weiß in drei Zügen einen Sieg erzwingen kann, während Weiß derzeit keinen Sieg in zwei Zügen erzwingen kann. Sobald wir eine Zahl erreicht haben, in der es keine Staaten gibt, in denen die Mindestanzahl von Zügen, in denen Weiß einen Sieg erzwingen kann, diese Zahl ist, haben wir bereits alle Staaten gefunden, in denen Weiß einen Sieg erzwingen kann. Wir können alle Staaten finden, in denen Weiß einen Sieg erzwingen kann Schwarz kann auf ähnliche Weise einen Sieg erzwingen. Alle übrigen Staaten sind solche, in denen beide Spieler ein Unentschieden erzwingen können. Wir können alle Zustände finden, in denen Schwarz auf ähnliche Weise einen Gewinn erzwingen kann. Alle übrigen Staaten sind solche, in denen beide Spieler ein Unentschieden erzwingen können. Wir können alle Zustände finden, in denen Schwarz einen Gewinn auf ähnliche Weise erzwingen kann. Alle übrigen Staaten sind solche, in denen beide Spieler ein Unentschieden erzwingen können.

Da es ungefähr 10 ^ 47 Zustände gibt, die in einem legalen Schachspiel vorkommen können, würde es mehr als unser ganzes Leben dauern, brachiale Gewalt anzuwenden, um einen Computer zu bauen, der Schach perfekt spielt, egal wie der Gegner spielt. Ich glaube, es wurde nicht bewiesen, dass es keinen viel kürzeren Algorithmus gibt, der Ihnen sagen kann, wie Sie perfekt spielen, egal wie Ihr Gegner spielt. Zum Beispiel kann möglicherweise nur ein kleiner Bruchteil der Zustände in einem legalen Spiel auftreten, in dem Sie so spielen, wie der Algorithmus es Ihnen vorschreibt, so dass der Algorithmus funktioniert, obwohl er Ihnen nur sagt, wie Sie in allen Zuständen, in denen dies der Fall ist, perfekt spielen kann auftreten, wenn Sie diesen Algorithmus seit Beginn des Spiels befolgt haben, jedoch nicht in allen Zuständen, die in einem legalen Spiel auftreten können. Vielleicht zusätzlich dazu, Dieser Algorithmus ist ein komplexer Algorithmus, der für jeden Zustand, der in einem Spiel auftreten kann, in dem Sie immer gefolgt sind, wesentlich weniger Schritte zur Berechnung eines optimalen Zuges benötigt als die Anzahl der Zustände, die in einem Spiel auftreten können, in dem Sie immer gefolgt sind. Gemäßhttp://onlinelibrary.wiley.com/doi/10.1002/sres.2171/abstractDie evolutionären Lernlabors planen, komplexe Probleme zu lösen. Vielleicht finden sie eines Tages eine komplexe Strategie, um perfekt Schach zu spielen. Selbst wenn ein Algorithmus, der sehr kurz ist und nur sehr wenige Schritte benötigt, um einen optimalen Zug in einem beliebigen Zustand zu berechnen, der in einem Spiel auftreten kann, in dem Sie diesen Algorithmus immer befolgt haben, existiert er möglicherweise nicht, ohne dass ein Mensch daran gehindert wird, dies zu tun perfekt Schach spielen lernen. Vielleicht könnte ein Mensch kontinuierlich Dinge herausfinden und behalten, was er herausgefunden hat, mehr Dinge herausfinden aus dem, was er zuvor herausgefunden hat, und sie durch eine komplexe Methode behalten.

Es ist wahrscheinlich noch einfacher für einen Spieler, eine Strategie zu haben, die sicherstellt, dass sein Gegner auch perfekt spielt, wenn er perfekt spielt. Ich vermute, beide Spieler haben zu Beginn des Spiels ein erzwungenes Unentschieden. Es ist wahrscheinlich einfacher, eine Strategie zu haben, die ein Unentschieden erzwingt, als eine Strategie, die garantiert, dass Sie sie nicht verlieren, wenn Ihr Gegner Ihnen einen erzwungenen Gewinn gibt. Eine Strategie, die ein Unentschieden erzwingt, ist auch eine Strategie, die sicherstellt, dass Sie perfekt spielen, wenn Ihr Gegner perfekt spielt. Wenn sie perfekt spielen, geben sie Ihnen keinen erzwungenen Gewinn, so dass Sie keinen erzwungenen Gewinn verlieren, nachdem sie Ihnen einen gegeben haben.

Timothy
quelle
Der Link zu Ihrer Antwort auf computer-science-SE ist hilfreich. Ich bin mir jedoch nicht sicher, ob es sich gelohnt hat, den gesamten Text zu kopieren.
Evargalo
3

1949 schätzte der Informationswissenschaftler Shannon, dass es 10 bis 90 Jahre dauern würde, Schach mit einem 1-MHz-Computer zu lösen. Die Energie- und Speichertechnologie des Computers hat sich seitdem erheblich verbessert (auch bekannt als Moores Gesetz), wobei sich die Energie- und Speicherkapazität des Computers jedes Jahr verdoppelt. Unter Berücksichtigung dessen würde es ungefähr 300 Jahre dauern, einen Computer zu entwickeln, der 10- bis 90-mal leistungsfähiger wäre als Shannons 1-MHz-Maschine. In der Computerentwicklung gibt es keine absehbaren Einschränkungen. Zum Beispiel wurde Intels 4004 mit 10 Mikrometer Photolithographie-Technologie hergestellt, während aktuelle i9s mit 14-nm-Technologie hergestellt werden. Wenn die Kerne sowohl leistungsfähiger als auch kleiner werden, ist es einfach, mehr Kerne in der gleichen physischen Größe wie in den Jahren zuvor zu stopfen, die nur halb so leistungsfähig sind wie die Vorfahren. In der Photolithographie sind wir gerade in die ultraviolette Wellenlängenkategorie unter 10 nm eingetreten, aber es gibt Wellenlängen wie Gammastrahlen, deren Wellenlänge 1 Pikometer (das sind 10.000 kleinere) beträgt. Ein Wasserstoffatom hat eine Größe von 0,1 nm, dh Quarks sind etwa 200-mal kleiner als 1 Pikometer (dh 0,43 x 10 ^ - 15 mm,https://www.theguardian.com/science/life-and-physics/2016/apr/07/how-big-is-a-quark )

Markku Litola
quelle
2

Nein

Wir können nicht sagen, wer gewinnen soll oder ob es ein Unentschieden sein soll

Es gibt viel zu viele Zugkombinationen, um überhaupt zu versuchen, die Antwort mit der aktuellen Technologie zu berechnen, indem alle möglichen Züge ausprobiert und die Ergebnisse angezeigt werden

dann müssten wir zurückschneiden, um zu sehen, was die Antwort wäre und ob sie einzigartig wäre

und wenn wir könnten, würde das Spiel keinen Spaß mehr machen

Joe Sixpak
quelle
5
"Wenn wir könnten, würde das Spiel keinen Spaß mehr machen" -> Die Leute spielen immer noch Connect-4 und einige andere gelöste Spiele.
Franck Dernoncourt
2

Zu Beginn des 20. Jahrhunderts war der Glaube populär, dass das Schach bald gelöst sein würde (genannt "der Unentschieden-Tod des Schachs"). Der Weltmeister J.-R. Capablanca neigte dazu, dies zu glauben. Die Spiele des Spiels Capablanca-Alekhine (fast alle im Gambit Declined der Königin) bestätigten ebenfalls diese Überzeugung. Siehe zum Beispiel: https://en.wikipedia.org/wiki/Capablanca_chess .

Die Revolution der modernen Eröffnungen (King's Indian usw.) und die Revolution der künstlichen Intelligenz lieferten intuitive Beweise dafür, dass das Lösen von Schach nicht so einfach ist. In der Tat werden heutzutage Großmeisterspiele oft mit einem Programm analysiert, und dies zeigt, welche Linien die Spieler (auch die besten) während des Spiels überwachten.

Vor diesem Hintergrund kann eine "absolute Rechenkraft" tatsächlich Schach im Sinne der Berechnungstheorie lösen.

Alexandre Aksenov
quelle
1

Der menschliche Geist ist viel komplexer als ein Tic-Tac-Toe-Spiel. So können Sie eine gute Strategie finden, um ein solches Spiel zu spielen.

Schach ist ganz anders. Schach ist ein heuristisches Spiel.

Sie können einen Soldaten nicht über einen General stellen. Der Verstand eines Generals ist militärisch gesehen viel komplexer als der eines Soldaten. Es ist nur eine Analogie.

Komplexität, darauf kommt es an.

Sie müssen komplexer sein als Schach. Es ist unmöglich, aber du musst es versuchen, du musst es versuchen. Sie können es in mehreren Ebenen erreichen. Viele Faktoren spielen eine Rolle. Anstrengungen sind wichtig, aber viele von uns unternehmen große Anstrengungen mit schlechten Ergebnissen. Es gibt jedoch Menschen, die wenig Anstrengungen unternommen haben und hervorragende Ergebnisse erzielen.

Die Natur ist ungerecht.

Aber wenn Sie mit fünf Jahren Schach lernen, sind Ihre Chancen besser, als wenn Sie mit zehn Jahren das Spiel lernen.

Wenn Sie als Kind viele Stunden vor dem Fernseher verbracht haben, haben Sie natürlich Ihre Intelligenz verschwendet.

Last, but not least, sorry für mein Englisch.

Fred
quelle
-1

Noch 2000 bis 3000 Elos bis zum perfekten Spiel, damit die aktuellen Top-Motoren ihre Stärke mindestens verdoppeln können. Schach ist eigentlich eher in den Kinderschuhen als in den späteren Stadien. Zum Beispiel würden aktuelle Top-Motoren nur einen von fünf besten Eröffnungszügen erraten. Noch ein langer Weg.

Lyudmil Tsvetkov
quelle
3
Wie kommst du zu dieser Nummer?
Annatar
Im Talkchess-Forum, dem fortschrittlichsten Schachforum im Internet, wurden verschiedene Tests durchgeführt und darüber berichtet, aber meine Beobachtungen weisen auch in diese Richtung. Auch durch den Vergleich der Motorbewertungen vor 20 Jahren und was in diesem Bereich noch verbessert werden könnte.
Lyudmil Tsvetkov