Author: Eugene Nalimov
Date: 22:36:20 05/16/99
Go up one level in this thread
Earlier I wrote how you can pack locations of both kings and castling status in 12 bits. In your schema you can do exactly the same - store not 10, but 12 bits in header, and don't store squares of the knigs in the bitmap. Then you don't need to store one extra bit that is castling status in the header. Eugene On May 16, 1999 at 23:24:37, Andrew Dados wrote: > >On May 16, 1999 at 22:39:59, KarinsDad wrote: > >>On May 16, 1999 at 14:18:27, Andrew Dados wrote: >> >>[snip] >>> >>> That is a nice one, KarinsDad! >> >>It was ok, but I screwed it up. I got about 3 hours of sleep last night, so I >>was zoning. The subset A and B equations are incorrect (I noticed this >>immediately when I saw your last schema) and in fact, you do not need subset A. >>Subset B is in reality 12^32 or 115 bits at all times. So, it was one complexity >>level too much and should have ended up being 23 bytes and 7 bits. >> >>> However 23 bytes suffice:). I just noticed I can pack EP info + castle status + >>>king positions >>>into 12 bits which brings schema of mine down to 23 bytes total....Let me recap >>>the format: >>> >>>-8 bits 50 move counter+side to move >>>-64 bits piece location bitmap >>>-up to 12 bits (with one exception) for: >>>1 bit *any* castle availability (none being worst case). if no castling for >>>either side then two 5 bit indexes for kings, otherwise 1 bit for castle[white] >>>followed by either 5 bit king[white] location or 2 bits castle status. This >>>followed by same structure for black... >>>1 bit EP possibility. If yes then 3 bit EP file in which case I don't have to >>>store max of 30 pieces, but 29 (I mark it mow as pawn and skip during unpacking >>>pieces) >> >>Glad you noticed it. It occurred to me on the drive to my nephew's soccer game >>today that you should be able to pack your castle and EP just like I did (i.e. >>into 2 bits for both in the header) and I was going to mention it. You beat me >>to it. >> >>Actually, you can store the EP as 28 pieces by adding another bit to EP (making >>it 1 EP exists and 4 for location and direction of EP) and subtracting out >>another pawn (see Eugene's earlier message; not needed, but eloquent none the >>less). Just something to remember when you are 2 bits shy. >> >>I was wondering since you did not mention it if once a piece is dropped (either >>due to being taken, or due to EP pawn removal from the bitboard) if it would be >>10 bits for 3 pieces, 7 bits for 2 pieces and 4 bits for 1 piece? I assume since >>you are doing a special pack (3 pieces per 10 bits) that you would do a >>different pack for the last 1 or 2 pieces (if, for example, you had 29 pieces on >>the board due to removing a piece for EP). >> >>>-up to 100 bits for 30 pieces (I pack 3 piece/color info (5x2=10 states for 1 >>>piece) into 10 bits (1000 states fits in 1024 :)) >>> when there is EP I save 3 bits here by storing only up to 29 pieces (those 3 >>>bits I need extra for EP file). >>> >>>total just equals 184 bits == 23 bytes. >>> >>> Andrew >> >>Well done! I thought alot about this problem today and realized that there are >>two ways that we have been looking at it. Either here are the locations and here >>are the pieces in those locations (your basic method) or here is a list of >>pieces within the bitboard and their order indicates their location (the first >>method I posted). >> >>In either case, I think that since the pieces themselves appear to be packed as >>much as possible, that we have to do a paradigm shift (i.e. not use one of the >>two above methods) to make it much smaller. >> >>I was toying with the idea of masks, ORs, and XORs to determine more information >>out of a much smaller packed set of data (where some data falls out of an XOR >>with a known mask type of thing, but different data falls out with an XOR with a >>different mask), but haven't come up with a single concrete idea yet. I believe >>that in such a concept, the masks cannot be location masks. >> >>But I think that the idea of storing ALL of the piece data in about 22 bytes is >>the bottleneck. That is the place to compress, but not with conventional >>methods. >> >>KarinsDad :) > > Little time here, so I'll keep my 2 further ideas short :) >- current schema allows up to 31 pieces per color; 32 pieces total. If we >deliberately narrow generality to maximum of 16 pieces per color (15+king) then >last piece color info is redundant and can be skipped (then last 3 pieces fit in >9 bits). This is nice, because allows to pack book information into 22 bytes if >we throw out 7 bit 50-rep info... > >- 64 bit location mask has *almost* one bit useless... that comes from limit of >total 32 pieces (we have always number of zeroes>=number of ones there). So I >thought last bit could be omitted and encoded with NOT opperation as follows: of >Ones>Zeroes then 63_bit->not(63_bit) and 64th bit can be figured out... however >this is *not always* possible (decoding will always be 1 on 1 relation, while 2 >positions could encode in same 63 bit set :) > >- Andrew-
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.