Returning score

[Kempelen]

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]

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]

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