Author: leonid
Date: 21:05:56 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 My choice of 1 byte for description of one square is practical but not the shortest one. The smallest piece of data in memory is one byte. So one byte goes for description of one square. Position of each square is seen after the position of given byte inside of the chain of 64 bytes. >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. Do we speak about the same thing? For me position is description on entire chess board. >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 In mine description sometime, in some special places, free three bites in the byte goes for description of the piece of promotion. But this description is seen not in 64 bytes description of the board but in description of the moves. >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. Not that practical in some places. Very often you must just see if given square is empty or not. For this (when using assembler) you need to check only one bit inside of four bytes that describe the move. If, for instance, you want to see what kind of material advantage move give to you, and move is 4 bytes long, you can load dword just by one instuction. Later for knowing exactly what value represent piece, that will be probably taken, you must reach one byte that describe square of entry. After the position of descriptive byte it could be that you need one instruction more to start even looking into that square. With bit that say "emtpy", "busy" you can see if square if empty in one instruction, just after loading your move. Biggest number of moves end by entry into empty squares. Also, very often you will be interested to know if given square, when busy, is not occupied by friendly piece. If there is somebody of your color, your piece can't enter into square. By checking one bit of color you can find your response. Having two bits for color and business is very handy for move generator. >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. Promoted piece goes into three empty bits. They are in the square of entry of promoted pawn. >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) Castling and prise en passant I never include in description of the board. They are rarely demanded. Castling is visible from one general variable that is demanded sometime only. Prise en passant is visible from the move previously executed. It goes also in some general variable that is demanded when need arrive. >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). Having 9 queens, and all other heavy pieces, was more that often occurence in my program usage. >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. If somebody is able to use 100 bites for entire board description without making manipulation of date too heavy and lengthy later in the game, he really well succeded! The best that I could find was 64 bytes. Leonid. >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.
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.