Author: Les Fernandez
Date: 23:18:49 09/29/00
Go up one level in this thread
On September 29, 2000 at 22:40:26, Vincent Diepeveen wrote: >On September 29, 2000 at 22:11:10, leonid wrote: > >>On September 29, 2000 at 20:03:02, Larry Griffiths wrote: >> >>>On September 29, 2000 at 19:11:17, Bo Sjögren wrote: >>> >>>>Some time ago, maybe a year or so, there was an interesting >>>>discussing about the minimum number of bits necessary to store an >>>>arbitrary chess position. What was the conclusion of the >>>>discussion? Can I find the discussion in the archive, or a >>>>summary somewhere on the net? >>>> >>>>Regards, >>>>Bo S >>> >>>I store mine in 32 bytes (256 bits). Each 4 bits contains the piece and its >>>color as follows... >>> >>>cppp >>> >>>where c is the color and ppp is the piece (could have up to 8 piece types). >>> >>>OR >>> >>>If you really like to pack bits you could have a fixed array of 6 bits times 32 >>>bits (192 bits) where each of the 32 buckets has the square the piece is setting >>>on. >>>The problem with this second arrangement is that you would need another 8 >>>buckets for each side (32*6bits+16*6bits=288 bits) if promotions occurred. >>> >>>Neither of these arrangements include bytes to hold the en-passant status of the >>>board or castleing state. >>> >>>Larry. >> >>I do save each position of chess board with 64 bytes. Every of those 64 bytes >>have three not used bits. >> >>5 busy bits are: 3 bits - description of piece. >> 1 bit - empty, occuped square. >> 1 bit - color for piece, if square is occupied. >> >>Leonid. > >that's 512 bits or so. > >can easily get it to 180 bits or so >let's first there are 2 approaches > a) storing entire positions in n bits always where n is a constant > b) storing it in a different sizes of bits. so only positions which > are UNLIKELY to occur like a position with more as 2 queens. > >b is far more attractive as a. > >A you can get easily in like > >64 bits piece versus no piece > >for all squares occupied now you need at most 32 bits >whether something is white or black. > >that's 96 bits so far. > >then we do 32 bits true or false for pawn versus non pawn. > >128 bits now done. we know now 8 pieces for each side at most >and we know its place, we just don't know what kind of piece it is. >we have choices: > king > rook > bishop > knight > queen > >Ok we have only 1 king, so we first start with king. >that's 3 bits. Now you have only 1 king so only 4 types of pieces left >for the remaining pieces. that can be done in 7x2 bits. > >so in total for each side: 3 bits + 7x2 = 14+3 = 17 >we do that for 2 sides. so besides the 128 bits we nees another 34 bits. > >that's in total 162 bits (without ep rights and without castling rights) >and you sure haven't promoted pawns yet to use the full extend of >bits, as to promote a single pawn to a queen you lose from all sides >together most likely at least 2 pieces/pawns using objective best moves, >so that's more as the extra bits for naming it below costs. > >Ok that's a first simplistic try to just index the board position, >without search status (castling rights, 1 time repetition etcetera, >en passant rights) > >162 bits ==> 2^160 = 5.8 x 10^48 >so this still is not a very accurate way of storing a position, >as i remember someone reported in JICCA 10^43 as the maximum amount >of positions, a number which i also doubt, as if you say 10^35 i >directly believe it too. > >Now let's also face the fact that it is *unlikely* that pawns are >between a1 and h1 and between a8 and h8. You can use that also. > >You can also use the fact that it's unlikely that there are more as or >equal to 2 queens on the board (already a bit used in the above definition). > >if that happens, then someone made already a big mistake in the game, or >the position is ready to resign for either side, or a quiescencesearch >already removes the queen. > >There are more rules. Like how likely is it that whites pieces are >being further as blacks pieces? > >suppose we see a1 as 0 in an array and b1 as 1 and c1 as 2 and a2 as 8, >b2 as 9 etcetera. > >How *likely* is it that many pieces of white are further as the >black pieces? > >If so, then more as 4 pieces? VERY unlikely!!! > >Well in positions with all pieces on the board i'm pretty sure that >it won't be too much pieces! > >and if so then only at 4th or 5th row. > >So now let's look to approach b, using a 'huffman' way of encoding, >i'm sure you can save a hell of a lot! > >not to mention illegal positions also. > >i have not had many games with all pieces on the board with the white >king being further as square second row! > >If we make big assumptions and each assumption is worth a single bit, >then to what size can we get the average position down? > >Let's use 'smart' rules, you really can go a long end then, >if you want to get 'normal' positions. > >perhaps you can easily get down the average size to 140 bits after >some years of rules work? > >I guess you'll do a bad job then, because some others claim that >getting down size to 100 bits then is perhaps possible for >normal looking legal positiosn which might occur on the board. > >Sure is that 162 is an easy start you get for free (hoping i didn't >make calculation errors) with, if you want to play on safe with >en passant and capturing and allowing n pieces (so 9 bishops and >such) then 168 bits is easily doable. Hi Vincent, How about this thought? Here is a thought I was just kicking around a few weeks ago and maybe it is a good time to mention it. Ok regardless of the method used initially 64 bits are used for squares occupied by a piece. Lets just look at this part and see if we can reduce the 64 bits. Suppose we have a board layout like this. (* equals each square on the chess board) 7 * * * * * * * * 6 * * * * k * * * 5 * * * * * p p * 4 * * * * * * * * 3 * R * * * * * * 2 * * * * * * * * 1 * * P * * B * * 0 * * * * * * * * 0 1 2 3 4 5 6 7 We determine the minimum box that can be drawn so that it encompasses all the pieces. Keep in mind we only need the lower left and upper right coordinates to define the shrinking chessboard which in this case is: lower left = 1,1 and upper right = 6,6 (knowing the coordinates also tells us the # of bits needed. use the full 64 bits for cases where squares >=56 ---------------------------------------------------------------- use the partial bit method for cases where squares <56 ++++++++++++------------------------------------ opposite squares within the box corner coordinates To store both these coordinates requires a total of 12 bits. Since we know the box that comprises all our pieces, we only need to use the number of bits that represent just the squares that are within this box which in the above example is only 36 bits. To this number we have to add the 12 bits we used to designate our two corners which is 36+12=48 bits. The one thing this method requires is 2 different databases, one for anytime the surrounding box is >=56 squares and the other database when the surrounding box is <56 squares. Anytime the surrounding box consists of a number <56 we are saving bits and in the case when it is >=56 we are no worse then before since we would use the 64 bit method for this case. Now I know this is probably not ideal to have 2 databases but perhaps we can add one more bit to the beginning of our string to indicate which method to apply to the following binary so that it can all go into one database. This does mean however in the cases where occupied squares are >=56 we actually need 65 bits instead of 64 bits. For example a 0 indicates to use the (1 bit) + 64 bit method and a 1 would indicate to use the (1 bit)+ 12 bits for the coordinates of the two diagonal corners which also tells us how many bits there are following which represents the occupied squares. Anyway just a thought and perhaps it may trigger someone else imagination into a similar but more compressed method.
This page took 2.61 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.