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

[hgm]

But in Chu Shogi you win only by King capture.

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

[Sven]

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

You might have lost the context of my reply, it was this one (bold added to highlight what I referred to):

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

So you were not talking about the root but about conditions for a TT cutoff. I tried to explain that at an arbitrary node in the tree (PV or non-PV node) a TT cutoff is also possible with a hash entry of type LowerBound or HigherBound, depending on the situation.

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.

I am not sure whether you understood what I meant. If you finish iteration 1 and do not find a mate in 1 ply from the root then iteration 3 will not find a mate in 1 ply from root either. If you finish iteration 2 and do not find that the moving side at root is mated in 2 plies from the root then iteration 4 will not find a mate in 2 plies from the root either. That means, if you are at iteration N (and you have no reductions or forward pruning!) then you will not find a shorter mate since all shorter mates must have been found in earlier iterations. Extensions can help to find deeper mates, e.g. mate in N+Q, in iteration N but not shorter mates. Therefore you can set alpha to something like "-(INF-N-1)" and beta to something like "+(INF-N-1)". Initially I wrote "+(INF-N)" etc. but with the -1 it is better since it keeps the valid "mate in N" score inside the window instead of leading to a fail high.

Sven

[xmas79]

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

I repeat again: this cannot happen. If opponent has a move to avoid that position, then this position will NEVER be stored as EXACT. So it is NOT possible to have an exact hash hit. It is likely you'll have a lower bound hash hit, as it will be stored as such.

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

This sounds strange to me, as the original poster says that Maverick fails-high at root, so he must be using a window different from (-INF,+INF) in PV nodes, AKA aspiration window? And in that situation you can (and will) fail high/low at root.

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

I'm saying that move A will be searched with window of (a,+INF) in the hope to find the mate, which is not guaranteed, and this thing is going to return a score inside the window. And I'm also saying that move B will simply be searched as usual, and I wouldn't call it a blunder as it is going to be the new best move at current iteration, even if doesn't lead to mate (very hard to believe that, move order should guarantee that).

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

I'm expressing the fact that when you are trying to figure out if a node X is a PV node you consider the first move as the best move, so you search it with (a,b) bounds (whatever they are). If this move doesn't fail high, then you search the rest of the moves with a zero window. If none of them fails-high then you have discovered that X is really a PV node. But if one of those moves fails high, how do you decide which move is best? You have to re-search this move with the original window (as it seemed to me that you said a few posts ago). And the hypothesis that X is a PV node still holds, as re-search can give a score less than the score of the first move. If after searching this second move fails high, then take a cut-off and send everything to the bin (as the first move you tried will bring you to a node Y which you believed was PV node until you discovered a better path), and this node X just failed high because you are *here* with a wrong beta value. It is possible that when you research you'll land at X again (with a different window) and discover that is a PV node.

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?

I do not allow King captures, so when searching with (-INF,+INF) I have no way to fail high/low.

[xmas79]

You might have lost the context of my reply, it was this one (bold added to highlight what I referred to):
So you were not talking about the root but about conditions for a TT cutoff. I tried to explain that at an arbitrary node in the tree (PV or non-PV node) a TT cutoff is also possible with a hash entry of type LowerBound or HigherBound, depending on the situation.

Ah yes, now I see. Right.

Therefore you can set alpha to something like "-(INF-N-1)" and beta to something like "+(INF-N-1)". Initially I wrote "+(INF-N)" etc. but with the -1 it is better since it keeps the valid "mate in N" score inside the window instead of leading to a fail high.

Why I should set alpha to a near -MATE score? If I'm gonna win (especially after a failhigh at root) I will only raise beta, and hope not to fail low. If that happens then I lower alpha, until AB window gets wide enough to avoid TT cutoffs so I get an exact score.

[hgm]

I repeat again: this cannot happen. If opponent has a move to avoid that position, then this position will NEVER be stored as EXACT.

Of course it can. Because you could have searched the move leading to it before you searched the move that avoided it.

In fact this is almost always what happens with mates. In the root you play a move that at low depth looks OK, and it comes out best and is sorted first. Then, at some iteration, where the daughter node is searched first, and thus with window (-INF, +INF) you find that it gets a mate score, say +INF-N. That is in window, so it will be stored in the TT as EXACT.

In the root the score shows up as -MATE+N, i.e. the root player now sees the move gets him checkmated. It is very easy for other moves to fail high against this very low alpha, and if he is not lost already he will eventually find such a move. This then becomes the new PV, and might have a score +500 (e.g. because the eval in the root was already +500). But that won't alter the fact that the TT entry for the move that got him mated remains stored as EXACT...

This sounds strange to me, as the original poster says that Maverick fails-high at root, so he must be using a window different from (-INF,+INF) in PV nodes, AKA aspiration window? And in that situation you can (and will) fail high/low at root.

Well, I don't do aspiration. PVS in itself is already a sort of aspiration search, because you close the window after the first move, which gives you the ultimate aspiration window, namely a null window, positioned at exactly the right score.

When I say that I do not re-search when the score is above beta, I mean the original beta of the node, not an artificially lowered beta from aspiration (like alpha+1). This is what I mean by "truly" in "truly fails high". Only if you fail high in the range between the true beta and whatever artificial upper window limit you used in aspiration needs to be re-searched. But not what scores above the true beta. But in the root, the true beta is +INF, and only King capture could score above it.

The only difference with aspiration is that you would also search the first move with an artificially narrowed window, and can thus get fail highs on it that require re-search, making the first move more similar to other moves in PVS.

I'm saying that move A will be searched with window of (a,+INF) in the hope to find the mate, which is not guaranteed, and this thing is going to return a score inside the window. And I'm also saying that move B will simply be searched as usual, and I wouldn't call it a blunder as it is going to be the new best move at current iteration, even if doesn't lead to mate (very hard to believe that, move order should guarantee that).

If move A leads you to checkmate your opponent, and move B loses the game, I would call B a blunder. That B at some search depth would seem the best move is completely irrelevant for that.

Seems to me the PV that follws after move B is of far less interest than move A, even if the PV would be immediately truncated after it. Because you still would have one good move of the PV. While on move B followed by a hundred others, you would have none.

[Sven]

Therefore you can set alpha to something like "-(INF-N-1)" and beta to something like "+(INF-N-1)". Initially I wrote "+(INF-N)" etc. but with the -1 it is better since it keeps the valid "mate in N" score inside the window instead of leading to a fail high.

Why I should set alpha to a near -MATE score?

What I meant is to use "-(INF-N-1)" instead of "-INF" whenever you would set alpha to "-INF". Sorry for not making this clear enough. Maybe it is not of high importance. I do it in my program since I want to stop the iterative deepening when I detect a mate (or being mated) that turns out to be the shortest mate that I would be able to find at that point. Maybe I don't even need to change alpha that way for this purpose, but it does not hurt and makes life easier for me ...

If I'm gonna win (especially after a failhigh at root) I will only raise beta, and hope not to fail low. If that happens then I lower alpha, until AB window gets wide enough to avoid TT cutoffs so I get an exact score.

Why "avoid TT cutoffs"? What is the goal behind that? I would assume the usual goal is to get TT cutoffs whenever possible. What you want is to avoid truncated PVs. But that has been discussed in lenght somewhere else, there are ways to achieve that (e.g. separate PV hash table). The goal to get TT cutoffs whenever possible should have a higher weight than avoiding PV truncation in my view.

Sven

[xmas79]

Therefore you can set alpha to something like "-(INF-N-1)" and beta to something like "+(INF-N-1)". Initially I wrote "+(INF-N)" etc. but with the -1 it is better since it keeps the valid "mate in N" score inside the window instead of leading to a fail high.

Why I should set alpha to a near -MATE score?

What I meant is to use "-(INF-N-1)" instead of "-INF" whenever you would set alpha to "-INF". Sorry for not making this clear enough. Maybe it is not of high importance. I do it in my program since I want to stop the iterative deepening when I detect a mate (or being mated) that turns out to be the shortest mate that I would be able to find at that point. Maybe I don't even need to change alpha that way for this purpose, but it does not hurt and makes life easier for me ...

I agree, I found myself that lowering alpha when mating has a little impact on search. But the fact is that opponent can see scores above -alpha as exact score, and that means opponent fails high less often, resulting in a increased number of (useless) nodes searched. so I don't. The same principle is when being mated. Never rise beta, as when it "my" turn to move I can see scores inside the window instead of cutting off. But I really don't know how many nodes. Perhaps zero nodes (as you will search with zero window), but from a theoretical POV it's plain wrong IMHO. I always take into account search instability, where you're not guarateed to always research the same tree in the same iteration/re-search.

If I'm gonna win (especially after a failhigh at root) I will only raise beta, and hope not to fail low. If that happens then I lower alpha, until AB window gets wide enough to avoid TT cutoffs so I get an exact score.

Why "avoid TT cutoffs"? What is the goal behind that? I would assume the usual goal is to get TT cutoffs whenever possible. What you want is to avoid truncated PVs. But that has been discussed in lenght somewhere else, there are ways to achieve that (e.g. separate PV hash table). The goal to get TT cutoffs whenever possible should have a higher weight than avoiding PV truncation in my view.

Sven

You guys seem to miss my point. The point is:
1) I'm going to search a position at depth D
2) I find a PV that has length D and complete iteration at depth D
3) I go on with iteration at depth D+1
4) I hash hit on a ply X<D, so I get a PV on length D and skip the subtree (note I wrote length D and not lenght X, supposing you are able to retrieve it from hash table or whatever way you have to restore PVs)
5) I complete search WITHOUT changing PV (typical in endgames where a few plies are foced?)

Just stopping here I already see a flaw: all the moves belonging to a PV at depth D are guaranteed to be the best moves when searching at depth D, but they are NOT guaranteed to be the best moves at depth D+1, so in step 5 I have just lost the possibility to change my mind in all the plies >= X to D+1 You even removed the possibility to fail low because you didnt analyze the moves at depth D+1 (typical in positions where you have a ping-pong of failhgh/faillow)

6) I go on with iteration at depth D+2
7) If I still get hash hit at ply X<D where I will be back again with the same PV at depth D instead of one at depth D+2
8) etc..etc..etc...

IMHO, it's clear that hash hitting (in PV nodes) two exact scores in a row (but even once can be enough) can lead to bad playing. The truncation of PVs is "only" a side effect of search really missing something.

Natale.

[xmas79]

Well, I don't do aspiration. PVS in itself is already a sort of aspiration search, because you close the window after the first move, which gives you the ultimate aspiration window, namely a null window, positioned at exactly the right score.

That's why we are speaking different languages! When you since start have a (-INF+INF) window you can never fail high/low at root. But this is NOT the context of the original poster, as he explicitly said Maverick failed high and then could not find the mate. So Maverick don't use PV search bounds (-INF,+INF).

Of course it can. Because you could have searched the move leading to it before you searched the move that avoided it.

In fact this is almost always what happens with mates. In the root you play a move that at low depth looks OK, and it comes out best and is sorted first. Then, at some iteration, where the daughter node is searched first, and thus with window (-INF, +INF) you find that it gets a mate score, say +INF-N. That is in window, so it will be stored in the TT as EXACT.

This is true for non aspirated window. If you use aspiration window (as the original poster does) it cannot happen, as when you are being mated, you have a window of (alpha,beta) at root, which will be (-beta, -alpha) for the opponent which will see a mate score well above -alpha, so it will fail high and never store this position as an exact score.

[hgm]

This is true for non aspirated window. If you use aspiration window (as the original poster does) it cannot happen, as when you are being mated, you have a window of (alpha,beta) at root, which will be (-beta, -alpha) for the opponent which will see a mate score well above -alpha, so it will fail high and never store this position as an exact score.

OK, I see what you mean. Yet the original poster also said he encountered an EXACT mate score from an earlier search. So he might not do aspiration in the way you think he does. And I think it can still happen if you speculatively ponder on a move that on deeper search turns out to get you mated. The position after that move becomes root during the ponder search, and if the mating move there fails high with aspiration, you would re-search with larger upper-window bound until it no longer does. And then it would go in the hash table as exact. That there are other moves than the ponder move that do not lead to mate then would not matter, as you fixed the ponder move, so that it could not change. After the opponent played another move you might be able to force him back to that ponder position through a detour.

The OP writes this:

If the previous search found the mate in 15 (Nf6+), the path and mate score will hopefully be stored in the hash table. This means on the next search it plays Nf7+ with a zero width window and gets an immediate fail-high cutoff due to the mate value stored in the hash table. It then opens the search window and tries to find the mate. However, at the lower ply it does not have the depth to see it and so fails low.

(emphasis mine). So I think he is just talking about re-searches in the framework of PVS, not in the framework of aspiration search. With aspiration search you would not normally start with a null window.