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