Author: KarinsDad
Date: 08:24:26 05/18/99
Go up one level in this thread
On May 18, 1999 at 00:43:35, Andrew Dados wrote: > >On May 17, 1999 at 23:08:33, Dann Corbit wrote: > >>On May 17, 1999 at 22:56:18, KarinsDad wrote: >>[snip] >>>This 174 does not include promotions. >>> >>>Actually, the 174 bits in the other posts came from a different scheme: >>> >>>100 bits 30 pieces and pawns packed >>>12 bits kings and castling >>>61 bits (62 remaining squares bitboard - last one not needed) >>>1 bit side to move >>> >>>or something to this affect (but I do not know where ep fits into this, maybe >>>into the kings structure). >> >>OK, stupid question time: >> >>Why do we need to store promotions for a position? After all, who cares how I >>got there. And if the piece information must be retrieved from this format, I >>could just consider the delta between this position and the previous one. >> >>There seems to be something major that I am missing here... > > Storing promotions was necessary for KarinsDad schema since he took >advantage of max number of pieces for given type and color.. (at least that's >how I understand it) > I rethought it all lately and am coming into conclusion that 165 bits can >do... > > Here's how: > >12 bit kings+castle status (see one of Eugenes posts how to fit it there) >1 bit side to move >62 bits piece location bitmap (minus kings which are given explicitely) > (in this schema I can't shave off last bit unfortunately). > > Now let's store info which will allow us to reconstruct piece list >[populating each consecutive square, as marked in bitmap]. For that we need: >- up to 30 bit pawn flags (depending upon number of bits set in 62_bitmap). 30 >comes from number of pieces - 2 kings. (We can shave off bits set at first rank >in 62 bit structure, but that won't help in worst case). >- up to 16 bit pawn color flags (depending upon number of bits set in previous >structure) > Note: one promotion will take away 3 bits from here if captured piece >(necessary for promotion to happen) was pawn: 2 pawn color flags and one pawn >flag. Actually we need only up to 8 bits set/unset in that structure to conclude >remaining pawn(s) color...so I would say up to 15, but promotion can get >complicated... >- now for each remaining piece we need 3 bit info: color bit + 2 bits type >(NBRQ). >that gives 14*3=42 bits. if we had a promotion then we either saved 3 bits in >pawn descriptions or taken piece other then pawn emptied room for promoted >one... >-3 bits EP file. (Or can we figure/encode it into above??) > >Let's add that all: 12+1+62+30+16+42+3=166 bits. Now in worse case of 32 pieces >we skip one color bit for last piece... getting closer to magic 20 bytes :) > >-Andrew- This is virtually identical to my structure in the original post here. You are going from a system of 30 of the 32 pieces at the same size (30 pieces in 100 bits) to one of pawns taking up the least amount of space and the rest of the pieces (except the kings) taking up more. You just have it listed slightly different. Here is the issue: Your basic schema of having 30 pieces in 100 bits makes all of the pawns/pieces the same size: 3.3333 bits per piece (not including location which is another bit). The advantage is that pawns and pieces are the same size, so you do not have to worry about promotions. My basic schema of having pawns at 2 bits (not including the location bit) and pieces at 4 bits results in 2 bits * 16 pawns + 4 bits * 14 pieces = 88 bits and the average is 2.9333 per piece. The disadvantage is caused by the advantage of pawns taking less space (since there are so many of them). Promotions increase the size of the structure. This is how my schema basically saved 12 bits (100-88) over your 174 bit schema (to get to 162 bits). If you think about it, we are basically at a standstill at this point. I could at this moment create a 160 bit structure if I said, well, due to the white king being on it's back rank until at least a few pieces are taken off and 2 of the four rooks are almost always on their back rank until at least a few pieces are taken off, the structure will always be 160 or fewer bits. However, unlike the promotion assumption where you know that at least a pawn has to be captured (dropping the size of the structure by 2 bits), these assumptions are weaker. Granted that they will happen in 99.99999 percent of games, there is always that chance that some game will have all pieces off the back ranks and no pieces taken and it would take 162 bits. I thought of a solution for this problem and the promotion problem. 1 bit structure fits into 160 bits 1 bit side to move 1 bit ep not available (eps are smaller) 12 bits kings (6 per) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits bishops (4 or 5 per) 20 bits knights (4 or 5 per) 20 bits rooks (4 or 5 per) 10 bits queens (4 or 5 per) This is 164 bits worse case (not including promotions). However, the following conditions decrease the size of the structure, so it can handle a large percentage (99.99999%) of real positions in 20 bytes: 1) If their are 32 pieces and the last one is not a pawn, you can save another bit. 2) If the white king is on the back rank, you can save another bit. 3) For every other piece on the back rank, you can save another bit. 4) For every pawn taken, you can save 2 bits. 5) For en-passant, you can save another 2 bits. 6) For every piece taken, you can save 4 bits. 7) If castling is possible, you can save 4 bits per rook that can castle. 8) For every promotion, you lose 1 or 2 bits (1 bit immediately when the piece is on the back rank, a second bit when the piece moves to row 2 through 7). Note: for every 3 possible promotions that gain bits (taking a piece and promoting is a wash of 0 bits), at least one pawn must be captured to open up the way. As can be seen, there are a lot of conditions which reduce the size of the structure by enough to handle the 4 extra bits (164 - 160) and any possible promotion. It would be extremely rare to have the "structure fits into 160 bits" flag as false. This is the best I can do so far. KarinsDad :)
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.