Checkers Solved - Chess around year 2060-2070!

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Checkers Solved - Chess around year 2060-2070!

Post by bob » Sun Jul 22, 2007 12:43 am

Terry McCracken wrote:
bob wrote:
Terry McCracken wrote:
bob wrote:
Terry McCracken wrote:
bob wrote:
that 2060 stuff shows such an incredible lack of comprehension that it really doesn't deserve a comment at all. It is a ridiculous statement. Only down-side is that I doubt I will live long enough for the idiocy of that statement to be proven. I'm almost 60 now. I'd need to live past 120 to see that fallacy put to rest...

chess won't be solved by 2060. Or even 2160.
Robert..Never say Never! I think throwing out a number like that was irresponsibly stupid as well, but we don't know when or exactly how chess will be solved. However, I do believe it's possible with the right technology and methods.

Terry
Simply not possible with any conceivable approach. More chess positions than atoms in the universe, by a _large_ margin. Even using quantum states to store multiple bits per atom would not be possible as there are not enough states.

This is something that simply is not going to happen. Even a density of one billion times one billion times greater than today's chips won't even come close...
None of that matters! You're being myopic. First you can prune 99% + of all positions on the board. Quantum computers when fully developed and very advanced and practical will be able to compute at speeds that are inconceivable to anything you've experienced.
Not being "myopic" at all. Do you have any idea what 1% of a tree that large is? Hint: It is _not_ a small number. 1% = .01 which is close to 1/2^8.

What do you get if you divide 2^160 by 2^8? 2^152.

the math is _daunting".



They may even be able to actually connect to parallel universes and work in tandem, so yes that technology could indeed be used to solve chess.
I thought we were talking real-world scenarios? Not science-fiction...


Even Jonathan realizes this!

I'm tired of that can't be done crap...that's what truly is absurd! It holds back scientific and technological progress!
I'm equally tired of the "this will one day be doable" when it is so obvious it will not be done. We knew checkers would be solved 30 years ago, we just didn't know when. No serious researcher says that chess will be solved by 2060 or at any point in the future. Wonder why that is?


You're a computer scientist, but you've but up barriers to things that are so different to your understanding and make false comparisons to the past evolution of computers. Well, the next 50 years will move much faster than the last 50 years. That's a fact!
based on what? I bought a 2.8ghz processor 4 years ago. You can almost buy 4.0 ghz today. 4 years, not a factor of two. That's a fact...


I have seen the impossible be done and I'll see it again!
You have _never_ seen something "impossible" done. Nobody has, for obvious reasons.


Terry

I've seen you post... :roll:


Robert, you are not an expert in quantum computing, that is obvious. It will be done, it's not science fiction!
Please read more carefully. The "science fiction" applied to your "connecting parallel universes". That's not reality. In fact, there is nothing that suggests such things actually exist, other than in the minds of the great science fiction authors.

quantum computing exists. In a useless form today. But even if it becomes a reality, you are still going to be dividing a huge number (potential search space) with a small number (quantum computing speedup). You still end up with a huge number (time required to search that space, even if it is searched ridiculously fast.)

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Checkers Solved - Chess around year 2060-2070!

Post by sje » Sun Jul 22, 2007 1:16 am

bob wrote:quantum computing exists. In a useless form today. But even if it becomes a reality, you are still going to be dividing a huge number (potential search space) with a small number (quantum computing speedup). You still end up with a huge number (time required to search that space, even if it is searched ridiculously fast.)
QC has a very long way to go before it's able to help in any practical manner. It may be that the technical difficulties involved in a physical realization are just too much. It may be that at the moment we don't even know enough to be asking the right questions on how to proceed. It could be that there is some kind of unyielding barrier akin to Plank's constant or the speed of light that prevents real QC. The same comments can be applied to the related goal of zero point energy.

But it's still an intriguing idea. Perhaps it's possible to superimpose multiple QC elements onto a single and very small physical object like an atomic nucleus. And although a quadrillion or so nuclei (molecule count of a single drop of water) won't make much of a dent solving chess, what if each nucleus can support quadrillions of simultaneous calculations? A quintillion here and a sextillion there can add up to some real throughput after a while.

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Checkers Solved - Chess around year 2060-2070!

Post by cms271828 » Sun Jul 22, 2007 2:58 am

I just solved chess, on the back of my hand, cool!!

But seriously, I read somewhere there were 10^125 possible games, and that a quantum computer could do it in a year, but its nonsense.

I think theres 10^80 or a bit less atoms in universe, so you need 10^45 universes of atoms to equal number of possible games.

I'm not sure exactly how quantum computers and qubits work, but obviously it wont be good enough.

Even if you goto superstring level, I don't think theres enough of em in an atom to get anywhere near, and there not exactly easy to see :D

The only way I can think of is by taking short cuts, kind of like in alpha-beta pruning, you dont need to check everything.

But I cant really see how that would work, so I would say impossible.
Colin

User avatar
M ANSARI
Posts: 3501
Joined: Thu Mar 16, 2006 6:10 pm

Re: Checkers Solved - Chess around year 2060-2070!

Post by M ANSARI » Sun Jul 22, 2007 3:07 am

I think that chess will be solved but not by conventional thinking. It already seems that chess is a draw because till today not a single opening has been found that guarantees a win with best play. While it can get a win OTB, others can always find refutations and manage to equalize. So it seems from that perspective that chess is drawn, otherwise with all the millions of games one opening that will always win would have been found.

So now we look for a chess entity that will never lose. I cannot see this as being a big deal within 10 or 20 years. Improvements in software and more importantly exponential improvements in hardware would seem to make a chess entity that never loses very possible. While that may not satisfy many who want to see every single chess move possible calculated, it sure would convince me that chess is solved. If I could see a computer play say 100,000 games without a single loss against all comers including Centaurs ... that would be quite convincing.

Terry McCracken

Re: Checkers Solved - Chess around year 2060-2070!

Post by Terry McCracken » Sun Jul 22, 2007 5:35 am

bob wrote:
Terry McCracken wrote:
bob wrote:
Terry McCracken wrote:
bob wrote:
Terry McCracken wrote:
bob wrote:
that 2060 stuff shows such an incredible lack of comprehension that it really doesn't deserve a comment at all. It is a ridiculous statement. Only down-side is that I doubt I will live long enough for the idiocy of that statement to be proven. I'm almost 60 now. I'd need to live past 120 to see that fallacy put to rest...

chess won't be solved by 2060. Or even 2160.
Robert..Never say Never! I think throwing out a number like that was irresponsibly stupid as well, but we don't know when or exactly how chess will be solved. However, I do believe it's possible with the right technology and methods.

Terry
Simply not possible with any conceivable approach. More chess positions than atoms in the universe, by a _large_ margin. Even using quantum states to store multiple bits per atom would not be possible as there are not enough states.

This is something that simply is not going to happen. Even a density of one billion times one billion times greater than today's chips won't even come close...
None of that matters! You're being myopic. First you can prune 99% + of all positions on the board. Quantum computers when fully developed and very advanced and practical will be able to compute at speeds that are inconceivable to anything you've experienced.
Not being "myopic" at all. Do you have any idea what 1% of a tree that large is? Hint: It is _not_ a small number. 1% = .01 which is close to 1/2^8.

What do you get if you divide 2^160 by 2^8? 2^152.

the math is _daunting".



They may even be able to actually connect to parallel universes and work in tandem, so yes that technology could indeed be used to solve chess.
I thought we were talking real-world scenarios? Not science-fiction...


Even Jonathan realizes this!

I'm tired of that can't be done crap...that's what truly is absurd! It holds back scientific and technological progress!
I'm equally tired of the "this will one day be doable" when it is so obvious it will not be done. We knew checkers would be solved 30 years ago, we just didn't know when. No serious researcher says that chess will be solved by 2060 or at any point in the future. Wonder why that is?


You're a computer scientist, but you've but up barriers to things that are so different to your understanding and make false comparisons to the past evolution of computers. Well, the next 50 years will move much faster than the last 50 years. That's a fact!
based on what? I bought a 2.8ghz processor 4 years ago. You can almost buy 4.0 ghz today. 4 years, not a factor of two. That's a fact...


I have seen the impossible be done and I'll see it again!
You have _never_ seen something "impossible" done. Nobody has, for obvious reasons.


Terry

I've seen you post... :roll:


Robert, you are not an expert in quantum computing, that is obvious. It will be done, it's not science fiction!
Please read more carefully. The "science fiction" applied to your "connecting parallel universes". That's not reality. In fact, there is nothing that suggests such things actually exist, other than in the minds of the great science fiction authors.

quantum computing exists. In a useless form today. But even if it becomes a reality, you are still going to be dividing a huge number (potential search space) with a small number (quantum computing speedup). You still end up with a huge number (time required to search that space, even if it is searched ridiculously fast.)
I read it fine Robert, and parallel universes are not ideas of Sci/Fi writers.

Please do some homework on this. It dates back to the 30's and much more was postulated in the 50's, and it has become serious science in the 90's to today.

You can't see past the numbers, and that is your error.

Terry McCracken

Re: Checkers Solved - Chess around year 2060-2070!

Post by Terry McCracken » Sun Jul 22, 2007 5:40 am

cms271828 wrote:I just solved chess, on the back of my hand, cool!!

But seriously, I read somewhere there were 10^125 possible games, and that a quantum computer could do it in a year, but its nonsense.

I think theres 10^80 or a bit less atoms in universe, so you need 10^45 universes of atoms to equal number of possible games.

I'm not sure exactly how quantum computers and qubits work, but obviously it wont be good enough.

Even if you goto superstring level, I don't think theres enough of em in an atom to get anywhere near, and there not exactly easy to see :D

The only way I can think of is by taking short cuts, kind of like in alpha-beta pruning, you dont need to check everything.

But I cant really see how that would work, so I would say impossible.
Nothing is impossible, if physics allows it. And I'm not so sure that physics is a barrier either!

Terry McCracken

Re: Checkers Solved - Chess around year 2060-2070!

Post by Terry McCracken » Sun Jul 22, 2007 5:45 am

M ANSARI wrote:I think that chess will be solved but not by conventional thinking. It already seems that chess is a draw because till today not a single opening has been found that guarantees a win with best play. While it can get a win OTB, others can always find refutations and manage to equalize. So it seems from that perspective that chess is drawn, otherwise with all the millions of games one opening that will always win would have been found.

So now we look for a chess entity that will never lose. I cannot see this as being a big deal within 10 or 20 years. Improvements in software and more importantly exponential improvements in hardware would seem to make a chess entity that never loses very possible. While that may not satisfy many who want to see every single chess move possible calculated, it sure would convince me that chess is solved. If I could see a computer play say 100,000 games without a single loss against all comers including Centaurs ... that would be quite convincing.
I agree...we will prove chess is a draw, and we don't need to explore all possibilities to determine that....

Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: Checkers Solved - Chess around year 2060-2070!

Post by Dirt » Sun Jul 22, 2007 6:21 am

cms271828 wrote:I just solved chess, on the back of my hand, cool!!

But seriously, I read somewhere there were 10^125 possible games, and that a quantum computer could do it in a year, but its nonsense.

I think theres 10^80 or a bit less atoms in universe, so you need 10^45 universes of atoms to equal number of possible games.

I'm not sure exactly how quantum computers and qubits work, but obviously it wont be good enough.

Even if you goto superstring level, I don't think theres enough of em in an atom to get anywhere near, and there not exactly easy to see :D

The only way I can think of is by taking short cuts, kind of like in alpha-beta pruning, you dont need to check everything.

But I cant really see how that would work, so I would say impossible.
As has been pointed out elsewhere, they're "only" about 10^45 different legal chess positions. This means it takes only a trivial amount of storage (in terms of the size of the universe) for a complete set of 32 piece tablebases. Even with the ability to store the data, actually calculating what to store would still have to be done, but given the life of the universe to finish it should be possible. However, it's hard believe so much effort would be devoted to such an ultimately pointless task.

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Checkers Solved - Chess around year 2060-2070!

Post by bob » Sun Jul 22, 2007 6:35 am

Dirt wrote:
cms271828 wrote:I just solved chess, on the back of my hand, cool!!

But seriously, I read somewhere there were 10^125 possible games, and that a quantum computer could do it in a year, but its nonsense.

I think theres 10^80 or a bit less atoms in universe, so you need 10^45 universes of atoms to equal number of possible games.

I'm not sure exactly how quantum computers and qubits work, but obviously it wont be good enough.

Even if you goto superstring level, I don't think theres enough of em in an atom to get anywhere near, and there not exactly easy to see :D

The only way I can think of is by taking short cuts, kind of like in alpha-beta pruning, you dont need to check everything.

But I cant really see how that would work, so I would say impossible.
As has been pointed out elsewhere, they're "only" about 10^45 different legal chess positions. This means it takes only a trivial amount of storage (in terms of the size of the universe) for a complete set of 32 piece tablebases.
It is going to take a table that has an index size of 2^160 or so. which is where that 10^50 comes from. I'm not sure how you are going to store that big a file. Something tells me that before you get even halfway there, the storage device will turn into a black hole, collapse in upon itself, and all the data stored will be lost as the gravitational well compresses things beyond comprehension.

talk of files that large actually _are_ impossible. So there's no hope of storing a 32-piece endgame table, nor of building it and the 31-30-29-...-7 piece tables needed to work your way up there. That leaves raw computation as the only solution. And nothing is going to search at the speed needed to traverse the complete game tree. If you operate at 1ns, the longest pathway you can have between two components is 12 inches, the distance light travels in one ns. If you want a picosecond machine, the distance between any two components just shrank to .012". Another factor of 1 million and now the entire thing has to fit in the space occupied by a single atom. And what then?

It's interesting to talk about such ideas, but it is ridiculous to seriously think this will happen.


Even with the ability to store the data, actually calculating what to store would still have to be done, but given the life of the universe to finish it should be possible. However, it's hard believe so much effort would be devoted to such an ultimately pointless task.

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Checkers Solved - Chess around year 2060-2070!

Post by bob » Sun Jul 22, 2007 6:37 am

M ANSARI wrote:I think that chess will be solved but not by conventional thinking. It already seems that chess is a draw because till today not a single opening has been found that guarantees a win with best play. While it can get a win OTB, others can always find refutations and manage to equalize. So it seems from that perspective that chess is drawn, otherwise with all the millions of games one opening that will always win would have been found.

So now we look for a chess entity that will never lose. I cannot see this as being a big deal within 10 or 20 years. Improvements in software and more importantly exponential improvements in hardware would seem to make a chess entity that never loses very possible. While that may not satisfy many who want to see every single chess move possible calculated, it sure would convince me that chess is solved. If I could see a computer play say 100,000 games without a single loss against all comers including Centaurs ... that would be quite convincing.
You are talking about a completely different entity than we are discussing here. Suppose programs are unbeatable in another 10-20 years, which might well happen. That does _not_ mean the game is solved, however. Solve implies a 100% certainty. We can't deliver that without exhaustively searching the entire game tree.

Post Reply