Fail Soft Alpha Beta & Transpositions
Orhan Öztürk
I am trying to implement fail soft version of AB.I already implemented
vanilla version,it works perfectly but i wonder the performance
difference so i decided to implement FAB.
I read many articles on fail soft AB and TT usage together with
FAB.But i could not understand a point.All say same thing,but i could
not get it.
Let me explain it.
While in search function,
* If the current score is greater than beta then stop searching this
node and store the score(not beta) to the TT.And put a flag that
denotes this is a lower bound since we did not search all child
nodes.This is a lower bound because pruned child nodes could increase
the score,if we searched all.(Here is no problem)
* If the current score is between alpha and beta then this is a exact
score since we searched everything below it.So store the score and
adjust the flag so that it donates this is a exact score.(No problem)
* This is the problematic part which i could not understand.Lets
say,we searched every child node and the score could not beat
alpha.This means that all child nodes are worthless.But,nevertheless
we want to store the best move and score for later move ordering(This
is the main difference with vanilla version).At this point,in the
vanilla version,we store alpha and name the flag as upper bound.Since
it is clear that score is less than alpha.
In FAB,
Here i dont know what to store to TT.Accoring to articles,the score is
an upper bound.But,IMO,it is an exact value since we searched all
child nodes.I think,it is not important if the score is between alpha
and beta for naming the flag as exact.The important thing is if we
searched all child nodes or not.Am i wrong?
(Maybe i am missing something)
How should i store the flag to TT at this point?Is it upper or exact ?
Thanks.
Orhan Ozturk
Gian-Carlo Pascutto
> Here i dont know what to store to TT.Accoring to articles,the score is
> an upper bound.But,IMO,it is an exact value since we searched all
> child nodes.I think,it is not important if the score is between alpha
> and beta for naming the flag as exact.The important thing is if we
> searched all child nodes or not.Am i wrong?
> (Maybe i am missing something)
In the subtree, you got a score >= beta. There's no guarantee there
won't be a score that's even more 'bigger than beta' since you stop
searching after the first such score.
Hence, your score cannot be exact.
--
GCP
Robert Hyatt
> Hi,
> Let me explain it.
> While in search function,
The main difference is that with normal alpha/beta, _all_ scores you
store are >=alpha and <=beta. With fail-soft, you store whatever is
backed up, even if it is > beta or < alpha. When you have searched _all_
moves at a node, you have two outcomes:
(1) best score is > alpha and < beta (if it were >= beta you should have
already stopped searching.) This is an EXACT score.
(2) best score is <= alpha. This means this score is an upper bound,
that the true score could be lower.
> How should i store the flag to TT at this point?Is it upper or exact ?
> Thanks.
> Orhan Ozturk
--
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
Dr A. N. Walker
=?ISO-8859-1?Q?Orhan_=D6zt=FCrk?= <ooz...@porttakal.com> wrote:
> [...].The important thing is if we
>searched all child nodes or not.Am i wrong?
Yes. The important thing is what we know about the
children. If we searched them *and* got exact scores, then
we know an exact return. But if we got only bounds, because
of beta cutoffs [ie, some of the grandchildren weren't looked
at], then we know only a bound.
When searching children, if [eg] your alpha and beta
bounds are close to zero, then winning a pawn will cause a
beta cutoff [other things being equal], but you may have missed
the win of a queen. That is the beta bound that you understand.
If your move *loses* a pawn "at first glance" [so to speak], eg
in the principal variation, then your child will similarly have
a beta cutoff but may have missed winning a queen, and so *you*
may have missed *losing* a queen.
[In human terms, this is actually the more intuitive
part of alpha-beta pruning. If you see that a move is bad,
eg that it loses a pawn, then you don't consider it further,
and in particular you don't waste time determining exactly
how bad it really is. But the computer only knows you lose
a pawn because it has analysed further, and the other player
is seen to be able to win a pawn.]
--
Andy Walker, School of MathSci., Univ. of Nott'm, UK.
a...@maths.nott.ac.uk
Orhan Öztürk
Ok I understand what you mean.Then i have a second question.
Lets say our alpha bound +1.0 and beta bound is +2.0.We searched all
child nodes and the returned value is +1.1 According to articles,this
should be stored as an exact value and when this position is probed
the value should be returned immediately(if depth,hash key etc are
ok).(IMO this is only correct if all child nodes are leaf)
What if the current node has at least one terminal child node?In this
case,there is probability of failing high in this node.Even though the
score is +1.1 and between bounds,maybe this score came from a beta cut
off!If so,this means that,this position value is at most +1.1.And can
be less.And maybe it is less than alpha!(because so close).So how can
I be sure that it is an exact value?Is the type of child nodes
important?(IMO,it's important).Or I am still missing something?
Regards...
Gian-Carlo Pascutto
> case,there is probability of failing high in this node.Even though the
> score is +1.1 and between bounds,maybe this score came from a beta cut
> off!
If the score is between bounds, it cannot have been coming from a fail
high (beta-cut) or a fail low.
You don't seem to understand how alpha beta itself works.
--
GCP