transposition tables and three-fold repetition

[zenpawn]

Is there a technique to avoid falling into repetition draws when using the values from a transposition table? I've observed my engine doing this on several occasions now. I'm thinking an exact or beta cutoff move of sufficient depth might have to first pass the repetition test before it can be used as is from a TT.

Thanks,
-Erin

[hgm]

Usually one checks all moves to see if they lead to repetitions, before making them. And usually the TT is only probed after making them.

It is true that the TT sometimes can mask repetitions deeper in the tree, by taking the result from a search of the same position reached by a different move sequence, so that a key position in that sub-tree which was not a repetition then would be a repetition now. There isn't any real solution to this problem.

A slight refinement is to not accept a negative score from the TT after moves that revert the previous move by that side when the ply in betwen was reversible, as it should be possible to reach a repeat by now also reverting that move. I don't think many engines do this.

[zenpawn]

Usually one checks all moves to see if they lead to repetitions, before making them. And usually the TT is only probed after making them.

I have the repetition check at the top of search when ply > 0, so the move has been made in the calling search.

The TT check follows with beta and exact matches of sufficient depth causing the move to be added to the PV and the entry's score returned. If the depth is insufficient, it's the first move searched before generating the rest of the moves.

A slight refinement is to not accept a negative score from the TT after moves that revert the previous move by that side when the ply in betwen was reversible, as it should be possible to reach a repeat by now also reverting that move. I don't think many engines do this.

You lost me.

[hgm]

I have the repetition check at the top of search when ply > 0, so the move has been made in the calling search.

Then a TT probe can never be a repetition, as you would already have returned with a draw score before doing the probe if it was.

You lost me.

Suppose you are in the branch Ra1-a7 Nb8-c6 Ra7-a1, and at that point you get a TT hit with a score -150 for the side to move. The position itself is not a repetition. But you know oneof the moves that can be played here is Nc6-b8, which wouldlead to a repetition. The side to move would perfer the draw score from that repetition over -150. Apparently the search that came up with the -150 was searched with a different path leading to it,so that Nc6-b8 was not a repetition there. But it surely is now. So it would be wrong to use the -150, and you should return 0.

[zenpawn]

I have the repetition check at the top of search when ply > 0, so the move has been made in the calling search.

Then a TT probe can never be a repetition, as you would already have returned with a draw score before doing the probe if it was.

Not if it's ply 0.

You lost me.

Suppose you are in the branch Ra1-a7 Nb8-c6 Ra7-a1, and at that point you get a TT hit with a score -150 for the side to move. The position itself is not a repetition. But you know oneof the moves that can be played here is Nc6-b8, which wouldlead to a repetition. The side to move would perfer the draw score from that repetition over -150. Apparently the search that came up with the -150 was searched with a different path leading to it,so that Nc6-b8 was not a repetition there. But it surely is now. So it would be wrong to use the -150, and you should return 0.

Right, so this suggests a move from the TT should be made and tested for repetition before we can just return, since in this case, we'd want to return 0.

[Evert]

A slight refinement is to not accept a negative score from the TT after moves that revert the previous move by that side when the ply in betwen was reversible, as it should be possible to reach a repeat by now also reverting that move. I don't think many engines do this.

Interesting. I don't think any engines do this.

In fact, you can generalise this further: if there is a move that reverts the position to two moves ago (or, in general, repeats) you can raise alpha to 0 if it is lower, which might be enough to produce a cut-off.

Whether that is worth it or not will depend on how common the situation is. At the very least (if the move would have been searched first anyway), it saves you a recursive call to detect the repetition.

[hgm]

Not if it's ply 0.

Wouldn't the game have already ended in a draw, when you havea repeat at ply 0?

Right, so this suggests a move from the TT should be made and tested for repetition before we can just return, since in this case, we'd want to return 0.

Not really. What should be done is test whether move[ply-1] is the reverse of move[ply-3], and whether the reverse of move[ply-2] is pseudo-legal.

I think TheKing does this, and Rookie does something even more elaborate (although I forgot exactly what, but it involved a small hash table).

[zenpawn]

Not if it's ply 0.

Wouldn't the game have already ended in a draw, when you havea repeat at ply 0?

I'm referring to the move in the TT entry, which hasn't been made yet. But, if we just accept it as gospel and return, then it might have been a repetition.

Right, so this suggests a move from the TT should be made and tested for repetition before we can just return, since in this case, we'd want to return 0.

Not really. What should be done is test whether move[ply-1] is the reverse of move[ply-3], and whether the reverse of move[ply-2] is pseudo-legal.

I think TheKing does this, and Rookie does something even more elaborate (although I forgot exactly what, but it involved a small hash table).

You just mean this as a more efficient way of checking for repetition than actually making the move, right? Since most of the time the TT move won't be a repetition, it's probably a wash whether you make the move then test or do some interesting investigation of previous plies.

[hgm]

I'm referring to the move in the TT entry, which hasn't been made yet. But, if we just accept it as gospel and return, then it might have been a repetition.

OK, I see. But it seems always wrong to take a TT cut in the root, as the root basically requests an infinite depth, only limited by time. So whatever draft a TT hit would have, it will never be enough. You would always start the next iteration, which would start making the hash move, after which you would see it is a repeat. At that point no time has elapsed yet.

You just mean this as a more efficient way of checking for repetition than actually making the move, right?

More efficient than making all moves. Because the TT move is not the only one that could give you a repetition. If another move would give you a repetition the stm wouldplay that one, when the TT move scores negative.

And there is no guarantee you would get hash hits after all of these moves, so each move could start an entire tree. Youmight make the hash move, see it is not a repeat, also get no hash hit, and thus also search all moves there... Eventually conirming the negative score for it. Only to find that an alternative move does create a repeat so that the entire exercise was in vain.

[zenpawn]

I'm referring to the move in the TT entry, which hasn't been made yet. But, if we just accept it as gospel and return, then it might have been a repetition.

OK, I see. But it seems always wrong to take a TT cut in the root, as the root basically requests an infinite depth, only limited by time. So whatever draft a TT hit would have, it will never be enough. You would always start the next iteration, which would start making the hash move, after which you would see it is a repeat. At that point no time has elapsed yet.

Thanks, this is certainly an easy enough fix. Much appreciated!

I'll leave the other suggestion on the table for now.