I thought I had found a serious bug with my engine, but now I'm not so sure. So I'm asking the experts.
In a nutshell, when a move improves beta, do you return the eval or the upper bound? I looked at several source files, and most (but not all) return the upper bound.
I would have thought that returning the eval would generate instabilities. But, as I said, now I'm not so sure that it makes a difference.
Thoughts?
Many thanks in advance,
jm
Return eval or upper bound?
Moderators: hgm, Rebel, chrisw
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Return eval or upper bound?
I'm not perfectly sure what you mean by "a move improves beta" but I guess you mean "searching a move returns a value > beta (but not == beta) causing a cutoff". I also guess you mean "return the eval or the *lower* bound", since failing high goes along with getting a value for a move that is already sufficient (but may be even higher) to cause a beta cutoff.JVMerlino wrote:In a nutshell, when a move improves beta, do you return the eval or the upper bound? I looked at several source files, and most (but not all) return the upper bound.
I would have thought that returning the eval would generate instabilities. But, as I said, now I'm not so sure that it makes a difference.
If my guesses are right, the answer depends on the search algorithm you are using.
With plain original AlphaBeta, you can always return beta at this point, and this is also the recommended and clean way. Returning the lower bound would make no difference for all nodes except the root, since the cutoff would work the same way: the previous move of the opponent is refuted and does not make it to improve alpha at the node above. At the root node it could make a difference to return the lower bound everywhere, but only if an aspiration window is used and a possible re-search is not done with proper bounds.
With the slightly improved version FAB (Fail Soft AlphaBeta), you *must* return the lower bound, since this is one of the basic elements of the algorithm.
For me the major impact of returning the lower bound everywhere with plain AlphaBeta would be "confusion", since it would partially look like FAB.
Sven
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Return eval or upper bound?
Hi Sven,
Sorry that my description was confusing. Here it is, in pseudo-code:
Should it be this:
or this:
jm
Sorry that my description was confusing. Here it is, in pseudo-code:
Should it be this:
Code: Select all
if (eval > alpha)
{
...save best move
...update pv
alpha = eval;
if (eval >= beta)
return beta;
}
Code: Select all
if (eval > alpha)
{
...save best move
...update pv
alpha = eval;
if (eval >= beta)
return eval;
}
-
- Posts: 27800
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Return eval or upper bound?
Both work. The first is known as fail-hard, the other as fail-soft. When you use a hash table, fail-soft is more efficient, as it tehds to lead to tighter bounds on the moves, which then get stored in tha hash table.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Return eval or upper bound?
Also adds a bit of instability, although I still use it. unstable != bad, just a pain at times when debugging or testing.hgm wrote:Both work. The first is known as fail-hard, the other as fail-soft. When you use a hash table, fail-soft is more efficient, as it tehds to lead to tighter bounds on the moves, which then get stored in tha hash table.
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Return eval or upper bound?
Ok, that's what I thought, as I'm occasionally seeing very strange (although very temporary) PVs. So I guess that's what happens with fail-soft when it affects a move at the root?bob wrote:Also adds a bit of instability, although I still use it. unstable != bad, just a pain at times when debugging or testing.hgm wrote:Both work. The first is known as fail-hard, the other as fail-soft. When you use a hash table, fail-soft is more efficient, as it tehds to lead to tighter bounds on the moves, which then get stored in tha hash table.
The reason I caught this is in this position from the WAC (#264):
r2r2k1/1R2qp2/p5pp/2P5/b1PN1b2/P7/1Q3PPP/1B1R2K1 b - -
Myrddin's output through the first half-second with fail-soft was this:
Code: Select all
1/ 4 -146 6 17 f4h2 g1h2 a4d1
2/ 7 -106 6 447 f4h2? g1h2
2/ 8 79 7 1932 f4h2 g1h1 h2c7 h1h2
2/ 8 60 7 3054 e7c5 b1c2 c5c4
3/ 8 65 7 3945 e7c5 b1c2 c5c4 c2a4 c4a4
3/10 20 9 4391 f4h2! b1c2 c5c4 c2a4 c4a4
3/10 -81 9 6982 f4h2 g1h1 e7b7 b2b7 a4d1
4/16 -109 12 26571 f4h2 g1h1 e7h4 b1c2 h2g3 h1g1 g3f2 g1f1 f2d4 c2a4
4/16 -116 14 31455 d8d4 b2d4 e7b7 d1e1 g8h8
4/16 -121 15 37123 e7c5! d1e1
4/16 -191 17 43245 e7c5 b7f7 g8f7 b2b7 f4c7
4/16 -32764 21 69743 d8d4 b7e7
5/10 -32724 21 72173 d8d4? b2d4 e7e1 g1h2
5/16 -116 32 151759 d8d4 b2d4 e7b7 d1e1 b7c7
5/16 -119 39 184296 f4h2 g1h2 e7e5 f2f4 e5h5 h2g3 h5d1 d4f3
5/16 -173 43 209067 e7e5 b1c2 f4h2 g1h1 a4c2 b2c2 d8d4
So I changed it to fail-hard, and it doesn't happen any more.
Or would the above be caused by something else entirely?
Thanks to all who have contributed!
jm
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Return eval or upper bound?
Maybe there is some mate scoring problem in your code to store/retrieve hash table values? I think this code is affected, too, by the difference between fail-soft and fail-hard.JVMerlino wrote:Obviously, that mate in 2 score for Black is just dead wrong.Code: Select all
... 4/16 -109 12 26571 f4h2 g1h1 e7h4 b1c2 h2g3 h1g1 g3f2 g1f1 f2d4 c2a4 4/16 -116 14 31455 d8d4 b2d4 e7b7 d1e1 g8h8 4/16 -121 15 37123 e7c5! d1e1 4/16 -191 17 43245 e7c5 b7f7 g8f7 b2b7 f4c7 4/16 -32764 21 69743 d8d4 b7e7 5/10 -32724 21 72173 d8d4? b2d4 e7e1 g1h2 5/16 -116 32 151759 d8d4 b2d4 e7b7 d1e1 b7c7 5/16 -119 39 184296 f4h2 g1h2 e7e5 f2f4 e5h5 h2g3 h5d1 d4f3 5/16 -173 43 209067 e7e5 b1c2 f4h2 g1h1 a4c2 b2c2 d8d4
So I changed it to fail-hard, and it doesn't happen any more.
Or would the above be caused by something else entirely?
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Return eval or upper bound?
So my guesses were right, and my answer in my longer posting above is still valid.JVMerlino wrote:Sorry that my description was confusing. Here it is, in pseudo-code:
Should it be this:
or this:Code: Select all
... if (eval >= beta) return beta;
Code: Select all
... if (eval >= beta) return eval;
Sven
Re: Return eval or upper bound?
Yes and no. Fail-soft is a bit more error-prone. When you return a lower/upper bound it must be really a lower/upper bound. You must have a mistake somewhere. I don't know the cause this time but generally speaking with fail-soft (acording to sven it is fail-soft, I never remember which is which) when doing futility be carefull don't return a score excesively low because it never got updated.JVMerlino wrote: Obviously, that mate in 2 score for Black is just dead wrong.
So I changed it to fail-hard, and it doesn't happen any more.
Or would the above be caused by something else entirely?
Re: Return eval or upper bound?
now I got confused as am doing other thing but just believe me at least until where I said "be carefull".
adieguez wrote:Yes and no. Fail-soft is a bit more error-prone. When you return a lower/upper bound it must be really a lower/upper bound. You must have a mistake somewhere. I don't know the cause this time but generally speaking with fail-soft (acording to sven it is fail-soft, I never remember which is which) when doing futility be carefull don't return a score excesively low because it never got updated.JVMerlino wrote: Obviously, that mate in 2 score for Black is just dead wrong.
So I changed it to fail-hard, and it doesn't happen any more.
Or would the above be caused by something else entirely?