Returning score

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Returning score

Post by Kempelen » Thu Jun 05, 2008 7:44 pm

I have seen implementation of alpha-beta that run:

Code: Select all

if (score>=beta) return beta
and others that go

Code: Select all

if (score>=beta) return score
I understand the first, but dont understand exactly why the second. Even with hash table implementation, where a low cut is store, same implementation return the score and not beta.

Could somebody explain what's the point?

thx.

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Returning score

Post by Pradu » Thu Jun 05, 2008 9:23 pm

Kempelen wrote:I have seen implementation of alpha-beta that run:

Code: Select all

if (score>=beta) return beta
and others that go

Code: Select all

if (score>=beta) return score
I understand the first, but dont understand exactly why the second. Even with hash table implementation, where a low cut is store, same implementation return the score and not beta.

Could somebody explain what's the point?

thx.
If a search fails high (score>=beta), it becomes a lower-bound for the current position (work through a small made-up alphabeta tree and you'll immediately see why--you can do a similar experiment and find that if a score fails low (score<=alpha), it becomes an upper-bound for the current position).

If (score>=beta), it is safe to return score to the parent node because it will fail low at the parent node and get thrown away. In addition, when you store in the hashtable before returning, the hashtable can use the information to cutoff other parts of the tree which it couldn't cutoff if you only stored beta in the hashtable because score is a better lower-bound than beta.

Sven
Posts: 4023
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Returning score

Post by Sven » Thu Jun 05, 2008 10:18 pm

Hi,

two different algorithms, where one is a slightly improved variant of the other:

"return beta" belongs to the plain alpha-beta algorithm which may also be called "fail hard alpha-beta". When working with aspiration windows, and your search at the root node fails high with a score >= beta, then it is really "score == beta", and you do a re-search with a window like "beta / +INF". Similar things apply to the "fail low" case (score == alpha).

"return score" belongs to the "fail soft alpha-beta" algorithm which has the advantages that Pradu has described in his answer. Especially at the root node you get tighter bounds for a possibly required re-search.

Sven

Post Reply