How many bones does a human have?
Will computers ever solve chess?
Sort:
May 14, 2016
0
#463
Hmm, maybe start with all the bones a human has for the first few. Then we can take away bones later to see if that makes a difference.
This seems like a sort of question that would be a subset of the P Vs. NP problem, one of the millenial problems. If you solve that one, there is a 1,000,000 dollar prize btw. But it will usher in some sort of terminator style apocalypse so spend some of that on good insurance or something.
s23bog wrote:
It's only a matter of time before the thing realizes it is capable of doing more than playing a silly board game.
Ehm, no, you have seen too many movies...
By the way, did you ever see this one? https://www.youtube.com/watch?v=qS5EPbsmCXs
s23bog wrote:
No, I hadn't seen that. The human shape is important for what I am thinking, but that is a decent start.
I don't see how the shape of a robot could possibly relate to its playing strength, so what are you thinking of?
Or whether it has an abdomen or not.
Yes, so much is clear, but the question is why the shap is so important, intelligence is found in the programming and not in the outward appearance
And the more important question, are you thinking about this as a means to solving chess, or are you just phantasizing about something that would look cool?
Software, written by human beings, is the solution - not computers.
Technically, can't a person become unbeatable at chess just by simply being great at analyzing the board entirely on every move.
like all a player has to do is never make a mistake. If you never make a mistake, you become unbeatable.
I have been following this YouTube series of videos on how to program a chess engine in javascript. I'm about half way through. There is so quite good information about representating positions and moves.
https://www.youtube.com/watch?v=2eA0bD3wV3Q
RCMorea wrote:
s23bog wrote:
True. In fact, it's not a matter of "would be." They are. But they still are limited by the speed of light and the fact that you need to make transistors at least several atoms across. Bottom line, we are running up against these limits now, and they are limits based on the structure of the universe, not limits that we can solve with cleverness.
The point people aren't focusing on, the really interesting one in my opinion, is quantum computers (if they are indeed possible). A regular computer depends on data stored as bits, either 0 or 1. Two bits can have a total of 2 squared states. Three is 2 to the third. A gigabit, is a billion bits, that's 2 to the billion possible states...it's an insanely large amount of possibilities (but still much too small to hold chess). But, a quantum computer would try to store information in electrons. Then, it would take advantage of quantum uncertainty, and the fact that electron position and spin isn't just unknown, but actually undetermined until observed, and therefore neither at once or both at once. It's conjectured that this would allow all possibilities to be examined at the same time, instantly, assuming you could set it up in the first place. Not necessarilly possible, but pretty cool if it turns out to be possible.
You claim we are running against hard limits imposed by the Universe. I would like to offer a correction to that, if I may.
We are running against hard limits imposed by our understanding of the universe using the method we are currently using.
Rather than looking at a computer as a single device, it may be useful to look at the cloud of computers on the internet as a whole. There are many users, and many processors, but there is great disconnect between the individual nodes. Data sharing is extremely limited, and there are a bunch of unruly people at the controls.
No, respectfully, the cloud isn't going to help in any material way, even if the whole world cloud were devoted to nothing but chess. Linear increases in power, such as adding a billion processors or a trillion processors, can never defeat problems which are exponentially too large. That is, 10^120 positions (Claude Shannon's estimate of the size of chess), is not even scratched by application of a trillion times more power even over a period of a trillion years.
Meanwhile, yes, the hard limits of the universe as we understand them. But if we happen to be wrong about everything, it becomes a philosophy discussion in which there is no point discussing anything, since we have no framework for doing so. Provided we must make our computers out of atoms, provided we can't really know the exact locations of electrons, provided the speed of light is constant--that sort of thing--then chess is not going to be solved by computers.
Hmm, this misunderstanding is repeated throughout this thread and in other discussions on solving chess. There are not 10^120 different chess positions, that is an estimate of the number of chess games of average length (40 moves). The number of chess positions is roughly 10^44, much less. This is important for the matter of solving chess, since it is not necessary to search the same position more than once, so 10^44 serves as a maximum for the difficulty of the problem.
Further, it is not necessary to actually search through all 10^44 positions to solve chess, there are pruning methods available that can greatly reduce the number of searched positions, to roughly the square root in the optimum case. To see why this is so, observe that, if chess is a draw, then solving chess would require finding a strategy for white that always leads to at least a draw, and a strategy for black that does the same. To find a strategy for white, an algorithm may start with e4; if there is a drawing strategy for white starting with e4, then it is not necessary to search positions that can't be obtained starting with e4. So a drawing strategy requires dealing with all the opponent's moves, but there is no need to examine all of your moves.
To see why some of these arguments for chess being insolvable are invalid, note that they would apply also to checkers. Checkers has complexity roughly the square root of chess, with about 10^21 positions and about 10^50 to 10^60 games of average length. If one needed to actually search through 10^60 games to solve checkers, that would obviously be too difficult as well. Even searching through 10^21 positions would be beyond current capabilities. But checkers was solved back in 2007! If you read the details of their proof, they searched through about 10^14 positions using 10^7 memory, using the pruning techniques I mentioned before combined with a partial endgame tablebase. This was just easy enough for them to be able to handle it.
Assuming a similar reduction for chess, one might guess it would take searching about 10^29 positions using a similar approach. This is a blowup of difficulty by a factor of 10^15, obviously too much for current computers, but not something obviously too much for human civilization until the end of eternity! Certainly, all this talk of "more than the number of atoms in the universe" is not relevant here.
You realize that when you spend this amount of time and quantity of posts that you are just trolling yourself, right?
The measure of "winning" among competing trolls is how little they can post to create the biggest uproar, and having to constantly bump one's own trolling thread is considered abject failure...
Deedlit wrote:
Hmm, this misunderstanding is repeated throughout this thread and in other discussions on solving chess. There are not 10^120 different chess positions, that is an estimate of the number of chess games of average length (40 moves). The number of chess positions is roughly 10^44, much less. This is important for the matter of solving chess, since it is not necessary to search the same position more than once, so 10^44 serves as a maximum for the difficulty of the problem.
Further, it is not necessary to actually search through all 10^44 positions to solve chess, there are pruning methods available that can greatly reduce the number of searched positions, to roughly the square root in the optimum case. To see why this is so, observe that, if chess is a draw, then solving chess would require finding a strategy for white that always leads to at least a draw, and a strategy for black that does the same. To find a strategy for white, an algorithm may start with e4; if there is a drawing strategy for white starting with e4, then it is not necessary to search positions that can't be obtained starting with e4. So a drawing strategy requires dealing with all the opponent's moves, but there is no need to examine all of your moves.
To see why some of these arguments for chess being insolvable are invalid, note that they would apply also to checkers. Checkers has complexity roughly the square root of chess, with about 10^21 positions and about 10^50 to 10^60 games of average length. If one needed to actually search through 10^60 games to solve checkers, that would obviously be too difficult as well. Even searching through 10^21 positions would be beyond current capabilities. But checkers was solved back in 2007! If you read the details of their proof, they searched through about 10^14 positions using 10^7 memory, using the pruning techniques I mentioned before combined with a partial endgame tablebase. This was just easy enough for them to be able to handle it.
Assuming a similar reduction for chess, one might guess it would take searching about 10^29 positions using a similar approach. This is a blowup of difficulty by a factor of 10^15, obviously too much for current computers, but not something obviously too much for human civilization until the end of eternity! Certainly, all this talk of "more than the number of atoms in the universe" is not relevant here.
10^15 times current computing power puts the solution well past the lifespan of anyone on this forum, or likely anyone that ever will read this forum before it is long gone ;). Even if the model resulting in Moore's Law (computing power doubles very 2 years, essentially) were still in effect (it is not, it has slowed way down)...
So, ultimately, the argument is the same...whether the universe cannot hold the answer or not, the answer is just as unreachable for anyone musing about the problem right now.
s23bog wrote:
Sounds like you are the expert on trolling, btickler.
I guess that is supposed to insult me somehow?
"I guess you are an expert on crime, detective...take that! It's like you are a criminal yourself...get it? Oh, wait...that doesn't follow at all. Ummm...hang on, I'll think of something..."
[...]
May 16, 2016
0
#478
Deedlit wrote:
This is a blowup of difficulty by a factor of 10^15, obviously too much for current computers, but not something obviously too much for human civilization until the end of eternity! Certainly, all this talk of "more than the number of atoms in the universe" is not relevant here.
10^15 times harder is still enormous of course. Not only do you have to compute it, but you have to store the solution.
Good points though.
btickler wrote:
10^15 times current computing power puts the solution well past the lifespan of anyone on this forum, or likely anyone that ever will read this forum before it is long gone ;). Even if the model resulting in Moore's Law (computing power doubles very 2 years, essentially) were still in effect (it is not, it has slowed way down)...
So, ultimately, the argument is the same...whether the universe cannot the hold the answer or not, the answer is just as unreachable for anyone musing about the problem right now.
Fair enough. But, I think it is still interesting to muse about whether a problem can ever be solved. People have been throwing around "the solution won't fit in the universe" and "chess will never be solved" without sufficient justification.
Also, I don't think we know for sure how much progress we will make in computing power even within our lifetimes. Progress may be slowing down currently, but just like the invention of the transistor and the IC sent the rate of computing power increase into overdrive, another advance or two might do so again (be it graphene chips/nanotubes, spintronics, etc).
Yes.
First we need to count the ways you can arrange a skeleton.