From 10acef9e6f2d1f56a39c7f4b9ccf4b4be6f8bed7 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Wed, 1 Jun 2016 19:04:57 -0700 Subject: A bunch of chess-related papers. --- programs/FewBits | 252 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 252 insertions(+) create mode 100644 programs/FewBits (limited to 'programs/FewBits') 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: TDR@PROVAX.intel.com (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: +- pigeons@JSP.UMontreal.CA (Steven Pigeon) +- jn@inf.ethz.ch (J Nievergelt) +- chess@uni-paderborn.de (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: TDR@PROVAX.intel.com (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: jn@inf.ethz.ch (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) -- cgit v1.3