Author: Andrew Dados
Date: 21:43:35 05/17/99
Go up one level in this thread
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 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.