Page 1 of 2
Correcting Evaluation with the hash table
Posted: Fri Feb 05, 2010 10:05 pm
by mjlef
OK, here is the idea. Programs get scores from both board evaluations, and from searches stored in the hash table (often the hash table just has limits). I noticed that the score limit from the hash could often be used to correct the score estimate from the evaluation function..For example, if the evaluation returned say -10, but the hash table entry for this position is an upper limit and is say -20, then we can correct the current evaluation and make it -20, closer to the "truth".
How could this be useful? Well, in the qsearch, we assume (unless in check) that the side to move can stand pat and accept the current score. If this score is too high from the evaluation, then the search misses the fact that if it was forced to move, it would lose something. This should make the qsearch more immune to zugzwang situations. Also, programs often use the current evaluationin pruning decisions. Correcting the eval using the hash values should make these decisions more accurate, since they are returned fomr an actual search.
So, what do you think? Worth testing?
Mark
Re: Correcting Evaluation with the hash table
Posted: Fri Feb 05, 2010 11:39 pm
by Edsel Apostol
mjlef wrote:OK, here is the idea. Programs get scores from both board evaluations, and from searches stored in the hash table (often the hash table just has limits). I noticed that the score limit from the hash could often be used to correct the score estimate from the evaluation function..For example, if the evaluation returned say -10, but the hash table entry for this position is an upper limit and is say -20, then we can correct the current evaluation and make it -20, closer to the "truth".
How could this be useful? Well, in the qsearch, we assume (unless in check) that the side to move can stand pat and accept the current score. If this score is too high from the evaluation, then the search misses the fact that if it was forced to move, it would lose something. This should make the qsearch more immune to zugzwang situations. Also, programs often use the current evaluationin pruning decisions. Correcting the eval using the hash values should make these decisions more accurate, since they are returned fomr an actual search.
So, what do you think? Worth testing?
Mark
I'm currently doing this on the latest public TL. It seems to help but not much though. I have not tested this idea much so it would be great to have another opinion from other programmers. I also think that it might make the pruning more conservative. Please do let me know the results if you managed to test it yourself.
Re: Correcting Evaluation with the hash table
Posted: Fri Feb 05, 2010 11:52 pm
by rvida
I'm doing this in Critter. But I'm not quite happy with it. It helps a little bit, but it causes some pretty bad instabilities in search.
A typical example: A move fails high on zero window search, but the widened window re-search does not see why it failed high, because the offending hash entry was in the meantime overwritten.
Re: Correcting Evaluation with the hash table
Posted: Fri Feb 05, 2010 11:58 pm
by rvida
Maybe this is not a problem for other engines, but Critter uses fail-soft with aspiration windows. It is easy to overshot the AW, and the search with widened bounds can take forever to finish - only to discover that the exact score was well insiede the original AW.
Re: Correcting Evaluation with the hash table
Posted: Sat Feb 06, 2010 2:12 am
by BubbaTough
rvida wrote:I'm doing this in Critter. But I'm not quite happy with it. It helps a little bit, but it causes some pretty bad instabilities in search.
A typical example: A move fails high on zero window search, but the widened window re-search does not see why it failed high, because the offending hash entry was in the meantime overwritten.
This kind of thing can also happen with lazy eval too. All part of the fun.
-Sam
Re: Correcting Evaluation with the hash table
Posted: Sat Feb 06, 2010 11:12 am
by mcostalba
mjlef wrote:
So, what do you think? Worth testing?
We are currently experimenting with this. Sometime it works, sometime doesn't. With futility it seems it does not work....but we are still investigating on it.
Re: Correcting Evaluation with the hash table
Posted: Mon Feb 08, 2010 2:40 pm
by diep
mjlef wrote:OK, here is the idea. Programs get scores from both board evaluations, and from searches stored in the hash table (often the hash table just has limits). I noticed that the score limit from the hash could often be used to correct the score estimate from the evaluation function..For example, if the evaluation returned say -10, but the hash table entry for this position is an upper limit and is say -20, then we can correct the current evaluation and make it -20, closer to the "truth".
How could this be useful? Well, in the qsearch, we assume (unless in check) that the side to move can stand pat and accept the current score. If this score is too high from the evaluation, then the search misses the fact that if it was forced to move, it would lose something. This should make the qsearch more immune to zugzwang situations. Also, programs often use the current evaluationin pruning decisions. Correcting the eval using the hash values should make these decisions more accurate, since they are returned fomr an actual search.
So, what do you think? Worth testing?
Mark
If i have information from hashtable it usually gives a cutoff in qsearch.
Mind sharing rough pseudo code with us if you're not describing the usual hashtable cutoff?
If we write down things in vague conceptual words, of course things can get interpreted in a wide manner. In Amsterdam we have a lot of cafe's where there is people who are very professional in saying things in a vague manner, meanwhile smoking very BIG cigarettes.
With pseudo code that is tougher.
Thanks,
Vincent
Re: Correcting Evaluation with the hash table
Posted: Mon Feb 08, 2010 3:27 pm
by metax
diep wrote:Mind sharing rough pseudo code with us if you're not describing the usual hashtable cutoff?
If I have understood this correctly:
Code: Select all
int CorrectEvalScore(int eval, int ttValue, int ttBound)
{
if (bound == LOWERBOUND)
{
return max(eval, ttValue);
}
if (bound == UPPERBOUND)
{
return min(eval, ttValue);
}
return eval;
}
And in search, after handling usual TT cut-offs etc.:
Code: Select all
// handle TT cut-offs
eval = CorrectEvalScore(Evaluate(), ttValue, ttBound);
Re: Correcting Evaluation with the hash table
Posted: Mon Feb 08, 2010 3:43 pm
by rvida
diep wrote:
If i have information from hashtable it usually gives a cutoff in qsearch.
Mind sharing rough pseudo code with us if you're not describing the usual hashtable cutoff?
He is talking about something like this:
Code: Select all
if (hash_entry->bound == EXACT)
stand_pat = hash_entry->score;
else {
stand_pat = position->eval();
if (hash_entry->bound == LOWER_BOUND)
stand_pat = max(stand_pat, hash_entry->score);
else
if (hash_entry->bound == UPPER_BOUND)
stand_pat = min(stand_pat, hash_entry->score);
}
if (stand_pat >= beta)
return stand_pat;
this "imporved" stand pat score can be later useful in futility (delta) pruning decision too.
Re: Correcting Evaluation with the hash table
Posted: Tue Feb 09, 2010 10:03 am
by hgm
diep wrote:If i have information from hashtable it usually gives a cutoff in qsearch.
I guess the proposed scheme would only resort any effect in the QS at the end of the PV branch. There the hash bound would not produce a cutoff as the window is still open, but the current eval could be in contradiction with the score bound from a deeper search.
Rather than using the bound in that case, I would be inclined to force an extension. If it happens in so few leaf nodes, this can hardy be costly.