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

[Sven]

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.

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.

I am not sure whether I understand your scenario. At least I think it might be possible that you did not take into account the fact that you can only get a hash hit from a TT entry that has a sufficient depth related to the current depth. In the light of that detail it appears to me that the scenario you are afraid of does not happen. I may be wrong, though.

You see some reasons against accepting TT cutoffs of type "exact" in PV nodes. In a previous post you saw some reasons against accepting TT cutoffs of type "LowerBound" or "HigherBound" in certain cases. I see no justification for both

Sven

[hgm]

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)

That makes no sense to me. You cannot get a cutoff from a TT entry that is not at least the depth you need. That is irrespective of bound or node type. So if you get a cutoff at ply X in the D+1 search, it must go accompanied by a PV that supplies all moves from X to at least D+1, not to D.

[xmas79]

Hi Sven,

I am not sure whether I understand your scenario. At least I think it might be possible that you did not take into account the fact that you can only get a hash hit from a TT entry that has a sufficient depth related to the current depth. In the light of that detail it appears to me that the scenario you are afraid of does not happen. I may be wrong, though.

I take this into account, as search can "swindle" for one ply and reach a position which will hash hit, as it will re-gain the sufficient draft to hit.

You see some reasons against accepting TT cutoffs of type "exact" in PV nodes. In a previous post you saw some reasons against accepting TT cutoffs of type "LowerBound" or "HigherBound" in certain cases. I see no justification for both

Where? I read all my post and I didn't find that.

Natale.

[xmas79]

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)

That makes no sense to me. You cannot get a cutoff from a TT entry that is not at least the depth you need. That is irrespective of bound or node type. So if you get a cutoff at ply X in the D+1 search, it must go accompanied by a PV that supplies all moves from X to at least D+1, not to D.

Hi HG,
that makes no sense to me instead. If you get a cutoff at ply X in the D+1 search, it will happen because search "swindled" one ply and hit a position searched previously (two plies ago). Now you'll complete this PV with a total of D+1 moves where two are swindles, which is indeed a PV you retrieved in the D-1 iteration except for the swindle two plies back, instead of having now another PV of length D+1 where the last two moves are new moves.

[hgm]

What you call "swindle" is simply grafting. The extra moves will be in the path that leads upto ply X. But everything from X to D+1 will still be the best continuation from the position at X. That it was obtained in a search with a shorter path to that positon doesn't alter that at all. (Assuming repetitions will not play a role, which in case of mate scores must be true.) The PV associated with the hashed position remains valid. There is nothing to be gained by searching it again: if you search it again to the depth with which it was stored in the TT, you would find exactly the same PV. If you would search it to a smaller depth, you might get a different, but inferior PV (which now might miss mates and other tactics the stored PV did see). If you should have searched it to larger depth, the stored PV and score are not good enough for what you need, which is why you never take hash cuts on TT entries that are of unsufficient draft. You can at best use those as a starting point for IID.

[Sven]

You see some reasons against accepting TT cutoffs of type "exact" in PV nodes. In a previous post you saw some reasons against accepting TT cutoffs of type "LowerBound" or "HigherBound" in certain cases. I see no justification for both

Where? I read all my post and I didn't find that.

http://www.talkchess.com/forum/viewtopi ... 1&start=28

I'm a bit confused now, I have great difficulties to understand your reasoning since it appears that you are now almost saying the opposite of what you wrote in the post linked above.

Maybe I lost track somewhere in the middle.

Sven

[xmas79]

Hi guys,
I thought about this and came to this conclusion: I now think I was wrong about PV truncation.

Suppose you have this TT entry:
- type: exact
- draft: 6
- PV stored: 6 moves here...

Suppose to search a position and hit this entry at iteration 13. It seems to me you can only hash hit with exact score at plies 7, 9, 11, 13, as you have draft respectively of 6, 4, 2, 0.
a) hitting at ply 13 means that after 13 plies you retrieve PV from hash and get back a final PV of length 19
b) hitting at ply 11 means that after 11 plies you retrieve PV from hash and get back a final PV of length 17
c) hitting at ply 9 means that after 9 plies you retrieve PV from hash and get back a final PV of length 15
d) hitting at ply 7 means that after 7 plies you retrieve PV from hash and get back a final PV of length 13

But Steve said it had an exact hash entry at ply 1... So let's do the same from iteration 1 onward:
If you are searching this position at iteration 1, you can hash hit at ply 1 as draft is 0:
e) hitting at ply 1 means that after 1 ply you retrieve PV from hash and get back a final PV of length 7

If you are searching this position at iteration 3, you can hash hit at ply 1 and 3 as draft is 2 and 0 respectively:
f) hitting at ply 3 means that after 3 ply you retrieve PV from hash and get back a final PV of length 9
g) hitting at ply 1 means that after 1 ply you retrieve PV from hash and get back a final PV of length 7

If you are searching this position at iteration 5, you can hash hit at ply 1, 3, 5 as draft is 4, 2, 0 respectively:
h) hitting at ply 5 means that after 5 ply you retrieve PV from hash and get back a final PV of length 11
i) hitting at ply 3 means that after 3 ply you retrieve PV from hash and get back a final PV of length 9
j) hitting at ply 1 means that after 1 ply you retrieve PV from hash and get back a final PV of length 7

If you are searching this position at iteration 7, you can hash hit at ply 1, 3, 5, 7 as draft is 6, 4, 2, 0 respectively:
k) hitting at ply 7 means that after 5 ply you retrieve PV from hash and get back a final PV of length 13
l) hitting at ply 5 means that after 5 ply you retrieve PV from hash and get back a final PV of length 11
m) hitting at ply 3 means that after 3 ply you retrieve PV from hash and get back a final PV of length 9
n) hitting at ply 1 means that after 1 ply you retrieve PV from hash and get back a final PV of length 7

If you are searching this position at iteration 9, you can hash hit at ply 3, 5, 7, 9 as draft is 6, 4, 2, 0 respectively:
o) hitting at ply 9 means that after 9 ply you retrieve PV from hash and get back a final PV of length 15
p) hitting at ply 7 means that after 7 ply you retrieve PV from hash and get back a final PV of length 13
q) hitting at ply 5 means that after 5 ply you retrieve PV from hash and get back a final PV of length 11
r) hitting at ply 3 means that after 3 ply you retrieve PV from hash and get back a final PV of length 9

If you are searching this position at iteration 11, you can hash hit at ply 5, 7, 9, 11 as draft is 6, 4, 2, 0 respectively:
s) hitting at ply 11 means that after 11 ply you retrieve PV from hash and get back a final PV of length 17
t) hitting at ply 9 means that after 9 ply you retrieve PV from hash and get back a final PV of length 15
u) hitting at ply 7 means that after 7 ply you retrieve PV from hash and get back a final PV of length 13
v) hitting at ply 5 means that after 5 ply you retrieve PV from hash and get back a final PV of length 11


So definitely, it seems to me that you are guaranteed to have a PV of length >= of the current iteration depth. Do you all agree with that?

Best regards,
Natale.

[hgm]

Yes, that sounds OK. If you hashed the full PV, or could still retreive it from the hash table at the point where you hit the draft-6 entry. If you don't do anything when you take a cutoff there, your PV would be truncated at the point where you got the hit. Note that in many case you got a PV that is longer than the depth of the search (even without extensions or QS plies). That is the grafting effect.

Not taking PV cutoffs is a kludge to let the ordinary search retrieve the PV from the hash table, as it will search all the PV moves, but any other move will usually immediately hit upon an entry that has sufficient depth to cause a cutof, as they are no longer PV. But if you had an over-deep hit (i.e. more draft than you really needed), it will not follow the PV to the very end, (even if it is still in the hash table), but stop as soon as you reaches the PV length corresponding to the requested depth, and do a QS there.

In case of an over-deep hit this could give you a score that is different from the hashed score of all the PV nodes you have been following. E.g. because you had not enough depth to see the mate, and get a normal eval score in stead of a mate score. If there was no overwrite in the hash, you could prevent this accuracy loss by using the hashed score in stead of the QS score (i.e. only allow PV cutoffs at depth <= 0), in which case your PV would be cut at the nominal length. You could also decide to extend at this point to the draft you find in the hash table. Or, more safely, extend 1 when you reach d=0 and have a hash hit of draft > 0, in an attempt to recover the grafted PV moves. In the worst case you would do an extra d=1 search if the entry was overwritten, but if it was still there you would then do another extension to step to the next, etc. This could eventually turn out expensive if you have a deep graft and many of the entries from the side branches are overwritten, as you would start to search these again. So it would probably be better to have a dedicated routine for this that tries to follow the PV in the hash.

A good poor-man's alternative, which is the one I proposed, is:
1) Don't do hash cutoffs in PV nodes, but remember (e.g. by setting a flag) that you could do one if the draft was larger than you needed
2) After searching the node, do such a cutoff anyway, returning the hashed score rather than the score obtained from search
This will give you the best score, but the price is that the reported PV beyond the point where you did the hash cut might not be the one corresponding to the score. In practice differences only occur when the search stumbled on missing hash entries, and starts to draw its own conclusions at the nominal depth lower than the hashed drafts; if nothing was overwritten you will find the PV belonging to the score (but you will not have followed it to the very end, just to the nominal depth).

Now this scheme interferes with a second reason why people don't do PV cutoffs, which is to detect repetitions. This is why I proposed to only do it when the hash score is a mate score.