Author: Vincent Diepeveen
Date: 19:40:26 09/29/00
Go up one level in this thread
On September 29, 2000 at 22:11:10, leonid wrote:
>On September 29, 2000 at 20:03:02, Larry Griffiths wrote:
>
>>On September 29, 2000 at 19:11:17, Bo Sjögren wrote:
>>
>>>Some time ago, maybe a year or so, there was an interesting
>>>discussing about the minimum number of bits necessary to store an
>>>arbitrary chess position. What was the conclusion of the
>>>discussion? Can I find the discussion in the archive, or a
>>>summary somewhere on the net?
>>>
>>>Regards,
>>>Bo S
>>
>>I store mine in 32 bytes (256 bits). Each 4 bits contains the piece and its
>>color as follows...
>>
>>cppp
>>
>>where c is the color and ppp is the piece (could have up to 8 piece types).
>>
>>OR
>>
>>If you really like to pack bits you could have a fixed array of 6 bits times 32
>>bits (192 bits) where each of the 32 buckets has the square the piece is setting
>>on.
>>The problem with this second arrangement is that you would need another 8
>>buckets for each side (32*6bits+16*6bits=288 bits) if promotions occurred.
>>
>>Neither of these arrangements include bytes to hold the en-passant status of the
>>board or castleing state.
>>
>>Larry.
>
>I do save each position of chess board with 64 bytes. Every of those 64 bytes
>have three not used bits.
>
>5 busy bits are: 3 bits - description of piece.
> 1 bit - empty, occuped square.
> 1 bit - color for piece, if square is occupied.
>
>Leonid.
that's 512 bits or so.
can easily get it to 180 bits or so
let's first there are 2 approaches
a) storing entire positions in n bits always where n is a constant
b) storing it in a different sizes of bits. so only positions which
are UNLIKELY to occur like a position with more as 2 queens.
b is far more attractive as a.
A you can get easily in like
64 bits piece versus no piece
for all squares occupied now you need at most 32 bits
whether something is white or black.
that's 96 bits so far.
then we do 32 bits true or false for pawn versus non pawn.
128 bits now done. we know now 8 pieces for each side at most
and we know its place, we just don't know what kind of piece it is.
we have choices:
king
rook
bishop
knight
queen
Ok we have only 1 king, so we first start with king.
that's 3 bits. Now you have only 1 king so only 4 types of pieces left
for the remaining pieces. that can be done in 7x2 bits.
so in total for each side: 3 bits + 7x2 = 14+3 = 17
we do that for 2 sides. so besides the 128 bits we nees another 34 bits.
that's in total 162 bits (without ep rights and without castling rights)
and you sure haven't promoted pawns yet to use the full extend of
bits, as to promote a single pawn to a queen you lose from all sides
together most likely at least 2 pieces/pawns using objective best moves,
so that's more as the extra bits for naming it below costs.
Ok that's a first simplistic try to just index the board position,
without search status (castling rights, 1 time repetition etcetera,
en passant rights)
162 bits ==> 2^160 = 5.8 x 10^48
so this still is not a very accurate way of storing a position,
as i remember someone reported in JICCA 10^43 as the maximum amount
of positions, a number which i also doubt, as if you say 10^35 i
directly believe it too.
Now let's also face the fact that it is *unlikely* that pawns are
between a1 and h1 and between a8 and h8. You can use that also.
You can also use the fact that it's unlikely that there are more as or
equal to 2 queens on the board (already a bit used in the above definition).
if that happens, then someone made already a big mistake in the game, or
the position is ready to resign for either side, or a quiescencesearch
already removes the queen.
There are more rules. Like how likely is it that whites pieces are
being further as blacks pieces?
suppose we see a1 as 0 in an array and b1 as 1 and c1 as 2 and a2 as 8,
b2 as 9 etcetera.
How *likely* is it that many pieces of white are further as the
black pieces?
If so, then more as 4 pieces? VERY unlikely!!!
Well in positions with all pieces on the board i'm pretty sure that
it won't be too much pieces!
and if so then only at 4th or 5th row.
So now let's look to approach b, using a 'huffman' way of encoding,
i'm sure you can save a hell of a lot!
not to mention illegal positions also.
i have not had many games with all pieces on the board with the white
king being further as square second row!
If we make big assumptions and each assumption is worth a single bit,
then to what size can we get the average position down?
Let's use 'smart' rules, you really can go a long end then,
if you want to get 'normal' positions.
perhaps you can easily get down the average size to 140 bits after
some years of rules work?
I guess you'll do a bad job then, because some others claim that
getting down size to 100 bits then is perhaps possible for
normal looking legal positiosn which might occur on the board.
Sure is that 162 is an easy start you get for free (hoping i didn't
make calculation errors) with, if you want to play on safe with
en passant and capturing and allowing n pieces (so 9 bishops and
such) then 168 bits is easily doable.
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.