Text File

Asri-unix.426 net.chess utzoo!decvax!ucbvax!menlo70!sri-unix!VaughanW@HI-Multics Tue Jan 5 05:41:16 1982 compact representation of a position From: VaughanW at HI-Multics (Bill Vaughan) Who knows a good compact representation of a chess position? For this purpose it is necessary to state the position of each piece, who is on move, what castles are still potentially available, and whether there is an e-p capture available -- but NOT enough history to know whether there is a draw by repetition.

I'm especially interested in a representation that is: (a) fairly easy (computationally) to translate to a real position; (b) dense in the worst case rather than the average case.

(The reason for (b) is that I intend to look up positions using fixed length records on a mini-floppy, so every representation must be allocated the same space as any other.)

The best I have so far is about 192 bits if there are no multiplies or divides (except shifts) to encode & decode; somewhat more than 176 bits if I don't mind a lot of divides. But that allows me to represent a whole raft of illegal positions, so it probably isn't very good.

What is the information-theoretic minimum? And how close can you reasonably come to it?

Thanks, Bill

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