6

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?

  • very much related: chess.stackexchange.com/q/7878/9025 – Herb Wolfe Dec 19 '17 at 22:32
  • 6
    Are you sure you have really understood what exponential complexity means? – leftaroundabout Dec 19 '17 at 22:48
  • 1
    "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 '17 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 '17 at 12:36
  • 2
    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 '17 at 12:37
7

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)

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.

  • 1
    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 '18 at 23:14
  • @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 '18 at 23:59
4

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!

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.