Newsgroups: rec.games.chess,rec.games.programmer
Subject: <None>
From: schiewer@pa881a.inland.com (Don Schiewer)
Date: 12 Sep 92 14:43:20 CDT
Followup-To: rec.games.chess,rec.games.programmer
 <NICKH.92Sep7145835@VOILA.VENARI.CS.CMU.EDU> <1992Sep8.192342.12106@ll.mit.edu> <1992Sep9.083511.10761@mits.mdata.fi>
Organization: Inland Steel Company, East Chicago, IN
Nntp-Posting-User: schiewer

In article <1992Sep9.083511.10761@mits.mdata.fi>, karttu@mits.mdata.fi (Antti Karttunen) writes:
> 
> 3) Variation of 1, where it is stored 6 bits per piece (3 for piece itself,
> 1 whether promoted and 1 for colour). If high-bit (bit-5) is 0, then it
> means that this is piece, but if 1, then bits 4-0 are count of empty squares to
> next piece (i.e. 1-32), so in minimum this takes only 40*6 + 32
> = 272 bits if all the pieces are clumped together, and in max. this takes
> 80*6 + 32 = 512 bits, if none of the pieces are next to each other.

I understand part 1, but don't you need more than 1-32 count of empty squares
to the next piece?  A1 to H8 is 62 empty spaces or am I missing something?
Also, I don't understand you conclusion (ie. 272 min/512 max.??)

> 
> So I wonder whether that 29 bits is valid for chess, 29 bytes (= 232 bits)
> sounds more plausible. There are more possibilities in Shogi because
> there are more pieces (possibly promoted) and more squares, although there
> is no need to save any kind of castling or en passant information in Shogi.
> 
> So if anybody knows some better (= more compressed) method to save the whole
> board situation in Chess then please let me know. I try to extrapolate
> it to Shogi. Of course, in principle, the most effective method to
> save the board is to save only the changes, i.e. moves, as with move log
> 
> -- 
> Antti Karttunen       --  $B%"%s%C%F%#!!%+%k%C%H%%%M%s(J  (et{ty|t|n)
> karttu@mits.mdata.fi  --  Apatheist, although not particularly proud of it.

The trade-off of compressed data structure is algorithmic complexity.
To optimize storage of chess positions (state) depends on the operations you
need to do on the data.  Just to reconstuct the board, in a case where you need
to save many states, high compression is fine.  If you want complexe analysis
of fewer states, more direct (physical) representations will be faster.

I can't see why info on pawn promotion or .ep. is important to game state.
Castle ability could be 2 global bits. (Perhaps pawn promotion for redundant
position test but not .ep.)  At any rate, if you limit pawn promotion to
Q/N, then you can encode a piece in 4 bits.

123                    + 1 bit for color.
000 - K 
001 - Q 
010 - B 
011 - N 
100 - R 
101 - P 
110 - P promoted N
111 - P promoted Q

A physical representation would be 64 * 4 bits per square = 256 
to represent state.

To represent position, I think you need 6 bits (2^6=64) so 10 bits per piece.

Now, you could have a "piece list" with each piece containing its postion.
That would make 10 bits per piece. 32*10=320 bits initially and decreasing
as pieces are removed.

You could also add a piece/space bit 5 to the 4 piece bits and make a 
contruction list with each item having 5 bits. You could use up to
4 "space" travel all 64 spaces (only need 62 space -- each space item
can encode 16 space plus one assumed if they are chained = 17 spaces 
counting left to right, bottom to top ).
A new board would be represented by:

 2 bits for castle ability +
 16 (white pieces) * 5 (bits per piece item) + 
 2 space descriptions * 5 (bits per space item) +    (ie. 32 spaces)
 16 (white pieces) * 5 (bits per piece item)      = 172 bits  

 This is probably around the average memory needed. 
 Some extremes would be:

 a piece on every other square:  2 + 16*5 + 31*5 + 16*5 = 317 bits (unlikely)

 white k/a1, black k/h8 : 
        
      2 + 1*5 + 4*5 + 1*5 or
                    16+(1)+ 16+(1)+ 16+(1)+ 11=62
      00 + 00000 + 11111 + 11111 + 11111 + 10111 + 00010 = 32 bits (unlikely)
      ^^   ^^^|^                       ^           ^^^^
      |    |  ||    set                |            |
castle   king |L---piece          set space     black king
codes       white

On clear board :  N/C3,  P/D5

           16+(1)+1=18 spaces        16 spaces
     00 + 11111 + 00011 +     01100 + 11111    + 10110   = 27 bits
                               wN                 bP


I'm not sure if I gave you any new info, but I like to twiddle bits.

Please let me know if there any problems with this.

-- 
Don Schiewer   | Internet  schiewer@pa881a.inland.com    | Onward Great
Inland Steel   | UUCP:     !uucp!pa881a.inland!schiewer  | Stream...