Win scores in the TT causing problems

[gschmidt]

Hi,

I'm new to this group so please be easy on me .

I'm hoping someone can suggest a good approach to the following problem:

Background:
My program uses iterative deepening and a transposition table (TT). I do not clear out the TT after each search, I reuse the results from past searches.

Also, when the best score returned from an iteration of a search is a Win/Loss/Draw, that search immediately terminates. This allows me to:
1) Avoid searching deeper when the outcome is known thus allowing the program to "not look stupid" and make an immediate move.
2) Allows me to set the time control to "infinite" and have the search terminate when it has performed an exhaustive search.
It's my understanding that the "all paths lead to W/L/D" case is typically handled this way.

Problem:
The above combination can result in a search which returns incorrect win/loss scores. For example, let's say that search N finds a win in 10. Search N+1 may now find a deeper transposition of the win in 10 in the TT at say depth = 2 when the iteration of the search is at depth 2. Since the ply is at 2 when we pull the win in 10 out of the TT, this will look like a win in 12. This can look like the best move, because all other competing nodes are not in the TT and thus their scores are eval'd and so look bad in comparision to the win score (even though we know that deeper searches will indicate otherwise). Since the search returns a win score, we stop iterating to be "smart". But we have returned a bad score which overestimates the number of moves to win.

I'm curious if anyone else has had to deal with this problem. If so, how did you deal with it?. One way is to clear out all W/L/D scores in the TT after each search, but that seems a bit severe to me. On the other hand, I don't currently have any better ideas.

I hope my description is clear. Thanks.
-- Greg

[MattieShoes]

Hi,

I'm new to this group so please be easy on me .

I'm hoping someone can suggest a good approach to the following problem:

Background:
My program uses iterative deepening and a transposition table (TT). I do not clear out the TT after each search, I reuse the results from past searches.

Also, when the best score returned from an iteration of a search is a Win/Loss/Draw, that search immediately terminates. This allows me to:
1) Avoid searching deeper when the outcome is known thus allowing the program to "not look stupid" and make an immediate move.
2) Allows me to set the time control to "infinite" and have the search terminate when it has performed an exhaustive search.
It's my understanding that the "all paths lead to W/L/D" case is typically handled this way.

Problem:
The above combination can result in a search which returns incorrect win/loss scores. For example, let's say that search N finds a win in 10. Search N+1 may now find a deeper transposition of the win in 10 in the TT at say depth = 2 when the iteration of the search is at depth 2. Since the ply is at 2 when we pull the win in 10 out of the TT, this will look like a win in 12. This can look like the best move, because all other competing nodes are not in the TT and thus their scores are eval'd and so look bad in comparision to the win score (even though we know that deeper searches will indicate otherwise). Since the search returns a win score, we stop iterating to be "smart". But we have returned a bad score which overestimates the number of moves to win.

I'm curious if anyone else has had to deal with this problem. If so, how did you deal with it?. One way is to clear out all W/L/D scores in the TT after each search, but that seems a bit severe to me. On the other hand, I don't currently have any better ideas.

I hope my description is clear. Thanks.
-- Greg

The easiest solution is to not allow hash cutoffs on win/loss/draw scores and sidestep the whole issue. The best move from hash will cause it to quickly find mate. Draws are often wrong due to transpositions.

The better solution would be to convert mate in X scores to be correct before you store them in the hash, then un-convert them when you pull them from the hash. So if at ply 5 you get a value for mate-in-7 (half-moves), that means you store mate-in-2 in the hash. When you revisit that node, you retrieve mate-in-2 and add it to how many ply you're currently at to convert it back to mate in 7. That way after your move and opponent's move when you visit the node at ply 3 instead of 5, you'll get mate-in-5 instead of mate-in-7.

[jwes]

Hi,

I'm new to this group so please be easy on me .

I'm hoping someone can suggest a good approach to the following problem:

Background:
My program uses iterative deepening and a transposition table (TT). I do not clear out the TT after each search, I reuse the results from past searches.

Also, when the best score returned from an iteration of a search is a Win/Loss/Draw, that search immediately terminates. This allows me to:
1) Avoid searching deeper when the outcome is known thus allowing the program to "not look stupid" and make an immediate move.
2) Allows me to set the time control to "infinite" and have the search terminate when it has performed an exhaustive search.
It's my understanding that the "all paths lead to W/L/D" case is typically handled this way.

Problem:
The above combination can result in a search which returns incorrect win/loss scores. For example, let's say that search N finds a win in 10. Search N+1 may now find a deeper transposition of the win in 10 in the TT at say depth = 2 when the iteration of the search is at depth 2. Since the ply is at 2 when we pull the win in 10 out of the TT, this will look like a win in 12. This can look like the best move, because all other competing nodes are not in the TT and thus their scores are eval'd and so look bad in comparision to the win score (even though we know that deeper searches will indicate otherwise). Since the search returns a win score, we stop iterating to be "smart". But we have returned a bad score which overestimates the number of moves to win.

I'm curious if anyone else has had to deal with this problem. If so, how did you deal with it?. One way is to clear out all W/L/D scores in the TT after each search, but that seems a bit severe to me. On the other hand, I don't currently have any better ideas.

I hope my description is clear. Thanks.
-- Greg

Two things. First, don't terminate on losses and draws until you know that all moves are losses or draws. Second, don't terminate on wins until you have searched deeply enough to know there are no shorter wins.

[zamar]

Second, don't terminate on wins until you have searched deeply enough to know there are no shorter wins.

And if you are worried that this affects negatively on your program's performance, the solution is to use aspiration window.

[gschmidt]

Matt wrote:
"The better solution would be to convert mate in X scores to be correct before you store them in the hash, then un-convert them when you pull them from the hash. So if at ply 5 you get a value for mate-in-7 (half-moves), that means you store mate-in-2 in the hash"

Matt - I am already doing that, I wrote:
"Since the ply is at 2 when we pull the win in 10 out of the TT, this will look like a win in 12"

The surprise to me is that one can have a "correct" implementation here and still have problems due to iterative deepening and the TT interacting in non-obvious ways. What happens is that at shallow iterations, one can stumble upon a non-optimal win score and all competing branches are not in the TT and thus pruned due to an eval which is much lower than a win score. A more intelligent replacement scheme beyond my simple minded "always overwrite" would likely help, but still I wouldn't rely on that solely for search correctness.

J. Wesley wrote:
"Second, don't terminate on wins until you have searched deeply enough to know there are no shorter wins."

It's unclear to me how one would know when to terminate as how does one know that there are no shorter wins. Here's an idea, terminate early if you find a win that's shorter than the win found in the previous search - does that seem reasonable?

Me again:
As suggested, one thing I suppose I should do is to terminate when all top level nodes are true leaf positions (i.e. return W/L, or D). Since I have distinct code for the root level search, that shouldn't be too hard.

Thanks for the ideas.
-- Greg

[zamar]

The surprise to me is that one can have a "correct" implementation here and still have problems due to iterative deepening and the TT interacting in non-obvious ways. What happens is that at shallow iterations, one can stumble upon a non-optimal win score and all competing branches are not in the TT and thus pruned due to an eval which is much lower than a win score.

If I understand correctly what you mean the usual way to solve this is not to use transposition table scores in assumed PV. This is usually bad idea anyway since we cannot check for repetition or fifty move rules.

J. Wesley wrote:
"Second, don't terminate on wins until you have searched deeply enough to know there are no shorter wins."

It's unclear to me how one would know when to terminate as how does one know that there are no shorter wins. Here's an idea, terminate early if you find a win that's shorter than the win found in the previous search - does that seem reasonable?

I guess there are two approaches to this:

* You could terminate when for example two or three iterations in row return a mate score. If your search tree is not highly imbalanced, it's quite likely that you have already found the shortest mate.

* Another way (AFAIK Rybka does like this) is not even try to find a shortest win. If last move we had mate in 12, now don't stop until we find at least mate in 10.

[gschmidt]

If I understand correctly what you mean the usual way to solve this is not to use transposition table scores in assumed PV. This is usually bad idea anyway since we cannot check for repetition or fifty move rules.

I don't know what the usual way to solve this is, but I think I mislead myself into naively thinking that relying on "correct" TT information should never lead to a problem. I neglected to consider the effects of terminating from shallow searches when a win score is returned.

* Another way (AFAIK Rybka does like this) is not even try to find a shortest win. If last move we had mate in 12, now don't stop until we find at least mate in 10.

I think that's what I meant when I wrote the following:

Here's an idea, terminate early if you find a win that's shorter than the win found in the previous search - does that seem reasonable?

It's good to know that this is done in practice.

-- Greg

[bob]

Hi,

I'm new to this group so please be easy on me .

I'm hoping someone can suggest a good approach to the following problem:

Background:
My program uses iterative deepening and a transposition table (TT). I do not clear out the TT after each search, I reuse the results from past searches.

Also, when the best score returned from an iteration of a search is a Win/Loss/Draw, that search immediately terminates. This allows me to:
1) Avoid searching deeper when the outcome is known thus allowing the program to "not look stupid" and make an immediate move.
2) Allows me to set the time control to "infinite" and have the search terminate when it has performed an exhaustive search.
It's my understanding that the "all paths lead to W/L/D" case is typically handled this way.

Problem:
The above combination can result in a search which returns incorrect win/loss scores. For example, let's say that search N finds a win in 10. Search N+1 may now find a deeper transposition of the win in 10 in the TT at say depth = 2 when the iteration of the search is at depth 2. Since the ply is at 2 when we pull the win in 10 out of the TT, this will look like a win in 12. This can look like the best move, because all other competing nodes are not in the TT and thus their scores are eval'd and so look bad in comparision to the win score (even though we know that deeper searches will indicate otherwise). Since the search returns a win score, we stop iterating to be "smart". But we have returned a bad score which overestimates the number of moves to win.

I'm curious if anyone else has had to deal with this problem. If so, how did you deal with it?. One way is to clear out all W/L/D scores in the TT after each search, but that seems a bit severe to me. On the other hand, I don't currently have any better ideas.

I hope my description is clear. Thanks.
-- Greg

There are a ton of reasons why you can get the wrong mate score.

The most common is caused by search extensions. In a mate where the first two moves are quiet, for the shortest mate, you may well find some much deeper path that is full of checks and which still leads to mate, only one that is deeper than the shortest available one. This is a result of check extensions. The general solution is that if you find a mate in N, that you search to iteration 2*N-1 before you stop. This way if there is any shorter mate, you will be guaranteed to find it. Whether you want to go to this trouble or not is a different issue.

Another approach is to simply stop when you find the first mate, and make the move. But on the next move, you must search until you find a mate in N-1 so that you "make progress" rather than checking yourself into a repetition.

Note that I am assuming that you are correcting the mate scores before you store them so that they represent "mate in N moves from this ply" rather than "mate in X from the root ply". You also have to "uncorrect" them when you do a probe and get a hit.

[bob]

Matt wrote:
"The better solution would be to convert mate in X scores to be correct before you store them in the hash, then un-convert them when you pull them from the hash. So if at ply 5 you get a value for mate-in-7 (half-moves), that means you store mate-in-2 in the hash"

Matt - I am already doing that, I wrote:
"Since the ply is at 2 when we pull the win in 10 out of the TT, this will look like a win in 12"

The surprise to me is that one can have a "correct" implementation here and still have problems due to iterative deepening and the TT interacting in non-obvious ways. What happens is that at shallow iterations, one can stumble upon a non-optimal win score and all competing branches are not in the TT and thus pruned due to an eval which is much lower than a win score. A more intelligent replacement scheme beyond my simple minded "always overwrite" would likely help, but still I wouldn't rely on that solely for search correctness.

J. Wesley wrote:
"Second, don't terminate on wins until you have searched deeply enough to know there are no shorter wins."

It's unclear to me how one would know when to terminate as how does one know that there are no shorter wins. Here's an idea, terminate early if you find a win that's shorter than the win found in the previous search - does that seem reasonable?

Me again:
As suggested, one thing I suppose I should do is to terminate when all top level nodes are true leaf positions (i.e. return W/L, or D). Since I have distinct code for the root level search, that shouldn't be too hard.

Thanks for the ideas.
-- Greg

The "when to terminate" is easy. If you find a mate in N, and you keep searching until you complete iteration 2N-1, there can't possibly be a shorter mate. I prefer my other solution as it is pointless to keep searching after you find a mate, just in the hope that you can find a shorter one.

[Sven]

The "when to terminate" is easy. If you find a mate in N, and you keep searching until you complete iteration 2N-1, there can't possibly be a shorter mate.

In my search I define a "minimum possible value" (minValue) and a "maximum possible value" (maxValue) for the root node based on this rule at the very beginning of each new iteration, like this:

Code: Select all

// 'it' := number of current iteration, starting at 1
minValue = -(MATE_VALUE - 2 * ((it + 1) / 2));
maxValue =   MATE_VALUE - 2 * it / 2 - 1;
if (hasOnlyBareKing(side))     maxValue = min(maxValue, 0);
if (hasOnlyBareKing(opponent)) minValue = max(minValue, 0);

I stop the search if the best value [EDIT: at the end of an iteration] is either maxValue (in case of a mate that's the 2N-1 rule in fact), or minValue and negative. Since shorter mates than given by minValue are already excluded I can safely stop if all of my moves lead to minValue; I will not be able to improve on that by a deeper search.

minValue and maxValue are also used as limiting borders for the aspiration window (and this closely cooperates with stopping the search as shown above). Here minValue tells me that when I am starting iteration 'it', there was no mate in either (it-1) or (it-2) plies [depending on 'it' being odd or even] found against me, so now the worst case is either mate in (it+1) or (it) plies. Similar things are done for maxValue. Using maxValue as beta sometimes helps my engine to find a mate slightly faster, and I have not found any negative impact of doing it this way.

I do quite the same at each full search node, too, only I additionally take into account the current search depth, which helps to do quick qutoffs frequently as soon as some mate has been found before and incorporated into alpha.

I prefer my other solution as it is pointless to keep searching after you find a mate, just in the hope that you can find a shorter one.

I think that very strong engines should also be strong in playing the shortest mate *if there is enough time left on the clock*. It may be right to say that this does not improve an engine's Elo but I'm pretty sure it satisfies a couple of users, and on the other hand it does not hurt anyone, provided search time is sufficient for that. And it's simple to implement, so why should it be pointless to look for a mate in 5 or 6 when a mate in 7 has been found during iteration no. 8, where we only know that there is no mate in 4?

Sven