Draw by Repetition Code
cma...@ix.netcom.com
I don't have any code yet that detects draws by repetition, and was
wondering how other people do it.
What I was thinking was this idea:
For each real game move made, store a linear array containing the 64
bit Hash Function for each of the board positions. As you search the
current move, add these search Hash Function values and remove them as
you make / unmake moves. For each position, do a linear search
backwards through this list to see if you have 2 other identical Hash
Function values in this array. If you do, you're there for the 3rd
time and its a draw. The Hash Function is already computed so there
is no time spent to use it for a second purpose.
For example, if you're at the 28th move in the game and you search to
10 ply, you have to do 38 compares to check for a draw. Is there a
faster way? Do other people include this check in the Qsearch as
well?
A second thought is that if you're down and wouldn't mind a draw,
could we completely forgo this test?
Thanks in advance,
Chris Mayer
PS. Am I correct in thinking the draw rule applies to the entire game
history, or is it just for back-and-forth repetitions?
Robert Hyatt
cma...@ix.netcom.com wrote:
: I don't have any code yet that detects draws by repetition, and was
: Thanks in advance,
: Chris Mayer
There are two obvious ways to handle this, and perhaps other not-so-obvious
ways as well.
In Crafty (and Cray Blitz) I use a linear list of hash keys. The list grows
until there is a non-reversible move at the root in which case the list is
re-started at with only 1 entry for the new position. That is, after a pawn
move, a capture, a o-o/o-o-o move the list is cleared. During the search I
maintain a starting index into this list that is normally set to position #1,
but if a non-reversible move is made, this starting index is set to that
position so that hopeless stuff doesn't have to be checked, since it is
impossible to have a repetition after a non-reversible move. On a Cray this
is the fastest way of all, because the list is loaded as a vector and checked
as a vector. On a PC, it works o.k.
Another way is to use your transposition table, and add a flag called "open".
When you traverse the search tree, when you make a move, you enter the position
in the transposition table and set the open flag. If you find it already open,
you just made a move that leads to a repetition. When you unmake a move you
have to "un-open" the position. I have some old code for this, and it is both
good and bad. Good in that it is just a tiny bit faster in endgames because
it is not uncommon for the repetition list to get quite long (also note that
if you ever get a repetition list >=99 you have a 50-move rule draw). The
drawback is that it is difficult to easily do something like internal
iterative deepending, which I do in Crafty. If I reach Ply=N on the PV
(the first move at each ply on a new iteration or after a fail high) and I
don't have a suggested move from the hash table, I call search from the current
position with depth-2 (since that call also will not find a transposition table
move, it will do this again and again until depth=0). Eventually, when depth=0,
we find the best capture, then do a depth=2 search and find a better first move,
then depth=4, ..., N to find the best move to try at this level. I found this
messy since when you enter search, you'd typically use LookUp() to see if you've
seen this position before, and it's the perfect place to mark the position as
"open".
I believe from prior discussions here that Bruce (Ferret) uses this latter
approach, suggested and used by Ken Thompson. I've tried both, but use the
list approach in Crafty because of simplicity. Either will work quite well,
and bugs will cause amazingly embarassing behavior. :)
Bob
brucemo
cma...@ix.netcom.com wrote:
>
> I don't have any code yet that detects draws by repetition, and was
> wondering how other people do it.
> What I was thinking was this idea:
> For each real game move made, store a linear array containing the 64
> bit Hash Function for each of the board positions. As you search the
> current move, add these search Hash Function values and remove them as
> you make / unmake moves. For each position, do a linear search
> backwards through this list to see if you have 2 other identical Hash
> Function values in this array. If you do, you're there for the 3rd
> time and its a draw. The Hash Function is already computed so there
> is no time spent to use it for a second purpose.
> For example, if you're at the 28th move in the game and you search to
> 10 ply, you have to do 38 compares to check for a draw. Is there a
> faster way? Do other people include this check in the Qsearch as
> well?
> A second thought is that if you're down and wouldn't mind a draw,
> could we completely forgo this test?
>
> Thanks in advance,
>
> Chris Mayer
>
> PS. Am I correct in thinking the draw rule applies to the entire game
> history, or is it just for back-and-forth repetitions?
The draw rule applies to the entire game history, to answer your last
question first.
If you find a repetition you return a draw score, and if causing a
repetition is really the best move, the score for this move will be best,
so you'll make the move, and draw by repetition, you hope. So you
absolutely want to do this check if you are down, because you want to
find drawing moves.
I don't think this linear search idea is the best way to do it, but I'll
make some comments about things you could do to make the idea work
better.
If you are going to do a linear search backwards, you can look at every
other ply, because you can't have a repetition if it's the other side's
turn to move. I think maybe you are already doing this.
You also only have to go as far backwards as the last pawn move or
capture.
If you find a position that has repeated during the search (as opposed to
the game history), you can return a draw after one repetition. This is
faster to find, and you might not get enough depth if you make yourself
have to find three repetitions in the search. Three entire repetitions
is a lot of plies.
Detecting positions that have been repeated in the game history is a
little different. You can return a draw if you find any of these, or you
can set it up so it only returns a draw if it's found the position in the
game history twice before.
The problem with a one-time game history repetition is that maybe your
opponent missed a win, and picked a move that really is a draw. If you
do this one-time repetion thing, you might transpose back into the
repeated position, where your opponent had the possibility of a win,
rather than keeping to the path you've proven to be a draw. If you force
the position to have been repeated twice in the game history, it really
is a draw if you find it again.
It's a matter of taste, so do that however you want.
Now, as to how to detect a draw using a method other than a linear
search. I use a method proposed by Ken Thompson, wherein you keep a
marker in your transposition table. When you visit a node, you mark the
element in the hash table as "open", and you "close" it when you leave
the node. If you find an open node during your search, you return a draw
immediately.
Another way would be to use a small auxilliary hash table that stores
keys, and allows faster lookup than a sequential search.
Perhaps there are other good ways?
bruce
John Stanback
cma...@ix.netcom.com wrote:
>
> I don't have any code yet that detects draws by repetition, and was
> wondering how other people do it.
> What I was thinking was this idea:
> For each real game move made, store a linear array containing the 64
> bit Hash Function for each of the board positions. As you search the
> current move, add these search Hash Function values and remove them as
> you make / unmake moves. For each position, do a linear search
> backwards through this list to see if you have 2 other identical Hash
> Function values in this array. If you do, you're there for the 3rd
> time and its a draw. The Hash Function is already computed so there
> is no time spent to use it for a second purpose.
> For example, if you're at the 28th move in the game and you search to
> 10 ply, you have to do 38 compares to check for a draw. Is there a
> faster way? Do other people include this check in the Qsearch as
> well?
> A second thought is that if you're down and wouldn't mind a draw,
> could we completely forgo this test?
>
In Zarkov I simply keep 32 bits of hash for each move in the game
history,
whether it has actually occurred on the board or during the current
search.
I also have a variable that contains the ply at which the last
irreversable
move occured. At each node in the search, including quiescence, if the
current ply is at least 4 plies beyond the last irreversable move I test
the current hash value against those for each position in the game
history
(for the current side to move only) back to the last irreversable move
and count the number of matches (repetitions). If the count is 2, then
this is the third repetition and a draw score is returned. If the count
is
1 and the current_ply > root_ply+2 then a draw score is also returned.
This
avoids problems that can occur if the program thinks that a move at the
root leads to a draw (due to a single repetition) when the oppenent may
vary, but it also lets the program treat repeated positions in the
search
as draws which helps a lot. Since most positions in a search are less
than
4 plies beyond the last irreversable move the repetition() function is
rarely
called and the performance hit for detecting repetitions is negligible.
John
cma...@ix.netcom.com
Thank you for the responses!
* Only check every other entry!
* Only check back to the last pawn/capture/castle!
I'm surprised I didn't think of stuff so obvious after its pointed
out.
One more Q, from an email response not posted. Is it still a draw if
the same position comes up but pieces have been transposed, like
swapping the exact positions of your 2 knights? If not, how do we
detect these 'bogus draws' by using the hash keys (as well as the
'open' flag in the Trans table)?
Chris Mayer
Robert Hyatt
cma...@ix.netcom.com wrote:
: Thank you for the responses!
: Chris Mayer
The rule says "the positions are identical if both sides have the
same potential legal moves"... so swapping knights makes no difference.
Swapping rooks might if it involves losing the right to castle, or
enpassant captures, etc. If you hash in castling status and enpassant
possibilities, you are covered...
lensp...@aol.com
In article <5aarjd$d...@sjx-ixn6.ix.netcom.com>, cma...@ix.netcom.com
writes:
>
>PS. Am I correct in thinking the draw rule applies to the entire game
>history, or is it just for back-and-forth repetitions?
You are correct. The draw-by-repetition rule applies to the whole game,
just remember that side-to-move is also taken into account. You can have
a position pop up a second time in a game, but if it is the other player's
turn to move, it is NOT the same position because of the move.
Hope this helps.
Simon Read
cma...@ix.netcom.com wrote:
> Is it still a draw if the same position comes up but pieces have
> been transposed, like swapping the exact positions of your 2 knights?
Hmmm... 2 rooks is more likely, since rooks tend to like to get
together.
2 bishops is rather less likely, though, since not many people promote
pawns to bishops.
2 queens, now, surely that's a sort of cruelty, letting your opponent
see you shuffling your 2 queens around and still not managing to
draw against his lone king? I think we ought to prevent that sort of
cat and mouse so let's make 2 positions with queens swapped equivalent
to a repeat.
I don't know about the letter of the law, but any position behaves
the same way as that position with knights exchanged. In practice,
those two positions are the same and I vote that the law treat
them as if they were the same.
Simon -hmmm, five bishops, I wonder...
lensp...@aol.com
In article <5ac0t9$c...@dfw-ixnews8.ix.netcom.com>, cma...@ix.netcom.com
writes:
>
>One more Q, from an email response not posted. Is it still a draw if
>the same position comes up but pieces have been transposed, like
>swapping the exact positions of your 2 knights? If not, how do we
>detect these 'bogus draws' by using the hash keys (as well as the
>'open' flag in the Trans table)?
Believe it or not, that argument HAS come up in OTB play. The last ruling
I heard was this: even if two same pieces (rooks, bishops, knights, or
queens) swap places through a sequence of moves, it is still the same
position with the same side to move. To quote rule 14C of the USCF
Official Rules of Chess:
"Triple occurrance of position: The game is drawn upon a claim by the
player on the move when the same position is about to appear for at least
the third time or has just appeared for at least the third time, the same
player being on move each time. In both cases, the position is considered
the same if pieces of the same kind and color occupy the same squares and
if the possible moves of all the pieces are the same, including the right
to castle or to capture a pawn en passant."
The FIDE rules state the same thing. One thing I don't think should be
there is the "or to capture a pawn en passant" part, being an impossible
situation as ANY pawn move means no more repetitions of that position.
Hope this helps.
Don Fong
In article <19970101192...@ladder01.news.aol.com>,
<lensp...@aol.com> wrote:
>In article <5ac0t9$c...@dfw-ixnews8.ix.netcom.com>, cma...@ix.netcom.com
>writes:
>player on the move when the same position is about to appear for at least
>the third time or has just appeared for at least the third time, the same
>player being on move each time. In both cases, the position is considered
>the same if pieces of the same kind and color occupy the same squares and
>if the possible moves of all the pieces are the same, including the right
>to castle or to capture a pawn en passant."
>
>The FIDE rules state the same thing. One thing I don't think should be
>there is the "or to capture a pawn en passant" part, being an impossible
>situation as ANY pawn move means no more repetitions of that position.
unf that part needs to be there. because the "en passant"
condition of a position can change without any pawns moving,
simply by the changing of the turn.
suppose i play a double advance that allows an en passant,
resulting in a position X. now (for whatever reason) we start
shuffling Kings back and forth. the 2nd occurrence of position X
is not the same as the first, because in the 1st occurrence
you had the possibility of capturing en passant, whereas in
the 2nd you didn't.
--
don fong ``i still want the peace dividend'' http://got.net/~dfong/
Dan Oetting
> In article <5ac0t9$c...@dfw-ixnews8.ix.netcom.com>, cma...@ix.netcom.com
> writes:
> One thing I don't think should be
> there is the "or to capture a pawn en passant" part, being an impossible
> situation as ANY pawn move means no more repetitions of that position.
A pawn must move to create a position in which the pawn can be captured en
passant. The same pieces can later occupy the same squares without moving
any pawn however the en passant capture move will not be available therefore
this will not be the same position for the repetition rule.
Simon Read
lensp...@aol.com wrote:
>[...] if the possible moves of all the pieces are the same,
>including the right to castle or to capture a pawn en passant."
>
>The FIDE rules state the same thing. One thing I don't think should be
>there is the "or to capture a pawn en passant" part, being an impossible
>situation as ANY pawn move means no more repetitions of that position.
It should be there, because the pawn might have moved 2 squares
allowing the en passant _several_moves_before_, so the first
occurrence of the position would not actually be the same as
the second and subsequent occurrences. Then the first occurrence
would be a different position and should not be counted.
Simon
_H_e_l_l_o_,_ _I_'_m_ _a_t_ _s_._r_e_a_d_@_c_r_a_n_f_i_e_l_d_._a_c_._u_k_
Urban Koistinen
Robert Hyatt (hy...@cis.uab.edu) wrote:
: : * Only check every other entry!
: : * Only check back to the last pawn/capture/castle!
: : I'm surprised I didn't think of stuff so obvious after its pointed
: : out.
: : One more Q, from an email response not posted. Is it still a draw if
: : the same position comes up but pieces have been transposed, like
: : swapping the exact positions of your 2 knights? If not, how do we
: : detect these 'bogus draws' by using the hash keys (as well as the
: : 'open' flag in the Trans table)?
: : Chris Mayer
: The rule says "the positions are identical if both sides have the
: same potential legal moves"... so swapping knights makes no difference.
: Swapping rooks might if it involves losing the right to castle, or
: enpassant captures, etc. If you hash in castling status and enpassant
: possibilities, you are covered...
Hashing in ep possibilities is easy to get wrong.
Also, it might well be that most computer chess
programs have the 50 move rule wrong. I have not gotten
a reply to my question about the 50 move rule to the swedish
chess federations rules committe yet.
/Urban
Busy typing in lots of games from Rilton Cup... watch:
<http://www.vks.is/skak/rilton96.html>
lensp...@aol.com
In article <5aejm2$h...@darkstar.ucsc.edu>, df...@cse.ucsc.edu (Don Fong)
writes:
>>
>>The FIDE rules state the same thing. One thing I don't think should be
>>there is the "or to capture a pawn en passant" part, being an impossible
>>situation as ANY pawn move means no more repetitions of that position.
>
> unf that part needs to be there. because the "en passant"
>condition of a position can change without any pawns moving,
>simply by the changing of the turn.
>
> suppose i play a double advance that allows an en passant,
>resulting in a position X. now (for whatever reason) we start
>shuffling Kings back and forth. the 2nd occurrence of position X
>is not the same as the first, because in the 1st occurrence
>you had the possibility of capturing en passant, whereas in
>the 2nd you didn't.
You're right. I wasn't thinking about that part. That's what I get for
reading this newsgroup at 4:30 AM... dB^)
Fernando Villegas Darroui
Hi John:
I always liked the style of your programs and so I have bought it all, the
last being Zarkov 3,0, from gambitsoft. My question: are you going to
prepare a new, more advanced version? I like the style of Zarkov but no so
much the strenght of zarkov.
Regards
Fernando
Komputer Korner
Bookup uses Zarkov 4.
--
Komputer Korner
The komputer that kouldn't keep a password safe from
prying eyes, kouldn't kompute the square root of 36^n,
kouldn't find the real Motive and variation tree in
ChessBase and missed the real learning feature of Nimzo.