Author: Derek Mauro
Date: 19:10:20 01/15/02
I'm having trouble believing that the repetition code in TSCP works.
From TSCP:
/* 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;
}
Can someone somewhat formally prove this works please.
Say you had a white knight on d3 and a black knight on d5, wtm, and the sequence
of moves 1.Nb4 Nf4 2.Nd5 Nd3 followed. This is clearly not a rep because the
white and black knight have exchanged squares. Unless I'm crazy (it's late here
in NY...) this algorithm should detect it as a rep.
I'll try to track all the variables below from the start of the for loop. I'm
going in reverse order since the algorithm checks the moves in the reverse order
they were played. Where have I gone wrong?
2...Nf4-d3
b[F4] = 1, ++c
b[D3] = -1, ++c
c = 2
2.Nb4-d5
b[B4] = 1, ++c
b[D5] = -1, ++c
c = 4
1...Nd5-f4
b[D5] = 0, --c
b[F4] = 0, --c
c = 2
1.Nd3-b4
b[D3] = 0, --c
b[B4] = 0, --c
c = 0, Therefore a rep??
I feel like I'm going insane here and I hope I haven't asked a dumb question :)
Derek
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.