Author: Dan Newman
Date: 03:14:49 05/17/99
Go up one level in this thread
On May 14, 1999 at 22:52:59, Dann Corbit wrote: >Does anyone have a copy of this article? It's not there anymore. I would sure >like a copy. I looked around and found a copy I downloaded in '96 and have pasted it below. -Dan. 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)
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.