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
fail high handling with tranposition tables
Moderators: hgm, Rebel, chrisw
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: fail high handling with tranposition tables
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.
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.
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: fail high handling with tranposition tables
alpha=x and beta=x+30 in the research.hgm wrote: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.
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
Re: fail high handling with tranposition tables
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.Uri Blass wrote: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.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: fail high handling with tranposition tables
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.Uri Blass wrote: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.
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.
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: fail high handling with tranposition tables
Yeshgm wrote: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.Uri Blass wrote: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.
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.
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
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: fail high handling with tranposition tables
Does it mean also not pruning based on hash even if the hash tell you score above beta?Alessandro Scotti wrote: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.Uri Blass wrote: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.
-
- Posts: 373
- Joined: Wed Mar 22, 2006 10:17 am
- Location: Novi Sad, Serbia
- Full name: Karlo Balla
Re: fail high handling with tranposition tables
It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.Uri Blass wrote:Does it mean also not pruning based on hash even if the hash tell you score above beta?Alessandro Scotti wrote: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.Uri Blass wrote: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.
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.
-
- Posts: 10296
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: fail high handling with tranposition tables
Not using hash for pruning when beta>alpha+1 mean that movei cannot solve fine70 in a reasonable time.Karlo Bala wrote:It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.Uri Blass wrote:Does it mean also not pruning based on hash even if the hash tell you score above beta?Alessandro Scotti wrote: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.Uri Blass wrote: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.
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
-
- Posts: 373
- Joined: Wed Mar 22, 2006 10:17 am
- Location: Novi Sad, Serbia
- Full name: Karlo Balla
Re: fail high handling with tranposition tables
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.Uri Blass wrote:Not using hash for pruning when beta>alpha+1 mean that movei cannot solve fine70 in a reasonable time.Karlo Bala wrote:It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.Uri Blass wrote:Does it mean also not pruning based on hash even if the hash tell you score above beta?Alessandro Scotti wrote: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.Uri Blass wrote: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.
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
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.