Author: KarinsDad
Date: 08:43:52 10/30/99
Go up one level in this thread
On October 30, 1999 at 01:16:45, Ratko V Tomic wrote: >> For example, the castling state information requires 2 bits per side for >> 4 additional bits. So, you could replace the 14 bits for kings and >> castling status with 12 bits (there are less than 3900 legal white >> king/black king pairings on the board, so the "can castle" info can >> be placed in the remaining 200+ bits). > >You don't even need these extra 2 "can castle" bits. Namely, the castle can >occur only if the king is on e1 (or e8 for black), while the extra bits allow >full freedom of "can castle" for all king placements, i.e. they reserve code >space for over ten thousands of bit combinations which can't ever occur (such as >king on e2 and "white can castle queenside" etc). Though what you say is true, you are forgetting that you have to take the worse case scenario in order to find a minimum number of bits for a maximum bit intensive position. Worse case scenario is white king on e1, white rook on a1, white rook on h1, black king on e8, black rook on a8, and black rook on h8. In this case, the 4 bits are required (with the Huffman type of schema). > >This combinatorics can be easily modelled by imagining that you have 3 extra >squares on top of e1 (for k, q and k+q castle possibilities) like 3 upper floors >(i.e. the ground floor is no-castle allowed). Since there are 3612 king pair >non-castling (ground floor) positions (4*60+24*58+36*55), that leaves 484 unused >combinations from the 4096 (12 bits available for the king pair). For non-ground >floor combinations you need (ignoring the attack or the occupancy by opposing >king of the squares between the castling king & potential rook; removing such >illegal castle cases would only reduce further the packing space): > >1) 3*58=174 for white non-ground (above e1, on floors 1,2,3) and black on the >ground (on any of the 58 legal ground floor squares), then >2) 3*58=174 for black king non-ground, white ground, and finally >3) 3*3=9 for both kings above ground, > >which totals 357 combinations, leaving still 127 unused combinations from the >484 leftover in the 12 bits code. Yes, of course. This is the 12 bit king proposal I mentioned in my previous message. Hence the 2 kings plus the full castling >status fit easily in 12 bits with room to spare (i.e. with about 0.05 bits >leftover). Using 2+2 rooks (allowing also for a blank-rook state) However, you are again forgetting worse case scenario. For the 12 bit king/king state schema, worse case is that castling cannot be done for either side. Hence, you have to indicate where the rooks are (in a worse case position). in addition to >the 2 kings, one can further reduce the size of the combined cluster of these >2-6 pieces with castling status (any castle-ok status also defines the content >and the attack status on the squares in between the king and the rook, giving >thus additional savings). This is not correct. A protected black knight can be on b1, preventing white queenside castling. However, if the knight moves to a3, castling can then be done (assuming b1 is the only backrank square being attacked on the queenside). The castling state has to be preserved and you cannot make an assumption as to what piece can or cannot be on the backrank, nor can you make assumptions on the attack status on the squares in between (which doesn't affect the right to castle overall, merely the right to castle at the moment). > >This seems to be the pattern of the general flaw in the proposals I have seen so >far in the thread, i.e. a great deal of code space is used for mutually >exclusive combinations. Exactly! In compression one first finds a suitable coding model >which doesn't allocate code/symbol space for impossible states (or at least not >very much such space), and only then, based on empirical statistics of these >symbols one applies Huffman or arithmetic coding to the resulting description. >Hence as the first phase one would need a parser or a finite state machine which >remembers the entire sequence processed so far (which need not work as a simple >single sequential scan of squares, but may perform multiple scans in any useful >order), Exactly, you are practically on top of my algorithm! so that at no point it provides code space for impossible placement. > >For example, regarding kings & castle, if the parser has already traversed board >and found white king on e1 and a white rook on h1, and no pieces in between and >no black attacks on e1, f1 or g1, only then the parser outputs one of the >symbols "wk-castle Ok" or "wk-castle not Ok", otherwise it outputs no castle >related symbols (and the decoder doesn't expect any since it replicates parsing >steps of the encoder). > >Similarly for ep pawn state, the parser identifies, say, a white and a black >pawn side by side on the 4-th rank and no piece on the 2nd or the 3rd rank >(behind white pawn), only then the parser outputs "ep-active" or "ep-not-active" Actually, EP can be done even more efficiently by knowing that you can save at least 4 bits in an EP position by removing the 2 pawns and then adding 4 EP bits. If you have 15 or 16 pawns in the representation of the position, then you know to not check for EP since the representation would have only had 13 or 14 pawns respectively (due to the algorithm) for the 15 or 16 pawn position. In other words, EP takes up no additional space whatsoever (with regard to the overall minimum size for a maximum bit intensive position). >symbol (if there are two black pawns around 1 white pawn, if the 1st black pawn >had ep-not-active, the second one has the same automatically, hence no ep-status >symbol is output for the 2nd black pawn). As soon as the first "ep-active" >symbol occurs, no more ep symbols are being output (since if there is another >black pawn on the 4-th rank on the other side of this ep-active white pawn, the >2nd black pawn has ep rights automatically, and since there can be no other >ep-active symbols there is no need to output either any more). (Of course, the >ep-status symbols need not be output until the entire board is already scanned >and the piece placements are known to the encoder and the decoder; each then >knows how many candidates, if any, are there and thus how many such symbols, at >most, will follow; since the sequence terminates with the 1st ep-active symbol, >that one need not be output at all but only a count of ep-not-active symbols in >the range 0-Max_EP is produced). > >For promotions it would useful to give, at least, the counts of w/b promotions >upfront (and possibly the type of promotion). That way one can know right away >the max number of pawns for each side and one can keep track of when promotions >are done and which pieces can still occur. Although this sounds good in theory, it does not work out. It takes 7 bits to indicate how many promotions (12 max promotions per side = 13 possibilities per side, 13 squared = 169 which is less than 256 = 7 bits) and that kills the bit count on normal positions. And, the most you can save is the color (1 bit) of the last piece on the board. The reason for this is that the second to last piece read in is the opposite color in the worse case scenario. And knowing the maximum number of pawns in promotion scenarios is not very helpful. The reason is that pawns can be promoted due to the capture of pawns by pawns (the most number of possible promotions) or pawns by pieces. Hence, the variance can be quite large (as much as 6 or 8 pawns) in a worse case scenario. It would be a nightmare to attempt to acquire any useful set of information from that. > >Only after the non-redundant encoding scheme (a sort of mini language) is >created one would go through the target sample of positions and count >frequencies of various symbols and apply Huffman or arithmetic encoding (i.e. >statistical encoding) of the symbol sequence. The Huffman or arithmetic code >tables can also vary from square to square. I considered a square to square variance, but only for around the side not to move's king. And, I proved that it would not save any space, so I discarded it. There are several problems. The first is one of how many bits can be saved in the worse case scenario. First off, the worse case scenario has to be defined. That would probably be king of side not to move in the corner. That would result in the least savings of bits. Well, king of side not to move on a1 cannot have an enemy knight on b3 or c2. However, that drops one piece out of the 11 other possible pieces (including color). Not a great savings. Also, the piece on a2 (or a3 if a2 blank, or a4 if a3 blank, etc.) cannot be an enemy queen or rook. 2 pieces out of 11. The piece on b2 cannot be an enemy queen or bishop (2 out of 11). The piece on b1 cannot be an enemy queen or rook (2 out of 11). So, for 2 squares (a2 and b2), there is an approximate savings of 2/11 * 3.33 bits per piece (including color). For 1 square (b1), there is an approximate savings of 2/11 * 3 bits per piece (no pawns on b1). For 2 squares (b3 and c2), the savings is about 1/11 * 3.33. Or, 2 * 2/11 * 3.33 + 2/11 * 3 + 2 * 1/11 * 3.33 = 2.36 bits. So, this effort results in a savings of 2 bits (worse case, it could save more if the side to not move's king was towards the center of the board). Note: this is an assumption, I will prove in a moment that it does not save a single bit. The next problem is one of: How do you acquire these savings? Well, you need to create a new compression schema, just for those squares. I won't bother to do this, but suffice it to say that it can be done. Now, the major problem. This schema does not save a single bit in the worse case scenario. The reason is that the a file can be blank, the backrank can be blank, the a1-h8 diagonal can be blank and the squares b3 and c2 can be blank. In this type of position, there are still 40 squares remaining on the board for the other pieces, so there is still plenty of positions that various subsets of 27 to 31 other pieces are on the board. Since you can only save space if the pieces are in the proper positions, you cannot save any space if they are not. Or if one is really ambitious, one >may use dictionary methods as the second phase and finally the statistical >encoding of the dictionary symbols. The dictionary methods would derive economy >from the commonly found clusters of pieces and their typical placements. Please explain this in more detail. Maybe an example. Thanks. KarinsDad :)
This page took 0.01 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.