Author: KarinsDad
Date: 14:45:33 11/02/99
Go up one level in this thread
On November 02, 1999 at 00:29:59, Ratko V Tomic wrote: > >> 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. I'm not sure I'm convinced of this. First, you have multiple SV algorithms. You use the one which best applies to the position. In the case of maximum promotions and few pawns, you use this Prime Search algorithm (for want of a better name). As a general rule, you would use: SV1: 8 to 16 pawns SV2: 5 to 7 pawns PS with SV2: 0 to 4 pawns, if needed when there are close to maximum promotions in the position. If this is not the case, you use normal SV2 for a low pawn count position. Additionally, SV2 is still the mechanism for compressing the pieces in the PS algorithm. It's just the bitboard that gets compressed as well AND a form of PA needs to be done for the lingering pieces. Note: If you have just one piece shy of maximum pieces, you can almost always get to 158 bits or fewer and hence do not need a PS method. Since there is only about a 1 to 2 bit difference between the optimum SV method and a PA method (per piece), you get a savings IF (and only if) you can get a majority (approximately 80% or so) of the pieces handled while accessing only about 60% or 65% of the bitboard. I haven't done the actual math, but it would appear that it would be something in the order of 80% of 26 pieces = 21 pieces; = 5 pieces not handled * 2 bits (max) per PA method + 8 bits PS method + 1 bit PS method indicator + 1 bit savings (minimum) = 20 bits; (62-20)/62 = 68% maximum bitboard. Now, this was for a maximum promotion case. Using primes (or some other sequence) should get you real close, but there is no guarantee. That is what makes the formal proof so difficult. The thing that makes this appealing is that there should be some prime sequence that gives you an 80% coverage fairly quickly when you consider that 58% of the bitboard is white space for most any position. In fact, it may be necessarily (if primes are used) to actually check the first 16 primes instead of the first 8 primes (1 more bit). 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). That's the problem. There is no actual data set since ANY pattern of 1 to 30 pieces (excluding kings) on a 62 bit bitboard is legitimate. Granted, this type of algorithm is only needed in the 26 to 27 maximum pieces on the board scenarios, but we are talking the best way to indicate ANY 26 or 27 bits out of 62. >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). Agreed. > > > >>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. Yes, but if the complete material is given in advance, then the SV piece indicator (for this example) can be compressed down to 1 bit, i.e. color. As opposed to 3.33 bits. But, with such an extreme example (i.e. few pieces), the PA method is still obviously better. >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. Yes. 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.