Are Aspiration Windows Worthless?

[Ferdy]

Don't you hate it when the bug does better than the correct code

Not necessarily as ignoring fail highs needs to be tested as well. Testing may give you 2 results, bad and good one can learn from these two.

[Ferdy]

Final result after 1000 games. The fix loses by 4 games.

Your error margin is +/- 31.5 points with 1000 games, so all you can conclude is that it has no major impact either way.

Right, more testing has to be done, we don't even know what will happen if TC is increased.

[Ras]

Btw., I tested my simple approach of -/-50 centipawns from depth 4 onwards and half-open window with fail high/low against no window at all, and the result was +18 Elo (52.5%) over 10k games at 10s/game. The usual depth is 8-10 plies at that time control.

[Ferdy]

Btw., I tested my simple approach of -/-50 centipawns from depth 4 onwards and half-open window with fail high/low against no window at all, and the result was +18 Elo (52.5%) over 10k games at 10s/game. The usual depth is 8-10 plies at that time control.

What do you mean by

half-open window with fail high/low against no window at all

[Ras]

What do you mean by

half-open window with fail high/low against no window at all

Testing two versions against each other with different root window handling. One uses a +/- 50 centipawns window and re-searches with half-open window upon fail high/low. The other always searches with fully open window.

[shinkarom]

I am wary about aspiration windows. It seems to me not as straightforward as other, more basic techniques. Or, maybe because I haven't implemented it even once, I just can't understand it.

[Joost Buijs]

It all depends very much upon the quality of the evaluation-function and the quiescence-search. When you play a game against an engine with aproximately the same strength the root-score will deviate only a few centipawns during the whole game and you can set a very narrow window without having to research anything.

Usually scores go up or down very gradually, only if one of the parties makes a mistake you will see a sudden score jump up or down, most of the time it's already too late when this happens. Then it is game over anyway.

If you have a bad evaluation-function or problems with your quiescence-search the root-score will jump all over all over the place, in this case aspiration-search is counter productive. This doesn't mean it's a worthless technique.

[Karlo Bala]

It all depends very much upon the quality of the evaluation-function and the quiescence-search. When you play a game against an engine with aproximately the same strength the root-score will deviate only a few centipawns during the whole game and you can set a very narrow window without having to research anything.

Usually scores go up or down very gradually, only if one of the parties makes a mistake you will see a sudden score jump up or down, most of the time it's already too late when this happens. Then it is game over anyway.

If you have a bad evaluation-function or problems with your quiescence-search the root-score will jump all over all over the place, in this case aspiration-search is counter productive. This doesn't mean it's a worthless technique.

We can offset that problem partially with a good TT. IMO, the most important thing is to have 2 values for depths and 2 values for scores, one for fail high, and one for fail low. If TT has only one value per position there would much fewer transpositions since the search will oscillate between fail low and fail high and overwrite again and again one with another.

[Ferdy]

Tested another method. Start at iter 4, Ignore fail highs and use fix fail low window margin when expanding the window. But similar to default to quickly reset the bounds to inf when there is successive fail lows. Default also tries to resolve the fail highs.

Code: Select all

aspWindow = 30
aspFailLowTries = 2
alpha = -INF
beta = INF

for (iter = 1 to max_iter) {

	score = search(alpha, beta ...)

	if (aspWindow && iter > 3) {
		// Fail low
		if (score <= alpha) {
			fLow++

			if (fLow >= aspFailLowTries) {
				alpha = -INF
				beta = INF
				iter--
				continue
			}
			else {
				alpha = score - aspWindow
				beta = score
				iter--
				continue
			}
		}

		alpha = score - aspWindow
		beta = score + aspWindow
		fLow = 0
	}
}

Result is promising so far against my default Deuterium v2021.1.38.1, at TC 3m+1s (more curious). Deuterium v2021.1.38.2 is using the above method.

Code: Select all

Score of Deuterium v2021.1.38.2 vs Deuterium v2021.1.38.1: 72 - 41 - 214  [0.547] 327
...      Deuterium v2021.1.38.2 playing White: 44 - 15 - 105  [0.588] 164
...      Deuterium v2021.1.38.2 playing Black: 28 - 26 - 109  [0.506] 163
...      White vs Black: 70 - 43 - 214  [0.541] 327
Elo difference: 33.0 +/- 22.0, LOS: 99.8 %, DrawRatio: 65.4 %
Started game 333 of 2000 (Deuterium v2021.1.38.2 vs Deuterium v2021.1.38.1)

[Ferdy]

Tested another method. Start at iter 4, Ignore fail highs and use fix fail low window margin when expanding the window. But similar to default to quickly reset the bounds to inf when there is successive fail lows. Default also tries to resolve the fail highs.

Code: Select all

aspWindow = 30
aspFailLowTries = 2
alpha = -INF
beta = INF

for (iter = 1 to max_iter) {

	score = search(alpha, beta ...)

	if (aspWindow && iter > 3) {
		// Fail low
		if (score <= alpha) {
			fLow++

			if (fLow >= aspFailLowTries) {
				alpha = -INF
				beta = INF
				iter--
				continue
			}
			else {
				alpha = score - aspWindow
				beta = score
				iter--
				continue
			}
		}

		alpha = score - aspWindow
		beta = score + aspWindow
		fLow = 0
	}
}

Result is promising so far against my default Deuterium v2021.1.38.1, at TC 3m+1s (more curious). Deuterium v2021.1.38.2 is using the above method.

Code: Select all

Score of Deuterium v2021.1.38.2 vs Deuterium v2021.1.38.1: 72 - 41 - 214  [0.547] 327
...      Deuterium v2021.1.38.2 playing White: 44 - 15 - 105  [0.588] 164
...      Deuterium v2021.1.38.2 playing Black: 28 - 26 - 109  [0.506] 163
...      White vs Black: 70 - 43 - 214  [0.541] 327
Elo difference: 33.0 +/- 22.0, LOS: 99.8 %, DrawRatio: 65.4 %
Started game 333 of 2000 (Deuterium v2021.1.38.2 vs Deuterium v2021.1.38.1)

I stop the test the result is still good.

Code: Select all

Score of Deuterium v2021.1.38.2 vs Deuterium v2021.1.38.1: 230 - 195 - 864  [0.514] 1289
...      Deuterium v2021.1.38.2 playing White: 139 - 77 - 429  [0.548] 645
...      Deuterium v2021.1.38.2 playing Black: 91 - 118 - 435  [0.479] 644
...      White vs Black: 257 - 168 - 864  [0.535] 1289
Elo difference: 9.4 +/- 10.9, LOS: 95.5 %, DrawRatio: 67.0 %