Fail-High / Fail-Low in mate situations...

[xmas79]

but it cannot take any kind of cut in PV nodes, as the score required is EXACT

Is that true? In my book, whenever I get a hash hit with a TT entry of type "lower bound" and the value I retrieve is >= beta then I can do a cutoff, even in PV nodes.

Any other opinions?

Sven

Hi Sven,
I was talking about the research, where you have a window of (alpha,+INF), where no beta cutoffs can occur. The only way to have a cut off is then an EXACT score, as getting a score < alpha really means you are NOT in a PV node, or that you could be on a PV node but have wrong a alpha value.
You can easily have cut-offs with exact/lower/upper bounds all the tree around, where you search 1+2+3+4+...+depth PV nodes and 1 bzillion of non PV nodes. In non-PV nodes you can take "always" a cut-off since your window is (alpha, alpha+1), and score can easily go above or below alpha or alpha+1. In PV nodes, when you have a window of (alpha,beta) it's also easy to get a cut off with exact/lower/upper bounds too, but failing high/low means something wrong with your bounds. Fail-high in this situations are typical of mate scores, and when you fail high because you got a mate score back, the window in now (alpha,+INF), so you can no more fail high and to have a TT cut you must hit an exact score (which will be inside the window).

These discussions are really interesting, but now I'm still under pressure at work, so I'll rest for a moment, I'll read all posts again in a few days.

Natale.


ps

The PV is only truncated when a PV node find an EXACT hash hit outside of the alpha beta bounds and with a great or equal depth. So as the search progresses the depth increases and eventually those EXACT matches don't cause a cut-off and the engine has to search for itself.

PV is truncated whenever you cannot retrieve a complete PV after hash hit, and this happens when you have an EXACT hash hit and do a cut-off (always for a fail-soft framework, with the score inside the window for fail-hard). If you fail-high at root you do NOT have a PV, you only have a best move in the root position. And inside your TT there is nothing that you can predict, as you don't know in advance which slots were replaced. The research, then, is not guaranteed to find the mate, as it hopefully can follow the moves that lead to the mate, but following is not enough. If the mate is behind the horizon then you CANNOT see it because you don't have a hash hit that says "hey, that's a mate in at most 7 plies from here" because your window is now (alpha,+INF) and the score +INF-7 is inside the bounds, so no cut off will occur. No cut-off means no backup of fail-high information to the root. And that means no mate report.

So by definition I would say:
- when you get a SCORE_IS_AT_LEAST score you are on a CUT node
- when you get a SCORE_IS_AT_MOST score you are on a ALL node
- when you get a SCORE_IS_EXACT score you are on a PV node.
- when you do not get a hash hit you must discover yourself with search.

The draft thing you say won't work because at next iteration you will have no sufficient draft to trigger a hash hit, so you CANNOT have a TT cut at PV nodes, you can only have a hash hit on nodes that have been searched completely, which were then stored as an EXACT entry, and that were of course part of a PV, and a hash hit on one of these nodes will produce a truncated PV *if* you are not able to search *COMPLETELY* its subtree (or retrieve the PV, that is the same thing). That cut-off has then nothing to do with a fail-high then fail-low behaviour.
I hope I made it clear.
Now I must stop!

[hgm]

In PV nodes, when you have a window of (alpha,beta) it's also easy to get a cut off with exact/lower/upper bounds too, but failing high/low means something wrong with your bounds.

Not really. It just means that it is not a PV node after all.

Fail-high in this situations are typical of mate scores, and when you fail high because you got a mate score back, the window in now (alpha,+INF), so you can no more fail high and to have a TT cut you must hit an exact score (which will be inside the window).

I only do a re-search when the score is between alpha and the original beta of the PV node (which needs not be +INF). And then I open the window to (alpha, original beta). When it fails high above the original beta I take the cutoff immediately. I thought this was the standard implementation of PVS.

PV is truncated whenever you cannot retrieve a complete PV after hash hit, and this happens when you have an EXACT hash hit and do a cut-off (always for a fail-soft framework, with the score inside the window for fail-hard). If you fail-high at root you do NOT have a PV, you only have a best move in the root position. And inside your TT there is nothing that you can predict, as you don't know in advance which slots were replaced. The research, then, is not guaranteed to find the mate, as it hopefully can follow the moves that lead to the mate, but following is not enough. If the mate is behind the horizon then you CANNOT see it because you don't have a hash hit that says "hey, that's a mate in at most 7 plies from here" because your window is now (alpha,+INF) and the score +INF-7 is inside the bounds, so no cut off will occur. No cut-off means no backup of fail-high information to the root. And that means no mate report.

But that assumes he did not take the cutoff. While he just wrote that he now does.

And I think it is indeed better to take the cutoff (in case of a mate score).

So by definition I would say:
- when you get a SCORE_IS_AT_LEAST score you are on a CUT node
- when you get a SCORE_IS_AT_MOST score you are on a ALL node
- when you get a SCORE_IS_EXACT score you are on a PV node.
- when you do not get a hash hit you must discover yourself with search.

Not necessarily. It just means you were in that type of node when the hash entry was created. In the mean time the root score, and thus the window could have changed, and you can get hits on EXACT entries with scores very much outside the window.

[Sven]

and when you fail high because you got a mate score back, the window in now (alpha,+INF), so you can no more fail high and to have a TT cut you must hit an exact score (which will be inside the window).

Almost correct for the side to move at root. Not correct for the opponent who searches with (-INF,-alpha). In the former case I wrote "almost" since in reality it is better to use something like (alpha, +(INF-maxDepthOfCurrentIteration)) instead of (alpha,+INF) which is a form of mate distance pruning applied at the root.

In general you can also leave the condition "hashEntryType == LowerBound && value >= beta" intact since even in your case the second part would not match. But the condition itself is still a valid one.

Code: Select all

// pseudo code
if (hashEntry has sufficient depth && "other conditions are met") {
    hashEntryType == Exact ===> cutoff
    hashEntryType == LowerBound && hashEntryValue >= currentBeta  ===> cutoff
    hashEntryType == UpperBound && hashEntryValue <= currentAlpha ===> cutoff
}

Sven

[xmas79]

In PV nodes, when you have a window of (alpha,beta) it's also easy to get a cut off with exact/lower/upper bounds too, but failing high/low means something wrong with your bounds.

Not really. It just means that it is not a PV node after all.

Not really. Being on a PV node has nothing to do with the bounds you have when you "land" on it. PV nodes are only a function of depth *and* eval: once you define depth and an evaluation function of a generic node "n" E(n) then a PV node is f(D,E(n)). Once defined that function, PV nodes "magically" are defined. Assuming no QS & extensions (for the sake of semplicity), to recover PV nodes you must take "the most balanced leaf node" (a function of depth *and* eval) and all its parent are magically PV nodes. The problem is that you must discover *where* is the most balanced leaf node by searching down the tree. If you search with wrong bounds, then you take the a real PV node (let's call it X) as a fail high/low node, NOT in the leftmost part of the tree, and then you must backup to a real PV node Y and research. Please note that *one* real PV node always exists, and it is always reachable: the root node. So if during backup you cannot understand that Y is a PV node due to wrong bounds, you backup and fail high/low up to root. Then you research with wider window, and once you "land" on that same node X with "right" bounds you understand that it is PV node and its parent are PV nodes either.

Fail-high in this situations are typical of mate scores, and when you fail high because you got a mate score back, the window in now (alpha,+INF), so you can no more fail high and to have a TT cut you must hit an exact score (which will be inside the window).

I only do a re-search when the score is between alpha and the original beta of the PV node (which needs not be +INF). And then I open the window to (alpha, original beta). When it fails high above the original beta I take the cutoff immediately. I thought this was the standard implementation of PVS.

So I assume you are on a fail hard framework. In a fail-hard framework you cannot have an EXACt hash hit if your score is outside your serch window. fail-soft frameworks can take advantage of that hits too, as scores can always be from -INF to +INF.

PV is truncated whenever you cannot retrieve a complete PV after hash hit, and this happens when you have an EXACT hash hit and do a cut-off (always for a fail-soft framework, with the score inside the window for fail-hard). If you fail-high at root you do NOT have a PV, you only have a best move in the root position. And inside your TT there is nothing that you can predict, as you don't know in advance which slots were replaced. The research, then, is not guaranteed to find the mate, as it hopefully can follow the moves that lead to the mate, but following is not enough. If the mate is behind the horizon then you CANNOT see it because you don't have a hash hit that says "hey, that's a mate in at most 7 plies from here" because your window is now (alpha,+INF) and the score +INF-7 is inside the bounds, so no cut off will occur. No cut-off means no backup of fail-high information to the root. And that means no mate report.

But that assumes he did not take the cutoff. While he just wrote that he now does.

And I think it is indeed better to take the cutoff (in case of a mate score).

I don't understand this.

So by definition I would say:
- when you get a SCORE_IS_AT_LEAST score you are on a CUT node
- when you get a SCORE_IS_AT_MOST score you are on a ALL node
- when you get a SCORE_IS_EXACT score you are on a PV node.
- when you do not get a hash hit you must discover yourself with search.

Not necessarily. It just means you were in that type of node when the hash entry was created. In the mean time the root score, and thus the window could have changed, and you can get hits on EXACT entries with scores very much outside the window.

That's the problem you must always face when probing TT. Fact is that if you get a score > beta on a lower bound or score < alpha on upper bound you can safely use that score and take a cut-offs. With exact scores, instead, the only place where you "should" hash hit are non-PV nodes. If you probe at PV nodes and get hash hits with EXACT score, then this WILL truncate your PV, as you ALWAYS discover *this* node being a PV node during the backup phase, and while you are probing TT you are actually going "forward". And if you are going forward and are on a PV node, you are going to search deeper than ANY other nodes you have always searched so far, so you are going to search PV one ply deeper. This unless you backed up on a fail-high to node Y and searched this subtree with a wider window, and then you can hash hit one of the already searched PV nodes so far, causing a cut-offs. And in that case you PV is NOT truncated, as you already searched this sub-tree in this iteration at depth D. And this will help search.

I hope I was explaining it right.

Natale.

[xmas79]

Almost correct for the side to move at root. Not correct for the opponent who searches with (-INF,-alpha).

We are talking at root indeed. Opponent always searches accordingly, failing low on every move if position failed high at root (of course).

In the former case I wrote "almost" since in reality it is better to use something like (alpha, +(INF-maxDepthOfCurrentIteration)) instead of (alpha,+INF) which is a form of mate distance pruning applied at the root.

That's not always works because of extensions. You search t depth D and reach depth D+Q, where Q is added by Qsearch & Co. If you set beta to +(INF-maxDepthOfCurrentIteration) you will get another fail-high for sure, since searching forward doesn't replace any single TT entry unless you do a backup (which is not going to happen as you will research the same tree getting the same score back and fail high again, then you have to wide again), that will happen ONLY if you use a window wider than the reported score.

I hope I explained it right.

Natale.

[hgm]

Not really. Being on a PV node has nothing to do with the bounds you have when you "land" on it. PV nodes are only a function of depth *and* eval: once you define depth and an evaluation function of a generic node "n" E(n) then a PV node is f(D,E(n)). Once defined that function, PV nodes "magically" are defined. Assuming no QS & extensions (for the sake of semplicity), to recover PV nodes you must take "the most balanced leaf node" (a function of depth *and* eval) and all its parent are magically PV nodes. The problem is that you must discover *where* is the most balanced leaf node by searching down the tree. If you search with wrong bounds, then you take the a real PV node (let's call it X) as a fail high/low node, NOT in the leftmost part of the tree, and then you must backup to a real PV node Y and research. Please note that *one* real PV node always exists, and it is always reachable: the root node. So if during backup you cannot understand that Y is a PV node due to wrong bounds, you backup and fail high/low up to root. Then you research with wider window, and once you "land" on that same node X with "right" bounds you understand that it is PV node and its parent are PV nodes either.

I don't understand what you are trying to say, and I doubt we are speaking the same language. When I say 'PV node' I am not referring to the game-theoretical concept (which you can establish only after having searched the entire tree), but to the PVS sense, where it is any node with an open window. The other interpretation is not useful for deciding if you are going to take a hash cutoff or not.

So I assume you are on a fail hard framework. In a fail-hard framework you cannot have an EXACt hash hit if your score is outside your serch window. fail-soft frameworks can take advantage of that hits too, as scores can always be from -INF to +INF.

No, I always do fail soft. I don't see how anything I have said could give you any indication to the contrary.

I don't understand this.

What is there not to understand when I say he does a hash cutoff in a PV node, and that this is better than not doing it?

That's the problem you must always face when probing TT. Fact is that if you get a score > beta on a lower bound or score < alpha on upper bound you can safely use that score and take a cut-offs. With exact scores, instead, the only place where you "should" hash hit are non-PV nodes. If you probe at PV nodes and get hash hits with EXACT score, then this WILL truncate your PV, ...

1) Who cares? It is better to have the correct move with an incomplete PV than a long PV for a blunder move. With a truncated PV you at least have some of the moves correct. The purpose is not to collect as many faulty moves as possible...
2) It will not truncate your PV (or truncate it less) if at that point you take action to prevent it (restore the PV from the hash entry, or recover it from the hash table).

[xmas79]

I was simply saying that if you search a PV-node (in both senses) and get a cut-off (because you have wrong bounds) then you know nothing about this node and must re-search, and it doesn't mean this node is a not a PV node, like you said. It only means you searched this node with wrong bounds.

No, I always do fail soft. I don't see how anything I have said could give you any indication to the contrary.
...
What is there not to understand when I say he does a hash cutoff in a PV node, and that this is better than not doing it?

Sorry I misread what you wrote. Now I understand.

1) Who cares? It is better to have the correct move with an incomplete PV than a long PV for a blunder move. With a truncated PV you at least have some of the moves correct. The purpose is not to collect as many faulty moves as possible...
2) It will not truncate your PV (or truncate it less) if at that point you take action to prevent it (restore the PV from the hash entry, or recover it from the hash table).

1) How can I get a PV full of blunders? I don't see any way of doing that.
2) It *will* truncate PV because when you search a PV-node (call it X), you search it at depth D. If you get an exact hash hit and "restore the PV from the hash entry, or recover it from the hash table", what you get is the PV you stored back the iteration before at depth D-1, with a length of D-1. Since you were going to search this node X at depth D (that would give you a PV with a length of D) and you end up with a D-1 length PV, you see you just truncated PV. As I early said, if you're lucky you'll hash hit on a "what you thought it was a PV node, but failed high and so you re-searched all the sub-tree and discovered it's not" PV node searched in this iteration at depth D, which will give you a PV with a length of D. I know of course that QS will mitigate this...

[hgm]

If an exact hash hit on move A at ply 1 tells you there is a mate-in-N, but you have not enough depth to find that mate, and at the depth that you can search you find a best move B that does not lead to mate, I would call B a blunder. And it would be the first move of your (non-truncated) PV. If a PV starts with the wrong move, I would say that everything that follows is pretty irrelevant. It hardly counts at an advantage that this non-sensical move sequence is not truncated...

If I get a cutoff by a lower bound above beta, I don't re-search at all. I just take the cutoff. And because it is a cutoff, I now know that it was not a PV node.

[Desperado]

I was simply saying that if you search a PV-node (in both senses) and get a cut-off (because you have wrong bounds) then you know nothing about this node and must re-search, and it doesn't mean this node is a not a PV node, like you said. It only means you searched this node with wrong bounds.

Hi Natale,

i think you know everything about that node you need to know.

1.
===

if the search result is not within the bounds it is _not_ a pv.

2.
===

a:
bounds are the result of the search ( beside artificial bounds, like aspiration windows like stuff ). So there isnt any need to research.

b:
it sounds to me, that you are talking of a potential pv node which can
be detected with a further iteration step or extension technique in other
words with more depth. That means too that a window state
[xxx , MAXVALUE] is needed. Otherwise there simply cannot be a mate be found by the search.

c: _if_ the bounds are "wrong" without being artificial, then it is simply because the search missed sth. before.

Michael

[xmas79]

If an exact hash hit on move A at ply 1 tells you there is a mate-in-N, but you have not enough depth to find that mate, and at the depth that you can search you find a best move B that does not lead to mate, I would call B a blunder. And it would be the first move of your (non-truncated) PV. If a PV starts with the wrong move, I would say that everything that follows is pretty irrelevant. It hardly counts at an advantage that this non-sensical move sequence is not truncated...

Sorry but this cannot happen. You cannot have an exact hash hit with a mate in N and NOT have the depth to see it, as you already have EXACTLY seen it, and indeed you got an exact score. You can only have a fail-high at root saying there's mate in N and not have the depth to see it. And by the way, move B will only be searched as expected, and with a window (a,+INF) trying to find that mate you are not guaranteed to find it, as NOW you don't have the depth to see it. And this is perfectly normal and expected behaviour. This is what I'm claiming here since my first post.

If I get a cutoff by a lower bound above beta, I don't re-search at all. I just take the cutoff. And because it is a cutoff, I now know that it was not a PV node.

If you get a fail high on a second move of a "supposed" PV node with the first best move you must reserach, as that move could be the real best move, leading to another PV node. So I don't get your point of cutting-off immediately in PV nodes. In non pv-nodes everything is ok.

Question: If you get a fail high at root you don't research? Does this mean that you go directly to the next iteration? What if searching with a wider window you now get a fail low? And what about move ordering in this case?