Author: Randall Shane
Date: 13:55:03 06/30/99
Go up one level in this thread
Trying again...
On June 30, 1999 at 16:27:33, Randall Shane wrote:
>On June 30, 1999 at 12:53:40, KarinsDad wrote:
>
>>On June 30, 1999 at 09:25:34, Randall Shane wrote:
>>
>>>Oops.
>>>
>>>I rechecked my calculations, and it came out to just under 2*166. Gotta work on
>>>it some more.
>>>
>>>Sorry about that.
>>
>>Not a problem. I thought that you must have either came up with a MAJOR paradigm
>>shift to get to 151 bits OR you forgot the promotions since 151 bits seems to be
>>the minimum number (at least in my spreadsheet) for all of the pawns still on
>>the board.
>>
>>Too bad it wasn't the paradigm shift since that would have been cool.
>>
>>KarinsDad :)
>
>
Well, I'll keep working -- it's a bit of a paradigm shift, but I'm not sure if I
have the right implementation.
The basic idea (in terms of encoding) was to discard base-2....
Here's what I had for the counting -- :
Define functions and terminology (since we're using ASCII) :
excess2(x) := {x<2 -> x; x>=2 -> x-2}
excess1(x) := {x<1 -> x; x>=1 -> x-1}
permut(a,x,y) := (a!)/(x!y!(a-x-y)!)
-- number of unique placements of x objects of one type, y of another
-- in a slots
permut(a,w,x,y,z,m,n,p,q) := (a!)/(w!x!y!z!m!n!p!q!)
valid_dist(pawns,n,b,r,q) :=
true if (excess2(n)+excess2(b)+excess2(r)+excess2(q)) <= 8-pawns
and n,b,r,q all nonnegative
false otherwise
-- Whether a particular count of knights, bishops, rooks, queens is
-- legal given the promotion possibilities with number of pawns
SUM(symbol,expression, formula)
The sum of 'formula' for all values of 'symbol' that satisfy 'expression'
Basically a text expression for the 'big sigma' summation symbol
can be extended as below to
SUM({list of symbols},{list of expressions},formula)
One possible upper bound for number of legal positions is
TM * PwCT * PbCT * EP *
SUM(Pw,0<=Pw<8,SUM(Pb,0<=Pb<8,(permut(48,Pw,Pb)*(3971-67*(Pw+Pb))*SUM({Nw,Bw,Rw,Qw,Nb,Bb,Rb,Qb},{valid_dist(Pw,Nw,Bw,Rw,Qw),valid_dist(Pb,Nb,Bb,Rb,Qb)},permut(62-Pw-Pb,Nw,Bw,Rw,Qw,Nb,Bb,Rb,Qb)
) ))
where TM is choices for whose move := 2
PwCT is the 9 choices for white pawn count
PbCT is the 9 choices for black pawn count
EP is the 9 choices for valid en-passant column (including one for not
legal) (this can be improved!)
permut(48,Pw,Pb) is the number of legal pawn positions with Pw white pawns
and Pb black pawns
(3971-67*(Pw+Pb)) is the number of legal dual king positions given Pw
white pawns and Pb black pawns, kings not next to each other, and castling
status represented by additional 'squares' for the king at home (details later
on the calc, but it's straightforward (and ugly) enumeration).
The "big expression" at the end is the possible permutations and positions
for the pieces. Summing over the range of valid_dist() provides all possible
positionless combos of pieces for one side, counting promotions. For 8 pawns,
there are 54, and for 0 pawns there are 2648.
This tkes care of all possible promotions. I want to rewrite program I did for
the calculation of the above number jsut to check, but for now I have it just
under 2**166. (I thought it was just under 2**151, but I believe I was
mistaken.)
My encoding method was loosely based on the above, with non-base 2 calculations
to extract the number of pawns. There are a few divisions, and a few stepped
enumerations of unique permutations (which can be done without a complete
enumeration, using lookup tables, in linear time). Unfortunately, it's not so
good. Gotta keep working....
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.