Author: Robert Hyatt
Date: 12:44:39 10/01/01
Go up one level in this thread
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. > >For sure the number of distinct board positions (discounting 50 move rule and >non-reversible moves) is not larger than 2^168 because chess positions have been >encoded perfectly in 168 bits. Therefore, we can number them all in 4e50 >distinct encodings. And that does not subtract all the illegal moves. I belive >that Uri has done some interesting work on counting legal board positions. I >even built a binary for him once, but I don't remember what the result was. The >figure of 2^100 comes from an entropy study where GM's asked yes/no questions >about the board position and were able to deduce the actual arrangment in less >than 100 guesses.
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.