Repetitions/50 moves and TT

[Sergei S. Markoff]

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

At least partially -- we have. We can search TT to extract stored part of the subtree and verify it.

[Sergei S. Markoff]

It should work like enchanced transposition cutoff. In SmarThink I have ECT which looks sometimes up to 2 plies "in-depth" trying to cutoff none w/o search.

[bob]

It should work like enchanced transposition cutoff. In SmarThink I have ECT which looks sometimes up to 2 plies "in-depth" trying to cutoff none w/o search.

I've never been able to get that to work in Crafty. The cost was ALWAYS higher than the savings... It adds overhead everywhere, for very little gain if the hash table is quite large...

[Sergei S. Markoff]

I've never been able to get that to work in Crafty. The cost was ALWAYS higher than the savings... It adds overhead everywhere, for very little gain if the hash table is quite large...

I think this is only the question of the right depth to do this. Bigger depth means higher savings/cost rate. For the bigger depth I'm doing special shallow search that tries TT moves, repetitions & mate checking, trying to cut-off node.

[Don]

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?

This problem can be solved, but it's not practical. It's called the GHI problem or Graph History Interaction.

One thing that I have tried is to never store a draw score in the TT table - but that has no impact on the strength of the program (or if it does it's negative.) Another thing I have done is set a special score for the draw, such as an odd number (making all "real" scores be even numbers.)

However, this does not really prevent the problem because a score can be BASED on the possibility of a draw and not be a draw. For example you might have a nice advantage but have to accept a lower score to avoid a draw - that doesn't show up as a score you can identify.

There might be some slight benefit to how some programs deal with the hash table, in PV nodes if you do USE the hash table score you probably have less problems. Many programs do not use the hash table score in the PV nodes for various reasons.

[Don]

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?

A partial fix, but it does not avoid the problem.

[bob]

I've never been able to get that to work in Crafty. The cost was ALWAYS higher than the savings... It adds overhead everywhere, for very little gain if the hash table is quite large...

I think this is only the question of the right depth to do this. Bigger depth means higher savings/cost rate. For the bigger depth I'm doing special shallow search that tries TT moves, repetitions & mate checking, trying to cut-off node.

I think that suggestion was in the original paper that suggested the idea. I tried lots of limits, but never found something that worked better than just normal hashing/ordering. However, it is certainly sensitive to hash replacement. The idea is that if you don't get a hash hit at this ply, try each move quickly to see if you will get a hash hit the next ply. With large hash tables that reduce overwriting/replacing, I think this idea is simply flawed. The deeper you go, the less likely you are to get a hit if you just base it on probabilities considering that draft-preferred strategies try to preserve the entries closer to the root over those farther away from it... I don't hash q-search at all, further reducing the stress on the replacement strategy..

Might have made sense in the megabyte days, but in the gigabyte days? Not so convinced...

[Don]

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?

We used to have that in Komodo but no amount of testing indicates which is better. As of this moment we do not distinguish.

Years ago I used a trick that all scores that come from the evaluation is divisible by 2 (even numbers) but draw scores must always be odd. Then I would not store true draw scores.

Even though I cannot prove that not storing draws is good, I believe that is an improvement but it does not solve GHI problems. The reason is that the threat of a draw can cause the search to avoid a given line - so the draw is affecting the score without it actually being a draw.