Is Chess solvable?

[disjunction]

[ QUOTE ]
Okay, so I've read before about endgame tablebases, and clearly there's a mind-numbing gap between the current coverage (wikipedia says all 6-piece endgames have been solved: 4 pieces, 2 kings) and the complete 32-piece endgame tablebase that would solve that pesky "chess" issue.

Are there any Folding-at-home type distributed efforts to advance this? Or is the effort pretty much proprietary?

And someone must have done the math somewhere to estimate the total storage space necessary for storing that data. Petabytes? Exabytes? Zettabytes?

[/ QUOTE ]

Bison I'm not quite sure what you're asking. If you want to explore all the possible moves with 32 pieces, the problem grows exponentially the further you look forward. In one step we can make 10 moves, change this horizon to 2 and there are 10*10 possible moves, etc. It is growing exponentially. (When you grow things exponentially, you very quickly exceed the number of atoms in the universe, it's no big deal)

By distributing the computing, you are increasing your computing power and storage arithmetically. It doesn't really help and won't even bring you close.

[Al68]

[ QUOTE ]
[ QUOTE ]
Although there is a limited number of legal moves, you have to consider the total number of combinations of all those legal moves. This would give you the total number of all possible endgames. This number is greater than the total number of atoms in the universe.

No, I'm not joking and I'm not making it up.
This is why IBM cannot just have their chess computer analize all possible endgames and always win. There is not enough computing power in the world to do that.
They have to try to teach the computor how to play, analize the strength of their position, anticipate future moves, etc., similar to the way a human plays.

[/ QUOTE ]

Can you show me the math behind your statement.

[/ QUOTE ]
Offhand, no, I can't. I may try to do a little research when I get the chance.
As far as where this claim came from, it was in a documentary about the IBM computer built to challenge the world chess champion, and the challenges they faced in building and programming the computer. They were asked why couldn't they just have the computer memorize every possible combination of legal chess moves, like you can do with a simpler game like checkers or tic tac toe, then it will always be a draw unless a mistake is made. That's when they said that the number of different combinations of legal chess moves is greater than the total number of atoms in the universe. So that was not an option.

[bisonbison]

Bison I'm not quite sure what you're asking. If you want to explore all the possible moves with 32 pieces, the problem grows exponentially the further you look forward. In one step we can make 10 moves, change this horizon to 2 and there are 10*10 possible moves, etc. It is growing exponentially. (When you grow things exponentially, you very quickly exceed the number of atoms in the universe, it's no big deal)

By distributing the computing, you are increasing your computing power and storage arithmetically. It doesn't really help and won't even bring you close.

Dis,

Oh, I'm not saying that I think this is a small issue, and I understand the implications of the exponential growth of possibilities. I'm just curious how the current effort to solve the 7-piece endgames is proceeding practically, and wondering what the theoretical processing time and required storage space is for that step, for the 8-piece, for the 9-piece, etc.

The followup question then is, who's generating these tablebases, and are they relying on proprietary technology to advance it (so their efforts are siloed) or are teams interested in solving the current frontier (7-piece games) using software that could marshall distributed computing to (at least in a minor way) augment their efforts?

[Al68]

According to Wikipedia, the number of atoms in the observable universe is estimated to be 10^80. And the game-tree complexity (the total number of possible games that can be played) of chess is 10^123.

I don't know how many bytes would be required to store each single "possible game", but no matter how small you make the "byte storage device", it wouldn't be able to store more bytes than the number of atoms it contains. So there would never be enough atoms in the universe to make the storage device. All of this tells me that chess cannot be "solved" completely, ever.

[disjunction]

[ QUOTE ]

Dis,

I'm just curious how the current effort to solve the 7-piece endgames is proceeding practically, and wondering what the theoretical processing time and required storage space is for that step, for the 8-piece, for the 9-piece, etc.

The followup question then is, who's generating these tablebases, and are they relying on proprietary technology to advance it (so their efforts are siloed) or are teams interested in solving the current frontier (7-piece games) using software that could marshall distributed computing to (at least in a minor way) augment their efforts?

[/ QUOTE ]

Ah, I misunderstood your question. I just read the wiki article and I had never heard of endgame tablebases before. This could be because I'm a dumb ass who avoids going to department seminars, or maybe it's more of a chess problem than a search problem. You'd have to be a theory geek as well as a chess geek to be up on this stuff. Maybe someone else can answer, I'm in awe right now because apparently a lot of people here are both. [img]/images/graemlins/laugh.gif[/img]

[valenzuela]

Al but many of those games would have missed mates.

[Philo]

And don't forget they have to program the computer to play specifically against Kasparov!

[chezlaw]

[ QUOTE ]
According to Wikipedia, the number of atoms in the observable universe is estimated to be 10^80. And the game-tree complexity (the total number of possible games that can be played) of chess is 10^123.

I don't know how many bytes would be required to store each single "possible game", but no matter how small you make the "byte storage device", it wouldn't be able to store more bytes than the number of atoms it contains. So there would never be enough atoms in the universe to make the storage device. All of this tells me that chess cannot be "solved" completely, ever.

[/ QUOTE ]
Can't we solve it with a quantumn computer. Searching every node on the tree simultaneously should only take a few minutes.

chez

[ChrisV]

[ QUOTE ]
Can't we solve it with a quantumn computer. Searching every node on the tree simultaneously should only take a few minutes.

[/ QUOTE ]

I don't really know what I'm talking about, but I'm not sure a quantum algorithm could be designed that could do this. The quantum algorithms I've seen are designed to find one specific "correct" result, for example encryption cracking.

In any case, a quantum computer of sufficient complexity to do this is a couple of centuries off, I would estimate.

[arahant]

[ QUOTE ]
[ QUOTE ]
Can't we solve it with a quantumn computer. Searching every node on the tree simultaneously should only take a few minutes.

[/ QUOTE ]

I don't really know what I'm talking about, but I'm not sure a quantum algorithm could be designed that could do this. The quantum algorithms I've seen are designed to find one specific "correct" result, for example encryption cracking.

In any case, a quantum computer of sufficient complexity to do this is a couple of centuries off, I would estimate.

[/ QUOTE ]

CENTURIES?!?! c'mon man....if it's doable, that is WAY too long. Look at the pace of advancement lately.

I'm actually willing to bet that chess is 'solved' within 100 years. Sadly, I only expect to live another 80 tops...