Author: KarinsDad
Date: 14:30:11 06/30/99
Go up one level in this thread
On June 30, 1999 at 16:55:03, Randall Shane wrote:
[snip]
>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....
Very impressive. My system does not take into account the number of permutations
per se (it indirectly does it based on bit arithmetic). Also, a permutation
system that does not fall directly into a given number of bits (for example: the
side to move falls into 1 bit; the king info falls into 12 bits) requires a
massive calculation to extract the data when data elements are not a power of 2
(due to multiplication of numbers not closely related to a power of 2). So,
although this may give you a good idea of the maximum number of bits, it will be
hard to enumerate.
Good work nonetheless!
BTW, due to a minor fluke in one of my adjustment algorithms, I now have 2 cases
at 165 bits and my number of 161-165 bit cases has raised to 69 out of 351. I
came up with another way to drop a bit, but it is so complex (with possible
conflictions with the other algorithms) that it will take me several days to
determine if it is feasible or not. I also have yet another compression
algorithm on the back burner which can drop as many as 5 bits, but it is even
more complex and will take quite a while (and a several page program) to
determine it's validity. Isn't bit manipulation fun?
KarinsDad :)
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.