Author: Dann Corbit
Date: 13:25:01 01/08/03
Go up one level in this thread
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.
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.