Datenbank aller möglichen Schachzüge

12

Stellen Sie sich vor, es gibt eine Schachdatenbank für jede mögliche Bewegung und Position. Diese Datenbank enthält alle möglichen Züge vom Eröffnungs- bis zum Endspiel.

Wenn ich mit meiner Intuition gegen eine Schachmaschine gespielt habe, kann sie vorhersagen, durch welchen Zug ich verlieren und gewinnen werde.

Dies bedeutet, dass keine "Schachmaschine" erforderlich ist, da alle möglichen Züge bereits aufgezeichnet sind.

Wenn eine solche Datenbank existiert, hätte sie folgende Vorteile:

  • In schnellen Blitzspielen verliert die Schach-Engine definitiv gegen die Schach-Möglichkeit, die Datenbank zu verschieben.
  • Wir können genau wissen, welche Eröffnung mehr Gelegenheit hat, gegen die anderen zu gewinnen.

Oder wenn eine solche Datenbank noch nicht existiert hätte, könnten wir eine mathematische Berechnung aller möglichen Züge vom Öffnen bis zum Ende des Spiels haben.

Wäre es möglich, dass eine solche Datenbank existiert?

Ahmad Azwar Anas
quelle
4
Nein, mit einer denkbaren Technologie ist das nicht möglich.
Tony Ennis
Ich wandere eine Weile .. Und schafft es immer noch nicht. Du hast recht. Ahaha.
Ahmad Azwar Anas
Viel Glück beim Aufbau einer Datenbank mit mehr Bytes als Atomen im Universum
David

Antworten:

31

Ich glaube, Ihre Frage läuft im Wesentlichen auf das Thema hinaus, ob es möglich ist, Schach vollständig zu "lösen". Wikipedia hat einen ausgezeichneten Artikel zum Thema, der Ihnen einen guten Überblick geben soll.

Zusammenfassend wird die Anzahl der möglichen Spielvariationen im Schach auf 10 ^ 120 geschätzt. Dies ist eine erstaunlich große Zahl. Zum Vergleich wird angenommen, dass die Anzahl der Atome im beobachtbaren Universum auf etwa 10 ^ 80 geschätzt wird . Mit anderen Worten, wenn Sie das gesamte beobachtbare Universum als Festplatte verwenden würden, müssten Sie immer noch 10 ^ 40 Kombinationen von Schachspielen auf jedem Atom speichern, um einfach alles zu speichern. Es ist unnötig zu erwähnen, dass dies so weit über unsere derzeitigen und vorhersehbaren Technologien hinausgeht, dass die meisten Menschen dies für völlig unmöglich halten.

Schachendspiele sind wesentlich weniger komplex und wir haben einen Punkt erreicht, an dem es möglich ist, alle möglichen Kombinationen für fünf- und sechsteilige Endspiele zu berechnen . Dies sind in der Regel große Unternehmungen von Forschern mit Zugang zu Supercomputern, und die daraus resultierenden Endspieldatenbanken sind riesig (in der Größenordnung von Hunderten von Terabyte). Jedes Mal, wenn ein neues Stück hinzugefügt wird, steigt die Größe und Komplexität der Berechnungen exponentiell an, was bedeutet, dass wir in absehbarer Zukunft erwarten können, dass sich diese Ergebnisse nur um wenige Stücke erweitern.

Daniel B.
quelle
Jetzt stelle ich mir vor, dass es Algorithmen gibt, die End Game Table darstellen. ^^
Ahmad Azwar Anas
2
@AhmadAzwarAnas Nun, ich denke, einfache werden bereits in Schach-Engines verwendet, und die vollständigeren werden hinzugefügt, wenn die Technologie dies zulässt. In Bezug auf einen Algorithmus könnte man einen Endspieltisch "komprimieren", indem man ihn auf Muster analysiert und sie in eine Reihe von Regeln verallgemeinert, die eindeutig zu einem Ergebnis führen. Höchstwahrscheinlich wäre dieses Regelwerk jedoch immer noch absolut massiv, da winzige Abweichungen (wie etwa Opposition oder Nicht-Opposition) das Ergebnis des Spiels verändern können.
Daniel B
@AhmadAzwarAnas eigentlich, warum nicht nur ein Algorithmus für Schach? In jedem verlorenen Spiel muss es einen Zug geben, der falsch ist, oder? dh der Zug, vor dem es einen Weg gab, unabhängig vom Zug des Gegners nicht zu verlieren, aber danach ist dies nicht mehr wahr. Dann muss der Algorithmus diese Bewegungen nur noch identifizieren, damit Sie sie vermeiden können.
Michael
1
@Michael es ist schwieriger als das - woher kannst du wissen, dass es einen Weg zum Gewinnen gibt, unabhängig davon, was der Gegner bewegt? bestenfalls gibt es nur 50% der Zeit, denn wenn eine Person gewinnt, muss die andere verlieren. Lassen Sie es tatsächlich auf die Startpositionen zurückkehren - damit es einen Pfad weiter unten im Spiel gibt, sollte es zu diesem Zeitpunkt einen "absoluten Gewinnpfad" geben - wenn wir das herausgefunden haben, warum sollte dann jemand die verlorene Farbe mehr spielen? , wissend, dass sie verlieren werden, unabhängig davon, was sie bewegen? warum sollte jemand mehr Schach spielen, wenn wir das könnten?
user2813274
1
+1 aber deine Analyse ist falsch. Um eine Tischbasis zu speichern, müssen Sie nur jede Position speichern, nicht jedes mögliche Spiel. Shannon schätzt, dass es ungefähr 10 ^ 43 Positionen gibt , verglichen mit ungefähr 10 ^ 50 Atomen auf der Erde . Sie können also Schach lösen, indem Sie die ganze Erde in einen Computer verwandeln .
David Richerby
6

Nein, eine solche Datenbank wäre nicht möglich. Für die Berechnung wäre ein unglaublich großer Computer erforderlich, und die Berechnung würde so lange dauern, dass Ihr Computer nicht lange genug existiert, um die Aufgabe abzuschließen.

Claude Shannon schätzte, dass es ungefähr 10 43 mögliche Positionen im Schach gibt und Ihre Datenbank das Ergebnis all dieser Positionen speichern müsste (dies wäre im Wesentlichen eine 32-Mann- Tabellenbasis ). Es wird jedoch geschätzt, dass die Erde nur etwa 10 50 Atome enthält. Selbst wenn Sie eine Speicherzelle aus nur 10.000.000 Atomen aufbauen könnten, würden Sie dennoch einen Computer von der Größe der Erde benötigen, um alle Positionen zu speichern.

Aber solch ein riesiger Computer bringt große Probleme mit sich. Der Erddurchmesser beträgt ungefähr 12.800 Kilometer und das Licht benötigt ungefähr 43 ms, um diese Distanz zu überwinden. Das bedeutet , dass, wenn ein Taktzyklus dauert länger als 43 ms, dann nur nicht zu tun haben Sie schrecklich Clock Skew , aber verschiedene Teile des Computers ist nicht einmal auf dem gleichen Taktzyklus. Wenn Sie dies vermeiden, wird Ihre Taktrate auf etwa 23,5 Hz begrenzt (nicht GHz oder MHz; nur Hz). Selbst wenn Sie eine Position in einem einzigen Taktzyklus vollständig auswerten könnten, würde Ihr Computer etwa 4,3 x 10 41 Sekunden benötigen , um seine Aufgabe zu erledigen. Das sind ungefähr 1,4x10 34 Jahre. Das sind 14 Millionen Milliarden Milliarden Milliarden Jahre.

Astrophysiker glauben, dass das Universum in 1,4x10 34 Jahren radikal anders aussehen wird als jetzt. Bis dahin werden Sterne längst nicht mehr existieren, und selbst Elemente, die in keinem sinnvollen Sinne radioaktiv sind, werden in großem Umfang radioaktiv zerfallen sein. Sogar die Protonen, die Atomkerne bilden, haben einen signifikanten radioaktiven Zerfall erfahren. Ihr erdgroßer Computer wird also einfach nicht mehr existieren.

David Richerby
quelle
2
Du meinst also, es gibt eine Chance?
Bpromas
4

Ich denke, Daniels Antwort ist ausgezeichnet (+1), aber ich möchte trotzdem ein paar Gedanken hinzufügen.

Würde eine 32-teilige Tischbasis wirklich Schachmaschinen ersetzen? Die Antwort ist definitiv nein!

Um gutes Schach zu spielen, werden mehr Informationen benötigt, als ob ein Zug gewinnt, zieht oder verliert. Natürlich wäre eine solche Datenbank unschlagbar, aber sie würde auch kaum jemanden schlagen.

Um stark Schach zu spielen, reicht es nicht aus, in jeder Runde einen nicht verlierenden Zug zu wählen. Von den vielen Ziehzügen in jeder Position gibt es nur wenige, die den Gegner wirklich unter Druck setzen.

Bestehende Schachengines werden durch den Zugriff auf Tabellenbasen erheblich gestärkt. Aber wenn die Datenbanken wachsen, wird die Zugriffszeit zu einem verbotenen Faktor, lange bevor jedes Atom im Universum als Speicher verwendet wird ;-).

Ich denke, Ihre Schlussfolgerung ist einfach falsch: Eine solche Datenbank würde niemals verlieren und kaum jemals gewinnen. Es würde uns nichts über Eröffnungen sagen, außer dass fast alle von ihnen Unentschieden sind. Wir könnten wahrscheinlich neue Algorithmen entwickeln, um diese Datenbank abzubauen und interessante Schlussfolgerungen über alle Arten von Positionen zu ziehen, aber ich denke, dies würde die Schachwelt nicht wesentlich verändern.

BlindKungFuMaster
quelle
Sie haben falsch verstanden, was die Datenbank enthalten würde. Jeder mögliche Zug wird entweder als "Wenn ich dies spiele, kann mein Gegner einen Gewinn erzwingen, was auch immer ich als nächstes tue", "Wenn ich dies spiele, kann ich einen Gewinn erzwingen, was auch immer mein Gegner als nächstes tut" oder "Unentschieden" markiert werden. Sie würden also nicht "nicht verlierende Züge in jeder Runde" spielen: Sie würden in jeder Runde erzwungene Gewinne spielen, solange ein solcher Zug existiert.
David Richerby
Nun, eigentlich habe ich genau verstanden, was die Datenbank enthalten würde ... Der Punkt, den ich ansprechen wollte, ist, dass in hochrangigen Schachspielen "Es gibt keine erzwungenen Siege!" in mehr als 90% der Positionen. Und Sie brauchen weit mehr Informationen als "dieser Zug zieht und dieser Zug verliert", um tatsächlich eine Gewinnposition gegen einen anständigen Spieler zu erreichen.
BlindKungFuMaster
1
Um ein Beispiel zu geben: In der Startposition wäre die einzige Information in der Datenbank aller Wahrscheinlichkeit nach "Alle Züge ziehen". Sie wären also ganz alleine. Und wenn Sie ganz alleine sind, wie können Sie eine Gewinnposition gegen einen starken Spieler erreichen? Die Antwort lautet: Sie nicht. Ihre Position wird immer schlechter, bis Sie der einzigen Zeichnungslinie folgen.
BlindKungFuMaster
Nein, das stimmt nicht. Es ist trivial, einen Gewinn zu erzielen. Berechnen Sie einfach alle möglichen Züge von der aktuellen Position, überprüfen Sie die resultierenden Positionen in der DB und wählen Sie eine aus, die gewinnt oder zieht. Wenn Ihre aktuelle Position "Sie gewinnen" ist, gibt es per Definition mindestens eine in den nächsten Positionen, die "Sie gewinnen" ist. und wenn Ihre aktuelle Position "Unentschieden" ist, wird mindestens eine der nächsten Positionen "Unentschieden" sein (und möglicherweise einige "Sie gewinnen", wenn Ihr Gegner nicht perfekt spielt).
Ignacio Calvo
Der Punkt ist, dass die aktuelle Position normalerweise nicht "Sie gewinnen" ist. Zum Beispiel ist es sehr wahrscheinlich, dass es in der Startposition keinen erzwungenen Sieg gibt.
BlindKungFuMaster
2

Ich denke, eines Tages wird Schach gelöst sein. Warum? Denn vor nicht allzu langer Zeit war es seltsam und undenkbar, Schach gegen einen Computer zu spielen! Wie könnte man einen Computer trainieren, um Schach zu spielen? Nun, sie haben es geschafft! (Außerdem war die Idee eines Computers seltsam ...) Mein Punkt ist, es könnte seltsam erscheinen, weil wir noch nie davon gesehen oder gehört haben. Das können wir uns nicht so leicht vorstellen. Die Technologie wächst jedoch exponentiell. Es würde mich nicht wundern, wenn es in naher Zukunft (über 10 Jahre) in der einen oder anderen Form gelöst wird.

Ryan Orr
quelle
Das Hindernis bei der Lösung von Schach ist die buchstäblich astronomische Datenmenge, die Sie sortieren müssen. Shannon schätzte, dass es ungefähr 10 ^ 43 Positionen im Schach gibt und Sie das Ergebnis für jede dieser Positionen speichern müssten. Um dies ins rechte Licht zu rücken, enthält die Erde ungefähr 10 ^ 50 Atome . Selbst wenn Sie eine Speicherzelle aus 10.000.000 Atomen aufbauen könnten, müssten Sie dennoch die gesamte Erde in eine Speicherbank umwandeln, um das Ergebnis zu speichern!
David Richerby
1
@ DavidRicherby Nehmen wir an, Schach ist ein Unentschieden mit bestem Spiel. Dann gibt es für jede weiße Bewegung eine angemessene Antwort für Schwarz. Auf den nächsten weißen Zug hat Schwarz auch eine angemessene Reaktion und so weiter. Es ist denkbar, dass der Bau eines solchen "Ziehbaums" viel weniger als 10 ^ 43 Positionen erfordert.
Dag Oskar Madsen
2
@DagOskarMadsen Ja, es ist möglich, dass das Speichern des Baums viel weniger Speicher erfordert (obwohl immer noch eine astronomische Menge). Die derzeitige Technik zum Erstellen solcher Bäume besteht jedoch darin, eine retrograde Analyse von allen Endpositionen aus durchzuführen, was die Erstellung einer vollständigen Datenbank darüber erfordert, was an jeder Position zu tun ist, zumindest als Zwischenstufe.
David Richerby
Es tut mir leid, Ihnen mitteilen zu müssen, dass Sie falsch liegen! @DagOskarMadsen Aber wenn Sie nicht wissen, wie Sie die "unangemessenen" Antworten widerlegen können, können Sie wirklich behaupten, Sie hätten das Spiel gelöst?
David
1

Als ich Anfang der 1980er Jahre auf dem College war, las ich in einem Spieltext, dass, wenn ein Computer einen Zug planen, bewerten und ausführen könnte, jeder einzelne Zug vom Beginn des Spiels bis zu allen möglichen Schlussfolgerungen alle 1/3 einer Nanosekunde. Das sind ungefähr 3 Milliarden Züge pro Sekunde. Um dies für jedes denkbare Ergebnis zu tun, würde es 10 bis 120 Jahre dauern, bis es abgeschlossen ist. Und wer muss so lange warten?

Noch eine erstaunliche Statistik? Sie haben offensichtlich von einem Googol gehört? Nicht DAS Google, sondern die Nummer? Es ist 10 zur 100. Potenz. Eine 10 gefolgt von 100 Nullen. Stellen Sie sich nun den Googolplex vor. Das sind 10 nach der googol'ten Kraft.

Ich habe gelesen, dass es im bekannten Universum nicht genug von irgendetwas gibt , nicht einmal Atome, um die Verwendung des Googleplex zu erfordern. Tatsächlich ist sogar der Googol zu groß, um irgendetwas zu beschreiben. Sie sollten sich einige der erstaunlichen Trivia über diese Zahlen ansehen.

Jon
quelle
-2

Ja, ich denke es wäre möglich. Aber nur, wenn die Datenbank eher einem neuronalen Netzwerk gleicht und Bewegungen ausführt, durch die sie verloren geht, und sie löscht. Diese Berechnung basiert darauf, alle möglichen Aktionen in einem Schachspiel im ersten Zug zu potenzieren (mit mir zu ertragen), um 100 oder so etwas zu bewegen. Wenn wir die Wiederholungen loswerden, könnte ((Ke3 Ke4 Ke3 Ke4) Looping) 10 ^ 120 wahrscheinlich so etwas wie 10 ^ 70 werden. Das ist immer noch lächerlich groß, aber wenn wir es irgendwie in ein 4D-Flugzeug kodieren könnten (was ich für möglich halte), wäre es ein Kinderspiel.

user19889
quelle
2
Willkommen bei Chess ! Bitte nehmen Sie an der Tour teil, während Sie gerade dabei sind. Ihr Beitrag wird möglicherweise abgelehnt, da er eher eine Meinung als eine Antwort ist, wie wir es hier erwarten. Weitere Informationen finden Sie im Hilfeartikel Antworten .
Glorfindel
Ich bin kein Schachspieler, und ich gehöre auch nicht zu den Leuten, die Sie abgelehnt haben, aber ich habe gelesen, dass es 10 ^ 43 verschiedene Positionen gibt. Nur weil Sie eine Methode haben, mit der einige Daten herausgefiltert werden können, warum nehmen Sie automatisch an, dass dies möglich ist? Ich denke, Sie unterschätzen genau, wie groß diese Datenbank sein könnte. Dies geht so weit über den Rahmen der modernen Computertechnologie hinaus, dass ich mir nicht vorstellen kann, dass wir uns in einem Jahrhundert auf einem guten Weg befinden. Aber willkommen bei SE Chess. (Und begrüßen Sie mich auch, ich nehme an: P)
Joe Majewski