Asri-unix.918 net.chess utcsrgv!utzoo!decvax!ucbvax!ARPAVAX:C70:sri-unix!YODER@USC-ECLB Sun Mar 7 15:36:24 1982 improved encoding Yet more bit squeezing... the new scheme doesn't save significantly for the opening position, but makes the worst case considerably better. One note: the worst case for the scheme which Tom Truscott was considering is 199 bits, not 195 as was stated earlier (he forgot 4 empty spaces). The worst case for most Huffman schemes will be when one has 12 promotions: in the following situation bp bp wp wp a capture will enable the three remaining pawns to be promoted. The key idea is that there is always exactly one white king and one black king on the board. Thus we use 12 bits to represent their positions, and encode the remaining 62 squares (in order) using the following code (c is a color bit): empty 0 pawn 1c0 knight 1c100 bishop 1c101 rook 1c110 queen 1c111 We use one bit to represent who is on move, and use the previously mentioned tricks to avoid en passant and castling bits (for the sake of those seeing this for the first time: one first replaces rooks which retain castling privilege by pawns of the opponent's color; then, if there is a pawn which can be taken en passant, one exchanges it with the square on its first rank. This is done before starting to encode.) For the initial position this takes 13 + 32*1 + 16*3 + 14*5 = 163 bits. For the worst case, we must use 13 + 36*1 + 26*5 = 179 bits. So on a PDP-10 we fit into 5 words with one bit to spare! The point to this is not, of course, that two bits have been squeezed out of the initial position, but that the worst case is brought considerably closer to the usual case. If your storage unit is either 32 or 36 bits, you need the same space. If it is 8 bits, it is just under 10% worse. It is also still within the bounds of reasonable complexity, being simple to describe. ------- ----------------------------------------------------------------- gopher://quux.org/ conversion by John Goerzen of http://communication.ucsd.edu/A-News/ This Usenet Oldnews Archive article may be copied and distributed freely, provided: 1. There is no money collected for the text(s) of the articles. 2. The following notice remains appended to each copy: The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman.