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