Are Aspiration Windows Worthless?

[emadsen]

They are for MadChess. I posted a detailed explanation on my blog at MadChess 3.0 Beta 4b7963b (Remove Aspiration Windows). Long story short: problems with search instability... fail high, fail low, fail high again, etc.

In the following position, MadChess, when using aspiration windows, struggles to find Magnus Carlsen's d6! move. Sometimes it finds it after four minutes. Other times it doesn't find it even after 18 minutes. (My engine, though single-threaded, has a non-deterministic search. See blog post for explanation.)

[d]2r2rk1/1ppq2b1/1n6/1N1Ppp2/p7/Pn2BP2/1PQ1BP2/3RK2R w K – 0 23

If I disable (or remove entirely) aspiration windows, MadChess find's Carlsen's move after searching for 45 seconds. In a gauntlet tournament against ten opponents, MadChess performed 9 ELO stronger without aspiration windows than when using them.

Chess engines being the fickle little monsters they are, your particular move ordering logic, search reduction conditions, evaluation parameters, etc in your engine may not produce the pathological behavior MadChess exhibits when searching the above position using aspiration windows. But perhaps you've observed similar behavior in your engine for a different position and decided to remove aspiration windows? Or perhaps you wrote aspiration window code a long time ago and haven't tested it recently. If you remove it now, does your engine play stronger or weaker?

I admit, I tested this change with only 4,000 games so it's possible removing aspiration windows from MadChess actually is a regression, not an improvement. I found a 9 ELO improvement though the 95% confidence error bar is +/- 17 ELO. This is a hobby not nuclear engineering. 4,000 games represents the maximum time and energy I'm willing to expend to answer the question.

Anyhow, I'm interested to hear about your experience with this issue.

[emadsen]

I should add MadChess uses PVS.

[Dann Corbit]

Do you mean that your search window is +/- infinity for every search?
I don't understand how that could be better.
Or is it something else?

Obviously, your pvs non-pv node searches are zero window.

Stockfish uses:

Code: Select all

            // Reset aspiration window starting size
            if (rootDepth >= 4)
            {
                Value prev = rootMoves[pvIdx].previousScore;
                delta = Value(17);
                alpha = std::max(prev - delta,-VALUE_INFINITE);
                beta  = std::min(prev + delta, VALUE_INFINITE);

[hgm]

Aspiration windows are tricky, and a bit of a kludgy device. The assumption is that disaster never happens. So if you get a certain score at depth D, you will likely get a a not-too-different score at D+1. So if somewhere half-way the PV it doesn't seem like you can get that, you count on switching move in a node that led to there to cure the problem, rather than spending large amounts of time for figuring out how bad things really get.

If the assumption is correct, this is a big time saver. Sometimes it is wrong, however, and your root score will drop spectacularly. Then you get pathological behavior, as the search will now fail low in the root. And keep failing low as long as you don't spectacularly increase the aspiration window. Stockfish increases it in very small steps, and in troublesome positions it can get many dozens of fail lows before it finally gets a score at that depth.

Point is that this tends to happen in positions that are decided (without the engine having realized it). So it doesn't matter much what you do there, no matter how bad it is, it won't lose you any Elo. It is just annoying during analysis.

The whole idea is a bit inconsistent, because it only controls the aspiration window in the root. Intuitively you would expect the chances that you have a better alternative along the path to the current node to be better if that path was long. I.e. deep in the tree you can be more demanding w.r.t. the score you expect, than very close to the root. So you could set an aspiration window in every PV node independently, the higher the ply, the narrower the window.

[emadsen]

Do you mean that your search window is +/- infinity for every search?

Yes, +/- infinity for every search (with PVS) is stronger than using aspiration windows. Presumably because the researches caused by failing high or low are too costly.

[Ras]

I'm using a +/- 50 centipawns window from depth 4 onwards (fully open window before that), and it did yield some Elo. However, anything else than the most simple solution failed: I'm doing a re-search with half-open window if I'm failing high or low.

With fail-high, I record the move that failed high as answer move so that even if the time isn't sufficient to nail it down, I'll just do that. In case the relevant root move isn't the one that is already in the PV, I'm moving it up.

With fail-low, I tried giving more time to resolve that (panic mode), but that didn't turn out well - presumably because that's in "too little, too late" situations where it's lost anyway. I just use whatever the PV is at that point, and if time runs out before the fail-low is resolved, I don't care.

[Joost Buijs]

I start with a fully open window for depths 1 to 3, from depth 4 on-wards I use a window of +/- 15 CP. With a fail low/high I open up the window with exponential steps in one direction only.

Most of the time my search/evaluation is stable enough to keep the root-scores within the 15 CP window. If the search fails low I give the engine up to 5 times the target time to try resolving the problem. If the search fails high I don't try to resolve it but immediately skip to the next iteration/depth with an adjusted window.

Recently I started experimenting with a NN which gives very unstable root scores, the +/- 15 CP window seems way to small now, I have to widen it up a lot or try to generate a more stable network.

[emadsen]

Aspiration windows are tricky, and a bit of a kludgy device. The assumption is that disaster never happens.

I agree with you, H.G. The technique seems kludgy to me. I never liked it. I added it years ago when I was new to chess programming, less disciplined about testing, and under the assumption it was a "must have" feature. I'm skeptical now and have hard data to show it.

If the assumption is correct, this is a big time saver. Sometimes it is wrong, however, and your root score will drop spectacularly. Then you get pathological behavior... The whole idea is a bit inconsistent, because it only controls the aspiration window in the root.

Kludgy and asymmetric as you say. Why just the root? The idea seems more trouble than it's worth. From what I've read, most people report only modest strength gains, on the order of 10 or 15 ELO.

With fail-high, I record the move that failed high as answer move so that even if the time isn't sufficient to nail it down, I'll just do that.

I'm not comfortable trusting a best move that's not been fully searched considering the bizarre fail high, low, high again search instability I've observed with aspiration windows. I'd prefer to return a move the engine has fully searched and confirmed is within the alpha / beta bounds. Otherwise I feel I'm subverting the correctness of the alpha / beta algorithm.

Recently I started experimenting with a NN which gives very unstable root scores, the +/- 15 CP window seems way to small now, I have to widen it up a lot or try to generate a more stable network.

Interesting. Perhaps related: MadChess limits quiescence searches to recaptures only when beyond three moves past the horizon. This is meant to prevent an explosion of the size of the search tree and encourage more predictable search times. I've noticed this causes unstable root scores in complex middlegame positions. Though I tested it and remember confirming a strength gain of 10 or 15 ELO. The position I cite in my blog post is a middegame position with 47 legal moves. Perhaps the position induces interference between quiescence recapture-only pruning and aspiration windows?

Here we go with another one of those difficult questions that takes a lot of CPU hours to answer to a sufficient degree of certainty. I either have to spend time and energy investigating whether my implementation is buggy, or whether components of my search interact in subtle ways not seen in top-class engines, or just delete aspiration window code from my engine (like I've done) and not worry about whether I'm "leaving cash (ELO) on the table" to borrow poker terminology.

What tips the balance in favor of ripping out aspiration windows, in my opinion, is the chess engine should be capable of pivoting quickly to a new best move. If it "sees" tactics that it was blind to one ply earlier, I don't want to put barriers in place (resolving fail low / high windows) that prevent it from committing to the new move or deciding it's unsound. I want the engine to turn quickly like a speedboat. I don't want it lumbering like an aircraft carrier though a five mile turn.

[Karlo Bala]

They are for MadChess. I posted a detailed explanation on my blog at MadChess 3.0 Beta 4b7963b (Remove Aspiration Windows). Long story short: problems with search instability... fail high, fail low, fail high again, etc.

In the following position, MadChess, when using aspiration windows, struggles to find Magnus Carlsen's d6! move. Sometimes it finds it after four minutes. Other times it doesn't find it even after 18 minutes. (My engine, though single-threaded, has a non-deterministic search. See blog post for explanation.)

[d]2r2rk1/1ppq2b1/1n6/1N1Ppp2/p7/Pn2BP2/1PQ1BP2/3RK2R w K – 0 23

If I disable (or remove entirely) aspiration windows, MadChess find's Carlsen's move after searching for 45 seconds. In a gauntlet tournament against ten opponents, MadChess performed 9 ELO stronger without aspiration windows than when using them.

Chess engines being the fickle little monsters they are, your particular move ordering logic, search reduction conditions, evaluation parameters, etc in your engine may not produce the pathological behavior MadChess exhibits when searching the above position using aspiration windows. But perhaps you've observed similar behavior in your engine for a different position and decided to remove aspiration windows? Or perhaps you wrote aspiration window code a long time ago and haven't tested it recently. If you remove it now, does your engine play stronger or weaker?

I admit, I tested this change with only 4,000 games so it's possible removing aspiration windows from MadChess actually is a regression, not an improvement. I found a 9 ELO improvement though the 95% confidence error bar is +/- 17 ELO. This is a hobby not nuclear engineering. 4,000 games represents the maximum time and energy I'm willing to expend to answer the question.

Anyhow, I'm interested to hear about your experience with this issue.

It is possible that your transposition tables are just not well suited for small aspiration windows. From my experience, it is best if you use a separate score/depth for alpha and beta, like in TT for mtd(f).

[Dann Corbit]

It does seem to be an interesting and complex subject.
Suppose, for instance, that you were up a queen and suddenly you fail low.
Perhaps you will be at +7 pawns after several re-searches, perhaps at +5 pawns or perhaps it is suddenly losing.
If you do not perform the full re-search to a resolution and simply move on to the next move, what if the next move is already losing?
Immediately going on to the next move would have value if and only if the move that fails low is worse after re-search than the best alternative.
We do not know if this is true or not, a-priori.
One alternative could be to store the next best score from the previous iteration (and possibly the next best move so we can search it first) along with alpha and beta.
The next best score could be used for the bottom of the window to search.
As soon as that second highest score appears higher than the move that is failing low, we can stop searching the current node and start searching the alternatives.
Let's call it alpha-beta-gamma search.