Two fold repetition rule

[Michel]

This discussion came up on the Stockfish developers forum.

https://chessprogramming.wikispaces.com/Repetitions quotes John Stanback about his implementation in Zarkov

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 opponent may vary, but it also lets the program treat repeated positions in the search as draws which helps a lot.

I think that the claim that the root position should be excluded from the two fold repetition rule is incorrect. If one of the players can force a repetition in search then it will be able to force a second repetition. The root position is in no way special in this regard.

Comments?

[Daniel Shawul]

I return draw score after just one repetition regardless of the location of the previous position we repeated at the current ply. The 3-fold repetition is used only to claim draws at the root. During search it doesn't make sense to wait for 2 or more repetitions to terminate search along the current line. If the engine repeats it once (to get a draw), it can do it twice.

[bob]

This discussion came up on the Stockfish developers forum.

https://chessprogramming.wikispaces.com/Repetitions quotes John Stanback about his implementation in Zarkov

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 opponent may vary, but it also lets the program treat repeated positions in the search as draws which helps a lot.

I think that the claim that the root position should be excluded from the two fold repetition rule is incorrect. If one of the players can force a repetition in search then it will be able to force a second repetition. The root position is in no way special in this regard.

Comments?

I was in that r.g.c.c discussion way back. What I remember John saying was that to count as a repetition, the position either had to be repeated three times overall, or repeated twice inside the current search.

That has 3 cases.

1. two repetitions in the game history (before the root move) means the next repetition is an actual draw, no escape.

2. one repetition in the game history, the first repetition in the search is NOT scored as a repetition, but the second one would be.

3. no repetition in the game history, the first repetition in the search IS scored as a repetition, even though it is not proven to be correct yet.

That was an attempt to address a pretty simple problem. With one position in the game history, any repeat (for those programs that just count 2 repetitions as a draw) appears to be a draw. But on some occasions you actually need to walk THROUGH the first repetition to escape a draw. But since any repetition is a draw, your program may well choose to go the wrong way.

An example. Your king is on e8, white has connected rooks on h7 and g7. You have a bishop that attacks the square a7. White checks with Rge7, and you go to f8. White checks with Ref7 and you go to g8. When white plays Rfg7 you see a 2-fold rep and think it is a draw. You move to f8. Now white plays Rgf7 and you have two choices. BOTH appear to lead to a draw since moving the K to e8 repeats, and moving it to g8 repeats (note one position is in game history, one is in search, but that is 2x which is treated just like 3x by most everyone. If you go to g8 is will end in a real draw.

If you use stanback's idea, you will play Ke8 and not score it as a draw, because one position is in the game history, one is in the current search, which is not enough. You need 2 in search or 3 if two of them are in history. You score Ke8 as safe, and on Rfe7 you have two choices. Kf8 gives a 3rd repeat, Kd8 does not, you get to a8 where the checks stop since you have a7 covered.

Now, more info.

The reason we score 2-fold as a draw is to recognize draws sooner. In the above position without the bishop, it would take you a LOT of searching to realize that you are winning, but your opponent can force a 3-fold rep, because if you start on a8, the king can walk all the way to g8, back to a8 back go g8 and back to a8 before the 3-fold rep triggers. DEEP search. Scoring the 2-fold rep as a draw catches it much sooner.

But it has a drawback, because you were originally checked, you went the wrong way not knowing, and now you can't get back to the original square and go the other way because your search is saying all of those positions are drawn.

But there is another side of the story. Twice in search or once in search + twice in history has its own problem. Sometimes repeating twice in search is too deep to find, particularly when you search a deep PV to win material and overlook an opponent's draw. "The crazy rook" is an example where you inadvertently make a move that stalemates your opponent, except that he has one rook that can move, nothing else. And he calmly moves it next to your king and checks you. You can't capture as it is a stalemate. All you can hope for is that you can search deeply enough to see the rep. It is easier to see 2 than 3.

I have not seen (or at least don't remember) the root+2 idea, although it might have come up. I tried this back then as the r.g.c.c discussion will show, but I didn't like the way it tended to delay detecting repetitions. Today, two repeats = draw from the search's perspective, although I require 3 to actually claim a repetition and end the game.

I agree with your reasoning. There is also an issue with search inconsistency and hashing, but that's best left to another topic.

[bob]

I return draw score after just one repetition regardless of the location of the previous position we repeated at the current ply. The 3-fold repetition is used only to claim draws at the root. During search it doesn't make sense to wait for 2 or more repetitions to terminate search along the current line. If the engine repeats it once (to get a draw), it can do it twice.

It actually makes good sense to do what John suggests, but IMHO the cost is too high and outweighs the advantage, which is still quite real, just too expensive for me.

[Michel]

My gripe is only with considering the root node special. I think that is likely harmful as it is making the search tree bigger for no benefit at all.

However treating positions before the root node in a special way is probably harmless, and useful for analysis. The reasoning is that an engine has no control over moves in the game history which might be suboptimal. So it should not use the game history to score positions as draw (except when mandated by the 3fold repetion rule).

People claim there might be some hash table impact but I don't really see how.

[Daniel Shawul]

My gripe is only with considering the root node special. I think that is likely harmful as it is making the search tree bigger for no benefit at all.

However treating positions before the root node in a special way is probably harmless, and useful for analysis. The reasoning is that an engine has no control over moves in the game history which might be suboptimal. So it should not use the game history to score positions as draw (except when mandated by the 3fold repetion rule).

People claim there might be some hash table impact but I don't really see how.

I have used it in the past but realized it doesn't make sense because you don't want to search the same position again in hope of a suboptimal play by the opponent. Say the rule was repeat in 1000 instead of 3, then 999h+1c, 998h+2c, .... 1h+998c which is an absolute waste of time. If you had returned after one position, you would see draws very quickly. It can only help if the opponent makes sub-optimal, and ofcourse it incurs big overheads.

[syzygy]

I think that the claim that the root position should be excluded from the two fold repetition rule is incorrect. If one of the players can force a repetition in search then it will be able to force a second repetition. The root position is in no way special in this regard.

I agree. Repeating the root position should already count as repeating a position in search.

[syzygy]

My gripe is only with considering the root node special. I think that is likely harmful as it is making the search tree bigger for no benefit at all.

However treating positions before the root node in a special way is probably harmless, and useful for analysis. The reasoning is that an engine has no control over moves in the game history which might be suboptimal. So it should not use the game history to score positions as draw (except when mandated by the 3fold repetion rule).

People claim there might be some hash table impact but I don't really see how.

I have used it in the past but realized it doesn't make sense because you don't want to search the same position again in hope of a suboptimal play by the opponent. Say the rule was repeat in 1000 instead of 3, then 999h+1c, 998h+2c, .... 1h+998c which is an absolute waste of time. If you had returned after one position, you would see draws very quickly. It can only help if the opponent makes sub-optimal, and ofcourse it incurs big overheads.

I don't see any increase in search overhead when going from 3-fold to 1000-fold. Only the game will last a lot longer.

Actually, a 1000-fold repetition rule is the same as no repetition rule, because the 50-move rule will ensure that the game has ended long before.

So this nicely illustrates that the "two-fold repetition rule" (i.e. 2-fold repetition WITHIN the path from root to current node) is in fact not an implementation of the 3-fold repetition rule, but a very sensible search heuristic. It makes no sense to search the same path twice in a row, even if chess would have no repetition rule but only the 50-move rule.

[Daniel Shawul]

Repeation draws are often check-evades so you extend those lines to 1000 plies and you have a search explosion. The 1h+999c case would require you 999 or so checks before it decides it is a draw.

[syzygy]

Repeation draws are often check-evades so you extend those lines to 1000 plies and you have a search explosion. The 1h+999c case would require you 999 or so checks before it decides it is a draw.

No, the point is you stop at the first repetition within the search, but do not stop if you merely repeat a position that in the game history.