11

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?

  • 4
    No, it is not possible with any imaginable technology. – Tony Ennis Dec 4 '14 at 12:25
  • I am wandering a while.. And still does not created it. You are right. Ahaha. – Ahmad Azwar Anas Mar 1 '16 at 20:55
  • Good luck building a database with more bytes than atoms in the Universe – David Aug 19 at 16:19
31

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.

  • now I am imagine that there are algorithm which represent End Game Table .. ^^ – Ahmad Azwar Anas Jun 5 '13 at 7:21
  • 2
    @AhmadAzwarAnas Well, I think simple ones are already used in chess engines, and the more complete ones will be added as technology permits. In terms of an algorithm, I guess you could "compress" an end game table by analysing it for patterns, and generalising them into a set of rules which clearly lead to an outcome. In all likelyhood however, this set of rules would still be absolutely massive, since tiny variations (such as having opposition or not) can change the result of the game. – Daniel B Jun 5 '13 at 8:12
  • @AhmadAzwarAnas actually, why not just an algorithm for chess? there must be a move in every lost game that is the wrong one, right? i.e. the move before which there existed a path to not losing regardless of opponents move, but after which this is no longer true. then "all" the algorithm must do is identify these moves so you can avoid them. – Michael Sep 29 '14 at 18:15
  • 1
    @Michael it's harder than that - how can you know a path exists for winning regardless of what the opponent moves? at best, there would be one only 50% of the time, because if one person wins, then the other is forced to lose. Actually lets back it up to the starting positions - for there to exist a path further on in the game, there should exist an "absolute winning path" at that point - if we figured that out, then why would anyone play the losing color anymore, knowing that regardless what they move they will lose? why would anyone play chess anymore at all if we could do that? – user2813274 Dec 1 '14 at 14:23
  • 1
    +1 but your analysis is wrong. To store a tablebase, you only need to store each position, not each possible game. Shannon estimates that there are about 10^43 positions, which compares to about 10^50 atoms in the earth. So you might solve chess by turning the whole earth into a computer. – David Richerby Dec 14 '14 at 12:02
6

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 1043 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 1050 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.3x1041 seconds to complete its task. That's about 1.4x1034 years. That's 14 million billion billion billion years.

Astrophysicists believe that the universe will look radically different in 1.4x1034 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.

  • 2
    So you mean there's a chance? – bpromas Jun 29 '15 at 14:59
4

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.

  • You have misunderstood what the database would contain. Each possible move would be marked as either "If I play this, my opponent can force a win whatever I do next", "If I play this, I can force a win whatever my opponent does next" or "draw". So you wouldn't be playing "non-losing moves at every turn": you'd be playing forced wins at every turn, as long as such a move existed. – David Richerby Dec 14 '14 at 11:54
  • Well, actually I understood exactly what the database would contain … The point I was trying to make is that in high level chess games "There Are No Forced Wins!" in more than 90% of the positions. And you need way more information than "this move draws and this move loses", to actually get to a winning position against a decent player. – BlindKungFuMaster Dec 15 '14 at 9:05
  • 1
    To give an example: In the starting position, in all likelihood, the only information in the database would be "All moves draw.". So you would be completely on your own. And if you are completely on your own, how do you get a winning position against a strong player? The answer is: You don't. Your position will get worse and worse up to the point were you follow the one and only drawing line. – BlindKungFuMaster Dec 15 '14 at 9:11
  • No, that's not right. It's trivial to get your winning move. Simply calculate all the possible moves from the current position, check the resulting positions on the DB and choose one that wins or draws. By definition, if your current position is "you win", there will be at least one in the next positions that is "you win"; and if your current position is "draw", at least one of the next positions will be "draw" (and possibly some "you win" if your opponent does not play perfectly). – Ignacio Calvo Nov 15 '17 at 10:47
  • The point is that the current position usually isn't "you win". For example it is very likely that there is no forced win in the starting position. – BlindKungFuMaster Nov 16 '17 at 14:19
2

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.

  • The obstacle to solving chess is the literally astronomical amount of data you'd need to sort through. Shannon estimated that there are roughly 10^43 positions in chess and you'd need to store the outcome for every one of those. To put this into perspective, the earth contains about 10^50 atoms so, even if you could build a memory cell from 10,000,000 atoms, you'd still need to convert the whole earth into a memory bank just to store the result! – David Richerby Dec 14 '14 at 12:04
  • 1
    @DavidRicherby Let's say chess is a draw with best play. Then for every white move, there is an adequate response for black. To the next white move, black also has an adequate response, and so on. It is conceivable that building such a "draw tree" requires a lot less than 10^43 positions. – Dag Oskar Madsen Dec 14 '14 at 15:56
  • 2
    @DagOskarMadsen Yes, it's possible that actually storing the tree would require much less memory (though still an astronomical amount). However, the current technique for building such trees is to do retrograde analysis from all ending positions, which does require building the complete database of what to do in every position, as at least an intermediate stage. – David Richerby Dec 14 '14 at 16:10
  • I am sorry to announce you that you are wrong! @DagOskarMadsen But if you don't know how to refute the "unadequate" responses, can you really claim you've solved the game? – David Aug 19 at 16:22
1

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.

-2

Yes, I think it would be possible. But only if the database was more like a neural network, taking moves that caused it to lose and deleting them. That calculation is based on exponentiating(bear with me) all possible actions in a chess game at move one, to move 100 or something. Meanwhile if we got rid of repeats, ((Ke3 Ke4 Ke3 Ke4) looping) 10^120 could probably become something like 10^70. That is still ridiculously huge but if we somehow were able to encode it onto a 4D plane (Which I believe is possible) it would be child’s play.

  • 2
    Welcome to Chess! Please take the tour while you're at it. Your post might be downvoted because it's more of an opinion and less of an answer as we expect it here; see the Help Center article How to Answer. – Glorfindel Aug 19 at 11:07
  • I'm not a chess guy, and for the record, I'm not one of the people who down-voted you either, but I've read that there are 10^43 different positions. Just because you have a method that allows filtering out some of the data, why do you automatically assume that that makes it possible? I think you are underestimating exactly how conceivably large this database would need to be. This is so far beyond the scope of modern day computing technology that I can't imagine we are on a trajectory for this to happen even a century from now. But welcome to SE Chess. (And welcome me, too, I suppose :P) – Joe Majewski Aug 29 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.