Author: Andrew Dados
Date: 20:24:37 05/16/99
Go up one level in this thread
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.