Are Aspiration Windows Worthless?

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.
User avatar
emadsen
Posts: 248
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Are Aspiration Windows Worthless?

Post by emadsen » Sun Dec 20, 2020 8:44 pm

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.
My C# chess engine: https://www.madchess.net

User avatar
emadsen
Posts: 248
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Are Aspiration Windows Worthless?

Post by emadsen » Sun Dec 20, 2020 8:51 pm

I should add MadChess uses PVS.
My C# chess engine: https://www.madchess.net

Dann Corbit
Posts: 12034
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Are Aspiration Windows Worthless?

Post by Dann Corbit » Sun Dec 20, 2020 9:05 pm

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);
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
hgm
Posts: 25904
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Are Aspiration Windows Worthless?

Post by hgm » Sun Dec 20, 2020 10:20 pm

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.

User avatar
emadsen
Posts: 248
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Are Aspiration Windows Worthless?

Post by emadsen » Sun Dec 20, 2020 10:54 pm

Dann Corbit wrote:
Sun Dec 20, 2020 9:05 pm
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.
My C# chess engine: https://www.madchess.net

Ras
Posts: 1785
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Are Aspiration Windows Worthless?

Post by Ras » Mon Dec 21, 2020 12:36 am

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.
Rasmus Althoff
https://www.ct800.net

Joost Buijs
Posts: 1255
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Are Aspiration Windows Worthless?

Post by Joost Buijs » Mon Dec 21, 2020 7:48 am

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.

User avatar
emadsen
Posts: 248
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Are Aspiration Windows Worthless?

Post by emadsen » Mon Dec 21, 2020 8:17 pm

hgm wrote:
Sun Dec 20, 2020 10:20 pm
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.
hgm wrote:
Sun Dec 20, 2020 10:20 pm
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.
Ras wrote:
Mon Dec 21, 2020 12:36 am
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.
Joost Buijs wrote:
Mon Dec 21, 2020 7:48 am
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.
My C# chess engine: https://www.madchess.net

Karlo Bala
Posts: 336
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Are Aspiration Windows Worthless?

Post by Karlo Bala » Mon Dec 21, 2020 8:18 pm

emadsen wrote:
Sun Dec 20, 2020 8:44 pm
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).
Best Regards,
Karlo Balla Jr.

Dann Corbit
Posts: 12034
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Are Aspiration Windows Worthless?

Post by Dann Corbit » Mon Dec 21, 2020 11:39 pm

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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Post Reply