Repetitions/50 moves and TT

[marcelk]

Threefold repetition and 50-moves rule are the worst enemies of Transposition Table. Formally, the same positions (from the point of view of the board state) can be different due to different preceeding "silent" moves. That's why full transposition probe can lead to error (usually too later seeng the repetition or 50th move). One of the probable solutions is to mark TT evaluations with some flag that indicates that score of TT position (1) depends of draw node, that depends on node preceeding to (1). It should be restricted to use this score to cut probing node. Anyone tried it?

I do this. The engine recognizes that a backed-up score is 'tainted' by a repetition to a parent node, and in that cases only stores the best move. It is cheap to implement, but 'solves' half of the problem though. (You still have the cases where a TT entry is 'untainted', but in reality there is a draw that you will never see anymore. This happens if you find the nodes in the opposite order).

I haven't measured yet if removing it makes the engine stronger or weaker. I can well imagine it is not a good thing to do at all.

Later I found an old (1985) article by Murray Campbell that describes this technique in more detail. With google you might find a free pdf. For example here: The graph-history interaction: on ignoring position history

PS: I also observe occasional problems in mating in KRK btw but I think in my program that has a different root cause.

[bob]

how can it work?

I have such an idea. Let's add to the eval in TT special flag — "repetitionDependent". During probe we can't use this eval, only TT move.

That only addresses 1/2 of the problem. What about the positions where you retrieve a score that is NOT a draw-based score, but the current path you are searching when extended by the path leading to the TT hit actually passes over a repetition or 50 move draw but you don't know? This is a far more common case for me, happens in endgames all the time, where you get a non-draw TT score and follow that path right into a forced draw where you have to then change to a different move and the score drops from what you expected..

When obtaining repetition in the beginning of Search(), you should return also ply at which this position previously occured ("repetitionPly").

If you got the search result, with repetitionPly < currentPly, you should store this search result in TT with repetitionDependent mark.

And finally the search() should return as repetitionPly the earliest ply from the results of recursive searches.

I think it's also possible to improve this approach to work better in alpha/beta framework, distinguishing repetitions that fails low and repetitions that fails high... It's neccessary to analyse it deeper...

[Sergei S. Markoff]

Later I found an old (1985) article by Murray Campbell that describes this technique in more detail. With google you might find a free pdf. For example here: The graph-history interaction: on ignoring position history

PS: I also observe occasional problems in mating in KRK btw but I think in my program that has a different root cause.

Thank you very much for the link.
So, yes, second half of the problem still exists. Of course, we can exclude all TT evals where best move is not irreversible and the current position has previous non-irreversible move. But it looks to be too excessive...

[bob]

I never thought about this problem before, but now that I do, I see that it can only lead to the TT being supplied with false draw scores.

Wouldn't a fix be to never store any draw score in the TT?

No, there is the other half of the problem.

You search to some position P by the following path:


a-b-c-d-e-f-g-h-i-j-k-l-m-n-o-P-q-r-s-t-u-v-w-x-y-Z where Z is the terminal score that produces a non-draw result. (each letter represents a position along the path from the root to P. So you store whatever score is backed up to P (a non-draw score) and then you search this:

x-y-a-b-c-d-e-f-g-h-i-j-k-l-m-n-o-P and you get a hash hit. Which gives you the score backed up from Z. Which required that you pass through positions x and y to get there. But you have already passed through those on this path and if you REALLY searched toward Z normally, when you hit x you would see a repetition and stop. But with the hash hit, you don't see draw score, yet you are walking right into one. And when it comes time to actually play the move that leads to position x in the real game, you realize "wait, this is a draw, can't play that, so I'll change my mind and play something else -- with a lower score."

[hgm]

In Joker I developed a method to keep the TT rigorously clean of draw-contaminated scores. It worked by not scoring the second occurrence a draw, but search through to the third. In the sub-tree behind the second occurrence hash storing is disabled, and repeated positions do not probe the hash. In practice this means that any side branch of the repeat loop is a hash hit, as it was already searched at larger depth the first time the loop was traversed. Only the branch that follows the repeat loop the second time will be searched, and the minimaxing there will be used to determine if it is favorable for either side to break the loop, or if it is better to follow it to the third occurrence, and get the draw score.

After that it is known if the repeat is a draw or not, and the score and its consequences can be safely committed to the hash table during the unwinding of the first loop traversal.

But even without draw contamination of the TT, the problem of not seeing a draw when there is one remains. And you have to take special measures to prevent it from abusing the possibility to play a single repeat to create horizon effect.

[Sergei S. Markoff]

That only addresses 1/2 of the problem. What about the positions where you retrieve a score that is NOT a draw-based score, but the current path you are searching when extended by the path leading to the TT hit actually passes over a repetition or 50 move draw but you don't know? This is a far more common case for me, happens in endgames all the time, where you get a non-draw TT score and follow that path right into a forced draw where you have to then change to a different move and the score drops from what you expected..

Of course — this is the problem. May be it's a good idea to verify main line from TT to be sure that it don't contain a repetition? I think this measure worth to try.

[Ralph Stoesser]

A General Solution to the Graph History Interaction Problem (PDF, year 2004)

[Sergei S. Markoff]

Pretty cool.

[mcostalba]

PS: I also observe occasional problems in mating in KRK btw but I think in my program that has a different root cause.

I really don't know what's the reason of the bug, mine is only a guess and the fact is that the bug is still open as of today

[bob]

That only addresses 1/2 of the problem. What about the positions where you retrieve a score that is NOT a draw-based score, but the current path you are searching when extended by the path leading to the TT hit actually passes over a repetition or 50 move draw but you don't know? This is a far more common case for me, happens in endgames all the time, where you get a non-draw TT score and follow that path right into a forced draw where you have to then change to a different move and the score drops from what you expected..

Of course — this is the problem. May be it's a good idea to verify main line from TT to be sure that it don't contain a repetition? I think this measure worth to try.

How can you do that? When you get a hash hit, you don't have the path that was searched to store the position...