17

The theory is that there are more that 10^40 positions, and a computer that works with an atomic scale has to be impossibly large(As in galaxy-scale large), and well beyond our current level of knowledge.

But now, quantum computers will soon be available. This computer can have 2^n, instead of n bytes of space, because of quantum states. With this new large place for tablebases, will chess be solved? Of course, this will take more breakthroughs in the future, but will we see 8 piece databases in the following years?

Many questions on the possibility of solving chess revolve on the fact that we don't have enough computer space to fill them. Will quantum computers change the status quo?

  • 10
    "But now, quantum computers will soon be available" Source on this? – Cleveland Aug 21 '14 at 13:09
  • 5
    As a physics student, let me assure you quantum computers will not be used to play chess anytime soon. – Danu Aug 21 '14 at 14:36
  • 3
    @Spork you could say the same about "A friend of mine showed me an article" – Cleveland Aug 21 '14 at 14:48
  • 3
    @Cleveland that one is so obvious I doubt many people would put a lot of faith in it. The friend was probably talking about 2015 Xbox games anyway neowin.net/news/… – Spork Aug 21 '14 at 14:52
  • 3
    A quantum computer does not work by storing classical information worth of 2^n bits in n qubits and using that like a classical computer would. – JiK Aug 21 '14 at 21:59
23

I'm not an expert on quantum computation but my understanding is that quantum computers are not expected to be useful for chess.

Quantum algorithms are very good at finding needles in haystacks: the three big quantum algorithms are Shor's factorization algorithm, Grover's database lookup algorithm and the Deutsch–Jozsa algorithm, which essentially determines whether a long list of numbers is either all zeroes, all ones or half of each. All of these problems can be seen as examples of "I've hidden something: you must find it quickly." In factorization, I've "hidden" the prime factors and you must find them; in database lookup, I've hidden an entry with a given key in a large unsorted table and you must find it; in the problem solved by Deutsch–Jozsa, I might have placed a large number of zeroes in a table of ones but, with a classical algorithm, when you've looked at half the table and seen only ones, you might have just been unlucky and looked at the "wrong" half. Note also that all of these problems could be solved quickly by an unrealistically parallel classical computer: you could try all the factors in parallel, look at all the database entries in parallel and look at all the values in the zero-one table in parallel.

Solving chess isn't even slightly like any of these problems. It's a fundamentally sequential activity. Whether or not my move is any good depends on what you do in response. Whether or not your response is any good depends on what I do in response to that. And so on. You might imagine you can do the first ply of the search by taking a superposition of the possible moves. But then what do you do at the second ply? You can't just take the superposition of all the positions we could be in after two ply because that has forgotten the tree structure. For example, consider this very artificial position, with white to move:

[FEN "1k6/ppp5/5Q2/7q/8/8/PPP5/1K6 w - - 0 2"]

If we forget the tree structure, Black is very happy. He says, "In two ply, the best position I can be in is that I deliver checkmate!" This is true but, of course, White will never allow that, since White's best move is one that prevents Black from checkmating (or doing anything else). Chess isn't about figuring out the best move you can possibly make in N ply: it's about figuring out the best move that your opponent will allow you to play in N ply. Quantum computers don't seem to be good at this back-and-forth, give-and-take reasoning. We don't even know how to solve chess with an unrealistically parallel classical computer.

  • 1
    I wouldn't put it past quantum computing... we've seen major progress in other graph search type problems, like using quantum annealing to solve the traveling salesman problem. Maybe some clever person can figure out how to do something similar in chess? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476 – tbischel Aug 23 '14 at 6:49
  • 2
    @tbischel But chess, an adversarial tree search, doesn't look at all like TSP, which is another needle-in-a-haystack problem. Also, note that DWave's claims are, shall we say, quite controversial. There are at least two groups who have written quantum annealing simulations that outperform DWave when run on an ordinary laptop, for example. – David Richerby Aug 23 '14 at 8:11
  • 2
    I don't deny that there currently doesn't exist a quantum equivalent to say alpha beta search... but given that quantum computing algorithms are still in their infancy, that doesn't mean they never will be. For example: web.ist.utl.pt/luis.tarrataca/publications/… As for DWave, I recognize the controversy exists since their model for quantum computing is different than standard models... I would approach them cautiously, although they do have customers like Google, NASA, and the NSA. – tbischel Aug 23 '14 at 16:45
  • Wouldn't quantum annealing solve chess? – Lambda Oct 11 at 3:08
-1

It should be verbalized what exactly means 'a solution to chess'.
Then we will understand what exactly we may get out from the hypothetical black-box chess solver (BBCS).
We will feed BBCS with the chess board position.
BBCS will spit out an integer number X. 0 means there is no solution for that position (or the position itself is not legit) Another integer number means the least number of moves to transform the original position into a checkmate position in a non-cooperative chess game. The ultimate solution to chess will be just an integer number which means the exact number of moves from the chess starting position to a checkmate position. Is it a task for quantum computer? IDK. As David Richerby lookup - chess is not for QC. But when we must find a single integer number X to declare "mate in X moves" it seems more like to find a needle in haystack... Am I wrong?

-3

Fair warning: This answer contains speculative numbers, and may be off by orders of magnitude.

It's just possible, but unlikely.

The issue isn't necessarily with whether or not quantum computers will be able to "parallelize" to that extent. The problem is one of simple physics, one that even quantum computers can't realistically get around. Put simply, there's a limited number of calculations that can ever be performed. This was answered by Thomas Pornin at Security.SE, and I quote some of his answer here:

Let's look at a more mundane perspective. It seems fair to assume that, with existing technology, each elementary operation must somehow imply the switching of at least one logic gate. The switching power of a single CMOS gate is about C*V2 where C is the gate load capacitance, and V is the voltage at which the gate operates. As of 2011, a very high-end gate will be able to run with a voltage of 0.5 V and a load capacitance of a few femtofarads ("femto" meaning "10-15"). This leads to a minimal energy consumption per operation of no less than, say, 10-15 J. The current total world energy consumption is around 500 EJ (5*1020 J) per year (or so says this article). Assuming that the total energy production of the Earth is diverted to a single computation for ten years, we get a limit of 5*1036, which is close to 2122.

Then you have to take into account technological advances. Given the current trend on ecological concerns and the peak oil, the total energy production should not increase much in the years to come (say no more than a factor of 2 until year 2040 -- already an ecologist's nightmare). On the other hand, there is technological progress in the design of integrated circuits. Moore's law states that you can fit twice as many transistors on a given chip surface every two years. A very optimistic view is that this doubling of the number of transistor can be done at constant energy consumption, which would translate to halving the energy cost of an elementary operation every two years. This would lead to a grand total of 2138 in year 2040 -- and this is for a single ten-year-long computation which mobilizes all the resources of the entire planet.

That is the absolute maximum number of elementary operations that can possibly be done. Now let's look at how many chess positions there are...

Let's do some quick numbers. Each of the 64 squares can be empty or hold one of 12 different pieces (R, K, B, Q, K, and P in black and white), so the total number of positions that you could set is at most

1364 = 196053476430761073330659760423566015424403280004115787589590963842248961.

That is about 2 x 1071 different positions. Of course this is a huge overestimate, because most positions are fake (we should eliminate positions with three or more kings, nine or more white pawns, pawns in the eighth rank, quadruple checks, etc). Let's take the square root:

1332 = 442779263776840698304313192148785281,

or about 5 x 1035. By taking the square root we are pretending that for each legal position there is a chess Universe worth of distinct fake positions. This is probably an underestimate, so the true answer must be somewhere in between these two numbers. Now we can confidently say that computers cannot study every legal position in a reasonable time. Even the "tiny" 1332 is too large...

That smallest number ends up being somewhere around 2120 or so.

Let's assume that we represent our boards with a 64-byte string. (Practically it would be handled a little differently, but let's go with it for now.) If I'm remembering my math correctly, a quantum computer would be able to represent this with an 8-byte string, or 64 bits. This leaves us with a total of 2126 to 2130 elementary operations just to store each legal and possible position.

Look at that for a moment. We're not doing anything useful with the information, we're just storing it. And to do so we are mobilizing the resources of the entire planet. Never mind where the storage is physically located. Ignore the whole issue of cooling. Set aside the issue of data transmission. We are diverting enough power to illuminate the Moon just to store the positions.

At the most optimistic of expectations, a quantum computer might be able to solve chess, at the cost of the entire planet's resources. Realistically, that will not happen.

  • 1
    Quantum computers don't have any problems with the capacity. The 2^n vs n thing, so 2^120 positions in a 64 byte string, is 2^126 positions, or 2^129. a quantum computer needs only 129 quanta particles for that(theoretically). Since we will have the technology for quantum computing until then, probably the computation won't take all planetarian resources, or all planetarian space. THe computer that can do this will probably be no larger than a big room. – MikhailTal Aug 21 '14 at 20:43
  • 1
    This seems like it might be a misunderstanding of how quantum computers work. As I understand it, qbits represent a superposition of all states, where a single computation (read gate transition) operates on all states simultaneously, returning a result probabilistically. The argument above applies to more traditional CMOS paradigms. – tbischel Aug 21 '14 at 20:45
  • I think the real question is can graph searching fit into a quantum computing paradigm... I've heard that there are good results solving the traveling salesman problem with quantum computers, so maybe there is an approach – tbischel Aug 21 '14 at 20:51
  • 2
    @JonathanGarber How do you get 2^126 or 2^130? And I don't understand how CMOS gates are related to estimating the power requirements of a quantum computer. – JiK Aug 21 '14 at 21:57
  • 3
    This answer is fundamentally wrong because it's entirely about classical computers and the question is about quantum computers. – David Richerby Aug 21 '14 at 22:51

protected by Phonon Mar 18 at 21:41

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.