(Fail soft) alpha beta
Delphi
I would like to know, what the difference between "normal" alpha-beta
and fail-soft alpha-beta is, concerning the usage of the returned values.
As far as I know, alpha-beta will always return values >= alpha and <= beta.
Fail-soft on the contrary could also return something < alpha or > beta.
How could this be used?
It seems to me, that narrower windows are better.
And is there probably a third variant, that returns values >= alpha
and _maybe_ > beta (this, as from my viewpoint the upper scores
are more important for possible cutoffs)?
Thanks,
-delphi-
Bo Persson
"Delphi" <del...@kabsi.at> skrev i meddelandet
news:10627066...@news.aic.at...
> Hi!
>
> I would like to know, what the difference between "normal"
alpha-beta
> and fail-soft alpha-beta is, concerning the usage of the returned
values.
> As far as I know, alpha-beta will always return values >= alpha and
<= beta.
> Fail-soft on the contrary could also return something < alpha or >
beta.
Correct.
> How could this be used?
It could tell you something about how far outside the search window
the real score is.
If you start your search with a window smaller that +/-inifinity, you
will sometimes have to research with a larger window. Any indications
of how far outside the score is, can be useful.
> It seems to me, that narrower windows are better.
In "hard" alpha-beta you will just get the results below alpha, within
the window, or above beta. Sometimes it can be useful to get "way
below alpha" or "at least beta + 500".
>
> And is there probably a third variant, that returns values >= alpha
> and _maybe_ > beta (this, as from my viewpoint the upper scores
> are more important for possible cutoffs)?
I have never seen that.
>
> Thanks,
> -delphi-
>
Bo Persson
Delphi
"Bo Persson" <bo...@telia.com> schrieb im Newsbeitrag
news:WWN5b.26939$dP1....@newsc.telia.net...
>
> "Delphi" <del...@kabsi.at> skrev i meddelandet
> news:10627066...@news.aic.at...
> > Hi!
> >
> > I would like to know, what the difference between "normal"
> alpha-beta
> > and fail-soft alpha-beta is, concerning the usage of the returned
> values.
> > As far as I know, alpha-beta will always return values >= alpha and
> <= beta.
> > Fail-soft on the contrary could also return something < alpha or >
> beta.
>
> Correct.
>
> > How could this be used?
>
> It could tell you something about how far outside the search window
> the real score is.
>
> If you start your search with a window smaller that +/-inifinity, you
> will sometimes have to research with a larger window. Any indications
> of how far outside the score is, can be useful.
>
> > It seems to me, that narrower windows are better.
>
> In "hard" alpha-beta you will just get the results below alpha, within
> the window, or above beta. Sometimes it can be useful to get "way
> below alpha" or "at least beta + 500".
Is it correct, that when using the fail-soft case, we have to have something
like a best score (instead of "starting" with alpha), which is initialized
with
the lowest possible value, which will only then be returned, if there is no
non-mate move?
>
> >
> > And is there probably a third variant, that returns values >= alpha
> > and _maybe_ > beta (this, as from my viewpoint the upper scores
> > are more important for possible cutoffs)?
>
> I have never seen that.
>
> >
> > Thanks,
> > -delphi-
> >
>
>
> Bo Persson
>
-delphi-
Bo Persson
>
> "Bo Persson" <bo...@telia.com> schrieb im Newsbeitrag
> news:WWN5b.26939$dP1....@newsc.telia.net...
> >
> >
within
> > the window, or above beta. Sometimes it can be useful to get "way
> > below alpha" or "at least beta + 500".
>
> Is it correct, that when using the fail-soft case, we have to have
something
> like a best score (instead of "starting" with alpha), which is
initialized
> with
> the lowest possible value, which will only then be returned, if
there is no
> non-mate move?
Sort of, yes.
The fail-soft variant is often used with a windowed search, where you
have (or guess :-) an initial value. This could be the score for the
previous search or, for the inital position, 0.
So, if you start the search with a window estimated_score +/-
window_size, and the true score is within the window, the search will
terminate much faster. The smaller the window, the faster the search
terminates, *if* the score is within the window.
If all scores fell outside the search window, you will of course have
to reasearch with a "better" window. Here a fail-soft result *might*
help finding a proper window, so you perhaps can avoid a +/-infinity
search.
The window_size and good values for the initial guess depends on how
your program scores positions, so you will have to experiment some.
Bo Persson
Delphi
And if I use TTs (the usual depth, value, and bounds stuff) should/could I
store the values outside the range and not only alpha or beta?
-delphi-
Robert Hyatt
> Hi!
> I would like to know, what the difference between "normal" alpha-beta
> and fail-soft alpha-beta is, concerning the usage of the returned values.
> As far as I know, alpha-beta will always return values >= alpha and <= beta.
> Fail-soft on the contrary could also return something < alpha or > beta.
> How could this be used?
> It seems to me, that narrower windows are better.
The advantage of fail-soft is that when you fail high or low at the
root, you have some idea about how much better the real score will
be.
IE with normal alpha/beta with a root aspiration window, you get beta
back, telling you to re-search with a higher beta bound. But how much
higher? .4, or 4.0???
fail-soft will return a better estimate on a lower bound for the new best
move, to give you some idea of how far to raise beta.
That's the main difference.
> And is there probably a third variant, that returns values >= alpha
> and _maybe_ > beta (this, as from my viewpoint the upper scores
> are more important for possible cutoffs)?
> Thanks,
> -delphi-
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Dieter Buerssner
> And if I use TTs (the usual depth, value, and bounds stuff)
> should/could I store the values outside the range and not only alpha
> or beta?
Yes, you could, and you should! However it may introduce some other very
subtle problems. Espescially, when you already use null move or other
pruning techniques. To give an idea about this problem. Sometimes, null
move will fail high with a certain window. With a different (from the view
of side to move, higher scores) it may not fail high again. So you do the
normal alpha-beta search. It can be the case, that this first beta cutoff
of the null move was just wrong. Searching "normally" would have proven it.
Fail soft alpha-beta search can hide this (you will search in general with
a different window, than fail hard alpha-beta search).
Anyway, I use fail soft search, and I store the bounds as found (which can,
as you had mentioned be outside of the alpha-beta window) in the
transposition tables. I believe, it is better in most cases.
Regards,
Dieter
Noah Roberts
> Delphi wrote:
>
>
>>And if I use TTs (the usual depth, value, and bounds stuff)
>>should/could I store the values outside the range and not only alpha
>>or beta?
>
>
> Yes, you could, and you should! However it may introduce some other very
> subtle problems. Espescially, when you already use null move or other
> pruning techniques. To give an idea about this problem. Sometimes, null
> move will fail high with a certain window. With a different (from the view
> of side to move, higher scores) it may not fail high again. So you do the
> normal alpha-beta search. It can be the case, that this first beta cutoff
> of the null move was just wrong. Searching "normally" would have proven it.
> Fail soft alpha-beta search can hide this (you will search in general with
> a different window, than fail hard alpha-beta search).
So how do you fix this problem? I ran into this repeatedly with the
MTD(f) algorithm in my engine. I never found a fix and would like to
avoid reintroducing it into the new one.
Dieter Buerssner
> So how do you fix this problem? I ran into this repeatedly with the
> MTD(f) algorithm in my engine. I never found a fix and would like to
> avoid reintroducing it into the new one.
I fear, there is no general fix. Introducing pruning (and extensions) into
a normal alpha-beta search, will do some errors.
Did you see the problems only with fail-soft?
Regards,
Dieter
Noah Roberts
No, the nega-scout routine also had problems (in fact worse) and it was
not fail-soft.
>
> Regards,
> Dieter
Dieter Buerssner
> Dieter Buerssner wrote:
>> Did you see the problems only with fail-soft?
>
> No, the nega-scout routine also had problems (in fact worse) and it
> was not fail-soft.
Do you really mean nega-scout? As introduced in:
A. Reinefeld. An Improvement of the Scout Tree Search Algorithm. ICCA
Journal 6,4 (1983), pp. 4-14. http://www.zib.de/reinefeld/bib/83icca.pdf
I believe nega-scout will not work in any modern chess program, which does
pruning, extensions and quiescence search. For me, the detail which really
differentiates between nega-scout and PVS, is Reinefeld's clever
observation, that you will not need to research after a zero-window fail
high close to the leaf. But that will only work with predictable depth (and
when you use qsearch or extensions, the "real" depth is not predictable
anymore).
Also note, that the formulation in Reinefeld's paper can leave you without
a PV in a research case.
Regards,
Dieter
Noah Roberts
This is probably why the engine often had no PV and so no move to make
when it was done thinking. Yeah, I stopped using it.
>
> Regards,
> Dieter