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

[xmas79]

Hi Natale,

I actually do have an EXACT mate score in the hash. This is the PV from the previous search. It makes sense to use this information. So now what I do is to take the PV node cutoff and fill the PV with info from the hash table.

Hi Steve,
don't let the algorithm fool you.
You think you have an EXACT mate score in the hash and think you can use this information. This is absolutely great, but when engine starts a new search, this search will probabily kill all those information. The only way to understand what's wrong (if any!) is to debug your search and see what happens on the research, as I did in my long post. After I debugged my code I really understood what a search is and how alpha/beta/TT PVs etc.. interacts. Everything was exceptionally clear then.

It seems to work well.
Best regards,

Steve

I repeat: it always worked the way it's designed to, no problems at all.

Best regards,
Natale.

[xmas79]

Hi Steve,
please give a try with the following:
- go to the initial mate position and let the engine find the mate in 31 plies
- take note of the nominal depth it found the mate, let's say depth D
- make the found mating move and the best opponent move
- start a search directly with a depth D-2, not an iteration.

I'm sure it will find the mate at a glance. Post the result.

Thank you,
Natale.

[Steve Maughan]

Hi Natale,

Of course it will - it did before the change.

My point is, if you have an exact score from a previous search it would be good to use the information in the current search. It now does and seems to work well.

Thanks,

Steve

[xmas79]

Hi Steve,
please correct me if I'm wrong. It seems to me that doing this way you are disallowing your engine to search the PV one ply deeper:
1) Your engine completes a search at depth 10. You'll have a PV from this search.
2) You search now at depth 11. You follow PV and immediately get hash hit because of the PV stored in TT and its EXACT score and make a cutoff. So you extract that PV, backup the score to the root, and move to the second move of the root move list, and complete the search at depth 11
3) If the search doesn't find a better move than the first, then all you'll get back is the PV you already got from previous search.

Is this thinking right?

Thank you,
Natale.

[Steve Maughan]

Hi Natale,

You're correct but there isn't any downside to my approach.

In the example I gave, Maverick has found Nf6+ mate in 15 on the previous search. It plays Nf6+ and get the expected response. So it start to search again. This time on the first ply it find Nf7+ with a score of mate in 14 in the hash table with an EXACT tag. So it fills the triangular PV with the moves following Nf7 extracted from the hash table. When it comes to depth 14 or 15 it will search and find the same mate.

I don't see a problem. What am I missing.

Steve

[xmas79]

Hi Steve,
from an "end of the game" point of view I think nothing is wrong, as you cannot have a PV length greater than the mate found. From a playing point of view, this could create other problems, eg where the engine could not go any deeper than the PV length. This has little impact in shallow searches and in positions where PV changes most of the times, but in long searches where only one line is pretty forced (with no mate or stalemate in the near future, eg an endgame with long checks sequences) could cause the engine to "hang" on a truncated PV, without the possibiity to search deeper.

Am I wrong?
Natale.

[Steve Maughan]

Hi Natale,

I don't think there is a problem even when it isn't a mate. Here's why.

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.

Steve

[Sven]

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

[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.