Author: Eugene Nalimov
Date: 17:55:40 05/19/99
Go up one level in this thread
I'm participating in that thread because I'm curious: how much we can "squeeze" the average position. Unfortunately, I don't see who will implement suggested algorithms and where it'll be used. To speak more generally, I can see 3 different goals for such the algorithm that results in 3 different representation requirements: (1) To store the entire game in the least possible # of bits. Here, as it was pointed earlier, you'd better store starting position (if necessary) and sequence of moves. (2) To store the random position in the *fixed* number of bits, so that the resulting file (database?) can be directly indexed. That means you have to optimize the worst case. And here majority of the clever tricks (e.g. using less bits for pawns or pieces on the 1st/8th ranks) will not work. IMHO, that representation must be able to cover even the pathological cases that cannot happen in the real games. (3) To store the *average* position in the minimum amount of bits. That representation can work if you plan to use only sequental search through those positions. And here is the place of KarinsDad's schema - *average* position will be stored significally better than by using the algorithm from the case (2). Eugene On May 19, 1999 at 18:25:54, KarinsDad wrote: >On May 19, 1999 at 15:38:27, Eugene Nalimov wrote: > >[snip] >>> >>>No, you only need 1 ep bit (based on the structure that this original statement >>>was made). Because, if ep exists, then you can add 4 more bits to the structure >>>to represent the square involved (3 bits) and the direction of capture (1 bit, a >>>file to b file, or b file to a file type of thing) and you can remove 6 bits >>>from the original structure for the pawn that can be taken by ep and the pawn >>>that can take (if you have 2 pawns that can take, you do not care since the >>>other one still shows up in the original structure). Hence, an en-passant case >>>takes up 2 bits less (+4 -6) than a non-en-passant case. >>> >>>So, only 1 ep bit is needed. >>> >>>KarinsDad :) >> >>Your forgot that you can also don't store 2 empty squares. So -4 bits. >> >>Eugene > >Yup, I did (duh). > >For those of you who did not read Eugene's earlier message from last week: 2 >empty squares for where the pushed pawn came from and the square it went >through, so -4 bits (+4 -8, i.e. +3 for ep square, +1 for ep direction, -3 for >taking pawn, -3 for pushed pawn, -2 for no blank needed for squares pushed pawn >came from and through). > >KarinsDad :) > >PS. Eugene, if you really think about it, it is only worth removing the taking >pawn and the empty squares (i.e. making it -4 bits as opposed to 0 bits) if the >structure is going to be represented as a variable length structure (and hence, >you do not read in, for example, 20 bytes at a time, but rather you read in 100s >of bytes at a time and grab what you need out of each of them). > >Why? > >Because if it is a fixed length structure, it will either fit into it's "maximum >size" (i.e. 160 bits in the representation I posted the other day) or it will >not. If for a REAL position the extra -4 bits are needed due to en-passant, then >the position before this real position (and most likely the position after this >real position) in a game would have failed as well. > >What good is it to have a position that can be stored in 20 bytes when a good >majority of positions based on legal moves from that position are ones that >require 21 bytes? > >In other words, why write the code for and do the extra compression / >decompression processing? Chances are that this will not matter for real game >positions.
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.