Wenn es eine Gewinnstrategie gibt, ist es für Weiß?

13

Bei zwei perfekten Spielern, Weiß und Schwarz, wissen wir nicht, ob das Spiel zwangsläufig unentschieden endet oder zwangsläufig gewinnt (für Schwarz oder Weiß).

Können wir jedoch beweisen, dass es für Weiß gilt, wenn es eine Gewinnstrategie gibt? Mit anderen Worten, können wir beweisen, dass Schwarz entweder verlieren oder ziehen muss?

Zufälliges Blau
quelle
1
Nein, wir können nicht beweisen, dass Schwarz verlieren oder ziehen muss. Vielleicht können wir mit Quantencomputern ...
Tony Ennis
1
Nebenbei bemerkt, sagte ein berühmter britischer Großmeister einmal im Scherz, dass in der Ausgangsposition beide Seiten in gegenseitigem Zugzwang sind. Aus diesem Grund ist Weiß der erste, der seine Position verändert, weshalb Schach zu Gunsten von Schwarz gelöst wird :)
Andrew Ng
Ich denke, Sie sollten angeben, dass Sie sich auf "Strategie" in einem spieltheoretischen Sinne beziehen, anstatt auf einen "Schach" -Sinn
David

Antworten:

8

Wenn es einen solchen Beweis gibt, hat ihn niemand gefunden, und ich bezweifle sehr, dass es einen solchen Beweis gibt (es ist schwer, sich eine mathematisch nachweisbare Strategie mit "garantiertem Draw" als Weiß vorzustellen). Man würde sicherlich erwarten, dass Weiß einen Vorteil hat, wenn jemand dies tut, aber es gibt auch einige Nachteile, die zuerst auftreten müssen (Sie müssen Informationen vor Ihrem Gegner preisgeben), so dass es theoretisch möglich ist, dass die Nachteile die Vorteile überwiegen. Die Wahrscheinlichkeit, dass dies der Fall ist, scheint jedoch infinitesimal zu sein.

dfan
quelle
3
Vielen Dank. Hast du eine Quelle?
Randomblue
1
Ich habe keine Quelle für die Behauptung, dass niemand einen solchen Beweis gefunden hat, außer dass es sehr unwahrscheinlich ist, dass ich davon nichts gehört hätte (zusätzlich zu den Gründen, aus denen es äußerst unwahrscheinlich ist, dass ein solcher Beweis existiert, wenn ich ihn gehört hätte) davon oder nicht).
dfan
Quelle: Wikipedia- Artikel "Schach lösen" . Hier ist ein relevantes Zitat: No complete solution for chess in either of the two senses is known, nor is it expected that chess will be solved in the near future. There is disagreement on whether the current exponential growth of computing power will continue long enough to someday allow for solving it by "brute force", i.e. by checking all possibilities. Obwohl es sich um eine vollständige Lösung handelt, bin ich mir ziemlich sicher, dass sie teilweise erwähnt hätten.
Daniel B
4
Ja, natürlich wissen wir, dass einer der Spieler eine Gewinn- / Zeichenstrategie hat, aber wir wissen nicht, ob dieser Spieler weiß oder schwarz ist. Die Frage lautete: "Können wir beweisen, dass es eine Gewinnstrategie für Weiß gibt?", Und wir haben diesen Beweis nicht.
dfan
4
White gibt Auskunft darüber, welchen Schritt er gemacht hat. Schwarz kann seinen Zug basierend auf diesen Informationen machen. Es gibt viele Informationsspiele, bei denen der zweite Spieler aus diesem Grund mit dem besten Spiel gewinnt. Das trivialste Beispiel ist ein Rock Paper Scissors-Spiel, bei dem die Spieler ihre Wahl nacheinander und nicht gleichzeitig offenlegen.
DFAN
4

Es kann theoretisch bewiesen werden, aber nicht mit der aktuellen Technologie.

Wenn Sie einen Brute-Force-Ansatz wählen, gibt es aufgrund der Anzahl der Positionen einige Schwierigkeiten.

Bei der Analyse der Shannon-Zahl wird vorgeschlagen, dass die Komplexität des Spielbaums für Spiele mit einer maximalen Länge von 80 Zügen mindestens 10 ^ 123 beträgt. Nehmen wir an, dass es für die Zwecke dieser Diskussion 10 ^ 123 ist.

10 ^ 81 = Geschätzte Anzahl der Atome im Universum

10 ^ 12 = Operationen pro Sekunde eines Terahertz-Prozessorkerns (Ihr Prozessor läuft wahrscheinlich mit ungefähr 1/300 dieser Geschwindigkeit.)

10 ^ 7 = gerundete Sekunden pro Jahr

10 ^ 12 = 1 Billion Jahre

Nehmen wir außerdem an, dass unsere Prozessoren eine Schachposition in nur einem Prozessorzyklus auswerten können.

Lassen wir also jedes Atom im Universum 1 Billion Jahre lang als Terahertz-Prozessorkern arbeiten.

Können wir jede Position für Spiele mit einer maximalen Länge von 80 auswerten?

Nein.

10 ^ 81 x 10 ^ 12 x 10 ^ 7 x 10 ^ 12 = 10 ^ 112

Wir sind nicht in der Lage, mit der Berechnung nur 0,0000000001% abzuschließen.

Mit fortschrittlichem Beschneiden (das Wegwerfen von schlechten Linien und ihren Nachkommen), besserer Technologie und etwas schlauem Programmieren ... vielleicht werden wir 40-max-Spiele in unserem Leben gelöst sehen! Wir können auch Positionen entfernen, die wir zuvor gesehen haben (wir können dort über die Transposition ankommen), aber denken Sie daran, dass es mindestens einen CPU-Zyklus dauert, um festzustellen, ob wir die Position zuvor bewertet haben!

Dies sollte Ihnen jedoch helfen, herauszufinden, warum es im Moment so weit außerhalb der Reichweite liegt.

Verweise

Brian Webster
quelle
Die Frage ist nicht, ob Schach effektiv gelöst werden kann, sondern ob wir nachweisen können, ob das (für uns unzugängliche) Ergebnis ein bestimmtes Merkmal hat (Schwarz hat keine Gewinnstrategie).
dfan
1
Dies beantwortet die Frage im Kontext von Brute Force. Die einfachste Methode, um eine Gewinnstrategie zu beweisen, besteht darin, jede Position zu analysieren. Ich gebe einen Kontext an, warum dies angesichts der gegenwärtigen Technologie nicht möglich ist.
Brian Webster
3

Theoretisch kann Schach "gelöst" werden, da es sich um ein "endliches" Spiel mit "perfekter Information" handelt. Genauer gesagt gibt es eine Strategie, bei der ein Spieler einen garantierten Gewinn hat oder beide Spieler bei perfektem Spiel ein garantiertes Unentschieden haben. Hier ist ein technischer Artikel zu den Grundkonzepten der Spieltheorie für diejenigen, die sich für die Besonderheiten interessieren. Im Wesentlichen jedes Spiel, das "perfekte Informationen" hat,dh jeder Spieler kann alle Spielsteine ​​sehen und ist sich zu jedem Zeitpunkt des Spiels aller erlaubten Bewegungen der Spielsteine ​​bewusst (ein Gegenbeispiel für ein perfektes Informationsspiel wäre ein Kartenspiel, bei dem Sie die Spielsteine ​​Ihres Gegners nicht sehen können Hand), ** eine begrenzte Anzahl von Spielern und eine begrenzte Anzahl von legalen Zügen **, dh das Spiel geht nicht auf unbestimmte Zeit weiter, dann hat es eine garantierte Gewinn- oder Ziehungsstrategie für einen der Spieler.

In der Praxis haben wir weder die Technologie noch die Intelligenz (ok, wenn vielleicht die besten Schachköpfe von heute bei der Suche nach der Strategie zusammengearbeitet haben, ist möglicherweise genügend Intelligenz erforderlich. Vielleicht.) Und Zeit, dies manuell zu tun.

Um Ihre Frage zu beantworten: Ja, es gibt eine Gewinn- (oder Zeichenstrategie). Nein, wir wissen nicht, ob es für Weiß oder für Schwarz ist.

Ja, Schach ist dazu verdammt, eines Tages gelöst zu werden. Aber wir werden die Technologie (meiner Meinung nach die einzige Möglichkeit, dies zu tun) für viele, viele Jahrzehnte (hoffentlich sogar Jahrhunderte) nicht haben.

chubbycantorset
quelle
3
Der erste Teil war implizit zu meiner Frage.
Randomblue
Ich habe diesen Artikel gelesen. Es scheint mir, dass die Rückwärtsinduktion (Zermelos Theorem) beinahe intuitiv erscheint, wenn man sagt: "Das Schachspiel muss immer enden. Wenn man genug Voraussicht hat, muss entweder Spieler 1 oder Spieler 2 eine Forcierungsstrategie haben."
ldog
Natürlich gibt es keinen Einblick in das Spiel selbst! Wenn Sie sich vorstellen, dass ein Anfänger gegen die beste Schachengine der Welt spielt, gewinnt oder zieht der Anfänger immer, vorausgesetzt, er hat unbegrenzte Möglichkeiten zum Rückgängigmachen.
Hund
Nur ein Kommentar zu "Schach ist dazu verdammt, eines Tages gelöst zu werden" - dies gilt natürlich, wenn Moores Gesetz (im Grunde genommen exponentielles Wachstum der Rechenleistung) unbegrenzt gilt. Bei der gegenwärtigen Geschwindigkeit würde dies dazu führen, dass Schach in etwa 250 Jahren gelöst werden könnte. Nicht einmal die wildesten Hochrechnungen (Diskontierung von Singularitätstheorien) halten dieses Gesetz so lange (z. B. geht Intel davon aus, dass sich das Gesetz aufgrund von Quantentunneln vor 2020 verflacht). Ich muss mich auch fragen, was für eine post-menschliche Zivilisation diese Verarbeitungsleistung haben würde, nur um Schach zu lösen :)
Daniel B
1
Nein. Selbst wenn diese Köpfe zusammenarbeiten, würden wir nicht
David
0

Meiner Meinung nach liegt die Gewinnstrategie im Kopf des Spielers. Weil dein nächster Zug vom Zug deines Gegners abhängt.

user17445
quelle
Willkommen bei Chess Stack Exchange! Beachten Sie, dass wir es im Allgemeinen vorziehen, Meinungen mit konkreten Beweisen zu untermauern. Wir sind eine objektive Q & A-Site und kein Diskussionsforum. Bitte haben Sie einen Moment Zeit, um die Tour zu machen .
Glorfindel
0

Es ist sehr unwahrscheinlich, dass Schwarz einen erzwungenen Gewinn erringen kann, da jede Linie, die als Gewinn für Schwarz angezeigt wird, als Weiß in einem höheren Tempo gespielt werden kann. Wenn zum Beispiel 1.e4, c5 ein erzwungener Gewinn für Schwarz ist, könnte Weiß 1.c4 in umgekehrter Reihenfolge für dieselbe Linie spielen.

Savage47
quelle
-2

Weiß hat einen kleinen Vorteil, weil es zuerst geht. Wir sprechen von 2% mehr Siegen auf der Ebene der Großmeister. Dieser geringfügige Vorteil beginnt sich im Verlauf des Spiels auszugleichen. In einem perfekt gespielten Spiel werden sie höchstwahrscheinlich unentschieden spielen.

Tyler Langan
quelle
-5

Weiß hätte den Vorteil, das Spiel zu eröffnen, aber ich bezweifle, dass es jemals eine Gewinnstrategie gibt, wie Sie vorgeschlagen haben.

Thang Do
quelle
4
Bitte lesen Sie die Frage noch einmal.
Randomblue
@Randomblue Sie verwenden das Wort "Strategie" in einem Schachforum, also nehmen die Leute an, dass Sie es eher mit seiner Schachbedeutung als mit seiner spieltheoretischen Bedeutung verwenden
David