Repetition Detection

[hgm]

I think the missed communication occurs in the term "history". Or more precisely "the past". I consider history anything that has happend up to now. Not anything that has happened up to the root of the tree we are searching. I find it more convenient to not make any distinction between whether a position occured on the real game board, or in the current search path, or both...

That makes the code _very_ simple and fast.

OK, clear. I can appreciate that "history" can mean anything upto a certain point, and "future" everything beyond it, even if it does not unambiguously imply what that point is. But "game history" still seems a good way to refer to anything from the beginning of the game upto the root of the current search tree. As opposed to "tree history". Or do you recommend other terminology for that?

[bob]

I think the missed communication occurs in the term "history". Or more precisely "the past". I consider history anything that has happend up to now. Not anything that has happened up to the root of the tree we are searching. I find it more convenient to not make any distinction between whether a position occured on the real game board, or in the current search path, or both...

That makes the code _very_ simple and fast.

OK, clear. I can appreciate that "history" can mean anything upto a certain point, and "future" everything beyond it, even if it does not unambiguously imply what that point is. But "game history" still seems a good way to refer to anything from the beginning of the game upto the root of the current search tree. As opposed to "tree history". Or do you recommend other terminology for that?

Either way works for me. In some context, "game history = moves actually played on board" seems accurate enough. The way repetition is usually defined, the same term there could be defined the same way as in "2-fold repetition in search or 3-fold repetition in search + game history". Or if you just say "twice in the game history" I would generally think of that as all moves up to the point of the repetition, as it would not occur to me to just check for repetitions in the game history and not in the search itself.

[Colin]

Thanks, I understand that.

I don't have a 50 move counter at present, but may make one at another time.
Searching backwards does seem a little inefficient, cause with your idea, you have to search 50 positions at each node in the tree.

I think a improvement would be too have another value attached to each position saying whether the move that lead to the position was a 'pawn move'/'capture'/'castling move', or not.

Then if it was a position P with the move that lead to it being a 'pawn move'/'capture'/'castling move', then none of the positions before P could be identical to any of the positions from P and after.

This would mean only searching backwards very few moves in most cases.

I'm a little unsure why 2 identical positions is sufficient to call it a draw, personally I would have looked for 3, and then return 0; if 3 identical positions were found.

Thanks for any help

[Ross Boyd]

Thanks, I understand that.

I don't have a 50 move counter at present, but may make one at another time.
Searching backwards does seem a little inefficient, cause with your idea, you have to search 50 positions at each node in the tree.

I think a improvement would be too have another value attached to each position saying whether the move that lead to the position was a 'pawn move'/'capture'/'castling move', or not.

Then if it was a position P with the move that lead to it being a 'pawn move'/'capture'/'castling move', then none of the positions before P could be identical to any of the positions from P and after.

This would mean only searching backwards very few moves in most cases.

I'm a little unsure why 2 identical positions is sufficient to call it a draw, personally I would have looked for 3, and then return 0; if 3 identical positions were found.

Thanks for any help

The 50 move counter gets reset to zero in the makemove every time a capture or non-reversible move is made... so therefore the backward scan for a repetition is usually quite short.

Cheers,
Ross

[bob]

Thanks, I understand that.

I don't have a 50 move counter at present, but may make one at another time.
Searching backwards does seem a little inefficient, cause with your idea, you have to search 50 positions at each node in the tree.

No, there is an easy optimization you can use. You only have to search backward for "50-move-counter" positions, because once the 50 move counter is reset, you can't repeat with positions that occur on either side of that reset, as a pawn was moved and it can never move backward, or a piece was captured, and you can't uncapture it. Most of the time you end up searching 3-5 entries max, usually less. In profiling, I can't even find "RepetitionCheck()" in the top 50...

I think a improvement would be too have another value attached to each position saying whether the move that lead to the position was a 'pawn move'/'capture'/'castling move', or not.

AKA "the 50-move counter"...

Then if it was a position P with the move that lead to it being a 'pawn move'/'capture'/'castling move', then none of the positions before P could be identical to any of the positions from P and after.

Which is the point of my previously mentioned "optimization"...

This would mean only searching backwards very few moves in most cases.

Correct..

I'm a little unsure why 2 identical positions is sufficient to call it a draw, personally I would have looked for 3, and then return 0; if 3 identical positions were found.

Thanks for any help

The reason is that if I can _force_ you to repeat a second time, I can also force you to repeat a 3rd time. And finding the second repetition takes a lot less search effort than finding the third repetition. Since we are limited by some sort of time control, I might not have enough time to detect a 3-fold repetition where I might detect the second repetition, and I would not realize it is a draw, and lose a drawn position, or draw a winning position, either of which is bad.

[bob]

The advanced programmers here know a lot more about this stuff than I do, but even though I could not implement a three move algorythm I did find a short cut that helps to eliminate that possiblity. When ever my program make a move I store a copy of that move and if the program trys to move back to that square I give it a penalty. Not prefect by a long shot but does prevent the repretition a little.
Bill

The problem would be if you have a knight on f3, and you play Nxe5 and then Nf3. No repetition there. The simplest solution is to take the Zobrist hash signature and store it for each ply. When you enter Search() recursively, at the top, you use that list and compare the _current_ Zobrist signature against entries in the saved table, starting at the end and working backward. But you only work backward for the number of moves indicated by the 50-move-rule since there is no point in looking for repetitions backward beyond a capture or pawn move since they would be impossible.

This is one of those features that is easy enough to get right that it is better to do it right from the beginning, otherwise you will spend lots of time looking at odd games and tracking the bad move back to a mistake caused by improper repetition detection. Even if you leave out the 50-move counter and just search the entire list, every time you make a capture or pawn push on the real board, you can always reset the list to zero, and searching thru 10-20 entries takes no significant time since it will remain in L1/L2 cache anyway.

[Colin]

Thanks,

I still don't get it though, would you return 0 once the same position is found twice?

Suppose white plays move to give position P (first time seen in search),
then,
black plays,
white plays,
black plays,
white plays,
giving position (P) again.

Then if white was a queen up on positon P, and could take a different path to avoid reaching P again, then its surely wrong to return 0 when white has a massive advantage.

I've probably got the wrong end of the stick though, as usual.

Thanks for any help.

[Sven]

Thanks,

I still don't get it though, would you return 0 once the same position is found twice?

Suppose white plays move to give position P (first time seen in search),
then,
black plays,
white plays,
black plays,
white plays,
giving position (P) again.

Then if white was a queen up on positon P, and could take a different path to avoid reaching P again, then its surely wrong to return 0 when white has a massive advantage.

I've probably got the wrong end of the stick though, as usual.

Thanks for any help.

Regarding the concept of returning 0 on first repetition (= second occurrence), it took me a long time until I got behind the idea of why this really works, and I will try to explain it in my words, hoping that other readers correct me if I miss something important.

The key point to quickly answer your question is that 0 will be returned from the node where position P is repeated but it's a different question whether that value 0 will make it back to the root (original P).

You can consider the following cases, based on your example above where in a position P, black is to move, and after four plies M1, M2, M3, M4 position P is repeated for the first time, reaching position PP which is identical to P:


1) If the value 0 makes it to the root (P) then we can say that black can enforce the repetition of P by making M1. Any other moves than M4 and M2 are not better than a draw for white, and black has no winning moves instead of M3 and M1. So the PV for black from P is M1-M2-M3-M4, and therefore black could repeat this PV again from PP.

2) If the value 0 does not make it to the root then either black has an even better choice instead of M3 or M1, or white can avoid the repetition of P by playing different moves than M4 or M2. In both cases the PV is different from M1-M2-M3-M4 and does not include PP, so it becomes irrelevant which value was returned from PP.

There is a third case which is indeed not really relevant since it is like case 1 so it could be skipped: the value 0 makes it to the root but does not originate from PP but from another node that evaluates to 0 for different reasons. This could happen if another white move turns out to be better than M4, so M3 indeed loses, but black has another choice instead of M3 that returns a draw; or the same with M2/M1 one move earlier.


Of course, when the search arrives at PP, you do not know yet the full outcome of searching P since the subtree of PP is a proper subset of the subtree of P. But knowing that in all cases discussed above you will not cause a wrong search result at P by returning 0 from PP, it is safe to do it, and it will also be a good idea to do it since
a) it saves nodes,
b) it may avoid missing the third occurrence of P ("PPP") due to your search depth, as Bob already pointed out.

A frequent problem when not applying this technique is that an engine plays a move that allows the opponent to repeat the position but the engine thinks it has an advantage (by not returning 0 on the first time), so the position is repeating in the game, and after that the engine is unable to avoid the second repetition which it can detect now, but too late.

The case may be different if PP is a node within your search but P is not, i.e. belongs to the part of the game that has already been played before the current search started. Here it can be discussed whether 0 shall also be returned on first repetition of a game position or not. In my old engine "Surprise" I don't do it, but some others do return 0 here, too, and maybe it is even the majority that does it. In my future engines I will change to the "return 0" fraction.


Another important issue is the hash table usage in case of repetition detection. A draw score (call it 0) that results from detecting a repetition must not be stored in the hash table, for this reason: when taking a different path to P in some other part of the search, it would be incorrect to return 0 there, too, if that other path is *not* a repeating path.


I also would like to add a few other hints on that topic, please forgive me if you are already aware of these.

- When searching backwards to compare the current hash key with hash keys of previous positions, you can obviously start at (currentPly - 4) and go backwards in steps of 2 plies while the ply you look at is >= (currentPly - fiftyMovesCounter), where usually 0 <= fiftyMovesCounter <= 100 (it might exceed 100 of course when the 50 moves draw is not [yet] claimed for some reason).

- When resetting the 'fiftyMovesCounter' to 0 after making non-reversible moves, don't forget to arrange for remembering the counter's previous value in order to restore it after unmakeMove(). It can be done by saving the 'fiftyMovesCounter' on a stack, perhaps along with other information that has to be saved there, too (like the hash key for each position of the game).

- Finally, you can of course omit the whole handling of repetition detection and 50 moves counting within qsearch (except directly at horizon nodes of course), provided your qsearch does only cover captures and promotions.


Sven

[bob]

Thanks,

I still don't get it though, would you return 0 once the same position is found twice?

Suppose white plays move to give position P (first time seen in search),
then,
black plays,
white plays,
black plays,
white plays,
giving position (P) again.

Then if white was a queen up on positon P, and could take a different path to avoid reaching P again, then its surely wrong to return 0 when white has a massive advantage.

But, and there is _always_ a but. Why would you allow the repeat of the second time if you could avoid it and eliminate the draw score. If I can force it once, I can force it again, assuming optimal play in previous moves searched...

I've probably got the wrong end of the stick though, as usual.

Thanks for any help.