Asri-unix.459
net.chess
utzoo!decvax!ucbvax!menlo70!sri-unix!YODER@USC-ECLB
Thu Jan 7 19:03:10 1982
compact reps
The castling bits can be hidden by representing a rook which still
can be castled with as a pawn of the opposite color (if of the same color
there are ambiguities with the en passant scheme). So the encoding scheme
is:
(1) Replace rooks with castling privilege by other-color pawns.
(2) Exchange pawn which can be captured e.p. with the square on
its first rank.
To decode:
(1) If there is a pawn on its own 1st rank it can be captured e.p.;
note this and exchange with the 4th rank square.
(2) If there are now pawns on their own 8th ranks, they represent
rooks which retain castling privilege of the other color.
I do not see, however, any simple way to hide the "to move" bit.
One could place an extra king on the board but a king takes more bits in the
Huffman code than an empty space, so this is false cleverness (I leave it to
the reader to see how to place it in such a way that which king is real is
not ambiguous). Schemes with more pawns on the 1st/8th ranks are likely to
either fail or be overly complex, as with promotions both ranks could be
filled with pieces none of which are kings or pawns or even rooks.
If your use of this is solely for storing (e.g.) endgame positions,
you could eliminate the bit by making the convention that white is always
on move! This requires reflecting the board about the line between ranks
4 and 5 (and changing colors) to look up or store positions with black on
move.
Unless this latter method is what was in mind (and such a scheme
is quite adequate if you are doing an "opening book" program or endgame
player -- it will automatically notice positions which are transpositions
from the other side, for example), I don't see how to easily hide the bit.
And as long as we are saving bits... note that you can use records
of any length you desire without needing an explicit "this position is
unusually long" bit. Simply start reading the record's bits, and if you
run out of them before you have picked up 64 squares, you must continue
to the next record.
A final comment: all this bit twiddling is not worth it unless
you are *VERY* desperate for space. Keeping the castling and e.p. bits
separate will make your program and data structures simple, which is a
big advantage. Simplicity wins.
The discussion does raise the (theoretically) interesting question
of what the minimum number of bits required is if only legally attainable
positions are to be considered. Obtaining a nontrivial lower bound for
this number seems to be much more difficult than finding nontrivial upper
bounds. A possible program for the latter is:
(1) Enumerate the possible pawn structures.
(2) For each one, enumerate the possible promotions and use this
to determine the possible sets of additional pieces on the board.
(3) For each such set, count the ways to distribute the additional
pieces while ignoring illegality due to kings in check.
(4) Make small corrections to allow for castling and en passant.
Has anyone carried out calculations like this? The feasibility clearly
depends on how careful one is in weeding out illegal positions and in
making deductions about possible placements of pieces.
-------
-----------------------------------------------------------------
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.
