Can quantum computer become perfect chess player?
Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)
$\begingroup$
$\endgroup$
-
$\begingroup$ Can you define "perfect chess player"? $\endgroup$ – ShadSterling Oct 6 '15 at 19:03
-
1$\begingroup$ @Polyergic One which always win whenever there is a winning strategy $\endgroup$ – porton Oct 6 '15 at 19:25
-
$\begingroup$ A non-quantum computer can be a perfect chess player, given enough time and memory $\endgroup$ – jmite Apr 20 '16 at 2:04
$\begingroup$
$\endgroup$
I've already answered essentially this question, on Chess Stack Exchange. The executive summary is that chess doesn't seem particularly well-suited to quantum computation's strengths so there's no particular reason to believe that a quantum computer would be any better at it than a classical one.
answered Oct 6 '15 at 14:29
-
1$\begingroup$ A more "computer science-y" answer could take in to account that it is generally believed that quantum computers can't solve $NP$-complete problems efficiently, and since chess is $EXPTIME$-complete it is even more unlikely that quantum computers are good at chess. $\endgroup$ – Tom van der Zanden Oct 6 '15 at 14:54
-
2$\begingroup$ @TomvanderZanden Generalized chess, on an $n\times n$ board is EXPTIME-complete but we're only interested in ordinary chess, on an $8\times 8$ board, which can be solved in constant time. It's not clear how observations about the complexity of generalized chess can be used to argue about $8\times 8$ chess. $\endgroup$ – David Richerby Oct 6 '15 at 15:55
$\begingroup$
$\endgroup$
Quantum computers can evaluate game trees asymptotically faster than classical computers, but this advantage is not sufficient to solve chess.
Wikipedia gives an estimate of $10^{123}$ for the game tree complexity of chess. The best known classical algorithm can solve a randomized NAND tree of size $N$ in $O(N^{0.793})$ steps. The quantum algorithm mentioned in the blog post I linked to can do it in roughly $O(N^{0.5})$ steps. Ignoring constant factors and other important things, this roughly means the quantum algorithm can explore and solve the chess game tree in $\sqrt{10^{123}} \approx 10^{62}$ steps instead of $10^{92}$ steps.
Unfortunately, $10^{62}$ is still obscenely gigantic. It is "consume all the entropy in the galaxy just to run the computation" levels of absurd. Maybe there's a tractable algorithm out there that can play chess perfectly, by relying on the fact that its game tree has more structure than an arbitrary NAND tree, but just switching from classical to quantum isn't enough.
-
$\begingroup$ Slight correction: 0.793 is the correct exponent for randomized game tree search with N leaves. $\endgroup$ – Kyle Jones Oct 11 '15 at 18:22
-
$\begingroup$ @KyleJones Added 'randomized' to the answer. (Of course chess is not a randomized tree, and this falls under the "other important things" clause I used to helpfully avoid all responsibility for errors.) $\endgroup$ – Craig Gidney Oct 11 '15 at 19:47
-
$\begingroup$ I meant 0.793 as a fix for 0.753, but mentioning randomization is also a good edit. $\endgroup$ – Kyle Jones Oct 11 '15 at 20:41
-
$\begingroup$ @KyleJones Could you give a reference (including page number) for that? The paper Scott linked to says $\Theta(n^{0.753})$ near the top-right of the third page (labelled page 31). $\endgroup$ – Craig Gidney Oct 11 '15 at 23:05
-
$\begingroup$ The Randomized Algorithms textbook at the bottom of page 30. $\endgroup$ – Kyle Jones Oct 12 '15 at 18:43
