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 » Sat Jul 21, 2007 4:26 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?
If you somehow believe that computers of 50 years in the future will be able to compute about 2^120 times faster than todays computers, then yes. But in the past 50 years, we have only moved from millisecond operations to .1ns operations. About 10M (~2^23) times faster. I somehow doubt that the next 50 years is going to multiply that by 2^120 or so...

This is an enormous search space. Too many are hanging up on the concept of 2^160 possible ways to put the pieces on the board. That is just a starting point. Because now you have to ask OK, for each of those positions, how many different ways are there to reach that position legally? That makes this impossibly large...

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

Re: Checkers Not (completely) Solved

Post by bob » Sat Jul 21, 2007 4:29 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.
I don't follow you. They _have_ searched from the starting position in checkers, such that _every_ pathway ended in one of the endgame databases. They can't do it anywhere near real-time. But since they can do it in reasonable time (even if it takes a year) we know that technology will reduce that year by year until it becomes real-time.

But chess? not gonna happen.

Uri Blass
Posts: 8972
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 4:45 pm

bob wrote:
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.
1)In case that the result is draw even without considering the 50 move rule no path needs to be included.

drawn 6 position by tablebases are drawn.
Won chess position by tablebases may be not won because of the 50 move rule but if you say that 6 piece position is drawn I consider it as solving the position and solving the initial position of chess is considered by me as solving chess.

If you build 32 piece tablebases then it is clear that drawn positions are draw and if we find by these tablebases that the opening position is drawn position then chess is solved to be a draw.

Solving a game does not mean solving every possible chess position but only determining the value of the opening position.

2)Note that even if you consider the 50 move rule then you can still solve every possible chess position in case that you have enough memory and 10^50 bits are clearly enough.

You simply divide the position to classes based on material and pawn structure and do a loop on all chess positions in a class.
first step:is determining the result of mate position.
second step is determining the result of positions when the side to move can mate in 1 move or play winning capture or pawn move in one move as win in 1(I assume that you already built the class of positions with less position or with more advanced pawn structure earlier).

You can continue in this way 100 times and say that the rest of the positions in a class are drawn by the 50 move rule.

Considering repetition is also no problem because you can mark position that were repeated twice in the game earlier as a draw(position that happened in the past of the game only one time are not relevant because the shortest way to win does not include repeating them twice so the number of legal chess positions is more than 10^1000 if you include paths but you have an algorithm to solve every possible chess position in O(10^50) steps(assuming that you enough memory).

Uri

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 7:17 pm

Uri Blass wrote:
bob wrote:
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.
1)In case that the result is draw even without considering the 50 move rule no path needs to be included.
How do you prove the result without considering those cases? There are obviously _many_ games that will go beyond 50 moves.

drawn 6 position by tablebases are drawn.
Won chess position by tablebases may be not won because of the 50 move rule but if you say that 6 piece position is drawn I consider it as solving the position and solving the initial position of chess is considered by me as solving chess.
Such claims would be wrong however. You could follow the computer's suggestions perfectly and a forced win would turn into a draw because in real games, _all_ rules have to be followed...

So you either have to store the endgame tables that are large enough such that you reach 'em from the starting position, or you have to be able to search deeply enough to reach positions you can evaluate with 100% accuracy. Either task is way beyond daunting. Not enough storage to store those endgame tables. 5 pieces take 7 gigs. 6's take way over 1 TB (a factor of at least 100x larger). Just the 10 piece endings would blow the capacity of every disk drive ever made added together.


If you build 32 piece tablebases then it is clear that drawn positions are draw and if we find by these tablebases that the opening position is drawn position then chess is solved to be a draw.
There we agree. But building such databases is, and always will be, completely impossible, until you can find a way to store billions of petabytes in a single atom.


Solving a game does not mean solving every possible chess position but only determining the value of the opening position.

2)Note that even if you consider the 50 move rule then you can still solve every possible chess position in case that you have enough memory and 10^50 bits are clearly enough.
What good is that? we don't have any way to store 10^50 bits, which I don't believe is enough. If you don't index intelligently, which would require more like 2^160 entries, then the cost of searching for a position match would be just as daunting as trying to store the thing in the first place...

You simply divide the position to classes based on material and pawn structure and do a loop on all chess positions in a class.
first step:is determining the result of mate position.
second step is determining the result of positions when the side to move can mate in 1 move or play winning capture or pawn move in one move as win in 1(I assume that you already built the class of positions with less position or with more advanced pawn structure earlier).

You can continue in this way 100 times and say that the rest of the positions in a class are drawn by the 50 move rule.
That won't work, and is the same flaw as in the current endgame tables. Things drawn by 50 moves are not absolute draws if you can take time out to reset the 50-move counter by making an unimportant trade or pawn push to delay the 50-move rule kicking in. You can't just say "this is drawn because no pawn has been pushed nor piece captures in the last 50 moves." So you end up having to have _all_ the complete N-x piece endgame tables before you can do the Nth. If you think this can be done in 50 years, more power to you. Based on the last 50 years of development, the next 500 years won't produce enough advances to touch this problem. Nor the next 5000. By the time our sun starts to dim, in a few hundred million years, we _might_ have made a dent in the problem, but not solved it.

Considering repetition is also no problem because you can mark position that were repeated twice in the game earlier as a draw(position that happened in the past of the game only one time are not relevant because the shortest way to win does not include repeating them twice so the number of legal chess positions is more than 10^1000 if you include paths but you have an algorithm to solve every possible chess position in O(10^50) steps(assuming that you enough memory).

No assumptions allowed here. You _must_ have it. And that is a problem. 10^50 is a number way beyond doing...


Uri

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

Re: Checkers Not (completely) Solved

Post by bob » Sat Jul 21, 2007 7:18 pm

Uri Blass wrote:
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
Sorry, but I (nor anyone else) accepts that definition of "solved". Solved means solved, as in the result is "proven". And "proven" does not mean just playing games and never losing. Every move has to be proven optimal so that mistakes don't influence the final result...

Terry McCracken

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

Post by Terry McCracken » Sat Jul 21, 2007 10:24 pm

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.

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.

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!

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!

I have seen the impossible be done and I'll see it again!

Terry

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 10:33 pm

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

Terry McCracken

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

Post by Terry McCracken » Sat Jul 21, 2007 10:56 pm

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!

Uri Blass
Posts: 8972
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 11:13 pm

bob wrote:
Uri Blass wrote:
bob wrote: 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.
1)In case that the result is draw even without considering the 50 move rule no path needs to be included.
How do you prove the result without considering those cases? There are obviously _many_ games that will go beyond 50 moves.

My claim is that drawn nalimov tablebases position are always drawn.

If both sides cannot win even when I ignore the 50 move rule then they certainly cannot win.

It is clearly possible that chess is a draw in case that you ignore the 50 move rule and in this case tablebases that are similiar to nalimov tablebases are enough to prove that chess is a draw.
bob wrote:
Uri Blass wrote: drawn 6 position by tablebases are drawn.
Won chess position by tablebases may be not won because of the 50 move rule but if you say that 6 piece position is drawn I consider it as solving the position and solving the initial position of chess is considered by me as solving chess.
Such claims would be wrong however. You could follow the computer's suggestions perfectly and a forced win would turn into a draw because in real games, _all_ rules have to be followed...

So you either have to store the endgame tables that are large enough such that you reach 'em from the starting position, or you have to be able to search deeply enough to reach positions you can evaluate with 100% accuracy. Either task is way beyond daunting. Not enough storage to store those endgame tables. 5 pieces take 7 gigs. 6's take way over 1 TB (a factor of at least 100x larger). Just the 10 piece endings would blow the capacity of every disk drive ever made added together.

I do not claim that it is practically possible to do it in that way but only that it is not correct that you need more atoms than the number of atoms in the universe.

If you build 32 piece tablebases then it is clear that drawn positions are draw and if we find by these tablebases that the opening position is drawn position then chess is solved to be a draw.
There we agree. But building such databases is, and always will be, completely impossible, until you can find a way to store billions of petabytes in a single atom.
I disagree that you need to store billion of perabytes in a single atom to build such database.

The number of atoms is more than 10^50.
I do not claim that it is possible to do it but only that you cannot prove that
it is impossible based on the number of atoms.

Solving a game does not mean solving every possible chess position but only determining the value of the opening position.

2)Note that even if you consider the 50 move rule then you can still solve every possible chess position in case that you have enough memory and 10^50 bits are clearly enough.
What good is that? we don't have any way to store 10^50 bits, which I don't believe is enough. If you don't index intelligently, which would require more like 2^160 entries, then the cost of searching for a position match would be just as daunting as trying to store the thing in the first place...
I do not claim that we have practically a way to store 10^50 bits and
I do not know if we will have in the future a way to do it.

My claim is that 10^50 bits are enough

You simply divide the position to classes based on material and pawn structure and do a loop on all chess positions in a class.
first step:is determining the result of mate position.
second step is determining the result of positions when the side to move can mate in 1 move or play winning capture or pawn move in one move as win in 1(I assume that you already built the class of positions with less position or with more advanced pawn structure earlier).

You can continue in this way 100 times and say that the rest of the positions in a class are drawn by the 50 move rule.
That won't work, and is the same flaw as in the current endgame tables. Things drawn by 50 moves are not absolute draws if you can take time out to reset the 50-move counter by making an unimportant trade or pawn push to delay the 50-move rule kicking in. You can't just say "this is drawn because no pawn has been pushed nor piece captures in the last 50 moves." So you end up having to have _all_ the complete N-x piece endgame tables before you can do the Nth. If you think this can be done in 50 years, more power to you. Based on the last 50 years of development, the next 500 years won't produce enough advances to touch this problem. Nor the next 5000. By the time our sun starts to dim, in a few hundred million years, we _might_ have made a dent in the problem, but not solved it.
I agree that you need to do the complete N-x piece tablebases before you do the N piece tablebases.

I did not claim to know if it can be done in 50 years for N=32.
I only claim that it is not correct that you need more bits than the number of atoms in the universe to do it.

Uri

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:37 am

Uri Blass wrote:
bob wrote:
Uri Blass wrote:
bob wrote: 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.
1)In case that the result is draw even without considering the 50 move rule no path needs to be included.
How do you prove the result without considering those cases? There are obviously _many_ games that will go beyond 50 moves.

My claim is that drawn nalimov tablebases position are always drawn.

If both sides cannot win even when I ignore the 50 move rule then they certainly cannot win.
My claim is that many positions that are claimed to be wins are actually draws because of existing rules in the game. And that means that you can't prove the game is won, lost or drawn. period.

Because at some positions you will think you are lost and prune when in fact it is drawn, leaving you with only moves where you might win or draw or lose. And that bogus loss (or bogus win) causes you to prune incorrectly.

You can't prove the game is drawn if the only question you can ask and get answered is "is this position drawn?" If you can't trust win/lose results then how would you ever prove anything where you encounter those results and have to make decisions based on the answers. Even in drawn endings there are _tons_ of winning and losing positions that have to be handled as well...


It is clearly possible that chess is a draw in case that you ignore the 50 move rule and in this case tablebases that are similiar to nalimov tablebases are enough to prove that chess is a draw.
I don't disagree. with a very big IF... IF you can store them. That is what I believe is completely impossible for all time... the number is just too big.

bob wrote:
Uri Blass wrote: drawn 6 position by tablebases are drawn.
Won chess position by tablebases may be not won because of the 50 move rule but if you say that 6 piece position is drawn I consider it as solving the position and solving the initial position of chess is considered by me as solving chess.
Such claims would be wrong however. You could follow the computer's suggestions perfectly and a forced win would turn into a draw because in real games, _all_ rules have to be followed...

So you either have to store the endgame tables that are large enough such that you reach 'em from the starting position, or you have to be able to search deeply enough to reach positions you can evaluate with 100% accuracy. Either task is way beyond daunting. Not enough storage to store those endgame tables. 5 pieces take 7 gigs. 6's take way over 1 TB (a factor of at least 100x larger). Just the 10 piece endings would blow the capacity of every disk drive ever made added together.

I do not claim that it is practically possible to do it in that way but only that it is not correct that you need more atoms than the number of atoms in the universe.

If you build 32 piece tablebases then it is clear that drawn positions are draw and if we find by these tablebases that the opening position is drawn position then chess is solved to be a draw.
There we agree. But building such databases is, and always will be, completely impossible, until you can find a way to store billions of petabytes in a single atom.
I disagree that you need to store billion of perabytes in a single atom to build such database.

The number of atoms is more than 10^50.
I do not claim that it is possible to do it but only that you cannot prove that
it is impossible based on the number of atoms.

Solving a game does not mean solving every possible chess position but only determining the value of the opening position.

2)Note that even if you consider the 50 move rule then you can still solve every possible chess position in case that you have enough memory and 10^50 bits are clearly enough.
What good is that? we don't have any way to store 10^50 bits, which I don't believe is enough. If you don't index intelligently, which would require more like 2^160 entries, then the cost of searching for a position match would be just as daunting as trying to store the thing in the first place...
I do not claim that we have practically a way to store 10^50 bits and
I do not know if we will have in the future a way to do it.

My claim is that 10^50 bits are enough

You simply divide the position to classes based on material and pawn structure and do a loop on all chess positions in a class.
first step:is determining the result of mate position.
second step is determining the result of positions when the side to move can mate in 1 move or play winning capture or pawn move in one move as win in 1(I assume that you already built the class of positions with less position or with more advanced pawn structure earlier).

You can continue in this way 100 times and say that the rest of the positions in a class are drawn by the 50 move rule.
That won't work, and is the same flaw as in the current endgame tables. Things drawn by 50 moves are not absolute draws if you can take time out to reset the 50-move counter by making an unimportant trade or pawn push to delay the 50-move rule kicking in. You can't just say "this is drawn because no pawn has been pushed nor piece captures in the last 50 moves." So you end up having to have _all_ the complete N-x piece endgame tables before you can do the Nth. If you think this can be done in 50 years, more power to you. Based on the last 50 years of development, the next 500 years won't produce enough advances to touch this problem. Nor the next 5000. By the time our sun starts to dim, in a few hundred million years, we _might_ have made a dent in the problem, but not solved it.
I agree that you need to do the complete N-x piece tablebases before you do the N piece tablebases.

I did not claim to know if it can be done in 50 years for N=32.
I only claim that it is not correct that you need more bits than the number of atoms in the universe to do it.

Uri

Post Reply