I do not know what sub atoms are, but are you refering to subatomic particles such has quarks?
Can Chess be Solved by computers?
Sort:
Even if chess is solvable, and the result was just a draw, then that would mean that the perfect line wouldn't be a draw, because that wouldn't be perfect. The perfect line would be the line that with some hope trick you opponnet into letting you checkmate him, or else be checkmated or drawn.
So, in order to play a perfect game of chess, you have to make mistakes. Interesting.
sgt_pepper wrote:
Even if chess is solvable, and the result was just a draw, then that would mean that the perfect line wouldn't be a draw, because that wouldn't be perfect. The perfect line would be the line that with some hope trick you opponnet into letting you checkmate him, or else be checkmated or drawn.
So, in order to play a perfect game of chess, you have to make mistakes. Interesting.
I don't think so buster. You best take that carnival logic back to the fun house.
sgt_pepper wrote:
...
So, in order to play a perfect game of chess, you have to make mistakes. Interesting.
Um, no.
Dec 3, 2009
0
#86
Loomis wrote: ...
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.
Loomis,
I understand your argument and it's various tenants, all of which contain a variety of classical ellements; and as such, really don't bear out my point about immagination.
What I'm trying to say is, suppose there was a job that required 10^120th hammers. Well, obviously hammers aren't going to turn the trick. But the purpose of a hammer is to drive in nails: so what if we built a nail that drove itself in, thus shortcutting the problem and eliminating the hammers altogether. Or what if we built a device called a Hammerschlag, and each Hammerschlag does the job of 10^120 ordinary hammers, or 10^1000, or 10^10^10^10. So once we invent the Hammerschlag, the whole hammer thing will just be pointless.
Now chess is a game of combinatorics, but a very special one, since it is contained in a set of other similar mathematical constructions. Not all games are contained in the set NP Complete, so much of what you said about set theory totally applies. I'm just saying that I think it is possible that we might build a device capable of solving NP Complete, the same way that we built devices that solved the set P (P is the set of all computational problems that can be solved in polynomial time). There are many problems in the set NP (NP=not polynomial) that are not NP complete, and there are whole subsets of NP that are much larger than, say, the set X (X being problems that take exponential time), and in those sets might be games that can't be solved.
I don't think you really understand my point about not being able to build 10^120 hammers. The fact that the object is a hammer is unimportant, that's why I said to pick your favorite. You can't build 10^120 of anything, ever, including nails that drive themselves in, or whatever other fancy thing you can imagine. The point is that there exists physical limits to the size of the universe.
As has been pointed out in this thread, chess can be solved by a straightforward brute force calculation. Simply extend the endgame tablebase idea to all 32 pieces. There are two limits to applying this solution -- time and space. The time limit is restricted by the fact that the algorithm is not polynomial as you state. I'm willing to concede that this problem can be overcome by some kind of clever computing. The space limit is different altogether and does not depend on the computational complexity. There is finite storage space for the solution. That is the point of the paper I referenced earlier. The universe can only contain a finite amount of information. And all indication is that the solution to chess requires more information than this limit.
Do you believe it is possible to construct a game like chess (turn based, perfect information) that cannot be solved?
I'm going to repost what I wrote in the other thread:
===
Will chess ever be solved? No.
I'll explain using an analogy. Will humans ever travel to other galaxies? No. Technology is improving, yes, and in the past it seemed impossible that we would ever travel to the moon, and we were proven wrong, but going to other galaxies is totally different. The nearest galaxy is the Andromeda Galaxy which is 2.7 million light-years away. We will continue to build faster and faster spacecraft, but it doesn't matter what technological advances we come up with because it's no longer a matter of speed. No matter how fast we go, even light speed, the fastest speed there is, it will take us at least 2.7 million years to get there, which might as well be forever. So, no, humans will never travel to other galaxies.
... at least not in fast ships. Yes, I have to qualify my "no" because it's not 100% certain, but until we figure out some other way that the universe works, some sort of major breakthrough like warp speed or wormholes, it's just flat-out impossible to get to other galaxies.
In much the same way, it's impossible to solve chess. The game of chess is so complicated that it's not a matter of computation anymore because no amount of computation will ever be enough to solve chess. To use some hard numbers, the potential computing capacity of a kilogram of matter equals pi times energy divided by Planck's constant [1], about 5.0 * 10^50 operations per second, which is roughly equivalent to the number of legal positions in chess [2]. Thus, it would take a theoretically perfect computer to even begin to list all the possible positions in chess, let alone analyze them. So, solving chess just isn't possible. Sorry.
... at least, not with faster computers. Again, I'm going to qualify my "no" because it's not 100% certain. Anything is possible, perhaps quantum computers will change things, or new mathematical theorems will arise, or maybe a forced win will be found in the first 20 moves, but probably not. There is nothing on the horizon to even hint that such an EXTRAORDINARY breakthrough could ever happen, and if chess ever is solved it's certainly not going to be because of faster computing speeds. Chess is not like Connect Four because Connect Four actually has a reasonable number of positions that's within the realm of computation, kind of like how the planets in our solar system are within the realm of reasonable travel.
What we can count on, however, is better and better computer chess software. I wouldn't rule out the possibility that one side, white or black, will become so dominant that computers can always win as them (even against other computers), but that's not the same as theoretically "solving" the game.
Let's also remember how much we've already learned from computers. In the past, it was thought that human imagination and ingenuity and grasp of strategy was what set us apart from machines and their rote calculation, and maybe so, but it's become clear that being able to play tactically perfect out to 20 moves in the future is far more important, and that our ability to "think" that we thought was so special really isn't special at all =)
[1] http://puhep1.princeton.edu/~mcdonald/examples/QM/lloyd_nature_406_1047_00.pdf
[2] http://www.thechessworld.com/Articles/how-complex-chess.html
===
So, to answer DJHeilke's optimism, although I don't like to use the word impossible, we really shouldn't be waiting around for chess to be solved. It probably won't be. It won't be solved with faster computers, so the only way it could be solved is with a clever mathematical theorem. Still, it took 400 years to solve Fermat's Last Theorem, an incredibly simple problem compared to chess, so to think that mathematicians will come up with a theorem that is capable of reducing something with the complexity of the entire universe down to a manageable proof not only would be the most extraordinary discovery of all time, but I also think we are giving us humans a bit too much credit.
What I wouldn't be surprised to see is if in the future mathematicians come up with some theories about positions in chess that fall under very specific guidelines. Somebody might prove, for example, that Alekhine's Gun is deadly in a certain situation where the opponent has a certain kind of defense. Or whatever. But solving all of chess? Hardly.
Oh, and you might be interested in an example of what I meant by a "clever mathematical theorem". The game of Munch has been "solved" in the sense that it can be proven that the first player always wins even though we are unable to find a general strategy that will win for boards of larger size. Using the "strategy stealing argument" it can be shown that any move the second player can make, the first player could have made before him on the first turn. Therefore, since the game cannot end in a draw, and since any winning strategy employed on the second turn could have previously been employed on the first, the first player always wins with perfect play. Even if we don't know how :-)
You can play the game here: http://www.philipbrocoum.com/munch/
pbrocoum wrote:
The nearest galaxy is the Andromeda Galaxy which is 2.7 million light-years away. We will continue to build faster and faster spacecraft, but it doesn't matter what technological advances we come up with because it's no longer a matter of speed. No matter how fast we go, even light speed, the fastest speed there is, it will take us at least 2.7 million years to get there, which might as well be forever.
It would take over 2.7 million years as seen from Earth. For the person going close to light speed, time is slower, so it doesn't take as long. In fact if you went fast enough, you could do the whole distance while only a minute goes by inside the ship (ignoring what happens when you hit a stray hydrogen molecule or two).
Of course we can't reach such speeds in practice, but it's not a great example.
To be clear on what it means to solve chess:
If it is simply a question of answering the question of what the outcome of the game is with best play from both sides the storage capacity issue may be something that can be worked around and it does come down to a question of computational complexity.
If it is a question of answering the question of what the best move is for any given legal position (effectively a 32 peice tablebase) then Loomis is correct and resolving the complexity issue still doesn't enable us to manufacture storage that doesn't exist.
You can only fit so many angels on the head of a pin.
Scarblac wrote:
It would take over 2.7 million years as seen from Earth. For the person going close to light speed, time is slower, so it doesn't take as long. In fact if you went fast enough, you could do the whole distance while only a minute goes by inside the ship (ignoring what happens when you hit a stray hydrogen molecule or two).
Of course we can't reach such speeds in practice, but it's not a great example.
Right, because a 2.7 million year discrepancy between arrival and departure is nothing to worry about. Barely even worth mentioning, really. I often arrive a few million years late to work in the morning, in fact. It's no big deal.
... the number of possible legal moves (look up "Shannon Number") rivals the age of the universe!
If the age of the universe in years (1.37 * 10^7) were to be represented by, say, a proton, Shannons number would be... probably larger than the size of our universe.
10^120.
Thats the estimated lower bound of the number of possible positions.
According to the person who formulated that incredible number: " A machine operating at the rate of one variation per micro-second would require over 1090 years to calculate the first move"
I seriously doubt that, even with the use of quantum computing, we would ever be able to make these computations in the timespan of a human lifespan, to not even say in a reasonable realtime setting!
So to answer your question quite frankly: No. The human species will most likely be extinct before we "solve" chess.
Having said that, I will say that we've already come pretty close to solving it with our various chess engines. "Pretty close," however, is as far as we're going to get.