Two fold repetition 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.

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.

That is what I meant by 1h+999c case where h=history and c=current. So to see the draw-in-1000-repeation you would have to search 1000 plies deeper. I would rather decide in the check-evade repeation cases that the players can repeat the position ad infinitum if they do it once. Searching a position again can only help if hashtable or other dynamic table brings new information.

[bob]

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.

I gave one scenario where it does make sense, which is what triggered the discussion with John way back.

The first time you get checked on the back rank example I gave, you can go to d8 or f8. You have no idea that going to d8 takes you to a8 where you escape the checks, while going to f8 traps you where you have to get back to e8 and then move on to d8 to get out. But when your king has moved f8-g8-f8, you can now go to e8 or g8, BOTH of which are 2-fold and draw, yet e8 lets you escape the 3rd rep by going to d8.

Down-side is it makes it harder to detect repetitions overall, so that you end up walking into repetitions that a 2-fold repeat would let you see and avoid.

I did it. Didn't like it.

John made another suggestion which I also tried but later removed, that was in the first 2 plies of the search, only count 3-fold repetitions as draws, beyond ply=2, 2 or 3-fold repetitions are scored as draw. That introduced a quirk in hashing at ply=2.

I do as you (and most everyone else on the planet does) and count 2-fold repetition as draw, period...

Seems to work well enough except when annotating or analyzing human games where they will voluntarily repeat once, often just to get to time control, then avoid the 3rd rep. Until the game gets past that point, scores provided by Crafty are questionable since they are so intermingled with draw scores.

[syzygy]

I gave one scenario where it does make sense, which is what triggered the discussion with John way back.

That scenario shows that it is useful to not count a repeat of a position in the game history as draw.

It is never useful to not count a repeat of a position WITHIN THE SEARCH as 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.

That is what I meant by 1h+999c case where h=history and c=current. So to see the draw-in-1000-repeation you would have to search 1000 plies deeper. I would rather decide in the check-evade repeation cases that the players can repeat the position ad infinitum if they do it once. Searching a position again can only help if hashtable or other dynamic table brings new information.

Do you mean check-evades that repeat quickly? Or are you thinking of a situation where white has the advantege but the black Q chases the white K over half the board while the white K desperately tries to get out of check in order to be able to deliver the final blow to black (and avoid a draw)?

Probably the latter. In that case I think I see your point, but still it probably won't help to detect the first repetion of a position in game history as draw. White should have tried to avoid getting his K in this situation. If the first checks are in the game history, white is already in trouble and is not really helped by knowing this sooner.

[Daniel Shawul]

I am thinking of perpetual check situations where a side can force a draw, even though it is down in material. In those types of positions, it can take forever to see the draw if the draw-in-1000 rules is used. My scorpio actually doesn't differentiate positions in history/current, because it assumes optimal moves are made to reach the current position. With that assumption, if I want to go back to a position I have been before, it can only mean either all my other options are inferior/indifferent, or i have discovered something that I missed before. Otherwise I should not have made a move to bring me to the current position in the first place (circular reasoning). Older shredder versions used to get some wins against scorpio in blocked-pawn endgame positions, where it sees something new on the second repeats due to the hashtable. I tried to fix this in scorpio but later droped it.

[bob]

I gave one scenario where it does make sense, which is what triggered the discussion with John way back.

That scenario shows that it is useful to not count a repeat of a position in the game history as draw.

It is never useful to not count a repeat of a position WITHIN THE SEARCH as draw.

Maybe I misunderstand what you mean but in the scenario I mentioned, the position occurred once in actual game history, and once along the current path in the actual search. Draw or not? John suggested no. I tried but did not like. He then changed it to "OK, once in the history, and once anywhere beyond the first two plies of search == draw, but within the first two plies, it is only a draw if there are two identical positions in history and one in the first 2 plies makes 3. Didn't like that either after a lot of testing.

I've found this is one of the simplest ideas (repetition detection) to develop, but one of the most bug-infested things you can write. Lots of subtle things when you try to get cute with 50 move counter and such.

[syzygy]

I gave one scenario where it does make sense, which is what triggered the discussion with John way back.

That scenario shows that it is useful to not count a repeat of a position in the game history as draw.

It is never useful to not count a repeat of a position WITHIN THE SEARCH as draw.

Maybe I misunderstand what you mean but in the scenario I mentioned, the position occurred once in actual game history, and once along the current path in the actual search. Draw or not? John suggested no.

In this case it can be useful to not count the repetition as draw. But what I was talking about:

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.

Note the WITHIN.

[syzygy]

My scorpio actually doesn't differentiate positions in history/current, because it assumes optimal moves are made to reach the current position. With that assumption, if I want to go back to a position I have been before, it can only mean either all my other options are inferior/indifferent, or i have discovered something that I missed before.

Or it is something that your opponent missed before. If you're playing an engine, this is unlikely (but still possible). If you're playing a human anything can happen.

[hgm]

Indeed, that is the main point. All these arguments for counting first-repeat = draw are only valid if the engine played all moves from the first occurrence. And then they are good. But if they were played by a human opponent, (which will certainly be the case in analysis mode), they break down badly, and this is typically the situation that draws user complaints.

In the tree the engine is obviously always playing. But in analysis mode or human-engine it would be better to ignore a first repeat of a game-history position.

[syzygy]

In the tree the engine is obviously always playing. But in analysis mode or human-engine it would be better to ignore a first repeat of a game-history position.

One way of implementing the latter is by tweaking the game history checked during the repetition checking in such a way that it only includes positions that occurred twice in the actual game history.

So one could keep track of the real game history somewhere and before every search extract from this game history the positions that have occurred twice. (Not including the root position itself, since that position should be treated as a position occurring within the search, i.e. first repetition of the root position is treated as draw.) After that, any detected repetition is either a first repetition of a position within the search (so should be scored as a draw) or a repetition of a position that already occurs twice in the actual game history (so should be scored as a draw as well).

It is difficult to see how this could lose Elo: can the presence of more positions in the game history result in a better search? I think it has often been reported that it does, but I am starting to believe that most of these attempts may have tested something else (because this is clearly something that confuses many).