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 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.