Cache over-writing and PV's

[hgm]

You might be right, but maybe there is more to it. The reason for avoiding hash cuts altogether is to avoid PV clipping and to improve search stability. [/qoute]
Well, taking a cutoff on an out-0f-window score would certainly not cut the PV, so that is not a reason to do it.

But how common are hash cuts in PV nodes anyway?

In end-games I see very deep grafted mates quite often. So it cannot be that uncommon.

Furthermore, I object to the logic: "lets's make an absolute mess of this case, because it doesn't occur often enough that it will hurt us".

[syzygy]

But how common are hash cuts in PV nodes anyway?

In end-games I see very deep grafted mates quite often. So it cannot be that uncommon.

Yes, in end games anything can happen.

Furthermore, I object to the logic: "lets's make an absolute mess of this case, because it doesn't occur often enough that it will hurt us".

In the end it will simply have to be tested to see if it helps or hurts for a particular engine with a particular set of PV/non-PV dependent extensions and reductions. Not really possible to resolve this question by logic imho.

[hgm]

If it would help, it means something else must be badly wrong, and you are trying to compensate error with error. That doesn't seem like a good development strategy to me.

For one, the TT out-of-window score could already have been obtained as a PV search with exactly the same extensions as needed now (i.e. you could find an out-of-window exact score in the TT). And if a 'sufficient-draft' TT hit would not be sufficient draft for PV search, there obviously is something badly amiss with our depth accounting. Which would only be partly cured by this hack.

[Zenmastur]

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time. Example 2 requires 288 units of time and example three requires 272 units of time. Example 2 gets its search horizon extended by two plies and example 3 gets its search horizon extended 4 plies. Both use considerably less time than an 11-ply search (1024 units of time) or a 13-ply search (4096 units of time). Neither is as good as their more traditional counter parts of the same length but they are much better than a straight 9-ply search.

I am not quite sure I follow. Example 1 goes 8 ply deep. 2^8 = 256 so we agree there. But example 2 goes 2 plies deeper. By my calculations, that turns into 1024 units of time, not the 288 you mentioned, so perhaps I don't quite follow what you mean with the consecutive same depths (if that is what those numbers represent).

Ahh, you must be thinking that this type of search extension is applied to the whole tree. It's not. Just to the PV or a line that is a perspective PV by virtue of its current score.

The point of performing a search like this is to provide more distance (plies) between the root node and the leaf node of a PV. The reason for the extra plies is to provided additional decision levels between the root and leaf node of the PV so that should the leaf node score be inaccurate due to eval() being unreliable it is less likely to propagate all the way back to the root. Therefore the root score of the PV is more reliable.

Normally additional reliability can only be had by allowing the search to reach much greater depths. This is very time consuming. Since you can't play a move across the board unless its the root move of the PV there is no reason to extend non-PV branches. So the first point is that this type of extension doesn't get applied to every branch of the tree. Just to those that are subject to get promoted to the PV. Before a line of play becomes part of the PV it has to be extended. The portion that lies at or beyond the first extended ply must be searched again with the proper extensions. The score for the extended branch is compared to the extended score of the current PV. If its better, then the current PV can be replaced. If not its rejected and the search continues as normal. If the score for the new extended PV is better than the score for the un-extended version, you shouldn't over write the original score. Instead store it with the PV as an extended score. If you try to uses the extended PV's score there will be problems. E.G. if the program is in a won position the scores will be monotonically increasing. Since the PV is significantly extended compared to the other lines of play its score will likely be higher than any non-extend score. Under these conditions the program may miss better lines of play due to the score advantage the extensions will provide to the extended PV. Therefore both the non-extended and extended score must be saved with the PV. The non-extended score is used to compare to all other lines of play. Any line of play that passes this test gets extended and the extended score get compared to the extended score for the current PV.

I don't know if this explanation is explicit enough to understand.

Now since we are dealing with single lines of play, like the PV or some line that might become the PV it should be a little easier to understand how I got my results.

Example 1 is a single 9 ply search = 256 time units. Example 2 is a single 9-ply search plus two addition 5-ply searches inserted at position 4 and 3 of a nine ply search = 256 + 2 * 16 = 288 time units. Example 3 is a 9-ply search plus 4 additional 3-ply searches inserted at positions 2, 1, 0, and -1 of the 9-ply search = 256 + 4 * 4 = 272 time units.

Regards,

Forrest.

[xmas79]

..The non-clipped part is correct. The clipped part is clipped, so you obviously don't see it. Does not make the clipped part incorrect. ...

SF is no different from other engines in how it searches the leftmost branch of the tree: TT probe to avoid generating moves etc.. etc... How can a (badly) clipped PV retrieved from TT not influence move ordering at ply in which clipping occurs?

Am I saying anywhere that it does not?

You actually didn't say, but it also seemed to me that in your opinion the truncated PV was fine... What do you mean then with "Does not make the clipped part incorrect"?

Indeed I did not say it, so I really wonder why you quoted that specific part of what I did write and did (apparently not) respond to it. Whether what SF is doing is fine or not I will leave for you to decide. Again, feel free to improve it in terms of Elo (as you were worrying about clipping affecting its strength).

What I mean by not incorrect I have explained. In any event I only see one possible reasonable explanation for what it means for a (clipped) PV to be "correct".

Whether what SF is doing is good or bad is up to the users, and the users (like the OP, not certainly me) are complaining about its behaviour. I quoted your text because you say something that I don't understand. You explicitly wrote:

The non-clipped part is correct. The clipped part is clipped, so you obviously don't see it. Does not make the clipped part incorrect

Now, can I ask you why do you think that something invisible is correct/not correct? From my understanding this is what you said:

Code: Select all

+------------------------- Real PV -------------------------------------+
|                              |                                        |
| e2e4 e7e5 g1f3 g8f6 d2d4 d7d5|aaaa bbbb cccc dddd eeee ffff gggg hhhh |  
|                              |                                        |
+--------Non clipped part------+----------Clipped part------------------+

aaaa bbbb etc... can be anything and you can't see it. And you clearly stated that "The non-clipped part is correct. The clipped part is clipped, so you obviously don't see it. Does not make the clipped part incorrect." Why?

And one last thing: even if your comment "If you already know things why ask?" was removed, the reason I ask is because I (unlike you Mr.GodOfChessProgrammers) think that I can be wrong. I'm here to learn something, and I know since your first post I will never learn anything from YOU.

[bob]

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time. Example 2 requires 288 units of time and example three requires 272 units of time. Example 2 gets its search horizon extended by two plies and example 3 gets its search horizon extended 4 plies. Both use considerably less time than an 11-ply search (1024 units of time) or a 13-ply search (4096 units of time). Neither is as good as their more traditional counter parts of the same length but they are much better than a straight 9-ply search.

I am not quite sure I follow. Example 1 goes 8 ply deep. 2^8 = 256 so we agree there. But example 2 goes 2 plies deeper. By my calculations, that turns into 1024 units of time, not the 288 you mentioned, so perhaps I don't quite follow what you mean with the consecutive same depths (if that is what those numbers represent).

Ahh, you must be thinking that this type of search extension is applied to the whole tree. It's not. Just to the PV or a line that is a perspective PV by virtue of its current score.

The point of performing a search like this is to provide more distance (plies) between the root node and the leaf node of a PV. The reason for the extra plies is to provided additional decision levels between the root and leaf node of the PV so that should the leaf node score be inaccurate due to eval() being unreliable it is less likely to propagate all the way back to the root. Therefore the root score of the PV is more reliable.

Normally additional reliability can only be had by allowing the search to reach much greater depths. This is very time consuming. Since you can't play a move across the board unless its the root move of the PV there is no reason to extend non-PV branches. So the first point is that this type of extension doesn't get applied to every branch of the tree. Just to those that are subject to get promoted to the PV. Before a line of play becomes part of the PV it has to be extended. The portion that lies at or beyond the first extended ply must be searched again with the proper extensions. The score for the extended branch is compared to the extended score of the current PV. If its better, then the current PV can be replaced. If not its rejected and the search continues as normal. If the score for the new extended PV is better than the score for the un-extended version, you shouldn't over write the original score. Instead store it with the PV as an extended score. If you try to uses the extended PV's score there will be problems. E.G. if the program is in a won position the scores will be monotonically increasing. Since the PV is significantly extended compared to the other lines of play its score will likely be higher than any non-extend score. Under these conditions the program may miss better lines of play due to the score advantage the extensions will provide to the extended PV. Therefore both the non-extended and extended score must be saved with the PV. The non-extended score is used to compare to all other lines of play. Any line of play that passes this test gets extended and the extended score get compared to the extended score for the current PV.

I don't know if this explanation is explicit enough to understand.

Now since we are dealing with single lines of play, like the PV or some line that might become the PV it should be a little easier to understand how I got my results.

Example 1 is a single 9 ply search = 256 time units. Example 2 is a single 9-ply search plus two addition 5-ply searches inserted at position 4 and 3 of a nine ply search = 256 + 2 * 16 = 288 time units. Example 3 is a 9-ply search plus 4 additional 3-ply searches inserted at positions 2, 1, 0, and -1 of the 9-ply search = 256 + 4 * 4 = 272 time units.

Regards,

Forrest.

I think this is more of a vocabulary issue than anything. For example, in my code I don't apply an extension to a ply. I extend selected moves. So that some branches go to depth N, others go to depth N+1, for that specific ply. Seeing an extension on successive plies can happen easily enough, which means that in a "dump the tree" trace, one would see exactly what you gave on one path, but possibly not on a different one.

At least now we seem to be talking the same language and you were just adding in the overhead for extending only along one specific branch, by calculating the increased size in just the sub-tree below the node where you extended.

Makes sense now that I understand what you were talking about.

[bob]

You might be right, but maybe there is more to it. The reason for avoiding hash cuts altogether is to avoid PV clipping and to improve search stability. [/qoute]
Well, taking a cutoff on an out-0f-window score would certainly not cut the PV, so that is not a reason to do it.

But how common are hash cuts in PV nodes anyway?

In end-games I see very deep grafted mates quite often. So it cannot be that uncommon.

Furthermore, I object to the logic: "lets's make an absolute mess of this case, because it doesn't occur often enough that it will hurt us".

It doesn't just happen in endgames either. I have seen <HT> PVs from Crafty since forever. I have seen cases where you can play the sequence A,B,C,D and go further beyond that point, then come back and search C,D,A,B and discover that is better, because playing C first forces your opponent more and gives him fewer good replies than playing A first. In either case, you still end up at the same position and with EXACT matches, you get a 4-move PV with that dreaded <HT> on the end. I agree that I have seen it more frequently in deep endgames, but it can happen anywhere. I don't see 'em any more, obviously...

But the idea of ignoring a perfectly good hash hit to provide a more complete PV just seems wrong, particularly when there is a simple solution to the problem available. This hash grafting is the reason most programs solve Fine #70 without having to search 26 plies, which is how deep you have to go before the pawn is captured at ply=27. Grafting lets programs see that far earlier.

[bob]

But how common are hash cuts in PV nodes anyway?

In end-games I see very deep grafted mates quite often. So it cannot be that uncommon.

Yes, in end games anything can happen.

Furthermore, I object to the logic: "lets's make an absolute mess of this case, because it doesn't occur often enough that it will hurt us".

In the end it will simply have to be tested to see if it helps or hurts for a particular engine with a particular set of PV/non-PV dependent extensions and reductions. Not really possible to resolve this question by logic imho.

Why would that be? Under what circumstances would it be better to ignore an existing result that can be used with zero time penalty, and replace that by an actual search that takes more than zero time? Logic is quite good enough here to see that disallowing EXACT hash hits on the PV is simply wrong.

[syzygy]

My claim, which is based solely on what I have witnessed it do time and time again, is that when it starts clipping the PV it's going to change.

OK, what you are looking at are probably not the "real PVs" output by SF, but the fail-low and fail-high PVs that SF outputs as well. I don't know if there are GUIs that filter those out, but yours probably does not.

When SF is playing, it usually finishes its iteration and displays a normal PV. Those should be accurate, clipped or not.

When you take the PV displayed at a random point in time, SF might be busy switching from one move to another, or simply realising the position is much better, or much worse, than indicated by the previous iteration. While it is doing this there is no real score available, but only an upper bound or lower bound.

Say SF is playing white and the score is a lower bound. That means the "real score" is at least the lower bound and white might have (much) better moves than displayed in the PV (still white's moves should lead to at least the lower bound score). Similarly, if the score is an upper bound, black's moves might be suboptimal (but still lead to a position better for black than in the previous PV). In either case the PVs shown should not be disastrously flawed, but they might need some interpretation.

It's likely true that these PVs are more often severely clipped than normal PVs.

The solution is probably to somehow ignore the upper bound / lower bound PVs. This is easy if you use SF from the command line, as it prints "upperbound" and "lowerbound", but might be harder when using a GUI. But of course the fact that SF is busy discovering new things (another best move, or the fact that the position is better or worse than it thought) means that the last "real PV" is already outdated, so likely not "reliable" in your view.

Other programs also have fail lows and fail highs, and they also very often take a long time to resolve. They might not be generating these PVs but simply show the new best move.

Rely on them for what?

To make your next move among other things.

So just look at the best move as shown by the engine. What you see is the best move it has determined thus far.

There is nothing inherent in the alpha-beta process that prescribes that each ply deeper into the search must be searched to a depth one ply less than the last. i.e. like this:

Example 1:
9-8-7-6-5-4-3-2-1

There is no reason that something like this couldn't be done:

Example 2:
9-8-7-6-5-5-5-4-3-2-1

or this

Example 3:
9-8-7-6-5-4-3-3-3-3-3-2-1

Those are called extensions. SF has them, but most of the time it is reducing rather than extending. This is an integral part of SF's search, so it can't be changed without making it a completely different engine. Same for all other engines.

Without major reductions an engine won't have a branching factor below 2, but a branching factor of about 5 or so. Add in extensions that are not strictly controlled and the search will never end at all.

There are advantages to the alternatives. One is time usage. e.g. if a 1 ply search requires one unit of time and each addition ply of depth doubles the search time then example 1 requires 256 units of time.

Example 1 will require 5^8 units.

Example 2 requires 288 units of time and example three requires 272 units of time.

It's not clear to me how you are arriving at these numbers.

In case you want to extend only in the PV (based on certain conditions, e.g. recaptures), then that's also something that many engines do or at least have tried. None of this solves the (what you perceive as a) problem that any PV gets less reliable as you walk down the PV, simply because it was searched with less and less depth. (Obvious exception is PVs leading to mate, it seems I have to add such things...)

So what you are saying is that the 09042014 compile has this issue and If I get a newer version the PV's will always lead to the node that produced the score displayed even if the PV has been clipped. Is that correct?

Yes, compiles from April have this problem. They don't always clip where they should. It is fixed in SF5.

I don't know where you got it from and where it says "09042014", but when I start stockfish:

Code: Select all

$ stockfish
Stockfish 181014 64 SSE4.2 by Tord Romstad, Marco Costalba and Joona Kiiski

This is from 18 October 2014.

[syzygy]

And if a 'sufficient-draft' TT hit would not be sufficient draft for PV search, there obviously is something badly amiss with our depth accounting.

Is that so?

What if an engine never reduces in the PV. Then a 10-ply search starting in a PV node is likely more reliable than a 10-ply search starting in a non-PV node.

Maybe you'll say that something is badly amiss with such an engine, but if it turns out to help playing strength not many people will care.

In such an engine, relying on a 10-ply non-PV bound retrieved from hash in a PV node that is to be searched to 10 ply will introduce an error compared to not taking the cut. (Of course it is not unlikely that accepting this error will actually improve the engine even further.)