Author: Uri Blass
Date: 13:31:57 01/08/03
Go up one level in this thread
On January 08, 2003 at 16:25:01, Dann Corbit wrote: >On January 08, 2003 at 16:00:47, Uri Blass wrote: > >>On January 08, 2003 at 15:41:28, Dann Corbit wrote: >> >>>On January 08, 2003 at 13:41:39, S. Loinjak wrote: >>> >>>>Thank you very much for the reply and escpecially for the hint about Petrovich's >>>>calculation (he seems to be a famous retrograde analysis composer). >>>> >>>>Does someone know how Petrovich came to his result and what kind of positions he >>>>regarded as being different. Has he taken into account the right to move, >>>>castling rights, e.p. rights and all possible material distributions (max. 8 >>>>promoted pawns per color). >>>> >>>>Let me give the following specification: >>>> >>>>N = number of legal positions in chess >>>>-------------------------------------------------- >>>>positions are different when they would generate different sets of legal moves >>>>so even optically identical positions must be counted up to 192 times (if we >>>>cannot prove that some of the special cases are impossible) >>>>-- color to move (counts twice) >>>>-- castling (max. 16 combinations per position) >>>>-- e.p.rights (max. 6 combinations) >>>>(example for max. en passant diversity: pawns on 4th rank: wbwwbwbw >>>>==> either one or none of the 5 white pawns moved to the 4th rank a ply before, >>>>all could be captured by an opposite pawn ) >>>> >>>> >>>>-------------------------------------------------- >>>> >>>>Based on the technical level of the year 1978 when Petrovichs got his result N >>>><= 2*10^43 I'd say this must have been a comparably short calculation. And I >>>>really doubt although I don't know the method he used that he has taken really >>>>everything into account (especially the underpromotions which can easily push up >>>>the number by at least 1000). >>>> >>>>I should not forget to mention Christoph Fieberg's result of N being >>>>approximately 3.02*10^46 published in CSS 2002/feb (CSS = Computer ,Schach und >>>>Spiele - in German). Although this result does not take into acount the color to >>>>move, the castling and the e.p. rights (this would push the estimation to >>>>roughly 6.0*10^48) it might be one of the rare calculations where really all >>>>underpromotions are counted correctly. >>>> >>>>My own computation to prove N < 1.0*10^46 runs for almost an hour on a 2 GHz PC >>>>- I use 256 MB for lookup tables for combinatoric values (products of binominal >>>>coefficients, results of certain local optimization problems) and so nothing is >>>>calculated twice. Originally I though it must be easy to prove that N < >>>>1.0*10^43 but meanwhile I think I'm quite near to the real number of the legal >>>>positions and I doubt there are less than 1.0*10^44 - I hope I'm wrong so chess >>>>could be easier to solve then it seems to me now. >>> >>>We should be able (according to these calculations) encode a complete chess >>>position into 155 bits or so. >>> >>>I remember KarinsDad used to work hard on this problem and had it down to >>>somewhere around 160 bits (I forget exactly). >>> >>>If someone can come up with a 155 bit encoding, it would forcibly prove that >>>there can be no more than 2^155 chess positions. >>> >>>Uri Blass wrote an interesting counting program a while back. I will try to >>>find the results from that program. He may have made improvements to it also. >> >>Retko v.Tomic improved my program but the difference was not big. >>I do not care about improving that program and it is more improtant for me to >>get rid of the bugs. >> >>I am surprised that movei could not only play but also give deterministic result >>when it used varaibles like numextensions[-1] >> >>I have numextensions[ply]=numextensions[ply-1] when ply-1=-1 for a long time(I >>am going to fix it. >> >>common sense tells me that it should lead to some garbage in numextension[0] >>that may lead to crush but for some reason it does not happen and movei is >>considered as relatively stable program(not like some programs that sometimes >>lose on time or have other problems like doing illegal moves). > >Reading beyond the bounds in an array is undefined behavior. That means that >anything can happen. Often, if there is a data object that precedes it in >memory, it will simply read from that data object. If it happens to be a code >object, you may get a crash. Or if you happen to write to it and it is in read >only space you may get a crash. >All sorts of strangeness is possible. The strange thing is that I did not get a crush because of that not in movei0.07a and not in later movei and I had many versions that I tested. I guess that movei was simply lucky to get the numextension[-1]=0 so it did not crush but I do not know. I already fixed it by int PADDED_ so I can call numextension[-1] when I really call PADDDED_numextension[0]. 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.