3
$\begingroup$

According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree:

A machine... would require over $10^{90}$ years to calculate the first move!

But his paper ends with a section entitled "Another Type of Strategy" and provides vague guidance on other options to solve chess.

Can it be proven whether chess can or cannot be solved with some algorithm (other than brute force) within some defined amount of time (for example, 100 years)?

$\endgroup$
1
  • 4
    $\begingroup$ Computers have sped up a lot since 1949. It's probably down to $10^{80}$ now. $\endgroup$
    – Pseudonym
    Nov 22 '17 at 0:15
2
$\begingroup$

You can't prove that chess can't be solved with less than 100 years time because you don't know what computers will be developed during that time. The only limits on computational speed we know are pretty ridiculous compared to what we can do today.

You might be able to prove that solving chess needs at least X many operations, but I don't know of any such results.

$\endgroup$
1
  • $\begingroup$ I also don't know if any work has been done to find the lower bounds for the number of operations required to solve chess. Shannon (in 1949) gave us some information on applying a brute-force evaluation. Unfortunately, his calculations give us no information on the lower limit for other types of analytical solution methods. Btw, the link you provided for the limits of computation is interesting, but in general, those bounds apply to technology that more than likely will require more than 100 years to become viable (i.e. "use a black hole as a data storage or computing device"). $\endgroup$ Sep 24 '17 at 2:15
0
$\begingroup$

Of course.

Well, maybe not in the span of a human lifetime yet, but there are lots of algorithms that given enough time, they would provide an answer!

Knowing if a problem is solvable or not doesn't depend on the amount of resources or people working on it, it only depends on the problem itself. It is a solvable problem, and it could eventually be solved. It's just that it's such a hard problem that it would take too long, and you would need an enourmous amount of memory. But even if you had only one person, or a team of millions of people, they could eventually find a way to always win the game.

$\endgroup$
14
  • $\begingroup$ My question doesn't pertain to yet. My question pertains to ever. If we had 100,000 researchers, and 100,000 programmers, and 100,000 mathematicians who specialize in game theory, and they had access to a large number of supercomputers, would their work be futile? Or is there a possibility they can solve chess? $\endgroup$ Jul 24 '17 at 13:01
  • $\begingroup$ Of course. Knowing if a problem is solvable or not doesn't depend on the amount of resources or people working on it, it only depends on the problem itself. It is a solvable problem, and it could eventually be solved. It's just that it's such a hard problem that it would take too long, and you would need an enourmous amount of memory. But they could (even tho they could find out that there is no way to always win, which would be as futile as not being able to find any answer whatsoever) $\endgroup$ Jul 24 '17 at 13:06
  • $\begingroup$ That's what I thought. I believe your newer comment is a better answer than the initial comment that you provided as an answer. (i.e your supplemental comment pertains to the question, whereas your original answer did not). Thanks for the answer. $\endgroup$ Jul 24 '17 at 13:10
  • $\begingroup$ Btw, learning that neither side has a way to win means that both sides can force a draw. So that is one of the possible answers to solving a game. $\endgroup$ Jul 24 '17 at 13:13
  • $\begingroup$ That's a bit complicated huh... If the computer played against a human, the game would probably end up in a state that would make the comp win. Being both computers, making the best move, they could end up always drawing... We don't know yet, so let's wait for a few more years to know if there's a solution to chess or not c: $\endgroup$ Jul 24 '17 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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