Author: Robert Hyatt
Date: 06:42:06 09/03/00
Go up one level in this thread
On September 02, 2000 at 02:00:33, Uri Blass wrote: >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). > Yes... but if the tabelbase says "win" you can't be sure it is a win. It could be a 50 move rule draw just as easily. This _already_ happens in today's tablebases. However the original question was just "how many unique positions are there?" and the path information _must_ be considered in that... because I can reach the "same" position with different sequences of moves, which limits what can happen after that position with respect to 50 moves and repetititions. >> >>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.