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

[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
&#125;

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?

[hgm]

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 have seen it in a previous search, before you saw that the opponent had a move to avoid that position, and then the opponent did not play that move, so you get in the position anyway, and start iterating from depth 1 (which is not enough to see the mate)...

You can only have a fail-high at root saying there's mate in N and not have the depth to see it.

You can never have a true fail high at the root, as it is a PV node, and the window is (-INF, +INF) there.

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.

Not sure what you are trying to say. In the example B is supposed to not lead to a mate no matter how deep you search it, no matter what window you search it with. It could be a losing move (but still seeming the best at the depth you have available, which is not enough to see the mate on move A).

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.

I don't understand what you mean by the phrase "with the first best move". I would say only one move can be best, in general. But if I get a fail high on a later move of a supposed PV node that is above beta, I don't have to re-search. That the score is above beta is all you need to know. (And the hypothesis that it was a PV node can go into the dust bin...) Only when you get a lower bound between alpha and beta (i.e. fail high w.r.t. the null window (alpha, alpha+1)) there is need for a re-search, because the true score might conceivably still be below beta (without violating the lower bound just found).

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?

The only move that can truly fail high in the root is King capture, as beta = +INF in the root, and only King captures score that high. And indeed, there is no reason to re-search, or even do a next iteration in that case.

[Uri Blass]

1)king capture is not a legal move in chess so assuming players play by the chess rule it is impossible to have a king capture in the root.

2)If you remember the reasons for the forced mate in the hash table(meaning memorizing all the positions that you found mate score in them) then after seeing a forced mate you can play the mating sequence simply from the hash tables when the opponent's reply changes nothing.

Of course you can have some long mate that you have not enough memory in the hash tables to memorize the reasons but even in this case
you can memorize the reasons in the first 10 plies and play the next 5 moves immediately.