At least partially -- we have. We can search TT to extract stored part of the subtree and verify it.bob wrote:How can you do that? When you get a hash hit, you don't have the path that was searched to store the position...
Repetitions/50 moves and TT
Moderators: hgm, Rebel, chrisw
-
- Posts: 227
- Joined: Mon Sep 12, 2011 11:27 pm
- Location: Moscow, Russia
Re: Repetitions/50 moves and TT
The Force Be With You!
-
- Posts: 227
- Joined: Mon Sep 12, 2011 11:27 pm
- Location: Moscow, Russia
Re: Repetitions/50 moves and TT
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.
The Force Be With You!
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Repetitions/50 moves and TT
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 wrote: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.
-
- Posts: 227
- Joined: Mon Sep 12, 2011 11:27 pm
- Location: Moscow, Russia
Re: Repetitions/50 moves and TT
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.bob wrote: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...
The Force Be With You!
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Repetitions/50 moves and TT
This problem can be solved, but it's not practical. It's called the GHI problem or Graph History Interaction.Sergei S. Markoff wrote: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?
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.
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Repetitions/50 moves and TT
A partial fix, but it does not avoid the problem.JuLieN wrote: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?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Repetitions/50 moves and TT
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..Sergei S. Markoff wrote: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.bob wrote: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...
Might have made sense in the megabyte days, but in the gigabyte days? Not so convinced...
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Repetitions/50 moves and 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.JuLieN wrote: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?
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.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.