Newsgroups: rec.games.chess,rec.games.programmer
Subject: <None>
From: schiewer@pa881a.inland.com (Don Schiewer)
Date: 12 Sep 92 14:32:44 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:
> In article <1992Sep8.192342.12106@ll.mit.edu> nates@ll.mit.edu ( Nate Smith) writes:
>>
>>this reminds me of the old computer problem:  how many bits does it take
>>to completely store a chess position?  remember that whether or not each
>>side can castle and what pawns are capturable by en-passant need to be kept
>>along with the usual image.  gee, i used to know the answer...bits = 29?
>>so then you get 2^29.  naw, maybe it was something else.  for go you need
>>to keep the number of captured stones and the state of each ko....hmmmm.
>>
>>- nate, 14kyu
> 
> Actually I just need this information for my Shoogi Server software,
> so that I can check when the same position is repeated.
> I remember that there was some similar discussion few months ago
> in the groups rec.games.chess and gnu.chess, concerning how the
> overall position for each move is saved in chess programs so that
> they can check whether the moves are repeated. (And what information
> are needed to save from each situation.)
> If somebody has saved any of those articles, could you mail them
> to me, thanks!
> 
> Then some technical rambling:
> 
> What I have thought about this myself, I have found the following ways
> to save the board situation in Shoogi:
> 
> 1) Save the whole board with 9x9 squares, with 5 bits per square.
> (4 bits for piece which is empty or one of the fourteen possible pieces,
> i.e. either king, gold, silver, knight, lance, rook, bishop, pawn, or one
> of the last six promoted, and 1 bit for colour.)
> That makes 5*81 = 405 bits. Plus pieces in hands for both players, which
> can be compressed as 2*16 bits. I.e. 437 bits total.
> 
> 2) For 40 pieces, store the location (either one of the 81 squares, in hand,
> or removed as handicap, i.e. 83 possibilities), whether promoted
> or not (well, not actually needed for gold & king), and colour.
> (Because colour of pieces are changed when they are captured and recaptured).
> That makes 40*9 = 360 bits.
> 
> 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.
> 
> 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.
> 
> I think it's important to notice that both in Chess and Shogi it doesn't
> matter which one of the 'physical' pieces are in which square, as long
> as they are similar. (I.e. concerning the rules of repetition. Do I have
> understood this right?)
> 
> 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
> but I mean the method where board can be generated without beginning
> the construction from the first move. Or at least so that it can be
> checked whether the same situation has been there previously.
> (Some kind of CRC, huh?)
> 
> Now, I replaced rec.games.board with gnu.chess in this humungous
> cross-posting, and set the follow-ups to rec.games.chess and
> rec.games.programmer. Use your own judgment whether they are
> valid groups if you post.
> 
> -- 
> 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.
-- 
Don Schiewer   | Internet  schiewer@pa881a.inland.com    | Onward Great
Inland Steel   | UUCP:     !uucp!pa881a.inland!schiewer  | Stream...
Newsgroups: rec.games.chess