185 views

Skip to first unread message

Sep 3, 2003, 5:44:30 AM9/3/03

to

Hi,

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

Sep 3, 2003, 6:45:28 AM9/3/03

to

> 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)

> 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

Sep 3, 2003, 11:39:18 AM9/3/03

to

Orhan <ooz...@porttakal.com> wrote:

> Hi,

> 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

Sep 3, 2003, 12:00:45 PM9/3/03

to

In article <532069cf.03090...@posting.google.com>,

=?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?

=?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

Sep 10, 2003, 11:01:12 AM9/10/03

to

"Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message news:<cDj5b.16954$QA2.7...@phobos.telenet-ops.be>...

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...

Sep 10, 2003, 11:58:18 AM9/10/03

to

> 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!

> 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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu