Werden Quantencomputer das Schach lösen?

18

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?

MikhailTal
quelle
10
"Aber jetzt werden bald Quantencomputer verfügbar sein" Quelle dazu?
Cleveland
5
Lassen Sie mich versichern, dass Sie als Physikstudent in Kürze nicht mehr mit Quantencomputern Schach spielen werden .
Danu
3
@Spork könnte man das gleiche über "Ein Freund von mir hat mir einen Artikel gezeigt" sagen
Cleveland
3
@Cleveland, dass man so offensichtlich ist, ich bezweifle, dass viele Leute viel Vertrauen in sie setzen würden. Der Freund sprach wahrscheinlich über 2015 Xbox-Spiele sowieso neowin.net/news/…
Spork
3
Ein Quantencomputer funktioniert nicht, indem er klassische Informationen im Wert von 2 ^ n Bits in n Qubits speichert und diese wie ein klassischer Computer verwendet.
JiK

Antworten:

24

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:

NN - NN

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.

David Richerby
quelle
1
Ich würde es nicht als Quanten-Computing bezeichnen ... wir haben große Fortschritte bei anderen Problemen mit dem Graphensuchtyp gesehen, wie z. Vielleicht kann eine kluge Person herausfinden, wie man etwas Ähnliches im Schach macht? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476
tbischel
2
@tbischel Aber Schach, eine kontroverse Baumsuche, sieht überhaupt nicht wie TSP aus, ein weiteres Problem, bei dem die Nadel im Heuhaufen steckt. Beachten Sie auch, dass die Behauptungen von DWave ziemlich kontrovers sind . Es gibt mindestens zwei Gruppen, die Quantenglühsimulationen geschrieben haben, die DWave übertreffen, wenn sie beispielsweise auf einem normalen Laptop ausgeführt werden.
David Richerby
2
Ich bestreite nicht, dass es derzeit kein Quantenäquivalent gibt, um Alpha-Beta-Suche zu sagen ... aber angesichts der Tatsache, dass Quantencomputer-Algorithmen noch in den Kinderschuhen stecken, heißt das nicht, dass sie es niemals sein werden. Zum Beispiel: web.ist.utl.pt/luis.tarrataca/publications/… Was DWave betrifft, erkenne ich die Kontroverse an, da sich ihr Modell für das Quantencomputing von den Standardmodellen unterscheidet. Ich würde sie vorsichtig angehen, auch wenn sie es tun haben Kunden wie Google, die NASA und die NSA.
tbischel
Würde Quantenglühen nicht Schach lösen?
Lambda
-1

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?

user21914
quelle
-3

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:

Schauen wir uns eine profane Perspektive an. Es scheint fair anzunehmen, dass bei vorhandener Technologie jede Elementaroperation irgendwie das Schalten von mindestens einem Logikgatter implizieren muss. Die Schaltleistung eines einzelnen CMOS- Gatters beträgt ungefähr C * V 2, wobei C die Gate-Lastkapazität und V die Spannung ist, bei der das Gate arbeitet. Ab 2011 kann ein sehr High-End-Gate mit einer Spannung von 0,5 V und einer Lastkapazität von wenigen Femtofarad betrieben werden ("Femto" bedeutet "10 -15 "). Dies führt zu einem minimalen Energieverbrauch pro Betrieb von nicht weniger als beispielsweise 10 –15 J. Der derzeitige Gesamtenergieverbrauch der Welt liegt bei etwa 500 EJ (5 × 10 20J) pro Jahr (oder so sagt dieser Artikel ). Unter der Annahme, dass die gesamte Energieproduktion der Erde für zehn Jahre auf eine einzige Berechnung umgeleitet wird, erhalten wir eine Grenze von 5 * 10 36 , was in der Nähe von 2 122 liegt .

Dann müssen Sie den technologischen Fortschritt berücksichtigen. Angesichts des aktuellen Trends in Bezug auf ökologische Bedenken und den Höhepunkt der Ölproduktion sollte die Gesamtenergieproduktion in den kommenden Jahren nicht wesentlich ansteigen (sagen wir nicht mehr als den Faktor 2 bis zum Jahr 2040 - bereits ein Albtraum eines Ökologen). Auf der anderen Seite gibt es technologischen Fortschritt beim Design von integrierten Schaltkreisen. Das Moore'sche Gesetz besagt, dass alle zwei Jahre doppelt so viele Transistoren auf einer bestimmten Chipoberfläche angebracht werden können. Eine sehr optimistische Ansicht ist, dass diese Verdoppelung der Anzahl der Transistoren bei konstantem Energieverbrauch erfolgen kann, was zu einer Halbierung der Energiekosten eines Elementarbetriebs alle zwei Jahre führen würde. Dies würde zu einer Gesamtsumme von 2 138 führenim Jahr 2040 - und das für eine einzige zehnjährige Berechnung, die alle Ressourcen des gesamten Planeten mobilisiert .

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 ...

Lassen Sie uns ein paar schnelle Zahlen machen. Jedes der 64 Felder kann leer sein oder eines von 12 verschiedenen Teilen enthalten (R, K, B, Q, K und P in Schwarzweiß), sodass Sie höchstens die Gesamtzahl der Positionen festlegen können

13 64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

Das sind ca. 2 x 10 71 verschiedene Positionen. Dies ist natürlich eine große Überschätzung, da die meisten Positionen falsch sind (wir sollten Positionen mit drei oder mehr Königen, neun oder mehr weißen Bauern, Bauern auf dem achten Rang, Vierfach-Schecks usw. streichen). Nehmen wir die Quadratwurzel:

13 32 = 442779263776840698304313192148785281,

oder ungefähr 5 x 10 35 . Indem wir die Quadratwurzel ziehen, geben wir vor, dass es für jede Rechtsposition ein Schachuniversum gibt, das unterschiedliche falsche Positionen enthält. Dies ist wahrscheinlich eine Unterschätzung, daher muss die wahre Antwort irgendwo zwischen diesen beiden Zahlen liegen. Jetzt können wir zuversichtlich sagen, dass Computer nicht jede Rechtsposition in angemessener Zeit untersuchen können. Auch der "winzige" 13 32 ist zu groß ...

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.

Jonathan Garber
quelle
1
Quantencomputer haben keine Probleme mit der Kapazität. Das 2 ^ n vs n-Ding, also 2 ^ 120 Positionen in einer 64-Byte-Zeichenfolge, ist 2 ^ 126 Positionen oder 2 ^ 129. Ein Quantencomputer benötigt dafür (theoretisch) nur 129 Quantenteilchen. Da wir bis dahin die Technologie für Quantencomputer haben werden, wird die Berechnung wahrscheinlich nicht alle planetarischen Ressourcen oder den gesamten planetarischen Raum in Anspruch nehmen. Der Computer, der dies kann, wird wahrscheinlich nicht größer als ein großer Raum sein.
MikhailTal
1
Dies scheint ein Missverständnis der Funktionsweise von Quantencomputern zu sein. So wie ich es verstehe, stellen qbits eine Überlagerung aller Zustände dar, bei der eine einzelne Berechnung (Lese-Gate-Übergang) alle Zustände gleichzeitig bearbeitet und wahrscheinlich ein Ergebnis zurückgibt. Das obige Argument gilt für traditionellere CMOS-Paradigmen.
tbischel
Ich denke , die wirkliche Frage ist grafisch darstellen kann passen in einen Quanten suche Paradigm - Computing ... Ich habe gehört , dass es gute Ergebnisse , die das Reiseproblem mit Quantencomputern zu lösen, vielleicht gibt es ein Ansatz
tbischel
2
@ JonathanGarber Wie bekommst du 2 ^ 126 oder 2 ^ 130? Und ich verstehe nicht, wie CMOS-Gatter mit der Abschätzung des Leistungsbedarfs eines Quantencomputers zusammenhängen.
JiK
3
Diese Antwort ist grundsätzlich falsch, da es sich ausschließlich um klassische Computer handelt und es sich um Quantencomputer handelt.
David Richerby