Asri-unix.428
net.chess
utzoo!decvax!ucbvax!menlo70!sri-unix!jim@RAND-UNIX
Tue Jan 5 12:06:35 1982
Re: compact representation of a position
Well, it depends on what you want it for. I normally use Forsythe notation
when I'm trying to do something that is human-readable as well as machine-
readable. So for an early position (in particular, Larsen-Fischer from the
2nd Piatigorsky Cup), the position would be represented as:
r3rk/2p2p1p/p3n1p/1p1pPn/7q/2PQ/PPBB1PPP/R3R1K
where the lower case are black pieces, upper case are white, and numbers
are the number of empty squares. The rows, starting with Black's first
row, are separated by slashes and read from left to right. Add another 3
or 4 bytes for castling information and en passant. An endgame position is
more compact (Najdorf-Petrosian from the same tournament):
5n/6k/1R5p/r4P1P/5K/5B/8/8
The alphabet consists of 12345678pnbrkqPNBRKQ/ for a total of 21 letters.
If you want to represent them as 5 bits instead of 8, these examples would
cost 230 and 130 bits respectively. Possibly in the worst case you could
save more by leaving out the slashes and including digits to fill out the
lines, at the expense of legibility. Getting fancier, you could use Huffman
coding on a statistically large sample of your positions and assign optimally
short variable-length codes for each of the letters in this representation.
But, as I say, it depends on what you want the positions for. If you just
want to look things up in an opening book, it's cheaper to store them in
a hash table using as large a check hash code as you want to guarantee that
you've got the right position to as high a probability as you want (32 random
bits of check hash would give you a probability of 2^32 that you've got the
right position). Or, if you are storing positions from a bunch of games
it would be much cheaper in disk storage to store the whole score (but much
messier to retrieve individual positions).
There are other tradeoffs depending on whether you've got most of the pieces
still on the board, etc.
Jim Gillogly
-----------------------------------------------------------------
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.
