Asri-unix.438
net.chess
utzoo!decvax!ucbvax!menlo70!sri-unix!Wedekind.ES@PARC-MAXC
Wed Jan 6 13:38:21 1982
compact representation of chess positions
Bill,
Since you want to store all reachable positions and you're interested only
in worst-case sizes, the benefits of Huffman coding are lessened by the
possibility of pawn promotions. You get the worst case by promoting as many
pawns as possible to the most "expensive" denominations. The Duchess scheme
Tom Truscott gave uses 180 bits to encode positions in which 4 PxP's and 12
queenings (!) have occured, which I think is the worst case for that code (but
how does Duchess avoid side-to-move and castling bits?).
By the way, I figure there are about 2^100 such positions and maybe (this
is a rough guess) 2^110 positions in all. If this is in the ballpark, it answers the
question about theoretical minimum bit length (110) since in theory you could
assign positions to consecutive binary numbers until you ran out (but it would
be hell to decode!). Anyway, that tells you you're within a factor of 2 of
optimal.
If somehow you could throw out "unreasonable" positions, for example
ones where there are more than 3 Pieces of any one color and denomination
(ever hear of a game where this happened?), you might save a lot more.
Jerry
-----------------------------------------------------------------
gopher://quux.org/ conversion by John Goerzen <
[email protected]>
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.
