From: karttu@mits.mdata.fi (Antti Karttunen)
Subject: How to check the repetition of moves in Chess/Shogi (was Re: Complexity - Ideas)
Followup-To: rec.games.chess,rec.games.programmer
Organization: MITS, Helsinki, Finland
Date: Wed, 9 Sep 1992 08:35:11 GMT

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.
Newsgroups: rec.games.go