Author: Robert Hyatt
Date: 13:12:42 10/01/01
Go up one level in this thread
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.)
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.