Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-02T23:14:00.000Z
Answers.Text: 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.
Answers.UserDisplayName: Niklas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-02T23:59:57.340Z
Answers.Text: @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
Answers.UserDisplayName: chessprogrammer
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T01:40:36.980Z
Answers.LastActivityDate: 2017-12-21T01:40:36.980Z
Answers.UserDisplayName: chessprogrammer
Answers.Body: <p>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! </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T06:28:02.843Z
Answers.LastActivityDate: 2017-12-21T19:19:19.837Z
Answers.LastEditDate: 2017-12-21T19:19:19.837Z
Answers.UserDisplayName: zaifrun
Answers.Body: <p>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.</p>
  
  <p>Based on <a href="https://chess.stackexchange.com/a/7879/9025">this answer</a>, 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.</p>
  
  <p>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 <a href="https://en.wikipedia.org/wiki/Shannon_number" rel="noreferrer">the Shannon Number</a>)</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T06:36:10.080Z
Answers.LastActivityDate: 2017-12-20T06:36:10.080Z
Answers.UserDisplayName: Herb
Body: <p>See here: <a href="https://chess.stackexchange.com/questions/19455/does-there-exist-an-algorithm-that-would-play-perfect-chess-if-given-infinite-pr?newreg=d4fad04da836482f9e275532d3ad5740">Does there exist an algorithm that would play perfect chess if given infinite processing power?</a></p>
  
  <p>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.</p>
  
  <p>At that point we would be able to definitely state whether perfect play leads to a White Victory, Black Victory, or Draw.</p>
  
  <p>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 <em>that</em> 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".</p>
  
  <p>But we also have a LOT of brute-force computing power available.</p>
  
  <p>How long would it take Google or Amazon to add another layer to our endgame tables, if they chose to?</p>
  
  <p>How long would it take to just SOLVE chess, if humanity chose to?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T22:32:53.307Z
Comments.Text: very much related: https://chess.stackexchange.com/q/7878/9025
Comments.UserDisplayName: Herb
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T22:48:34.803Z
Comments.Text: Are you sure you have really understood what _exponential complexity_ means?
Comments.UserDisplayName: leftaroundabout
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T22:52:33.127Z
Comments.Text: @leftaroundabout I could just as easily ask "Are you sure you have really understood how much computing power humanity has available, and how quickly THAT is growing"?
Comments.UserDisplayName: Brondahl
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T22:53:10.430Z
Comments.Text: @leftaroundabout the same solution approach is valid in chequers, and is still exponential, but that's been solved. It's just a question of the coefficients.
Comments.UserDisplayName: Brondahl
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T23:15:43.540Z
Comments.Text: *"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?
Comments.UserDisplayName: gented
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-20T12:36:20.430Z
Comments.Text: @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. https://www.electronicsweekly.com/news/moores-law-still-law-2017-09/ In the long term, we should expect available computing power to grow at most quadratically.
Comments.UserDisplayName: leftaroundabout
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-20T12:37:28.943Z
Comments.Text: 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”.
Comments.UserDisplayName: leftaroundabout
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T02:07:26.250Z
Comments.Text: 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 (https://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.
Comments.UserDisplayName: Allure
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T09:14:00.193Z
Comments.Text: Going from N to N+1 pieces grows the tablebase by a factor of more than 100. Humanity can't choose to solve chess.
Comments.UserDisplayName: RemcoGerlich
Tags: <tablebases>
Title: How far from solving chess are we?
ThreadText: # How far from solving chess are we?
  
  (Asked by: username_0 on 2017-12-19)
  
  See here: [Does there exist an algorithm that would play perfect chess if given infinite processing power?](https://chess.stackexchange.com/questions/19455/does-there-exist-an-algorithm-that-would-play-perfect-chess-if-given-infinite-pr?newreg=d4fad04da836482f9e275532d3ad5740)
  
  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?
  
  **Tags:** tablebases
  
  > **Comments:**
  > **username_1**: very much related: https://chess.stackexchange.com/q/7878/9025  
  > **username_2**: Are you sure you have really understood what _exponential complexity_ means?  
  > **username_0**: @username_2 I could just as easily ask "Are you sure you have really understood how much computing power humanity has available, and how quickly THAT is growing"?  
  > **username_0**: @username_2 the same solution approach is valid in chequers, and is still exponential, but that's been solved. It's just a question of the coefficients.  
  > **username_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?  
  > **username_2**: @username_0 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. https://www.electronicsweekly.com/news/moores-law-still-law-2017-09/ In the long term, we should expect available computing power to grow at most quadratically.  
  > **username_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”.  
  > **username_4**: 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 (https://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.  
  > **username_5**: Going from N to N+1 pieces grows the tablebase by a factor of more than 100. Humanity can't choose to solve chess.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2017-12-20. Score: 11 | Accepted answer
  
  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](https://chess.stackexchange.com/a/7879/9025), 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](https://en.wikipedia.org/wiki/Shannon_number))
  
  
  ---
  
  ### Answer by username_6 on 2017-12-21. Score: 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.
  
  > **Comments:**
  > **username_7**: 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.  
  > **username_6**: @username_7 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  
  
  ---
  
  ### Answer by username_8 on 2017-12-20. Score: 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!
  
  
  ---
  
  