Database of every possible move in chess

Question

Imagine that there is a chess database of every possible move and position. This database contains all possible moves from opening to end game.

If I played using my intuition against a chess engine, it can predict which move will make me lose and win.

So this means there is no need for a "chess engine" because all of the possible moves are already recorded.

If such a database exists it would have the following advantages:

• In fast blitz games, chess engine will definitely lose against chess possibility move database.
• We can exactly know which opening will have more opportunity to win against the others.

Or if such a database didn't already exist we could have a mathematical calculation of all possible moves from opening till end game.

Would it be possible for such a database to exist?

Answer 1

I believe your question essentially boils down to the topic of whether it is possible to completely "solve" chess. Wikipedia has an excellent article on the topic which should give you a good overview.

To summarise, the number of possible game variations in chess is estimated to be 10^120. This is a staggeringly huge number, for comparison, consider that the number of atoms in the observable universe is estimated to be around 10^80. In other words, if you were using the entire observable universe as your hard drive, you'd still need to store 10^40 combinations of chess games on each atom, in order to simply store it all. Needless to say, this is so far beyond our current and forseeable technologies that most people consider it to be completely impossible.

Chess endgames are considerably less complex, and we've got to a point where it's possible to calculate all possible combinations for five-piece and six-piece endgames. These are typically huge undertakings done by reasearchers with access to supercomputers, and the resulting endgame databases are huge (on the order of hundreds of terabytes). Each time a new piece is added, the size and complexity of the calculations goes up exponentially, which means that in the forseeable future, we can expect these results to expand by only a few pieces.

Answer 2

No, it would not be possible for such a database to exist. Calculating it would require an infeasibly large computer and the calculation would take so long that your computer wouldn't exist for long enough to complete the task.

Claude Shannon estimated that there are around 10⁴³ possible positions in chess and your database would need to store the outcome of all of these (this would be, essentially, a 32-man tablebase). However, it is estimated that the Earth contains only about 10⁵⁰ atoms so, even if you could build a memory cell out of just 10,000,000 atoms, you would still need a computer the size of the Earth just to store all the positions.

But such a huge computer brings big problems. The earth's diameter is about 12,800 kilometres and light takes about 43ms to cross that distance. That means that, if a clock cycle lasts longer than 43ms, then not only do you have horrible clock skew but different parts of your computer aren't even on the same clock cycle. Avoiding this limits your clock speed to about 23.5Hz (not GHz or MHz; just Hz). Even if you could completely evaluate a position in a single clock cycle, that means your computer would take about 4.3x10⁴¹ seconds to complete its task. That's about 1.4x10³⁴ years. That's 14 million billion billion billion years.

Astrophysicists believe that the universe will look radically different in 1.4x10³⁴ years than it does now. By then, stars will have long ago ceased to exist and even elements that are in no meaningful sense radioactive will have undergone large amounts of radioactive decay. Even the protons that form atomic nuclei will have undergone significant radioactive decay. So your earth-sized computer simply won't exist any more.

Answer 3

I think Daniel's answer is excellent (+1) but want to add a few thoughts anyway.

Would a 32-piece tablebase really replace chess engines? The answer is definitely no!

To play good chess, more information is needed than whether a move is winning, drawing or losing. Of course such a database would be unbeatable, but it would hardly beat anybody either.

To play chess strongly it is not enough to chose a non-losing move at every turn. Of the many drawing moves in each position, there are only a few that put real pressure on the opponent.

Existing chess engines are made significantly stronger by accessing tablebases. But as the databases grow, the access time would become a prohibiting factor long before using every atom in the universe for memory ;-).

So I think your conclusion is just wrong: Such a database would never lose and hardly ever win. It wouldn't tell us anything about openings except that almost all of them are draws. We could probably devise new algorithms to mine this database and come up with interesting conclusions about all kinds of positions, but I think this wouldn't change the world of chess in any significant way.

Answer 4

I think someday chess will be solved. Why? Because, well, not that long ago, playing chess against a computer was weird and unthinkable! How could you train a computer to play chess? Well, they did it! (In addition, the idea of a computer was strange...) My point is, it might seem weird because we've never seen of or heard of it. Its not something we can easily imagine. But technology is expanding at an exponential rate. I wouldn't be surprised if in the near future (10+ years) that it is solved, in one form or another.

Answer 5

Back in college in the early 1980s, I read in a game playing text that if a computer could plan, evaluate and execute a move, any single move, from the start of the game to all possible conclusions every 1/3 of a nanosecond, that is approximately 3 billion moves/second, to do this for every conceivable outcome would take 10 to the 120th centuries to complete. And who has that long to wait?

Another staggering statistic? You've obvious heard of a googol? Not THE Google, but the number? It is 10 to the 100th power. A 10 followed by 100 zeros. Now imagine the googolplex. That's 10 to the googol'th power.

I've read that there isn't enough of anything in the known universe, not even atoms, to require using the googleplex. In fact, even the googol is too big to describe anything. You should check out some of the astonishing trivia about these numbers.

Answer 6

If you use "pruning" you can delete the bad options (the ones that will lead you to a loss for sure) and keep on looping while pruning. This way you might have enough memory to store the "good" options.

Answer 7

Although it might not be possible to realise chess in a database in this universe, the abstract structure of the game can be said to exist as a finite mathematical object. One can reason about it and conclude that it has a definite result, although we might not know what that is. And then if you view it as a matrix you can ask questions like what is the maximum eigenvalue of chess approximately. Indeed Plato thought that numbers have real existence, so I guess he would say that the chess game exists in the same sublime and unhelpful way.

But more practically, I could imagine an advanced quantum computer might genuinely be able to represent this, and indeed solve chess. The jury is still out as to the capabilities of this technology, but in principle I can’t see that it’s impossible