Aduke.1553 net.chess utzoo!decvax!duke!trt Tue Jan 5 21:38:40 1982 Re: sri-unix.426: compact representation of a position The Duchess program (Bruce Wright, Eric Jensen, and myself) uses simple Huffman encoding for storing chessboards on disk in 22 bytes/board. Only shifts are used, no arithmetic. Each of the 64 four squares are encoded as follows: If empty square then 0 else 1 followed by followed by if pawn then 0 else 1 followed by if knight then 00 elif bishop then 01 elif rook then 10 else 11 followed by if queen then 0 else 1 All that takes 156 bits. A pawn promotion lengthens that by 3 bits, but something has to be captured to have a pawn promotion, so one is safe. Hmmm, it is not that simple. Anyway. Then append side-to-move bit, 4 bits of castling indicator, and 4 bits of enpassant indicator. An enpassant pawn could instead be indicated by swapping its square with the one on the first rank, same file. The side-to-move and castling indicators can be similarly avoided. So 156 bits/board is not too hard to obtain. Robert Wagner (duke!raw) devised a ~130 bit (average) encoding employing mixed-radix arithmetic. It's mainly of theoretical interest: How many unique chessboards *are* there? How much time would an n-processor dynamic programming approach require to solve chess?. He has a paper for those interested. Tom Truscott (duke!trt) ----------------------------------------------------------------- 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.