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.
User avatar
Leto
Posts: 2052
Joined: Thu May 04, 2006 1:40 am
Location: Dune

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

Post by Leto » Sat Jul 21, 2007 6:52 am

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...
You might find this article interesting:
http://www.sciencenews.org/pages/sn_arc ... 9/bob2.htm

"David Deutsch and Artur Ekert of the University of Oxford in England have considered how a chess-playing quantum computer would use Grover's procedure. It could investigate a trillion possible continuations from a given position in the same number of steps as a conventional computer would need to check out a million. Quantum superposition allows the computer to cancel out a lot of unpromising possibilities that a conventional computer must look into one by one."

Uri Blass
Posts: 8943
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

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

Post by Uri Blass » Sat Jul 21, 2007 7:59 am

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...
This is not correct that there are more chess positions than atoms in the universe.

number of atoms in the universe is clearly more than 10^50 when number of chess positions is clearly less than 10^50

Number of chess positions also prove nothing about the possibility of solving chess because it may be possible to solve chess without analyzing all positions.

Uri

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

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

Post by Tord Romstad » Sat Jul 21, 2007 8:11 am

bob wrote: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.
It is not at all obvious that you need to inspect every possible chess position in order to solve chess. At least in principle, it could happen that we discover theorems (with the help of very sophisticated computer programs) which can classify huge classes of positions as won, lost or drawn without searching every single position. As a trivial example, consider the endgame of KR vs K: It is easy to prove by hand that the side with the rook is winning, without looking at a big number of concrete positions.

The world "solved" is also not quite as easy to define as it might first appear. Imagine that some time in the distant future, we have built some super-powerful AI vastly more intelligent than ourselves, and that this AI writes a program which solves chess, using algorithms so complicated that no human could possibly understand them. The AI tells us that "chess is a draw", but cannot explain us how or why in a language we can understand. In this scenario, would you say that chess has been solved?

Tord

Martin Thoresen
Posts: 1833
Joined: Wed Jun 21, 2006 10:07 pm

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

Post by Martin Thoresen » Sat Jul 21, 2007 10:15 am

Tord,

With talk like that I really want to watch a good sci-fi movie. ;)

Gandalf

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

Post by Gandalf » Sat Jul 21, 2007 10:27 am

Knowing that advances in computing speed are not linear, isn't it at least plausible that with distributed computing in, say, 50 years solving chess could be achieved?

gerold
Posts: 10121
Joined: Wed Mar 08, 2006 11:57 pm
Location: van buren,missouri

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

Post by gerold » Sat Jul 21, 2007 12:39 pm

Gandalf wrote:Knowing that advances in computing speed are not linear, isn't it at least plausible that with distributed computing in, say, 50 years solving chess could be achieved?
State-space complexity of 10 to the 46th Chess will not be solved.

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 » Sat Jul 21, 2007 4:17 pm

Leto 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...
You might find this article interesting:
http://www.sciencenews.org/pages/sn_arc ... 9/bob2.htm

"David Deutsch and Artur Ekert of the University of Oxford in England have considered how a chess-playing quantum computer would use Grover's procedure. It could investigate a trillion possible continuations from a given position in the same number of steps as a conventional computer would need to check out a million. Quantum superposition allows the computer to cancel out a lot of unpromising possibilities that a conventional computer must look into one by one."
"trillion" being the failing point. We need to cover about 2^160 positions. A trillion is about 2^40. Leaving a paltry 2^120 units of time to search those...

Better break out the s'mores and soft drinks. we gonna be here a while...

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 » Sat Jul 21, 2007 4:20 pm

Uri Blass 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...
This is not correct that there are more chess positions than atoms in the universe.

number of atoms in the universe is clearly more than 10^50 when number of chess positions is clearly less than 10^50

Number of chess positions also prove nothing about the possibility of solving chess because it may be possible to solve chess without analyzing all positions.

Uri
It takes 2^160 bits to encode a chess position. And that ignores the 50 move rule and repetitions. To prove the game won, lost or drawn is _far_ more than just enumerating all the possible positions. Pathways have to be included and that turns this into a _huge_ problem. And "huge" doesn't really do it justice.

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 » Sat Jul 21, 2007 4:22 pm

Tord Romstad wrote:
bob wrote: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.
It is not at all obvious that you need to inspect every possible chess position in order to solve chess. At least in principle, it could happen that we discover theorems (with the help of very sophisticated computer programs) which can classify huge classes of positions as won, lost or drawn without searching every single position. As a trivial example, consider the endgame of KR vs K: It is easy to prove by hand that the side with the rook is winning, without looking at a big number of concrete positions.

The world "solved" is also not quite as easy to define as it might first appear. Imagine that some time in the distant future, we have built some super-powerful AI vastly more intelligent than ourselves, and that this AI writes a program which solves chess, using algorithms so complicated that no human could possibly understand them. The AI tells us that "chess is a draw", but cannot explain us how or why in a language we can understand. In this scenario, would you say that chess has been solved?

Tord
There is other issues. As I mentioned previously, "paths" are critical because of repetitions and the 50-move rule.

As far as your question, no. The proof has to be verifiable in order to be accepted. I've already seen way too many programs claim a mate in N when it is a mate in N-x or N+x or not even a mate at all because of repetitions or the 50 move rule.

Uri Blass
Posts: 8943
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Checkers Not (completely) Solved

Post by Uri Blass » Sat Jul 21, 2007 4:25 pm

Dirt 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.
One standard of considering a game "solved" is that an optimal move, in the sense never converting a won position into a draw or a draw into a loss, can be determined for every reachable position. This standard has not been achieved in checkers. They have "only" shown that with best possible play the result is a draw.

Proving chess to be a draw is probably also much easier than creating a full 32-piece set of tablebases. A certain draw for chess may be easy enough that it is eventually proved, but I am amazed such an exact time frame for success would be suggested.
Another meaning of solving a game is if there is a program that the perfect player is unable to beat in a match.

I suspect that checkers was solved by this meaning already some years ago.

I remember that the last checkers computer tournament was from predefined positions and even in this conditions almost all the games were drawn so I suspect that playing from the opening position when programs can use opening book could lead to 100% draws by the top programs.

Uri

Post Reply