repetition draw detection + transposition table?

[cyberfish]

Hi,
I was wondering how is everyone dealing with the repetition draw + transposition table problem.

More specifically, how should I track repetitions "through" a table lookup? Eg. If the current search tree has a position once, and the "PV" of the table entry has the same position twice, the move should be scored as a draw, but isn't, because the table doesn't keep track of the history of positions.

The problem is even more pronounced if one doesn't clear the table across moves. On the other hand, clearing the table after each move doesn't sound too inviting for obvious reasons.

Thank you

[hgm]

This is an unsolved problem. Most engines try to minimize errors due to this problem by not using TT for cutting off the PV.

[cyberfish]

Thanks for your reply, but I don't quite get what you meant by "not using TT for cutting off the PV." Does that mean I don't store PV nodes in the TT? (and only alpha and beta nodes)

Thanks

[hgm]

It means that if you get a hit on a position stored in the TT that has a better depth than you need, and the stored score is an exact value between alpha and beta, you will not use that score, but search on.

You still store them, because an exact score can in another context be a cutoff (abve beta or below alpha). And of course you wil use the move as a hint for what to search frst.

[cyberfish]

That answered my question.

Thank you very much

[bob]

It means that if you get a hit on a position stored in the TT that has a better depth than you need, and the stored score is an exact value between alpha and beta, you will not use that score, but search on.

You still store them, because an exact score can in another context be a cutoff (abve beta or below alpha). And of course you wil use the move as a hint for what to search frst.

Sounds like a horrible solution to a relatively minor problem. I always use good scores, period...

[cyberfish]

Sounds like a horrible solution to a relatively minor problem. I always use good scores, period...

That is what I have always done, but my engine seems to have lost quite a few games because of just that.

[bob]

Hi,
I was wondering how is everyone dealing with the repetition draw + transposition table problem.

More specifically, how should I track repetitions "through" a table lookup? Eg. If the current search tree has a position once, and the "PV" of the table entry has the same position twice, the move should be scored as a draw, but isn't, because the table doesn't keep track of the history of positions.

The problem is even more pronounced if one doesn't clear the table across moves. On the other hand, clearing the table after each move doesn't sound too inviting for obvious reasons.

Thank you

The problem is not as serious as you would think until you get to the 50 move draw rule. First, let's take repetitions.

There are two cases:

(1) your hash says draw, but it is not a draw. This is a bug and should be fixed or it would never happen.

(2) your hash says normal score, but in reality the tree will pass through a repetition position before getting to the terminal score. How does this happen? Here's an example.

We start searching at position A below, and then reach position B and finally position C where we compute a static score and back it up. But I have inserted two extra positions R1 and R2... The path looks like this:


A-------R1-------B-------R2-------C

Clearly if you search toward C, you will pass through R1 and R2 and at R2 (a repeat of position R1) you would detect a repetition and never reach C. But suppose you search from A to B using a different sequence of moves so that you do not hit R1, and when you get to B you keep searching all the way to C. When you return to B, you store the non-draw score computed at C.

But now the real game follows a slightly different path so that you do encounter position R1. And now you start searching and when you get to position B, you retrieve the old table entry that has a score for C, but notice that it ignores the fact that now R2 would be an instant draw.

That is the problem you encounter. And it doesn't solve it to just not use draft > depth hash entries. draft == depth will do exactly the same thing give similar circumstances. The problem is our hash signatures have no path information. Including this would reduce hash hits to nearly zero. So we just put up with it as it is not very common.

The 50-move rule is a different matter entirely and you have to do something about it or you will get burned. The problem is that as you near the 50-move-draw boundary, hash entries were stored that come from positions that occur beyond the 50-move-rule limit. What I do is that once I pass move 40 on the way to 50, I start flagging hash entry scores as unusable (leaves the hash move for ordering alone, but says "don't use this score"). This solve the problem, at a loss of search efficiency caused by not using all available information from the hash table...

[cyberfish]

Thanks for the information. That is exactly what I had in mind when I asked this question.

And it doesn't solve it to just not use draft > depth hash entries. draft == depth will do exactly the same thing give similar circumstances.

I think what hgm meant is to not use any exact score between alpha and beta, regardless of the depth.

I just tried it with my engine, and, surprisingly (to me at least), that didn't slow the engine down noticeably. I am not sure if the problem is solved or at least minimized, though.

After some careful analysis of my engine's games, I don't think this is the problem anymore. It seems to me that my engine is just too slow to see the repetition (in 6 plies) before getting itself into trouble (have the queen being chased around by a rook). Of course, in that case, a draw would be preferred over losing a queen.

As for the 50-moves rule, I don't think I need to worry about that yet, as my engine is still early in its development (~2000 standard on FICS). (I am already dealing with it, just not the problem with TT).

[bob]

Sounds like a horrible solution to a relatively minor problem. I always use good scores, period...

That is what I have always done, but my engine seems to have lost quite a few games because of just that.

Then you have a bug of a different sort. The problem being discussed here is thinking you are winning, and instead you fall into a draw by repetition that was hidden from you by the hash table. The hash table leads you toward a position that is good for you, when, in fact, it passes over a position that caused a forced draw. But you won't recognize that until it is too late.


There's no way this can cause you to lose games, it is more a matter of not wanting to draw won games...