9

See here: Does there exist an algorithm that would play perfect chess if given infinite processing power?

With infinite power, we could trivially recursively check every board state for winnability, and gradually work back towards knowing the winnability of the opening position.

At that point we would be able to definitely state whether perfect play leads to a White Victory, Black Victory, or Draw.

I don't know what the maximal tablebases currently are, but it seems like if you have a perfect tablebases for N-pieces, then exhasutively testing a single N+1 piece position shouldn't be that hard, and you would in the process also cross out a bunch of other N+1 positions. So the difficulty isn't specifically in evaluating positions at the next N, it's merely "there are a lot of those, and exponentially more of the next layer".

But we also have a LOT of brute-force computing power available.

How long would it take Google or Amazon to add another layer to our endgame tables, if they chose to?

How long would it take to just SOLVE chess, if humanity chose to?

Improve this question
10
  • 8
    Are you sure you have really understood what exponential complexity means?
    – leftaroundabout
    Dec 19, 2017 at 22:48
  • 3
    "it seems like if you have a perfect tablebases for N-pieces, then exhasutively testing a single N+1 piece position shouldn't be that hard" this statement is clearly wrong, where have you taken it from?
    – gented
    Dec 19, 2017 at 23:15
  • 1
    @Brondahl Moore's law, while having been surprisingly accurate in the past, is not really a law but an empirical trend. It cannot go on forever, at least not with classical computers of the principle as we understand it today. In fact it's been struggling for a couple of years now. electronicsweekly.com/news/moores-law-still-law-2017-09 In the long term, we should expect available computing power to grow at most quadratically.
    – leftaroundabout
    Dec 20, 2017 at 12:36
  • 3
    As for draughts: indeed that has exponential complexity too and is therefore “unsolvable” as well, but as the rules are very simple and symmetry-rich there's a lot you can do to prune the tree growth at each step. Each step in effect only multiplies the size by a small factor. Therefore, the exponential needs quite a few steps to really “kick in” (by Taylor expansion, exp looks locally linear) and the 8×8 size could indeed be exhaustively covered. Chess has much less symmetry, thus each step increases the space by a factor of rather ~100, which means it's immediately “hard exponential”.
    – leftaroundabout
    Dec 20, 2017 at 12:37
  • 1
    This might be relevant: in 2012, Chessbase posted an April Fool's prank that claimed to have solved the King's Gambit. In their retraction article (en.chessbase.com/post/the-chebase-april-fool-s-prank), there's the following quote from Rybka programmer Vas Rajlich: "If processing power doubles every 18 months for the next century, we'll have the resources to [solve the King's Gambit] around the year 2120, plus or minus a few decades." In other words, we're a long long way away from solving chess.
    – Allure
    Dec 21, 2017 at 2:07

3 Answers 3

Reset to default
11

Currently most of the 7-piece Lomonosov tablebases have been created. the only ones that weren't, were the K vs. K + 5 pieces. Those took about 6 months using the Lomonosov supercomputer.

Based on this answer, creating the 8-piece tablebases could take 100x the time it took to create the 7-piece, give or take an order of magnitude. Extrapolating, that would mean it could take 5/50/500 years, and probably on the lower end, 5-50 years for a supercomputer, and likely longer for Google or Amazon.

After a certain point, however, storage becomes a problem, as the number of game-tree possibilities surpasses the number of atoms in the universe. (see the Shannon Number)

Improve this answer
7

Not only are we far from solving chess, in all likelihood chess will never be solved. There are more possible positions in chess than atoms in the known universe, so not only would in take forever (literally) to traverse the tree, but it would be impossible to store. At current cpu speeds, even with infinite storage, the universe would die of heat death before the computer could solve chess.

Improve this answer
2
  • 3
    Upvoted, however the argument is not airtight: For example Antichess has more positions than atoms in the known universe as well, but it was solved regardless.
    – Niklas
    Dec 2, 2018 at 23:14
  • 1
    @Niklas correct. For games that have many forced moves, or where many moves are irrelevant to the final outcome, this argument would not hold true. However for chess, neither of those things is true
    – chessprogrammer
    Dec 2, 2018 at 23:59
5

We are very very far from solving chess. We would need a 32 man tablebase for that. Currently, we have a 7 man tablebase. Each increase of 1 step, requires exponentially more computing power and storage space. Short of some incredible break-through in storage or computing power, solving chess is many many years in the future. I don't see it happening in this century. Your question reminds me of the old story about the peasant asking for 1 rice corn for the first square on the board, 2 for the next, 4 for the next, and 8, and so on. This illustrates nicely the problem of exponentiality. Try calculating the total weight of the rice the peasant was asking for!

Improve this answer

Your Answer

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

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