# 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?

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