Author: Russell Reagan
Date: 22:18:53 12/26/02
I was looking over some TSCP code tonight, and I got to thinking about the
reps() function. Here it is:
/* reps() returns the number of times that the current
position has been repeated. Thanks to John Stanback
for this clever algorithm. */
int reps() {
int i;
int b[64];
int c = 0; /* count of squares that are different from
the current position */
int r = 0; /* number of repetitions */
/* is a repetition impossible? */
if (fifty <= 3)
return 0;
memset(b, 0, sizeof(b));
/* loop through the reversible moves */
for (i = hply - 1; i >= hply - fifty - 1; --i) {
if (++b[hist_dat[i].m.b.from] == 0)
--c;
else
++c;
if (--b[hist_dat[i].m.b.to] == 0)
--c;
else
++c;
if (c == 0)
++r;
}
return r;
}
I see how it works, but I couldn't explain how it works. If anyone would care to
take a shot at explaining the principle behind this, I'd love to hear it.
Anyway, the main reason I'm posting is because this function seems to only take
into account the from and to squares. It dawned on me that there are moves that
are different, yet have the same from and to squares. So my question is, will
this algorithm think white castling kingside (e1 to g1) is the same as moving
your queen from e1 to g1, promoting a pawn on e7 to a queen on e8 is the same as
promoting a pawn on e7 to a knight on e8, moving a rook from a1 to d1 is the
same as moving a queen from a1 to d1, and so on...? Or does it work because
detecting a repitition requires everything to be "undone", and the only way to
"undo" e1g1 is for the piece on g1 to move back to e1, and that can only be the
piece that moved there (obviously).
It's a clever little algorithm. Is it always correct?
It seems like this same algorithm could be used with a bitboard mask. For
example, g1f3 would be the bitboard:
00000000
00000000
00000000
00000000
00000000
00000100
00000000
00000010
Using the bitboard xor method, it would detect all repititions, but it also
fails, for example:
[D]8/5K2/8/7k/8/2r5/8/R7 w - - 0 1
After 1. Ra3 Rc1 2. Rc3 Ra1, the "difference bitboard" (as opposed to the
"difference array" b[64] in the TSCP example) is back to zero, and a repitition
would be detected.
So, assuming the function in TSCP is correct, how could you make this work with
bitboards? How about using two difference bitboards, one for the "from" masks,
and one for the "to" masks?
Russell
This page took 0.01 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.