Author: Ratko V Tomic
Date: 21:29:59 11/01/99
Go up one level in this thread
> For example, with the kings handled by the 12 bits, and all possible promotions
> and no pawns, that would leave 62 squares and 26 pieces, or 36 empty squares.
> Since this is 58% white space, it seemed a good possibility for bitboard
> compression of same nature.
Bitboard is ideal when exactly 1/2 or 1/2^k portion is filled and with uniform
probability per square, otherwise if you use prefix codes of variable length,
such as Huffman code, you lose on roundoff to the next integer bit.
>Another compression idea of the bitboard with an SV method is to sort the
>squares by every nth square where n is a prime number (going back over
>the board each time). You could use 5 bits to indicate the number of
>pieces to look for and 3 bits to indicate which prime to use (1, 2, 3,
>5, 7, 11, 13, or 17). To enhance this even more, a start position set of
>bits could be added, but I am uncertain whether a 6 bit actual location
>or some form of exponential relative positioning indicator (fewer bits)
>would work better.
>
>The encoder finds out which prime works best (i.e. gets the largest number of
>piece locations the quickest). If you could use this to "jump" over the blank
>squares and then use a PA method to indicate the remaining pieces, once it is
>determined which pieces are missing. The other advantage of such a scheme is
>that since you have probably removed more than 32 squares in the first pass, the
>PA would start with a 5- bit pointer instead of with a 6- bit pointer and
>hopefully, this would then only be needed for 2 to 5 pieces anyway.
This method could work only when you're dealing with a small subset of all
legal positions, where such pattern may be of help. In fact you don't need
primes as sequence generator but only a common dictionary of most common
skip patterns (which are selected via tests against the actual data set).
Then you simply give index of the pattern, it's much more flexible than
primes for generating arbitrary sequences, and it's no more expensive to
give a dictionary sequence index than to give a prime index. The only
requirement is that encoder and decoder have the same skip sequence
dictionary.
For your objective, though, there is no real pattern or constraint to
all chess positions (other than legality of position, checks etc, and these,
I think we agree, don't amount to much savings).
>The other disadvantage of the PA method is that you also have to
>determine pawn promotions.
PA method assumes that encoder and decoder have agreed on an indexing scheme
to identify the material and a sequencing convention how the pieces are
scanned for a given material. So, if you have a list of all distinct material
possibilites, an index into such list identifies uniquely the material present.
Last time I gave you calculation for material possibilities without promotions
-- there were 236196 such distinct material possibilities, which is a 17.8 bits
index. Extending the same calculations to promotions would require a program to
classify all possibilities (using a max of 12 extra pieces due to promotions,
and
removing 4 pawns on every 3 additional promotion generated pieces, since that
is the best ratio of additional pieces one can get).
For the non-promotion the indexing is quite simple:
1) You always have 2 kings, so they don't add to material content index
2) Other pieces, Q,R,B,N,P have count values 0-1,0-2,0-2,0-2,0-8 for
white and black, hence your index is a number given in a mixed radix
representation (i.e. representation where each digit corresponds
to differnt radix), where digits correspond to Q,R,B,N,P,q,r,b,n,p
and radix for different digits is 2,3,3,3,9,2,3,3,3,9. The number
of up to ten digit numbers in this radix is MC(0)=(2*3^3*9)^2=236196.
To handle the promotion cases, one would need to enumerate all cases with
1 promotion (by reducing the max on pawns from 8 to 6, and by increasing the
max on one of Q, R, B, N from 1 or 2 to 2 or 3), 2 promotions, ... 12
promotions.
The max on pawns is dropped by 1 on b & w for the 1st promotion, then by a
single pawn (of the color of the extra piece) on the next 2 promotion etc (i.e.
every 3 promotions the max for pawn count is dropped by addional 4 pawns, and
for each triplet of promotions, the 1st one takes out 1 of b & w pawns, and the
next 2 promotions take one pawn per promotion).
Since pieces produced by promotions are indistingushable from regular pieces
(assuming you handle castle rights separately, e.g. with king pair encoding),
you wouldn't replicate same material possibility which occurs due to promotions
from those from non-promotions cases.
For example, in 1 promotions case, you would increase max, say on WQ (from 1
to 2), decrease the max on white pawns by 2, and enumerate as addition
only the positions with 2 W.Queens (but not 1 or 0 W.Queens since these
were already counted in 0-promotions case). So, by keeping W.Queen count
fixed (=2) we vary R,B,N,P,q,r,b,n,p where (P & p varie 0-7 this time), which
gives you MC=(3^3*8)*(2*3^3*8)=93312 new Material Content cases. Then one
would do same type calculation for R,B,N,q,r,b,n. For example, for 1 promotion
into R, one would count only cases with 3 white rooks (since cases with 2 white
rooks were already counted in 0-promotion case), resulting in:
MC=(2*3^2*8)*(2*3^3*8)=62208 cases. The number of cases for B or N producing
promotion is same as for rooks. Then the same sequence for black.
This totals (as new material contents cases) for 1 promotion:
MC(1)=2*104976+6*69984=559852 cases.
The combined MC(0)+MC(1)=796048=19.6 bits, which is an extra 1.75 bits
from the 18.7 bits in 0-promotions index.
For 2 promotions one has to distribute 2 new pieces, counting as above
only the cases with these two piece types maxed out (since other material
content cases were already counted in 0 or 1 promotion sets). If the two
new pieces are both white (i.e. the max on 2 white pieces increased),
the max on white pawns drops by 2 (to 6) and on black pawns by 1 (to 7),
and similarly if both new pieces are black. If one new piece is white and
one black, then the max on white and black pawns would be 7, but we would
have to exclude separately the cases when both actual counts are 7.
There are 8*9/2!=36 distinct ways to pick two new pieces out of 8 possible
(i.e. out of Q,R,B,N,q,r,b,n and we can pick twice the same new piece and we
don't count QR as distinct from RQ). For example, if we pick WQ and WR, the new
material content cases are those with 2 W.Queens and 3 W.Rooks (other cases
with 1 WQ, 3 WR were already counted in MC(1) set). So the
MC(Q,R)=(3^2*7)*(2*3^3*8)=27216. To go through the whole set of 36 pairs for 2
promotions, then on to 3 promotions, etc through 12 promotions, the paper and
pencil technique would take too long and a small brute force program (which
simply generates all possible material contents cases and checks that no
duplicates were seen before) is probably the quickest way to get the full
number. Even if each new promotion after 1, adds 1 new bit to MC index (i.e.
it doubles the total for all previous MC's, which it probably won't, we would
get to about 30 bits for indexing all material cases (all promotions and all
captures). The Q&D estimate of upper bound of number of all positions (for the
full material) is 134 bits, hence going through all material (roughly 30 bits)
we get 164 bits for all positions, very close to your target.
> This is not quite complete. You have to indicate with a PA method that the white
> queen knight is NOT on the board, that the white queen bishop is not on the
> board, etc., etc., etc. This takes up a lot of bits (minimum of 30 with some
> form of does piece exist bitboard). The total bits would be 1 side to move + 34
> kings and rooks + 30 piece exist = 65 bits.
I wasn't talking about general position (with arbitrary material) but only
as a specific counterexample to the validity of suggested manner of comparison,
e.g. if the complete material is given in advance as 2K+2R+2r (in SV and PA
method), then SV method needs also the 7 lengths of empty square runs, while PA
method already has all it needs to reconstruct the position for that material.
Now, for a general position, as you say, the PA method needs a way to index all
various material contents cases, which takes around 30 bits (also indicated with
rough promotion estimates in the earlier section). The SV method gets the
material automatically (from the Square Values), but it pays for the empty
square listing. It is a tradeoff stuation with some break-even point (which you
roughly estimated to 15 pieces plus 2 kings). In any case, I think we agree now
that the original comparison of the 3 methods for 2K+4R wasn't right.
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.