Author: Dann Corbit
Date: 17:10:25 05/21/99
Go up one level in this thread
On May 21, 1999 at 19:33:51, blass uri wrote: >On May 21, 1999 at 12:49:59, KarinsDad wrote: > >>On May 20, 1999 at 15:24:36, Dann Corbit wrote: >> >>>On May 20, 1999 at 14:13:34, Dann Corbit wrote: >>>[snip] >>>>>The thread about representing positions in the minimum number of bits is also >>>>>about setting an upper bound on the maximum number of chess positions. 160 bits >>>>>is 2^160 or ~= 10^48. >>>>Yes, what a fascinating rejoinder! In this case, if 10^52 is correct, then 173 >>>>bits should be the minimum, since 2^173 = 1.197e52 >>>>If we can encode in less, then the number of board positions is less than we >>>>thought (or we have an error in our thinking and the scheme won't work). >>>Which brings up another fascinating idea. If we can come up with a minimal >>>encoding, we can bound the maximum possible number of chess positions. If the >>>claim that all positions can be encoded in 100 bits is true, then there are >>>"only" about 1e30 board positions!! Several orders of magnitude below any limit >>>claimed that I know of. After all, if the mapping really is invertible, we will >>>have a one to one and onto map from a 100 bit binary number to all possible >>>board positions! >> >>Dann, >> >>Where did you come up with this 100 bit possibility? >> >>It seems extremely unlikely that this is true for 2 reasons. One, is that the >>10^30 board positions is many many magnitudes lower than even the most >>aggressive minimum number of positions estimate that I have ever read. >> >>Secondly, after spending many hours on attempting to decrease the minimum even >>to 160 bits, I cannot even fathom a paradigm shift (such as a compression scheme >>after getting to the 170+ bit range) that would enable someone to decrease the >>documented minimum (of approximately 173 bits) by over 40%. This seems absurd to >>me. > >This seems absurd also to me. > >I think that we can prove practically that it is impossible. > >I believe that we needs more than 100 bits only to represent the positions when >every side has exactly 2 queens,2 rooks,2 bishops,2 knights,2 pawns. > >The first step to prove it is to create 1000 random positions with this material >configuration when the pawns are at legal squares. > >It is not hard to create the random positions by a program. > >we have 48*47/2=1128 cases for white pawns. >46*45/2=1035 cases for black pawns, >60*59=3540 cases for kings > >58*57/2=1653 cases for white queens, 56*55/2=1540 cases for black queens >54*53/2=1431 cases for white rooks,52*51/2=1326 cases for black rooks >50*49/2=1225 cases for white bishops,48*47/2=1128 cases for black bishops >46*45/2=1035 cases for white knights,44*43/2=946 cases for black knights > >If we multiply these 11 numbers we get more than 2^110 > >The second step is to check how many random position out of 1000 are legal. > >If we assume that there are less then 2^100 positions then we expect probability >of less than 1/1024 for a legal position by putting the pieces at random >squares. > >I believe that more than 1/1000 of these random positions are legal but I am not >sure because I did not do this experiment. I think the legal positions may be much more rare than you imagine. Imagine (for instance) that we put the kings on first. Now, neither king can sit next to the other one, so both of them have an invisible circle around them. Also, when we are done, we cannot have both kings in check. It might be as small as one in a million positions that are legal. I have no idea, really, what the ratio is but intuition can be a tricky way to make such a judgement. At any rate, you can well imagine that I am interested in that paper by J. N.
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.