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.