Text File

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