I hadn't even calculated for a second, just typed the first number that came to my mind because it wasn't about accurate estimations, I was only trying to make it clear that it's not something unimaginable, and it's in fact well underway.
That's my point, really - a few billion terabytes is imaginable. Who knows, maybe Google's total storage capacity will get there some day.
Something with 40 zeros extra isn't imaginable though, and you can't really say it's well underway when so far we've done about 0.000000000000000000000000000000000000000000000001% of the work -- give or take a few zeroes.
That's my point, really - a few billion terabytes is imaginable. Who knows, maybe Google's total storage capacity will get there some day.
Something with 40 zeros extra isn't imaginable though, and you can't really say it's well underway.
Why not? I can easily imagine computers storing the same data they have today (tablebases), only much, much more. What I can't imagine though is the degree of freaky technological advances in the next 50 years, it even scares me sometimes. Note that in the future not only data storage will be different, probably the representation of positions will be improved too. And it is well underway, we already have tablebases, why would you say it's not?
one minute how to the chess.com servers work then if they contain a set rules and how things move surly they must have something like every move possible so it already has been done. I probably am wrong so i will be expecting a few arguments against it
To digress a little, still stay on a related topic: Shouldnt it be able to compute the maximum number of moves a chess game can have? I've seen discussions on it on the net, but no conclusions. Given the 50 moves rule for draw, I should think this problem is, well, certainly not trivial, but still possible to solve without solving chess exhaustively.
Any takers?
One simplification I can think of, and that I'm sure must be used in the creation of existing table-bases, is that any position that is devoid of pawns and castling rights can be reduced eight-fold as it's demonstrably equivalent to seven other positions -- its four 90˚ rotations and their respective mirrors.
You are correct, this is exactly what is done in tablebase creation at this very moment.
I noticed when scanning through the thread that quite a few people seem to think we're heading towards eight-piece tablebases right now. I'd like to correct them by pointing out we have not yet completed our seven-piece tablebases, and it is believed that there will be a few years to go before this task is completed.
Of course, all this is dependent on the advent of certain areas of quantum computing. Already, it allows us to do many tasks in mere seconds compared to what it used to take us.
Here's some fairly recent news on the subject:
http://www.sciencenews.org/view/generic/id/49951/title/First_programmable_quantum_computer_created
To digress a little, still stay on a related topic: Shouldnt it be able to compute the maximum number of moves a chess game can have? I've seen discussions on it on the net, but no conclusions. Given the 50 moves rule for draw, I should think this problem is, well, certainly not trivial, but still possible to solve without solving chess exhaustively.
Any takers?
http://blog.chess.com/kurtgodden/the-longest-possible-chess-game
There used to be a follow up to this where we refined that figure somewhat (same blog, similar title that included the word revisited) but for some reason I can't find it now.
http://www.chess.com/forum/view/off-topic/the-longest-possible-chess-game
Revan24 was a key contributor to the "revisisted" version of the above blog, which appears to have been deleted:
http://www.chess.com/forum/view/general/longest-possible-chess-game
To digress a little, still stay on a related topic: Shouldnt it be able to compute the maximum number of moves a chess game can have? I've seen discussions on it on the net, but no conclusions. Given the 50 moves rule for draw, I should think this problem is, well, certainly not trivial, but still possible to solve without solving chess exhaustively.
Any takers?
Of course this presumes that after a threefold repetition or 50 moves without pawn move or capture, the draw is actually claimed, even though it doesn't have to be. This also presumes the current version of the 50 move rule, i.e. that the number is 50 (it hasn't always been).
To digress a little, still stay on a related topic: Shouldnt it be able to compute the maximum number of moves a chess game can have? I've seen discussions on it on the net, but no conclusions. Given the 50 moves rule for draw, I should think this problem is, well, certainly not trivial, but still possible to solve without solving chess exhaustively.
Any takers?
Of course this presumes that after a threefold repetition or 50 moves without pawn move or capture, the draw is actually claimed, even though it doesn't have to be. This also presumes the current version of the 50 move rule, i.e. that the number is 50 (it hasn't always been).
Yes, one have to establish that, otherwise it will continue forever.
This make me realise, can you claim threefold repetition when the position on the board is equal three times, or does it need to be the same actual pieces occupying the same squares (e.g. if it the two rooks have swiched place since last time, it does not count as a repetition). This would have an impact on the puzzle.
For repetition of position, different rooks exchanging position are included in the repetition.
Thirdly, IMHO chess will probably not be solved by either the tablebase method or the steady state method. I predict that some schmo who knows nothing about chess, possibly an Afgahn goat herder or something, will figure out a really ellegant solution to one of the other problems in the class NP(c). Some random journalist (probably from the BBC) will interview said goat herder without realizing exactly what it is he's got. Then finally one of the esoteric hermits who understands the math behind problems like this will make the connection years later and thousands of miles away, and rush to talk to said goat herder himself. In fact, this may have already happened; well, steps 1 & 2 anyway. Now we just have to make sure we don't kill the goat herder......
Is Nicholas Cage available for the film?
I would think any game with consistent rules and a finite possibilities, however enormous the number (I think DeGroot said 2^143 positions in chess, obviously many many more in chess960), is "solvable". Computers are getting more and more powerful day by day, so maybe it will happen, though maybe not in our lifetimes.
By similar argument, since 100m runners are still getting faster and faster, the day will come that humans can run at 99% light speed.
I can't wait -- I was thinking that when that day comes I was going to run around the world until time reverses so that I can save Lois Lane, but now I wonder: If I reverse time to a point before humans could run at 99% the speed of light, does that prevent me from continuing to run at 99% the speed of light? If so there must be a limit to just how far I'd be able to turn back time and maybe I can't save Lois after all.
First, lots of people refer to the number of chess positions being greater than the number of atoms in the universe. This is used primarily to illustrate the size of the problem, but more practically as a constraint of storage (the argument runs something like ".... and it takes at least 7 atoms to make a NAND gate, which stores 1 bit of data (classical computing), etc...). This is slightly fallacious, since we will probably develop viable quantum computers and other storage methods. For information on just how much information the universe can store, google the Holographic Principal; but the answer is basically A/4h where A is the surface area of the universe and h is Planck's constant, the answer given in binary bits.
So, the fact that someone conceded that you can use every particle in the universe to store the solution to chess wasn't enough for you? You also want them to concede that in the future you might be clever enough to squeeze out a few additional orders of magnitude out of the universes capacity to store information?
This is the kind of oddness that the optimists insist on to support their optimism for the eventual solution of the game. It's a pretty big clue that they are probably being too optimistic.
Instead of just asking us to Google something, why not refer us to a peer reviewed scientific article? For example, Physical Review Letters, volume 88, article number 237901, which calculates that the Universe, in its entire history, can have at most performed 10^120 elementary logic operations on 10^90 bits. The author of that article is Seth Lloyd from the Laboratory for Information Systems and Technology at MIT.
First, lots of people refer to the number of chess positions being greater than the number of atoms in the universe. This is used primarily to illustrate the size of the problem, but more practically as a constraint of storage (the argument runs something like ".... and it takes at least 7 atoms to make a NAND gate, which stores 1 bit of data (classical computing), etc...). This is slightly fallacious, since we will probably develop viable quantum computers and other storage methods. For information on just how much information the universe can store, google the Holographic Principal; but the answer is basically A/4h where A is the surface area of the universe and h is Planck's constant, the answer given in binary bits.
So, the fact that someone conceded that you can use every particle in the universe to store the solution to chess wasn't enough for you? You also want them to concede that in the future you might be clever enough to squeeze out a few additional orders of magnitude out of the universes capacity to store information?
This is the kind of oddness that the optimists insist on to support their optimism for the eventual solution of the game. It's a pretty big clue that they are probably being too optimistic.
Instead of just asking us to Google something, why not refer us to a peer reviewed scientific article? For example, Physical Review Letters, volume 88, article number 237901, which calculates that the Universe, in its entire history, can have at most performed 10^120 elementary logic operations on 10^90 bits. The author of that article is Seth Lloyd from the Laboratory for Information Systems and Technology at MIT.
Loomis,
Thanks. I must have missed that article... I don't get access to all the journals all of the time, as I am on the road alot. Also, strict information science is not my best suit. But again, thanks for mentioning the article as it sounds rather fascinating.
I take it from your tone that you are a pessimist. So do you really believe that we as a race will not advance our methods and technology to a level beyond that which is based on silicon, copper, and the semi-classical movement of electrons? I think this is pretty naive considering that the transistor has been around for only a single lifetime. It would be like taking a caveman, but a caveman who has seen and touched this strange thing called "metal" and asking him to beleive that real, practical tools will only ever be made of sticks and stones; that "metal" stuff is just heady optimism.....
PS I really don't mean that as an insult, or in an argumentative way; I'm just asking you to be a little more open-minded and immaginative.....
I am open minded an imaginative on what humanity might achieve in the future. And I'm well aware that it is unimaginable to us in present day. As has been pointed out ad nauseum, you don't have to go to a caveman to shock people with our current day technology. Cars, radios, televisions, telephones, computers, cell phones, etc. would all look like magic 200 years (or less!) ago. I can only imagine what will exist 200 years from now that looks like magic to us today.
But that really has nothing to do with whether or not a game like chess can be solved.
I believe that the advancements humans will make in the future will increase our capacity to solve problems like this by orders of magnitude. Unfortunately, as it has been pointed out, it will take even more than that to have a solution for a game like chess. The size and computational complexity of the (brute force) solution to the game of chess rivals the size and complexity of the entire universe.
Let me make an analogy to your argument. A few hundred years ago (pre industrial revolution) it would be very difficult for humans to imagine assembly line mass production. Pick your favorite object, I'll choose the hammer. In modern times we can easily mass produce millions of hammers if we like. And if a problem existed that required the production of 10 billion hammers, it could be done. But what if a problem existed that required the production of 10^120 hammers? The current production capacity on earth could not achieve this. Your argument says, essentially, look how far we've come in hammer production in the last few hundred years! we used to hardly be able to make any hammers and now we can make billions, surely we'll be able to make 10^120 at some point. Unfortunately, there is not enough mass in the universe to make 10^120 billion hammers, no matter how good your hammer making technology becomes.
Allow me to rephrase the question of whether or not chess can be solved.
First, let's agree that it is possible to construct a game that is too complex for the universe to contain the solution. This should be easy to agree to since the size of the solution grows faster than the size of the game. Even a simple game like chess with relatively few rules, played with a handful of pieces on a small board has a rather large solution. A game played on a 15x15 board with 30 pieces on each side could have an exponentially larger solution.
Instead of making the question specifically about chess, ask the question in general, can we divide games of perfect information into two groups, those whose solutions are small enough to fit in the universe and those whose solutions are not?
Then it's just a matter of checking which group chess is in.
We know of some games that fit in the "small solution" group -- tic-tac-toe, connect four, checkers -- because we have solved these games. Every indication for the size of the solution to the game of chess is that it is in the "large solution" group. I have never seen a reasonable argument otherwise.
It's more than 40 orders of magnitude off. The difference in size between the Milky Way and an electron is only 35 orders of magnitude.
Yes, I think it's a pretty weak estimation :-)