# How far from solving chess are we?

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?

• Are you sure you have really understood what exponential complexity means? Commented Dec 19, 2017 at 22:48
• "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? Commented Dec 19, 2017 at 23:15
• @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. Commented Dec 20, 2017 at 12:36
• 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”. Commented Dec 20, 2017 at 12:37
• 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. Commented Dec 21, 2017 at 2:07