Author: KarinsDad
Date: 19:39:59 05/16/99
Go up one level in this thread
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 :)
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.