Author: blass uri
Date: 10:31:20 04/23/00
Go up one level in this thread
On April 23, 2000 at 12:16:54, Bruce Moreland wrote: >Did you guys ever determine an upper bound for this? I can't remember what >happened last time we went through this. But I know that if you can count the >legal positions, you are done. You just take log2(total) and you are done, you >can't do any better than that if you are talking about the minimum number of >bits necessary to store *any* position. > >If you put a white pawn on the board, there are 48 places it can go. The next >white pawn has 47 places, and so on through the white pawns and black pawns. >The first white knight has 48 places, since 16 squares are occupied by pawns, >and there are 48 left. The second white knight has 47, and so on. > >If you continue doing this you get 2.23*10^51, which is 171 bits. There is a different way to calculate it. calculate an upper bound for every material configuration and calculate a sum of these numbers by a computer program. I did it in the past and I found that the sum is clearly smaller. I do not rmemeber the exact number now but It was less 2^160(I did not take into account game history and 50 move rule and castling rights en passant rule and side to move). I think the number was something like 2^156 but I am not sure. I have an idea how to improve the bound by calculating an upper bound for every configuration of material+information about the number of good pawns(I define good pawns as passed pawn or pawns that have another pawn with the same colour on the same file) but calculating the sum can take a long time(a program may need some days for it) so I did not do a program to solve this problem > >This does not include cases where pieces have been captured, or where pawns have >been promoted. And it also doesn't cover cases with different castling flags >(this should be minor), or cases with different en-passant values (possibly a >little more major). Of course it doesn't take into account illegal positions, >but even if 90% of positions are illegal (which has got to be way too much), you >only subtract three or four bits. more than 90% and even more than 99.9999% of your positions are illegal. If you consider only cases with no captures there are only 15^8 options for pawns and not 48*47*46*45*44*43*42*41*40*39*38*37*36*35*34*33/(8!)^2 that is the number of possibilities to put 16 pawns on the board when you do not have to put 2 pawns in every file. The part of the legal positions is about 8!^2*15^8/40^16 48*....33 is something close to 40^16 8!=40320 and (8!)^2<40^6 so less than 15^8/40^10 of your cases are legal positions and it is clearly less than 1/1000000 of the cases. 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.