Author: Uri Blass
Date: 23:00:33 09/01/00
Go up one level in this thread
On September 01, 2000 at 23:41:29, Robert Hyatt wrote: >On August 31, 2000 at 15:54:16, Frederic Friedel wrote: > >>On August 31, 2000 at 15:01:18, Vincent Lejeune wrote: >> >>>If I remember well I red in a magasin some years ago that there is 10^80 >>>possible positions and there is 10^120 different playable games (no >>>demonstration was given). >> >>There are 10^112 possible games lasting 40 moves. This is considerably more than >>the 10^82 elementary particles in the universe. It is clear that, for principle >>reasons, all possible games will not be reconstructed (generated and stored) in >>the course of this universe. >> >>But we don?t need to do that in order to solve chess (in the Thompson endgame >>sense). The number of possible legal chess positions is far smaller: between >>10^53 and 10^55. So will we (or someone or something) be able to work them out, >>effectively retro-analysing the 32-piece endgame chess represents? >> >>Again the answer is no, but not on principle grounds but for practical reasons. >>A computer processing a billion positions per second would require about 10^38 >>years to solve the game. If you use a billion computers in perfect >>multi-processing you will still have to wait 10^29 years for the answer (and if >>you are not careful with the program it might simply produce ?42?). >> >>But there is still a major problem. You cannot store the tables on CDs or DVDs. >>As John Nunn explained to me we will need the matter from many millions of >>galaxies to store the information that is generated. So solving the game using >>the method of exhaustive analysis is theoretically possible, but one wonders >>what Greenpeace would say if we started dismantling galaxies in order to store >>chess positions. > > >This is way too simplistic an estimate, unless the 50 move rule and 3-fold >repetition rules are discarded. In reality there are nearly an infinite number >of positions, because each position is unique to the path leading to it. Just >because the same piece configuration has been reached in two or more positions, >the positions are not guaranteed to be equal. How many different pathways can >be spanned to reach those identical positions? And how do those pathways >affect the 50 move and repetition rules? > >When you take a single position with the 32 pieces (or fewer) placed on the >board in a legal configuration, and then try to enumerate all the pathways >from the original position which can lead to these two identical positions, >the number of pathways is absolutely enormous. And each "identical" position >would be different because the moves played _after_ each of these positions >would inherit different 50 move counters and different repetition lists. Repetitions are not relevant for the 32 piece tablebases so they are not relevant for the complexity of the problem of solving the game. The 50 moves rule is usually not relevant and a program that has the 32 piece tablebases without considering the 50 move rule probably can solve the game(It can solve the game without the 50 move rule and if it say that the game is drawn then you can be sure that the game without the 50 move rule is also drawn). > >I think you could safely say that the game is nearly infinite... or at least >so large that the difference between the real number and infinity is not >easy to interpret. I agree that you can safely say that the number is so big that the game will not be practically solved. Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.