Threefold repetition questions

[jaespo]

Hi

I'm starting work on a chess engine (for fun), and I have questions about threefold repetition draws. (I want to make sure I get this right...)

1) Is the rule by "piece type" or by actual piece? I know that's not very clear, so let me give an example. If I have two positions that look identical, except the first one has the queen's rook in it, and the second one has the king's rook in it (on the same square as the queen's rook in the first position), are they considered to be equal for the purpose of the threefold repetition rule?

2) Is perft supposed to honor the threefold repetition rule?

3) Is it good enough to use a simple hash table to detect repeated positions? Or do I have to worry about hash key collisions and do something to handle them?

[bob]

Hi

I'm starting work on a chess engine (for fun), and I have questions about threefold repetition draws. (I want to make sure I get this right...)

1) Is the rule by "piece type" or by actual piece? I know that's not very clear, so let me give an example. If I have two positions that look identical, except the first one has the queen's rook in it, and the second one has the king's rook in it (on the same square as the queen's rook in the first position), are they considered to be equal for the purpose of the threefold repetition rule?

2) Is perft supposed to honor the threefold repetition rule?

3) Is it good enough to use a simple hash table to detect repeated positions? Or do I have to worry about hash key collisions and do something to handle them?

Actually, neither. The rule is "the same side must have the same exact potential moves available". You can have the same position occur three times, but not have the same moves possible. If white has a pawn at d5, and black plays e5, this is one occurrence of this group of pieces on the same square. But if both just shuffle knights back and forth, the second "repetition" would not be a true repetition, because the ep capture is not possible the second time around. So in this case, it takes 4 actual repeats with the same pieces on the same square, because the first occurrence has an extra move that the 2nd and 3rd do not, requiring a 4th repeat to be able to claim the draw...

hash key works for everybody, assuming you mean 64 bits.

[hgm]

Pieces of the same type are indistinguishable.

Perft does not count draw claims. (Note these do not automatically finish the game.) Not sure if they should count regklementary game end by insufficient mating material; I guess no one subjects pieces where this can happen to perft.

If you have a single-threaded engine, you could mark hash entries as 'busy' when you reserve them for the current node. Or better yet, initialize them with zero exact score and infinite depth, such that every probe deeper in the branch causes a hash cutoff with the draw score. (And when you searched the node, you overwrite that with the real score/depth/bound type.)

It pays to check for repeats from a small list of hash keys since the last irreversible move before you do the hash probe, however. This list would easily fit in cache, and checking there is way cheaper than the hash probe, and then you would not have to do the latter on moves that are repeats.

[jaespo]

Thanks.

I was aware of the issue of position-rights (castling and enpassant).

However, I didn't know that a 3-repetition needed to be claimed by a player to be a draw.

The idea of keeping the recent position hashes is very good.

I'm not sure I understand this:

"If you have a single-threaded engine, you could mark hash entries as 'busy' when you reserve them for the current node. Or better yet, initialize them with zero exact score and infinite depth, such that every probe deeper in the branch causes a hash cutoff with the draw score. (And when you searched the node, you overwrite that with the real score/depth/bound type.) "

but I'm still working on move generation and haven't started the search code at all. Maybe it will make more sense then when I'm trying to evaluate a draw in the search.

[Norm Pollock]

http://en.wikipedia.org/wiki/Threefold_repetition

Make sure you look at the Fischer-Spassky misuse of this rule during their World Championship match. It's at the bottom of the article.

[hgm]

I'm not sure I understand this:
...

The point is that in a multi-threaded engine different threads will be searching different branches. But they will share the hash table. So you cannot label positions in the hash table as 'occurring in the current branch', (to catch a later return to them), because other threads which come there through a completely different path would then also think it is a repetition, even if they see it for the first time.

Of course that doesn't apply to repetitions of game positions. Those can be hashed as absolute zero scores. This is how micro-Max does it. But micro-Max cannot see repeats in search, and thus plan them, or plan to avoid them.