Solving chess with distributed parallel processing
Once in awhile someone asks me about the possibility of computers completely "solving" chess - coming up with a perfect opening that accounts for all possible moves and leads to a win no matter what the other side plays - possibly using a technique like massive distributed parallel processing (SETI@home style).
The answer is, of course, that in the first six moves there are over four quadrillion (4,096,000,000,000,000) possible positions and the count increases exponentially with each move. So basically brute force calculation is out of the question, even with ten thousand machines working on the problem.
This article, which is written by Steven Lopez from Chessbase (they code most of the strongest chess engines such as Deep Fritz), addresses the possibility of starting with the existing human analysis and solving from there.
That analysis actually does exist in one place. There's a massive collection of tomes called the ECO (the Encyclopedia of Chess Openings), that lists every opening known to man. It starts with the beginning of a certain opening and then lists all the strongest known variations that occur from there, then rates the end positions according to which side is winning. It also goes into sub-openings, some of which begin 10 or 15 moves deep.
The article concludes that it would still take 367,242 years to solve it all even with 10,000 computers evaluating 250,000 positions a second, and that assumes that the starting human analysis is always right -- and it isn't. I play an obscure line of the King's Indian Attack specifically because ECO says it's busted and, according to my coach (who is a very strong master), it's wrong.
It does take a very interesting and informed look at the problem, though, so if the nuts and bolts of the issue are of use to you, dig in.
The answer is, of course, that in the first six moves there are over four quadrillion (4,096,000,000,000,000) possible positions and the count increases exponentially with each move. So basically brute force calculation is out of the question, even with ten thousand machines working on the problem.
This article, which is written by Steven Lopez from Chessbase (they code most of the strongest chess engines such as Deep Fritz), addresses the possibility of starting with the existing human analysis and solving from there.
That analysis actually does exist in one place. There's a massive collection of tomes called the ECO (the Encyclopedia of Chess Openings), that lists every opening known to man. It starts with the beginning of a certain opening and then lists all the strongest known variations that occur from there, then rates the end positions according to which side is winning. It also goes into sub-openings, some of which begin 10 or 15 moves deep.
The article concludes that it would still take 367,242 years to solve it all even with 10,000 computers evaluating 250,000 positions a second, and that assumes that the starting human analysis is always right -- and it isn't. I play an obscure line of the King's Indian Attack specifically because ECO says it's busted and, according to my coach (who is a very strong master), it's wrong.
It does take a very interesting and informed look at the problem, though, so if the nuts and bolts of the issue are of use to you, dig in.