A bunch of chess-related papers.HEADmaster

1 files changed, 252 insertions, 0 deletions

diff --git a/programs/FewBits b/programs/FewBits
new file mode 100644
index 0000000..68f0ae5
--- /dev/null
+++ b/programs/FewBits
@@ -0,0 +1,252 @@
+From: [email protected] (toby robison)
+Newsgroups: rec.games.chess
+Subject: Notating positions in as few bits as possible
+Date: 9 Mar 1993
+
+
+HOW TO NOTATE CHESS POSITIONS IN THE FEWEST AVERAGE BITS PER POSITION
+
+This article is Copyright (C) by Toby Robison, Princeton NJ USA 1993.
+Please name the author when quoting from it.
+
+This is a discussion, not a solution to this rather difficult problem.
+
+Several people provided useful information that I will be quoting below:
+- [email protected] (Steven Pigeon)
+- [email protected] (J Nievergelt)
+- [email protected] (Peter Rainer)
+
+
+
+INTRODUCTION:
+
+The problem here is to come with ways to encode chess positions
+that require, on the average, as few bits as possible. We shall
+consider legal positions only (illegal positions being less useful
+and requiring more bits). 
+
+We are considering idealized solutions. It should not be necessary
+to encode or decode a position very fast, and we accept that any
+error in the data may make the positions unreadable.
+
+It turns out that this problem is similar
+to general problems of video compression. Consequently we even have
+to consider what sorts of positions are intertesting to us --
+the solution could be different if we want to find the best average
+result for "every legal position", or for "every typical legal position
+that comes up in good games" or in "every typical position of the sorts
+that are published (using a diagram or other direct notation, such
+as Forsyth) in chess publications".
+
+I shall not try to decide which is the proper target for this 
+investigation. Just please bear in mind that the open question will
+affect the solutions we consider later. I shall sidestep this issue by
+referring to "common" or "likely" positions, without having any idea
+what these are.
+
+Notating a position also requires indicating which player is "to move"
+and whether each player can castle (on each side). Strictly speaking we
+should also indicate how long since a pawn has moved, whether en passant
+captures are currently possible, and what positions
+have occurred in the game (so that draws by repetition can be properly
+analyzed). However these requirements simply push us back onto the
+solutions that represent the position as the entire game, SO I SHALL
+IGNORE THESE REQUIREMENTS. Let us just assume that one bit is set aside
+to indicate which player is to move, unless the position is a checkmate.
+
+It is clear that the solution is less than 200 bits per position.
+This is quite good considering that there are 64 squares.
+Intuitively we have a budget of about 3 bits (8 possibilities) to
+tell us what's going on at each square (11 possibilities for the ten
+types of pieces and "empty").
+
+
+Apparently other people have been working on this problem in print.
+Peter Rainer sent me this message:
+
+>Your approach to chess game compression is not new,
+>there has been a paper in the ICCA Journal by
+>Ingo Althoeffer discribing the idea.
+>I think it was in 1991 or 1992.
+>Peter Mysliwietz
+
+See also the information from Nievergelt, below.
+
+THE INVESTIGATION:
+
+APPROACH #1:
+
+Steven Pigeon starts with the number of legal chess positions, which he
+says has been claimed to be 10^43 (but he did not check this out).
+That value can be stored in 143 bits, so if we simply state an  algorithm
+for ordering all possible chess positions, we simply record the ordinal
+number of the position. 
+
+The drawback of this approach is that it requires
+143 bits for ALL positions, but we ought to shoot for a better average than
+that. One way to improve the solution is to find an ordering of all positions
+such that more common positions come first in the ordering. THEN we use
+a method of compressing the ordinal number of a position that favors
+lower numbers. It is HIGHLY SPECULATIVE that any such really useful
+ordering could be found of course. But if we find an ordering that
+morely makes "sensible" positions come before unlikely and bizzarre ones,
+we can waste LOTS of bits on the bizzarre and get an average a lot less
+than 143 for "common" positions.
+
+APPROACH #2:
+
+One basic approach is to record which squares of the board are
+occupied (64 bits), and then try to be extremely efficient about how
+to say what the pieces in those squares are. For example, we could assume
+that following the first 64 bits there is a code to identify the "first"
+piece, then the second, and so on, assuming that we will start at A1 and
+work, say, across and then up the board.
+
+Pigeon puts it this way:
+
+>The trick is to store the board's occupation as an 8x8 bit matrix,
+>(1=occupied,0=free) and then list the pieces in order of presence
+>in some list, where the codes for the pieces are derived from a
+>Huffman adapative coding (since it is exponential coding), and it
+>is the upper bound. Less pieces there is, less space it takes.
+
+>I'd say  I should be able to drop it still a few bits, If I can figure
+>a way of "discarding" the 8x8 matrix.
+
+We should note that as the board gets populated, the number of
+possibilites for the remaining pieces is reduced, because we are considering
+only legal positions. For example, both kings cannot be in check, there can
+only be one king of each color, etc. In addition, pawns cannot be on the
+first and last ranks; a white bishop at square A1 prevents a white pawn at
+B2, etc.
+
+This approach is terrific for endgame positions even though it
+wastes 64 bits on the board. Eight-piece positions will require less than
+100 bits. But a position with all 32 pieces threatens to take a lot more
+than 143. Consider for example, that we might need 4.5 bits per piece,
+or 144 bits plus the 64 for the position.
+
+However as Pigeon observes above, if we use a code to represent each piece
+that requires few bits for LIKELY occurrence of given pieces at each square,
+we might do a lot better.
+
+APPROACH #3:
+
+This approach is very much like a pure video compression solution.
+We divide the board up into smaller regions (such as 2 squares by
+2 squares, but it would be better to make a subdivision based on chess
+experience). We then use Huffman or some other probability based encoding to
+characterize the piece patterns in each subregion. This approach takes advantage
+of the fact that (especially in the late middle and endgames), a relatively
+small number of piece patterns is common in each region.
+
+APPROACH #4:
+
+This is also a video-based compression technique. We encode where the
+pices are based on a probabilistic knowledge of where they are likely to be.
+(For example, it takes a lot of bits to place a knight on the rim.)
+With a few additional bits to characterize the TYPE of position, this
+approach might work well.
+
+APPROACH #5:
+
+J. Nievergelt sent me this astonishing claim:
+
+>It should be possible in under 100 bits. If interested, read:
+
+>J Nievergelt: Information content of chess positions, ACM SIGART Newsletter
+>62, 13-14, April 1977.
+
+>reprinted in:
+>Information content of chess positions: Implications for game-specific
+>knowledge of chess players, 283-289 in Machine Intelligence 12, (eds. J. E.
+>Hayes, D. Michie, E. Tyugu) , Clarendon Press, Oxford, 1991.
+
+I have not had a chance to check the reference, but I think 100 bits is
+incredibly few. In effect, it means specifying the state of each square
+in 1.5 bits, or the state of each piece in 3 or 4 bits.
+
+
+IN SUMMARY:
+
+We have a number of speculative approaches, unless Nievergelt has
+really solved the problem. It seems likely that the best solution should
+spend a few bits to characterize the position (opening, early middle, 
+late middle, endgame; open or closed), since different solutions may apply to 
+each. In particular, for the OPENING the best solution is either to record the
+game moves, or else to encode only those differences that make
+the position different from the starting one.
+
+In any case the validity of any solution must be tested against the
+type of positions we WANT to encode, and I really think a lot
+of experiemntation would be needed (which nobody probably wants to pay for).
+
+Please keep your comments coming, I will try to summarize...
+
+-- toby robison (not robinson)
+
+
+
+
+From: [email protected] (toby robison)
+Newsgroups: rec.games.chess
+Subject: Notating positions in as few bits as possible
+Date: 29 Mar 1993
+
+A number of people responded to me regarding the problem of
+notating chess positions in as few bits as possible.
+The low bidder for REALISTIC positions seems to be J. Nievergelt,
+whose solution, and a related game that looks like fun, are discussed below.
+
+For a solution that includes UNREALISTIC (but legal) positions,
+The key question is how many positions there are.
+I received several assertions regarding the number of possible chess
+positions (roughly 2^143 ?). If one comes up with a method
+for ordering all legal positions, then this number of bits can be
+used to notate them.
+
+
+TO NOTATE REALISTIC positions, see:
+
+J Nievergelt: Information content of chess positions, ACM SIGART Newsletter
+62, 13-14, April 1977. It is also reprinted in:
+Information content of chess positions: Implications for game-specific
+knowledge of chess players, 283-289 in Machine Intelligence 12, (eds. J. E.
+Hayes, D. Michie, E. Tyugu) , Clarendon Press, Oxford, 1991.
+
+or correspond with: [email protected] (J Nievergelt)
+
+
+JN's method is based on the observation that realistic positions are a small
+fraction of the total possible. To verify this, he presents the following game, 
+which I encourage others to try (I'm going to try it myself).
+Person A looks at a realistic position. Person B cannot see it, and asks
+A multiple choice questions. Both A and B are KNOWLEDGABLE chess players.
+B tries to figure out the position, using questions that require as few
+total bits of answer-information as possible.
+
+It's obvious that a Y/N question requires one bit to record the answer.
+A question with 4 choices requires 2 bits. Two three-way questions
+together require slightly more than three bits, and so on. 
+JN's assertion, based on some experimentation, is that about 70 bits-worth 
+of answers are reasonable figure out positions. 
+
+NOTE that we assume the questioner and responder can apply chess judgment, 
+so questions like "does the pawn structure suggest a closed French Defense?" 
+are acceptable. Even more important, the questioner gets to apply judgment 
+about what to ask next, depending upon the partial information currently known.
+
+Now to fully comprehend the solution, imagine a sophisticated program that
+both asks and answers the questions, and figures out a position. The position 
+is recorded as the answers to the questions the program asked. To recreate the 
+position, we run the same program again and supply the same answer bits.
+
+The problem of creating this GENERAL program is very difficult.
+According to JN, it may be impractical to write a program that gets
+anywhere near to the best possible solution. Writing a program that requires
+about 100 bits per position might be practical, though!
+
+The basic assertion looks like fun to test. Can you guess straightforward, 
+typical positions, in less than 100 bits of answer info? In 70?
+
+- toby robison (not tony, not robinson)