Will Chess Ever Be Solved by Computers?

I have had the distinct honor of previously having a chess coach who was both an International Master as well as a Ph.D in machine intelligence! We had extensive conversations about this exact topic, which strayed from chess to some actual philosophy, math, and statistics. I hope you find this as fascinating as I did!

It is very unlikely that chess will be brute-force solved for millions of years. Even with computing power advancing as fast as it is, the theoretical number of possible chess moves is simply too large for a computational solving. There is, however a possibility that chess could be solved through a weak-method, also known as a “sandwich method” which is a way to partially solve a chess game.

What is Brute-Force Solving?

Brute-force solving, or “strong solving” is listing out all of the literal move possibilities, and then all of the literal possible responses to those responses, so on and so forth. Brute force computation would even account for absolutely absurd positions like the following.

The number of possible chess moves, even ridiculous ones, which could possibly arise from a game is so unbelievably large, our brains literally cannot comprehend it. This is the so-called Shannon Number, which is 10¹²⁰. Ten to the one-hundred and twentieth power is a 1, with 120 zeroes behind it. To give you some idea how absurdly large this number is, let’s provide a few examples for context.

102 years	Fewer than 1% of humans reach this age.
103 miles	Distance between Miami, FL and Washington D.C.
104 maniacs	A pop band from the 80’s
105 dollars	Fewer than 20% of American households earn this amount of money annually
106 people	Population of Delaware
107 centimeters	Distance from San Francisco, CA to San Jose, CA (in centimeters!)
108 seconds	3.1 years (in seconds!)
109 miles	(A little bit further than) the distance between the sun and Saturn
1011 people	The estimated number of people that have ever existed
1015 seconds	31 million years
5*1020 positions	Estimated number of total positions in a game of checkers
1025 stars	Total number of stars in the entire universe
1078 atoms	Total number of atoms in existence in the universe
1079 atoms	Ten times the number of atoms in existence in the universe!
10120	The Shannon Number

Solved Games

The first game that was ever strongly solved was Tic Tac Toe. It is a forced draw from any opening move with optimal play. There is no forced win for either side. Pentago is a strongly-solved strategy game, where the first player to move has a forced win. Quatro is also strongly-solved and is a forced draw with optimal play.

Notice that few games are strongly solved, and all of them are very simple in complexity. However, we can add several other games to the solved list if we include “weakly solved” games. So what’s the difference?

A weakly solved game is a game where the ending, with just a few pieces remaining, is strongly solved. And a sequence of moves in the beginning of a game can lead, by force, to a strongly solved ending. So we pick moves at the beginning that can lead, by force, to a known ending. This is a weakly solved game, or a game solved by a “sandwich method.” To understand why chess is likely never going to be strongly solved, let’s take a look at a game similar to chess, but much simpler.

Checkers is Weakly Solved

Checkers also has a number of theoretical possibly positions (5*10²¹). Not all of them are known, but the game itself is weakly solved, because a known sequence of moves can drive the game into a strongly solved endgame. The strongly solved checkers endgame has 39 trillion positions! Compiling that was a heavy lift that would be impossible without computers. If weakly solving checkers was so difficult, what would it take to strongly solve the game?

If the human foot contained 50,000 checkers positions then you would have to walk on every square inch of Earth to strong solve every checkers position. Checkers has 500 billion billion possible positions. And chess is 10¹⁰⁰ more complex than that! For the record, checkers is a forced draw with optimal play. If you are interested, you can play versus Chinook, the world’s strongest chess engine that uses the weakly solved game information. But, fair warning it is literally impossible to beat it, but certainly possible to lose to it.

Solving Chess

So what would it take to brute force solve chess? Don’t worry, I did the math for you. So let’s say we want to write a chess book that shows every possible white move, with every possible black response. I think we already understand this book would be “pretty thick” but just how thick? First we would need to solve every chess position before we recorded it into a book. If we could network one billion computers together, and each computer was able to solve and record 1 billion chess positions per second, it would take 3.17*10⁹⁴ years for that computer network to solve every position.

Now let’s look at printing this book. I think we likely understand already this is not going to fit into one book. So let’s break out all the possible chess positions into, say, 100 million volumes. We will use small print and put 100,000 positions on each page. If we could use paper that’s 1/1000th of inch thick, then we would need a total of 10¹⁰² pages, and each volume would be 1.5*10⁹⁴ miles thick. And then there’s a matter of storage, as each volume would weigh, 17,846,306,832,821 tons. Good luck getting Amazon to provide free shipping on that.

So, I do think there’s a good chance chess will be weakly solved, but honestly probably not for another 10³ years. I don’t think it’s possible to brute force solve chess, there’s just way too many possible positions.