Author: KarinsDad
Date: 19:27:02 10/29/99
Go up one level in this thread
On October 29, 1999 at 16:00:55, Guido wrote: >Huffman coding for recording a chess position, should be as follows: > >Empty square: 0 >Pawn: 10C >Bishop: 1100C >Knight: 1101C >Rook: 1110C >Queen: 11110C >King: 11111C > >where C indicates the colour bit (0 = White, 1 = Black). > >For the starting chess position we have a total size of 32*1 + 16*3 + 4*5 + 4*5 >+ 4*5 + 2*6 + 2*6 = 164 bits with additional bits (from 1 to 8 IMO) for side to >move, castle status and en passant capture. > >But Pawns cannot occupy the first and the last row, so only for these rows, the >coding can be modified eliminating the first '1': > >Empty square: 0 >Bishop: 100C >Knight: 101C >Rook: 110C >Queen: 1110C >King: 1111C > >In the best case of starting position it is possible to save 16 bits, for a >total of 148 bits vs 164 bits of the original Huffman coding. In a generic >situation the saving is less and equal to the number of pieces in the first and >in the last row. > >Is this reduction already known? Yes. And, there are well known algorithms to reduce it's size a little. 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). Since the king no longer needs to be part of the Huffman coding, the queen no longer needs to be 5/6 bits long, but only 4/5 bits. Hence, another 2 bits can be saved for queens for a total savings of 4 bits. However, you will note that the moment a piece leaves the back rank, it gains another bit. And, if all pawns are promoted (without any pieces being taken), then you have a maximum additional 22 bits (-3 bits per pawn removed, +5 bits per piece added, 16 pawns removed, 12 pieces added to the middle of the board). This could result in a maximum number of bits of 148 bits (your calculation) - 4 bits (my king calculation savings) + 22 bits (my promoted calculation) + 14 bits (14 pieces moved off the back rank) + 1 bit side to move = 181 bits (note: an en passant bit is not required since you can remove the two pawns from the board and use the resulting 4 bits to indicate en passant and which pawns; or no en passant). So, it is not really the normal chess positions that take more than 160 bits in this type of encoding scheme (159 bits max). It's the promoted pawn positions when no or few pieces are captured. KarinsDad :) > > >OT Argument > >In a past thread the problem of the language to use in CCC was discussed, as >many people are not of english mother tongue and have problem with english. I'm >italian and probably I speak and write english very badly. >I don't suggest to use latin or esperanto, but more concretely that all the >english mother tongue persons who write to CCC make an effort to use the easiest >words and expressions they know, so more non-english people can understand and >learn english as well as chess. > >Regards >Guido
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.