Aduke.1593
net.chess
utzoo!decvax!duke!trt
Thu Jan  7 18:51:20 1982
Re: sri-unix.444: compact representation of chess positions
Apologies for the various errors in duke.1553.
First, the coding given yields 164 bits for the opening, not 156.
Second, I do not see how to hide side-to-move and castling
information in the position, either.
Third, Wagner's encoding requires ~143 bits, not ~130.

As for the Huffman coding, duke.1553 correctly avoids enpass bits.
So the total is 164+5 = 171 bits, plus a few for promotions.
For rational chess 176 bits (22 bytes) is quite adequate.
In the worst case (sri-unix.438) it takes 171-16*3+12*6 = 195 bits.
The encoder should certainly check the length of the code.
The average case can be improved alot by having a different
encoding tree for each square of the board.
For example, white's back rank rarely has black pieces on it.

The above encodings can be decoded; if that is not necessary
then I heartily recommend Jim Gillogly's suggested n-bit hashing.
It is compact, with low error rate, and can be very fast.
For each piece type and each square have an n-bit "random" signature.
The n-bit position hash H is the XOR of all the piece signatures.
Then if piece type t is moved from square a to square b,
the new H' = H XOR signature[t][a] XOR signature[t][b].

For just storing an opening book, if transpositions are not needed,
then there is a 1-byte/position tree encoding something like:
(e4 (e5 (Nf3) Nc6 Nf6 ...) d4 (d5 ...) ...)
The moves are numbered in the order the move generator produces them,
and flag bits indicate parentheses.
This scheme was used by Ken Thompson in his 1977,1978 chess machine
and has been adopted by the Sprachlens for Sargon.
	Tom Truscott (duke!trt)

-----------------------------------------------------------------
 gopher://quux.org/ conversion by John Goerzen <jgoerzen@complete.org>
 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.