3

Mathematicians have categorized chess as a trans-computational problem. A transcomputational problem is one in which a computer would need to exceed the size of the earth in order to have the processing power to complete the theoretical problem through brute force. Also, to solve the game of chess means that everything would have to be decided on the first move and any subsequent deviation from the 'correct line' would result in a guaranteed loss. It is categorically different than having an engine who can win every game. Other games have been 'solved' like checkers, where the national championship has seen the exact line of play for numerous years in a row.

Also worth noting, the expression 'transcomputational' comes from Bremermann's limit - http://en.wikipedia.org/wiki/Bremermann%27s_limit - read up if you are unfamiliar.

My question is whether or not this is an accurate diagnosis? Does the math take into account the growing sophistication of chess engines, or even computers for that matter? Will we ever have a chess engine that can 'solve' the game of chess without exceeding the size of the earth. I guess to simplify my question; what is the context of this mathematical limit?

Improve this question
1
  • I'm skeptical they can prove that a computer would need to exceed the size of the earth. How do they know how fast computers will be in the future? Also, as already pointed out, deviating from the correct line would definitely not be a guaranteed loss. For the game to be solved it is quite simple, from each position we would have to know if either side would win, draw, or lose with best play.
    – Alan
    Commented Jun 20, 2014 at 14:03

1 Answer 1

Reset to default
1

Also, to solve the game of chess means that everything would have to be decided on the first move and any subsequent deviation from the 'correct line' would result in a guaranteed loss.

Then this will never happen, even theoretically. Chess does not have that much instability. In many positions multiple moves are equally good. This is both obvious and has been proven (see tablebases).

Assuming now that you are just talking about "playing theoretically optimally" (if it is possible to win it wins, otherwise if it is possible to draw it draws), then it is certainly possible that a computer merely the size of the earth could play perfect chess, but it is exceedingly unlikely that a computer the size of the earth could prove that it was playing perfect chess. No one has been able to prove things about the state of a chess position except by, effectively, brute force (except for special cases where the situation is simple enough that you can reason logically about it, such as bishop and wrong rook pawn).

(The context of the mathematical limit is the number of possible chess positions, which has been estimated to be on the order of 10^43.)

Improve this answer
3
  • +1 for the insight between a non-existent perfect line and theoretically optimum play. What I am more curious about, however, is whether or not theoretically optimum play will be a possibility without earth-size computers. I guess you are saying no because we 'only' have brute force available to us currently. Do you think that is apt to change with some element that shifts the context of the problem laterally?
    – maxwell
    Commented Jun 20, 2014 at 1:57
  • I thought we were allowed to have an earth-size computer, just no bigger. I am in fact saying the opposite; I'm saying that theoretically optimal play with an earth-size computer may be possible, it just wouldn't be possible to prove that it's optimal.
    – dfan
    Commented Jun 20, 2014 at 14:11
  • I understand that but I guess what I am asking is whether or not there are other alternatives besides creating an earth-size computer? I stumbled upon this thread in hopes of learning more about our current level of sophistication in regards to AI chess.stackexchange.com/questions/1003/… I am asking whether or not this limit is subject to change given innovation in computer efficiency or a new method of tackling the problem
    – maxwell
    Commented Jun 20, 2014 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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