Unfortunately that is not true. You would also have to work into the key how often every other position has been repeated. A position visited for the first time can be a draw because the only reasonable way out of it has already been visited twice, while if it hadn't, a path through a win (bungled on the previous two occasion) would lead through it.
So basically you would have to hash on complete path, rather than the position, destroying all hope of catching transpositions. This is why Bob says the cure is worse than the disease. You could easily do this, and you would never misjudge a repetition anymore,and perhaps gain 20Elo by that. But at the same time you would lose hundreds of Elo because of the decrease in search depth it causes.
a way to prevent broken PV's when using hash tables...
Moderators: hgm, Rebel, chrisw
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: a way to prevent broken PV's when using hash tables...
The change is so small you might need 200,000 games, not 200.lucasart wrote:OK I am now testing the following TT pruning:bob wrote:There is _nothing_ you can do about that. Ignoring EXACT hits doesn't help a bit, because you still trust the fail-hi/fail-lo entries and they suffer from the same problem. Failing low or high because of either an overlooked repetition, or because you see an incorrect repetition score, is just as damaging.lucasart wrote:displaying a full PV is the least of my concerns. What I was worried about is the 3 repetition problem.bob wrote:First, describe the specific problem. If it is a short PV, then you can look at what I do to hash the PATH below an exact entry so that it can be grafted onto the PV when you get an EXACT hit.lucasart wrote:I also do the the same. So how do solve the 3 move problem if you use htable pruning at PV nodes ?bob wrote:That will hurt more in endgames than you suspect. And it hurts somewhat overall, or you would never see a short PV in the first place...sluijten wrote:I noticed that the percentage of exact entries in the hash table is quite low, this technique will not break the PV: only use null-move cut-offs and beta cut-offs from the hash table. You can still store exact results, but only use them for move ordering.
If you are concerned about repetitions, and missing them because of a hit, or seeing them where you should not, you can't do a thing about it. You also get wrong hash results on non-EXACT entries. I don't see any reason to weaken an engine just to try to hide a _perceived_ problem...
This is a problem not worth worrying about. There is one well-known solution, that of not allowing matches when draft >= depth, and restrict it to draft == depth. But that is a performance-killer and will hurt more than it helps, from actual test measurements.versus my previous one, which is the same but discarding the ScoreExact case (which inevitable comes from PV nodes, and onl;y prunes when encountered at PV nodes)static inline bool can_return_tt(const TTEntry *tte, int depth, int alpha, int beta, int ply)
{
int tt_score = adjust_tt_score(tte->score, ply);
if (tte->type == ScoreExact)
// NB: if ply == 0, we don't want TT depth > depth, because of the 3 move rule
return (ply ? tte->depth >= depth : tte->depth == depth)
&& alpha < tt_score && tt_score < beta;
else
return (tte->depth >= depth
|| tt_score >= max(mate_in(MAX_PLY), beta)
|| tt_score < min(mated_in(MAX_PLY), beta))
&& ( (tte->type == ScoreLbound && tt_score >= beta)
|| (tte->type == ScoreUbound && tt_score <= alpha));
}
I'll probably need 200 games to decide, played 20 so far...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: a way to prevent broken PV's when using hash tables...
That only solves 1/2 of the problem. What if the hash entry you hit on has a path that would produce a draw if grafted on to the current path you have? You miss that as no path information is stored. What if the hash entry was influenced by a draw score that is not possible in the current path? Again, you get the wrong answer. This really isn't fixable unless you really wreck the efficiency of the hash algorithm, which will lose you much more than this fix gains, in terms of Elo.tpetzke wrote:>>displaying a full PV is the least of my concerns. What I was worried about is the 3 repetition problem.
IMO you should have a 3 fold repetition detection that doesn't rely on a hash table. Before you probe the hash table you check for a repeated position (1 repetition is enough) and just return a draw or contempt score if it is repeated.
In such a case the hash table isn't probed at all and whatever is stored there doesn't interfere with the DRAWish evaluation of that node in the current path.
Thomas...
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: a way to prevent broken PV's when using hash tables...
Hmm, I don't think I can follow you with that yet
If I have a position A and a principle variation of moves that lead to position A again, something like
A - B - C - D - A
the 2nd encounter of A is scored as DRAW, the score of position D is influenced by the DRAW evaluation of one of its children.
Now in another part of the tree I have the positions
F - G - H - D
D is found in the hash table and the score (with the DRAW influence) is used, although the child A is not a repeated position so far.
Problem ? I think not, because
we know from A the losing side can reach A again (because of that we could already score the 2nd repetition of A as DRAW), so it is Ok using the score from the hash table for position D even we did not see a repetition of A yet, we will see one if we just search deep enough.
Or did you think of another problem I haven't even spotted yet ?
Thanks
Thomas...
I might get a different answer using the hash entry score than I would get from search, but if so I think the hash entry score is the more correct oneWhat if the hash entry you hit on has a path that would produce a draw if grafted on to the current path you have? You miss that as no path information is stored. What if the hash entry was influenced by a draw score that is not possible in the current path? Again, you get the wrong answer.
If I have a position A and a principle variation of moves that lead to position A again, something like
A - B - C - D - A
the 2nd encounter of A is scored as DRAW, the score of position D is influenced by the DRAW evaluation of one of its children.
Now in another part of the tree I have the positions
F - G - H - D
D is found in the hash table and the score (with the DRAW influence) is used, although the child A is not a repeated position so far.
Problem ? I think not, because
we know from A the losing side can reach A again (because of that we could already score the 2nd repetition of A as DRAW), so it is Ok using the score from the hash table for position D even we did not see a repetition of A yet, we will see one if we just search deep enough.
Or did you think of another problem I haven't even spotted yet ?
Thanks
Thomas...