Can Chess be Solved?

I use to follow the Quora chess space to catch up on what people ask about chess. Questions about solving chess are frequent, but not as frequent as "What's the best opening?". The most popular answer, and probably the most correct one (to both those questions) is "We don't know". It's a logical question though - chess is a complete information game, meaning that the pieces, the squares and the rules of chess are fully available to both players att all times. In theory, all complete information games can be solved (Tic-tac-toe is easy to solve).

A game of chess can be described as a path of linked positions, where each move leads to a new position. The game continues until a decisive position (check mate or draw) is reached. Now, if we can chart all possible paths (like in the tic-tac-toe example), we would have solved the game. The problem with this approach is that there are 10^120 (a one followed by 120 zeros) possible legal positions in chess (that's a guess known as the Shannon number). 

As a comparison, the known universe consists of 10^80 atoms (also a guess, the Eddington number). If we could build a computer that use every atom in the universe to store chess positions and their relations (ignoring limitations such as the speed of light), we would need to store 10^40 positions in each atom.

This doesn't stop people from trying. The Chinese Chess Cloud Database now (at the time of writing) has  48 782 458 363 positions. That's an 11-digit number, to be compared with Shannon's 121 digits.

This leads us the the conclusion that chess won't be solved by brute force anytime soon. 

Another try is the Perfect Play strategy. The idea behind this is that in every position, there is one (or a few) perfect move that leads to the best possible outcome for that player regardless of the response by the opponent. In the starting position, the Chess Cloud Database offers four candidates for perfect play: d4, e4, Nf3 and c4. That reduces the number of possible positions after White's first move from 20 to 4, and after Black's first from 400 to 16. That might sound promising, but even using a Perfect Play strategy, the number of possible positions will be be far beyond what's solvable.

There is another problem with Perfect Play - we cannot know what "perfect" is. Perfect Play is only useful in solved games, so it can't be used to solve chess. The four candidate opening moves have all scored well, but that doesn't prove that any of them is a perfect move. The worst opening move according to CCDB is g4. It has a poor performance score, and also breaks a number of established opening principles. Still, g4 might be the Perfect Move, even if it's highly unlikely. We just don't know.

The Perfect Play strategy is what modern chess engines like Stockfish use. By pruning away all branches that don't look perfect, Stockfish can calculate 30-40 moves in less than an hour on a standard PC. This almost always produce good moves, but very rarely a fantastic move (they are always in the pruned branches).

The most promising attempt to solve chess is the retrograde analysis. That means starting from an end position (check mate or draw), and working backwards. So far, this work has progressed to solving any seven-piece ending. However, Shannon will prevent a solution with this approach too. The most effcient way (to date) to store retrograde analysis is the Syzygy tablebase. Here's the current state of affairs:

An eight-piece tablebase is in the works, but it would require 2 PB of disk space. That's a lot. To solve chess, a 32-piece tablebase would be required, and Shannon says no long before that. 

Takeaway

It looks like chess will remain unsolved, and continue to be a struggle between mere mortals with all our flaws and shortcomings. The outcome of the game will still be decided by mistakes. That's good!