Author: Bruce Moreland
Date: 20:36:47 04/23/00
Go up one level in this thread
On April 23, 2000 at 13:31:20, blass uri wrote: >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. Yes, I made a mistake. bruce
This page took 0.02 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.