Author: Uri Blass
Date: 13:08:01 10/01/01
Go up one level in this thread
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
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.