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 <COLOR BIT> 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 <
[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.
