Die Theorie besagt, dass es mehr als 10 ^ 40 Positionen gibt und dass ein Computer, der mit einer atomaren Skala arbeitet, unglaublich groß sein muss (wie bei Galaxien) und weit über unseren derzeitigen Wissensstand hinaus.
Aber jetzt werden bald Quantencomputer verfügbar sein. Dieser Computer kann aufgrund von Quantenzuständen 2 ^ n anstelle von n Byte Platz haben. Wird Schach mit diesem neuen großen Platz für Tischgestelle gelöst? Natürlich wird dies in Zukunft weitere Durchbrüche bringen, aber werden wir in den nächsten Jahren 8 Stück Datenbanken sehen?
Viele Fragen zur Möglichkeit, Schach zu lösen, drehen sich um die Tatsache, dass wir nicht genug Computerraum haben, um sie zu füllen. Ändern Quantencomputer den Status Quo?
engines
tablebases
computer-chess
MikhailTal
quelle
quelle
Antworten:
Ich bin kein Experte für Quantencomputer , aber mein Verständnis ist , dass Quantencomputer sind nicht für Schach , nützlich zu sein erwartet.
Quantenalgorithmen können sehr gut Nadeln in Heuhaufen finden: Die drei großen Quantenalgorithmen sind Shors Faktorisierungsalgorithmus , Grovers Datenbanksuchalgorithmus und der Deutsch-Jozsa-AlgorithmusDies bestimmt im Wesentlichen, ob eine lange Liste von Zahlen entweder alle Nullen, alle Einsen oder die Hälfte von jeder ist. Alle diese Probleme können als Beispiele für "Ich habe etwas versteckt: Sie müssen es schnell finden." Bei der Faktorisierung habe ich die Primfaktoren "versteckt", und Sie müssen sie finden. Bei der Datenbanksuche habe ich einen Eintrag mit einem bestimmten Schlüssel in einer großen nicht sortierten Tabelle versteckt, und Sie müssen ihn finden. In dem von Deutsch-Jozsa gelösten Problem hätte ich vielleicht eine große Anzahl von Nullen in eine Einstabelle gesetzt, aber mit einem klassischen Algorithmus hätten Sie vielleicht einfach Pech gehabt, wenn Sie die Hälfte der Tabelle betrachtet und nur Einsen gesehen hätten und schaute auf die "falsche" Hälfte. Beachten Sie auch, dass all diese Probleme durch einen unrealistisch parallelen klassischen Computer schnell gelöst werden könnten: Sie könnten alle Faktoren parallel ausprobieren,
Das Lösen von Schach ist mit keinem dieser Probleme vergleichbar. Es ist eine grundsätzlich sequentielle Aktivität. Ob mein Schritt gut ist oder nicht, hängt davon ab, was Sie als Antwort tun. Ob Ihre Antwort gut ist oder nicht, hängt davon ab, was ich als Antwort darauf tue. Und so weiter. Sie könnten sich vorstellen, dass Sie die erste Schicht der Suche durchführen können, indem Sie die möglichen Züge überlagern. Aber was machst du dann bei der zweiten Lage? Sie können nicht einfach alle Positionen überlagern, die wir nach zwei Lagen einnehmen könnten, da dies die Baumstruktur vergessen hat. Betrachten Sie zum Beispiel diese sehr künstliche Position, in der sich Weiß bewegen kann:
Wenn wir die Baumstruktur vergessen, ist Schwarz sehr glücklich. Er sagt: "In zwei Lagen ist die beste Position, in der ich sein kann, dass ich Schachmatt gebe!" Dies ist wahr, aber natürlich wird Weiß dies niemals zulassen, da der beste Zug von Weiß ein Zug ist, der Schwarz daran hindert, Schachmatt zu setzen (oder etwas anderes zu tun). Beim Schach geht es nicht darum, den besten Zug zu finden, den Sie in N Ply machen können. Es geht darum, den besten Zug zu finden, den Ihr Gegner Ihnen erlauben wird, in N Ply zu spielen. Quantencomputer scheinen in diesem Hin und Her, Geben und Nehmen nicht gut zu sein. Wir wissen nicht einmal, wie man Schach mit einem unrealistisch parallelen klassischen Computer löst.
quelle
Es sollte verbalisiert werden, was genau "eine Lösung für Schach" bedeutet.
Dann werden wir verstehen, was genau wir aus dem hypothetischen Black-Box-Schachlöser (BBCS) herausholen können.
Wir werden BBCS mit der Schachbrettposition füttern.
BBCS gibt eine Ganzzahl X aus. 0 bedeutet, dass es für diese Position keine Lösung gibt (oder die Position selbst ist nicht legitim). Eine andere Ganzzahl bedeutet, dass die geringste Anzahl von Zügen erforderlich ist, um die ursprüngliche Position in eine Schachmattposition in einer nicht kooperativen Position umzuwandeln Schachspiel. Die ultimative Lösung für Schach ist nur eine ganze Zahl, dh die exakte Anzahl von Zügen von der Schachstartposition zu einer Schachmattposition. Ist es eine Aufgabe für den Quantencomputer? IDK. Als David Richerby Lookup - Schach ist nicht für QC. Aber wenn wir eine einzelne Ganzzahl X finden müssen, um "Mate in X Moves" zu deklarieren, scheint es eher so, als ob wir eine Nadel im Heuhaufen finden ... irre ich mich?
quelle
Faire Warnung: Diese Antwort enthält spekulative Zahlen und kann um Größenordnungen abweichen.
Es ist nur möglich, aber unwahrscheinlich.
Die Frage ist nicht unbedingt, ob Quantencomputer in diesem Ausmaß "parallelisieren" können oder nicht. Das Problem ist die einfache Physik, an der sich selbst Quantencomputer nicht realistisch orientieren können. Einfach gesagt, es gibt eine begrenzte Anzahl von Berechnungen, die jemals durchgeführt werden können. Dies wurde von Thomas Pornin bei Security.SE beantwortet , und ich zitiere einige seiner Antworten hier:
Das ist die absolut maximale Anzahl von Elementaroperationen, die möglicherweise ausgeführt werden können. Nun schauen wir uns an, wie viele Schachpositionen es gibt ...
Diese kleinste Zahl liegt irgendwo bei 2 120 oder so.
Nehmen wir an, dass wir unsere Boards mit einer 64-Byte-Zeichenfolge darstellen. (Praktisch würde es ein wenig anders gehandhabt, aber lassen Sie uns jetzt damit weitermachen.) Wenn ich mich richtig an meine Mathematik erinnere, wäre ein Quantencomputer in der Lage, dies mit einer 8-Byte-Zeichenfolge oder 64-Bit-Zeichenfolge darzustellen. Damit haben wir insgesamt 2 126 bis 2 130 Grundoperationen , um jede rechtliche und mögliche Position zu speichern .
Sehen Sie sich das einen Moment an. Wir tun nichts nützlich die Informationen, sind wir nur zu speichern es. Und dafür mobilisieren wir die Ressourcen des gesamten Planeten . Egal, wo sich der Speicher befindet. Ignorieren Sie das gesamte Problem der Kühlung. Legen Sie das Problem der Datenübertragung beiseite. Wir leiten genug Energie ab, um den Mond zu beleuchten und nur die Positionen zu speichern.
Wenn die Erwartungen am optimistischsten sind, kann ein Quantencomputer möglicherweise Schach auf Kosten der Ressourcen des gesamten Planeten lösen. Realistisch wird das nicht passieren.
quelle