Asri-unix.428 net.chess utzoo!decvax!ucbvax!menlo70!sri-unix!jim@RAND-UNIX Tue Jan 5 12:06:35 1982 Re: compact representation of a position Well, it depends on what you want it for. I normally use Forsythe notation when I'm trying to do something that is human-readable as well as machine- readable. So for an early position (in particular, Larsen-Fischer from the 2nd Piatigorsky Cup), the position would be represented as: r3rk/2p2p1p/p3n1p/1p1pPn/7q/2PQ/PPBB1PPP/R3R1K where the lower case are black pieces, upper case are white, and numbers are the number of empty squares. The rows, starting with Black's first row, are separated by slashes and read from left to right. Add another 3 or 4 bytes for castling information and en passant. An endgame position is more compact (Najdorf-Petrosian from the same tournament): 5n/6k/1R5p/r4P1P/5K/5B/8/8 The alphabet consists of 12345678pnbrkqPNBRKQ/ for a total of 21 letters. If you want to represent them as 5 bits instead of 8, these examples would cost 230 and 130 bits respectively. Possibly in the worst case you could save more by leaving out the slashes and including digits to fill out the lines, at the expense of legibility. Getting fancier, you could use Huffman coding on a statistically large sample of your positions and assign optimally short variable-length codes for each of the letters in this representation. But, as I say, it depends on what you want the positions for. If you just want to look things up in an opening book, it's cheaper to store them in a hash table using as large a check hash code as you want to guarantee that you've got the right position to as high a probability as you want (32 random bits of check hash would give you a probability of 2^32 that you've got the right position). Or, if you are storing positions from a bunch of games it would be much cheaper in disk storage to store the whole score (but much messier to retrieve individual positions). There are other tradeoffs depending on whether you've got most of the pieces still on the board, etc. Jim Gillogly ----------------------------------------------------------------- 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.