Impact of Aspiration on tree size

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Franky
Posts: 2
Joined: Thu Jan 03, 2019 1:38 am
Full name: Frank Kopp

Impact of Aspiration on tree size

Post by Franky » Wed Jan 16, 2019 9:15 pm

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 :wink: 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
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Impact of Aspiration on tree size

Post by D Sceviour » Wed Jan 16, 2019 9:42 pm

Franky wrote:
Wed Jan 16, 2019 9:15 pm
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
Posts: 3743
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Impact of Aspiration on tree size

Post by Sven » Wed Jan 16, 2019 11:38 pm

Franky wrote:
Wed Jan 16, 2019 9:15 pm
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Ras
Posts: 1079
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: Impact of Aspiration on tree size

Post by Ras » Wed Jan 16, 2019 11:48 pm

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

Franky
Posts: 2
Joined: Thu Jan 03, 2019 1:38 am
Full name: Frank Kopp

Re: Impact of Aspiration on tree size

Post by Franky » Thu Jan 17, 2019 9:22 am

Sven wrote:
Wed Jan 16, 2019 11:38 pm
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
Posts: 2
Joined: Fri Dec 07, 2018 1:47 pm
Full name: Antoine Houdayer

Re: Impact of Aspiration on tree size

Post by Hanamuke » Thu Jan 17, 2019 12:55 pm

Franky wrote:
Wed Jan 16, 2019 9:15 pm
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
Posts: 144
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: Impact of Aspiration on tree size

Post by abulmo2 » Thu Jan 17, 2019 3:39 pm

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).
Richard Delorme

Post Reply