Bounds for aspiration window re-search

[Sven]

When using an aspiration window at the root together with any alpha-beta based search algorithm, how do I set alpha and beta bounds correctly in case of a fail-high or fail-low?

Let's assume a fail-soft framework (fail-hard will be similar) and the following code:

Code: Select all

int score = rootSearch(position, alpha, beta, maxDepth);
if &#40;score <= alpha&#41; &#123;
    score = rootSearch&#40;position, -INF, NEW_BETA, maxDepth&#41;;
&#125; else
if &#40;score >= beta&#41; &#123;
    score = rootSearch&#40;position, NEW_ALPHA, +INF, maxDepth&#41;;
&#125;

So what should NEW_BETA and NEW_ALPHA be?
1) NEW_BETA = score, NEW_ALPHA = score
2) NEW_BETA = score+1, NEW_ALPHA = score-1

(fail-hard: replace 'score' by 'alpha' and 'beta', respectively.)

My question arises since I am not quite sure what happens if the true minimax value of the search for the given 'maxDepth' is equal to 'score'. (In other cases there should not be any problem, I hope.)

- With solution 1), the re-search after failing low will immediately fail high since the best move returns 'score'. Is this cutoff o.k. or not?
- With solution 1), the re-search after failing high might fail to produce a PV since none of the moves improves over NEW_ALPHA. Is this o.k. or not? Note that I don't assume that the PVS algorithm is used; it might actually depend on the search algorithm.
- With solution 2), both seems to be corrected but at least the re-search after failing low will often need more nodes than solution 1).

Solution 1) is what can be read everywhere, so my guess is that it is the right solution. But I'd like to understand why. Any suggestions are welcome.

Sven

[sje]

A new bounded interval must always include all values in the previous interval. Bounds for a re-search at the root should only be loosened, not tightened.

[Sven]

A new bounded interval must always include all values in the previous interval. Bounds for a re-search at the root should only be loosened, not tightened.

I have not seen this definition yet. I think it is only required that the *value that is returned* from searching with the previous interval must be included in the new interval. (Note that I'm not talking about re-searches within the PVS algorithm.) This is fulfilled in both "solution 1/2" scenarios in my posting above:

- In "solution 1", the bounds are (-INF,score) for fail-low and (score,+INF) for fail-high. (Well-known.)
- In "solution 2", the bounds are (-INF,score+1) for fail-low and (score-1,+INF) for fail-high, which overlaps the original window in both cases.

Sven

[pijl]

A new bounded interval must always include all values in the previous interval. Bounds for a re-search at the root should only be loosened, not tightened.

I have not seen this definition yet. I think it is only required that the *value that is returned* from searching with the previous interval must be included in the new interval.

Without search instability (mainly due to null-move, but also due to LMR, extensions, etc) that would be true. However, if you do this in the real world you should be prepared for a fail-high, followed by a fail-low. Only allow widening the window is an easy way of handling this without adding too much cost (as the hashtable will guide you to a good alpha value quickly anyway).
Richard.

[Harald]

When using an aspiration window at the root together with any alpha-beta based search algorithm, how do I set alpha and beta bounds correctly in case of a fail-high or fail-low?

Let's assume a fail-soft framework (fail-hard will be similar) and the following code:

Code: Select all

int score = rootSearch(position, alpha, beta, maxDepth);
if &#40;score <= alpha&#41; &#123;
    score = rootSearch&#40;position, -INF, NEW_BETA, maxDepth&#41;;
&#125; else
if &#40;score >= beta&#41; &#123;
    score = rootSearch&#40;position, NEW_ALPHA, +INF, maxDepth&#41;;
&#125;

So what should NEW_BETA and NEW_ALPHA be?
1) NEW_BETA = score, NEW_ALPHA = score
2) NEW_BETA = score+1, NEW_ALPHA = score-1

(fail-hard: replace 'score' by 'alpha' and 'beta', respectively.)

My question arises since I am not quite sure what happens if the true minimax value of the search for the given 'maxDepth' is equal to 'score'. (In other cases there should not be any problem, I hope.)

- With solution 1), the re-search after failing low will immediately fail high since the best move returns 'score'. Is this cutoff o.k. or not?
- With solution 1), the re-search after failing high might fail to produce a PV since none of the moves improves over NEW_ALPHA. Is this o.k. or not? Note that I don't assume that the PVS algorithm is used; it might actually depend on the search algorithm.
- With solution 2), both seems to be corrected but at least the re-search after failing low will often need more nodes than solution 1).

Solution 1) is what can be read everywhere, so my guess is that it is the right solution. But I'd like to understand why. Any suggestions are welcome.

Sven

Perhaps it could be this way:

Code: Select all

int score = rootSearch(position, alpha, beta, maxDepth);
if &#40;score < alpha&#41; &#123;  // < instead of <=
    score = rootSearch&#40;position, -INF, alpha, maxDepth&#41;;
&#125; else
if &#40;score >= beta&#41; &#123;
    score = rootSearch&#40;position, beta, +INF, maxDepth&#41;;
&#125;

Using a half open interval, written [alpha,beta[ or [alpha,beta).
But this is just a new question, not an answer.

Harald

[Gian-Carlo Pascutto]

Perhaps it could be this way:

Code: Select all

int score = rootSearch(position, alpha, beta, maxDepth);
if &#40;score < alpha&#41; &#123;  // < instead of <=
    score = rootSearch&#40;position, -INF, alpha, maxDepth&#41;;
&#125; else
if &#40;score >= beta&#41; &#123;
    score = rootSearch&#40;position, beta, +INF, maxDepth&#41;;
&#125;

Using a half open interval, written [alpha,beta[ or [alpha,beta).
But this is just a new question, not an answer.

Harald

As stated in the post above yours, this is a bad idea because of search instability.

[Gian-Carlo Pascutto]

My question arises since I am not quite sure what happens if the true minimax value of the search for the given 'maxDepth' is equal to 'score'. (In other cases there should not be any problem, I hope.)

In this case, you will have no way to know if the search failed low or if it just happened to be equal to score.

[Harald]

Perhaps it could be this way:

Code: Select all

int score = rootSearch(position, alpha, beta, maxDepth);
if &#40;score < alpha&#41; &#123;  // < instead of <=
    score = rootSearch&#40;position, -INF, alpha, maxDepth&#41;;
&#125; else
if &#40;score >= beta&#41; &#123;
    score = rootSearch&#40;position, beta, +INF, maxDepth&#41;;
&#125;

Using a half open interval, written [alpha,beta[ or [alpha,beta).
But this is just a new question, not an answer.

Harald

As stated in the post above yours, this is a bad idea because of search instability.

That may be, but where does the instability come from?
I mean all the time during the search we rely on the scores and bounding
conditions and suddenly at the root we do not trust it any longer?
Could you give an example?

Would there also be a random result in the score if I just for fun
started tho searches with identical bounds and depth one after the other?

Without instability my code would be save since I do not even use score
in the re-search but alpha and beta only and even the corner cases
score == alpha or score == beta would be ok.

And even when there is an instability it could be a rare exception and a
good idea to use the narrow bounds in a first re-search and wide open
bounds in case of a second re-re-search. Perhaps this even tells us
something about the situation on board. I have not tested this or
really thought through it. There is certainly someone who has done it
and I would like to read some advice here. But please give a good and
easy to understand reason or example.

(And what posting "above mine" do you mean? The one I answered to
or the last one in the sub-thread that happens to be listed in the tree
one line above my posting. That may change any minute. Or are you
using that horrible flat view?)

Harald

[Edmund]

There are various reasons for search instability and it very much depends on your specific implementation.

Many of those are introduced with Transposition tables.
So it might happen that the second time you do a search there already exists an entry that wasn't there when you came to the same position the previous search. Often thats no problem, but there lie some potential risks for search instability.
Eg the value in the TT might come from a previous search that was searched deeper than the depth of the current node.
Or the node was searched as a NonPV node the last time (thus using nullmove pruning etc) and is now searched as a PV line (with Pruning).
If you are using Fractal extensions, the last time there might have been a different counter for fractal extensions.
One time you might have just estimated the result with lazy eval - the next time you want an exact score.
Another issue with TT is the replacement scheme.
Usually the result will only be off the actual score by a couple of cP, but sometimes it is this amount that decides whether a move gets pruned or researched, etc.

Another main cause for search instability are all sort of heuristics that rely on history information. If one decides whether to prune a move or not based on the number of beta-cut-offs a certain move has produced in the previous search, I think this is another obvious example for potential search instability.

[Gian-Carlo Pascutto]

That may be, but where does the instability come from?

Hashtables, nullmove, LMR, extensions that depend on alpha/beta, ...

I mean all the time during the search we rely on the scores and bounding
conditions and suddenly at the root we do not trust it any longer?
Could you give an example?

Yes, the root is special. At the root, you NEED a move. In other nodes, just a score is enough.

If you have a search instability and get a search result that indicates "fail low", you will not have any (reliable) move associated with that score.

Actually, in Deep Sjeng, I always open the window so I can get a PV, even inside the tree. Having a reliable PV is worth something.