Return eval or upper bound?

[JVMerlino]

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

[Sven]

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.

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.

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

[JVMerlino]

Hi Sven,

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;
}

or this:

Code: Select all

if (eval > alpha)
{
...save best move
...update pv

alpha = eval;
if (eval >= beta)
    return eval;
}

jm

[hgm]

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.

[bob]

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.

Also adds a bit of instability, although I still use it. unstable != bad, just a pain at times when debugging or testing.

[JVMerlino]

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.

Also adds a bit of instability, although I still use it. unstable != bad, just a pain at times when debugging or testing.

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?

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 

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?

Thanks to all who have contributed!

jm

[Sven]

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 

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?

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.

Sven

[Sven]

Sorry that my description was confusing. Here it is, in pseudo-code:

Should it be this:

Code: Select all

...
if (eval >= beta)
    return beta;

or this:

Code: Select all

...
if (eval >= beta)
    return eval;

So my guesses were right, and my answer in my longer posting above is still valid.

Sven

[adieguez]

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?

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.

[adieguez]

now I got confused as am doing other thing but just believe me at least until where I said "be carefull".

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?

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.