fail high handling with tranposition tables

[Uri Blass]

I try to implement using hash for pruning in movei

It seems that so far my effort are productive and movei can solve fine70 in a reasonable time but a problem that I find is that there is no wrong
fail high and I wonder how to change it.

The problem is that after searching with minimal window (x,x+1) the program write in the hash that the score is at least x+1 and later when I do a research it automatically increase alpha to x+1 so the research with bounds x,x+30 can never return x.

I know from experience that without using hash for pruning research can return x because the search with bounds x,x+30 is more correct and less moves are pruned and I wonder how to solve the problem.

A possible solution may be simply to do the research with higher depth(I do not need to increase the depth by a full ply and I can simply increase the depth by 1/400 ply so practically the same lines are going to be searched but not pruned based on hash)

I wonder what do you do with this type of problem?

Uri

[hgm]

I am not sure what the problem is. If your search to depth N with window (x,x+1) returns a fail high, it gows into the hash table with Depth=N, ScoreType = LB and Score = x+1 (or perhaps higher if you do soft fail).

If you now re-search with window (x, x+30) to depth N, you will not get a hash hit, as the LB is inside the window, unless it is at least x+30. But in normal PVS you would not re-search with a score above the original beta, but take a cutoff immediately.

If you think the search instabilit is large enough to warrant re-searches even in that case, (with fully open window), you should simply refrain from cutoffs in nodes with open window. After all, if the score stays above alpha, this will now become your new PV.

We already decided that it is wise to not do hash pruning in the PV, in connection with the rep-draw prroblem.

[Uri Blass]

I am not sure what the problem is. If your search to depth N with window (x,x+1) returns a fail high, it gows into the hash table with Depth=N, ScoreType = LB and Score = x+1 (or perhaps higher if you do soft fail).

If you now re-search with window (x, x+30) to depth N, you will not get a hash hit, as the LB is inside the window, unless it is at least x+30. But in normal PVS you would not re-search with a score above the original beta, but take a cutoff immediately.

If you think the search instabilit is large enough to warrant re-searches even in that case, (with fully open window), you should simply refrain from cutoffs in nodes with open window. After all, if the score stays above alpha, this will now become your new PV.

We already decided that it is wise to not do hash pruning in the PV, in connection with the rep-draw prroblem.

alpha=x and beta=x+30 in the research.
The problem is not that I get a cutoff that means a score above beta but that when I search with window (x,x+30) probing the hash table change alpha and tell me that the score is at least x+1 so alpha is increased to x+1 and the minimal score that I can get is x+1.

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

Uri

[Alessandro Scotti]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

A common (I think) approach is to use the hash table only for move ordering whenever the window is not a null window, which implies not updating alpha in those cases.

[hgm]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

Indeed. If a fail high of the null-window search would not make you draw the conclusion that the score is above the obtained LB (so that you search with alpha = x, in stead of alpha = x+1), it would be inconsistent to up alpha on a hash hit. After all, the hash hit is just a stored version of a previous search that failed high, and should be treated identically to the way it would if a real search returned it.

If you want, you could introduce a fourth bound type, in order to distinguish lower bounds obtained in an open-window search from those in a null-window search, and only use the former for upping alpha. But I really don't see how the lower bound of the window could have any effect on the reliability of the lower bound.

So what you propose seems an obvious (and in fact the only consistent) solution.

[Uri Blass]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

Indeed. If a fail high of the null-window search would not make you draw the conclusion that the score is above the obtained LB (so that you search with alpha = x, in stead of alpha = x+1), it would be inconsistent to up alpha on a hash hit. After all, the hash hit is just a stored version of a previous search that failed high, and should be treated identically to the way it would if a real search returned it.

If you want, you could introduce a fourth bound type, in order to distinguish lower bounds obtained in an open-window search from those in a null-window search, and only use the former for upping alpha. But I really don't see how the lower bound of the window could have any effect on the reliability of the lower bound.

So what you propose seems an obvious (and in fact the only consistent) solution.

Yes

The reason that I changed alpha is simply because I read it in glaurung1.2.1 and I thought that it is a good idea without considering the fact that my search is different than glaurung.

I already did some testing in test suites in the first option that I thought about(researching with higher depth that is practically usually the same depth but not stored in the hash as the same depth)

I plan to try again simply not to update alpha and use the hash for pruning only to return beta in case that the score is above beta.

Uri

[Uri Blass]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

A common (I think) approach is to use the hash table only for move ordering whenever the window is not a null window, which implies not updating alpha in those cases.

Does it mean also not pruning based on hash even if the hash tell you score above beta?

[Karlo Bala]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

A common (I think) approach is to use the hash table only for move ordering whenever the window is not a null window, which implies not updating alpha in those cases.

Does it mean also not pruning based on hash even if the hash tell you score above beta?

It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.

[Uri Blass]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

A common (I think) approach is to use the hash table only for move ordering whenever the window is not a null window, which implies not updating alpha in those cases.

Does it mean also not pruning based on hash even if the hash tell you score above beta?

It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.

Not using hash for pruning when beta>alpha+1 mean that movei cannot solve fine70 in a reasonable time.

The problem is that searching the first root move is not done with null window and if the program cannot use hash for pruning in that search then it means that it practically cannot use hash for pruning in searching the first move.

Uri

[Karlo Bala]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

A common (I think) approach is to use the hash table only for move ordering whenever the window is not a null window, which implies not updating alpha in those cases.

Does it mean also not pruning based on hash even if the hash tell you score above beta?

It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.

Not using hash for pruning when beta>alpha+1 mean that movei cannot solve fine70 in a reasonable time.

The problem is that searching the first root move is not done with null window and if the program cannot use hash for pruning in that search then it means that it practically cannot use hash for pruning in searching the first move.

Uri

Hmmm, I'm not sure that you don't have a bug. My program solves fine70 with brute force. It take about 70.000 nodes. Positions where beta>alpha+1 are less than 0.1% of all position searched.