Author: Uri Blass
Date: 13:29:05 10/01/01
Go up one level in this thread
On October 01, 2001 at 16:12:42, Robert Hyatt wrote: >On October 01, 2001 at 16:08:01, Uri Blass wrote: > >>On October 01, 2001 at 15:44:39, Robert Hyatt wrote: >> >>>On October 01, 2001 at 15:27:30, Dann Corbit wrote: >>> >>>>On October 01, 2001 at 15:14:07, Slater Wold wrote: >>>> >>>>>I am not a math expert, and I know a lot of you (Uri) out there are. So I ask >>>>>all you experts to solve this problem: >>>>> >>>>> *How many legal positions are their in chess?* >>>>> >>>>>Also, please take into account that the king will always be present on the >>>>>board. >>>>> >>>>>I understand that there will more than likely be more positions than actually >>>>>possible. Such as the position of PPPPPPPPK vs ppppppppk. But I am willing to >>>>>deal with these. >>>>> >>>>>What would be the formula, and more importantly, the solution to this? >>>> >>>>Nobody knows. Estimates vary from about 1.3e30 to 4e50 (2^100 to 2^168). >>>>But that does not take everything into account. In particular, the half-move >>>>clock changes the meaning of the position. >>> >>>I haven't seen any credible 2^100 examples. I have seen one detailed 2^168 >>>arithmetic encoding scheme that was provably correct. Whether the 168 can be >>>reduced or not is another question. I suspect it won't be beat by much, if at >>>all. >> >>My guess is that the number of legal position is something close to 2^140. >>It does not mean that it is possible practically to use 140 bits for the >>positions. >> >>It is possible to get a good estimate by generating random pseudo legal >>positions and counting the number of legal positions from them >> >>Explanation:the first thing that we need for a good estimate is to have a good >>program to generate an upper bound for the number of legal position and after >>doing it the way to choose a random pseudolegal position is by the following >>steps: >> >>(note: by material structure I mean the number of white queens.white rooks,white >>bishops,white knights,white pawns and the same for black >> >>By pawn structure I mean only to the number of pawns and passed pawns of every >>side in every file.) >> >> >>1)choose a random number >>2)calculate material structure+pawn structure based on the interval of that >>number. >>3)choose a random position with the relevant material structure and pawn >>structure based on the number. >> >> >> >>After choosing 1000 random positions we can look at everyone of them and decide >>if it is legal or not legal(it may be illegal for many reasons for example one >>possible reason is that both kings may be in check) >> >>Suppose that we find that exactly 20 positions out of 1000 are legal and we also >>find that the upper bound is 10^40 then we can say that 10^40*20/1000 is a good >>estimate for the number of legal positions in chess when you do not consider >>side to move or castling or en passant rule. >> >>This is not something that is easy to do but I believe that it is possible to do >>it >> >>Uri > > >That is called a Monte-Carlo approximation. It might well work. But finding >that upper bound is not going to be easy. The 2^168 is the shortest encoding >of a full chess position I have seen. That probably means that is very close >the the actual number of different positions there are. Note that some illegal >positions were not included in this count (pawns on first rank for example). >But some were (IE no restriction on check, etc.) I do not see how to include restrictions on check in calculating the upper bound and my idea also does not include restrictions on check. I believe that some illegal material strcture were included on the count that you talk about because if I count only the number of positions of possible material structure when I restrict pawns to be not in the first or the last rank I get less than 2^160. I guess for example that positions with 32 pieces without the original material structure were included or that positions with 31 pieces when the side with 16 pieces promoted 3 pawns were included(this side can promote at most 2 pawns). 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.