Impact of Aspiration on tree size

[Franky]

I did some tests on several features of my engine (Java based) and was wondering if the impact of Aspiration search make any sense.

My engine is still simple and uses AlphaBeta (fail-hard), PVS, TT, Null Move, Reverse Futility Pruning, Razoring, Mate Distance Pruning, Minor Promotion Pruning, Late Move Reductions and Killer Moves.

I recently added Aspiration Window search which does a 3 step approach. After searching 1 depth normally it starts using a window of -30/+30, then -200/+200 and if this fails -unlim/+unlim.

I did some measurements on 400 positions (random from some test sets) and I'm wondering if the impact of Aspiration Windows should not be better. Obviously there could be many causes for the results - mainly wrong impementatiion and/or bugs or not good enough implementation of the aspiration feature.

This is why I'd like to ask you if you think these results are totally off or if PVS and Aspiration together really do not have much impact.

WDYT? Thanks!

Btw. this is a short test searching only to ply 6 on 400 positions - could be a reason for the results as well. But my other features clearly show improvements already at ply6.

Code: Select all

Result (summing up all 400 tests):
============================================================
 Test			nodes		nps			time
 SIZE BASE         	197.423.838   	274.772.806   	315.450   
 SIZE ALL          	52.036.476   	241.874.059   	95.805   
 SIZE ASPIRATION   	54.422.250   	245.262.102   	99.795     << impact is negative! more nodes search, longer time needed 
			
BASE: Only AlphaBeta and TT
ALL: All features except Aspiration Window
ASPIRATION: Aspiration WIndow active
			
			
Test examples:
========================================================
Test				Nodes		nps			search time

 R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1			
 SIZE BASE         	2.304.131	194.032		11875
 SIZE ALL          	1.317		263.400		5
 SIZE ASPIRATION   	1.315		328.750		4
 			 			
 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1			
 SIZE BASE         	144.535		241.697		598
 SIZE ALL          	37.432		256.384		146
 SIZE ASPIRATION   	49.646		378.977		131
 			 			
 r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -			
 SIZE BASE         	344.089		292.593		1176
 SIZE ALL          	142.740		297.375		480
 SIZE ASPIRATION   	205.521		322.639		637
 			 			
 1r3rk1/1pnnq1bR/p1pp2B1/P2P1p2/1PP1pP2/2B3P1/5PK1/2Q4R w - -			
 SIZE BASE         	277.985		515.742		539
 SIZE ALL          	9.926		709.000		14
 SIZE ASPIRATION   	9.958		905.273		11

 ... total 400

[D Sceviour]

I recently added Aspiration Window search which does a 3 step approach. After searching 1 depth normally it starts using a window of -30/+30, then -200/+200 and if this fails -unlim/+unlim.

I used an open window search until discovering Ethereal's aspiration method. Aspiration increments are best in multiples of 2:
e.g. 30, 60, 120, 240, 480 ... until MATE SCORE.

[Sven]

I did some tests on several features of my engine (Java based) and was wondering if the impact of Aspiration search make any sense.

My engine is still simple and uses AlphaBeta (fail-hard), PVS, TT, Null Move, Reverse Futility Pruning, Razoring, Mate Distance Pruning, Minor Promotion Pruning, Late Move Reductions and Killer Moves.

I recently added Aspiration Window search which does a 3 step approach. After searching 1 depth normally it starts using a window of -30/+30, then -200/+200 and if this fails -unlim/+unlim.

I'm not sure whether you do the following: When failing high, the lower bound of the original window should be kept and only the upper bound should be raised. The same vice versa when failing low. See also CPW.

[Ras]

I'm starting with full window until depth 3. Then I always use the score from the previous iteration as base, +/- 50 centipawns. When failing low/high, I open the lower/upper boundary to full, i.e. re-search with half-open window. That also handles pathologic corner cases: if I fail low, I search from -infinity to score+50, and if that suddenly fails high, the lower bound is already at -infinity, and the other window opening kicks in so that I get a full window search.

I remember this brought a couple of Elo in self-play.

[Franky]

I'm not sure whether you do the following: When failing high, the lower bound of the original window should be kept and only the upper bound should be raised. The same vice versa when failing low. See also CPW.

Hallo Sven,
I did that before and it didn't feel better. Gonna put it back in and repeat my measurements.
Thanks

[Hanamuke]

Btw. this is a short test searching only to ply 6 on 400 positions - could be a reason for the results as well. But my other features clearly show improvements already at ply6.

At low depth, there are a lot of fluctuation in evaluation between sucessive depths, hence why aspiration is ineffective. For the same reason, using a TT value as an aspiration value wouldn't work either. As a matter of fact, aspiration search only kicks in at depth 5 in stockfish, but you could also try wider windows at shallow depths.

Besides, if your engine is not so strong, it's possible that its evaluation fluctuates more between depths than in top engines making aspiration less effective overall.

[abulmo2]

I did a fast test with Amoeba:
- On tree size & search time. I did count the nodes & time searched at depth 18 on 200 positional positions:
with aspiration: 674769965 nodes in 592.523s : 1138807 nps
without: 654081365 nodes in 651.913s : 1003326 nps

So aspiration window does not seem to reduce tree size, but to increase search speed. I am not sure also comparing tree sizes on a set of unrelated positions is the right way to measure aspiration efficiency. In normal game, successive positions are (cor)related and transposition table can play a role in the aspiration window efficiency.

- On strength: the aspiration window is worth about 100 ELO (+/- 10).