Aspiration Window Instability?

[Meesha]

I recently added aspiration windows to my search and for debugging purposes ran a bunch of positions while having the engine display the current alpha and beta and the scores returned to make sure the window was expanding correctly after fail highs/lows etc...It seems to work fine but I noticed i sometimes get a situation where lets say the previous score from a depth 15 search was +30. Now at depth 16 i search the previous best move with a window of +10 / +50, at which point it fails low and preforms a re-search with a window of -10 / +50 and returns a score of like +15 (inside the initial window). Is this type of search instability common? It doesn't happen all the time, but certainly more often than I thought would occur.

[emadsen]

Is this type of search instability common? It doesn't happen all the time, but certainly more often than I thought would occur.

Yes, this is well known. See Remove Aspiration Windows and Are Aspiration Windows Worthless?

I asked chess programmers how much ELO they got from aspiration windows. I received mixed answers. Many got a measurable gain, some (like me) got no gain or an ELO loss. I'm not sure if that's due to different search implementations (fail-hard versus fail-soft) or a bug in my implementation of aspiration windows. One issue everyone agreed on is aspiration windows do cause search instability. Your observation of scores that bounce between failing low and failing high only to settle on a score that was inside the initial window (wasting time) has been observed by others.

[Meesha]

Thanks Erik. I notice the aspiration code you removed from Madchess had successive windows on the order of
{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 5000, Infinte}. Maybe thats a problem for your engine. Like most people I use an open window until depth 5....then i use previous score +/- 18 centipawns. In most stable positions thats good enough to get a PV move quickly and have the remaining moves fail low using PVS. In the event of a fail high/low i expand the window in the appropriate direction another 20 cps, then another 100, then another 325 before opening the window completely. So I'm basically covering the scenarios where a move gains a small/medium positional advantage, a big positional/small material advantage (winning a pawn), and a big material advantage (winning a piece). But after that i just open completely. I dont want to get bogged down with too many re-searches, particularly with search instability. I also aesthetically like my engine to be able to find mates quickly without doing a tonne of re-searches. In fact when alpha is a guaranteed won score (lone king vs sufficient mating material), I open the window completely after the first fail/high so I can find the mate quickly. I know Stockfish opens the window very slowly, but it searches so fast I guess it can get away with it. For me this strikes the right balance. Maybe you should give it another try by reducing the number of times you widen the window?

[emadsen]

Thanks Erik. I notice the aspiration code you removed from Madchess had successive windows on the order of
{100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 5000, Infinte}. Maybe thats a problem for your engine.

Those windows are for MultiPV where the user specifies how many moves (say, x) they'd like analyzed and the engine must figure out how wide of a score window is required to fit MultiPV = x moves. MadChess does a single root search for MultiPV. Other engines may do x successive root searches, each search excluding one more move from the x-1 search.

For single PV, MadChess used aspiration windows of 100, 500, infinite with a minimum depth of 7. Even restricting aspiration windows so they kick in only after 7 ply and quickly expand from 100 to 500 to infinite, I didn't find any strength improvement over fail-hard + PVS. And I noticed the search instability you mentioned in your first post. So I removed aspiration windows from MadChess' (default) competitive search.

I did keep aspiration windows for MultiPV and UCI_LimitStrength.