Aspiration window problem

[sandermvdb]

My aspiration window gives an advantage of about 15 elo. Still there are certain positions where it is behaving pretty badly. This is one of them:

[d]8/1p3pk1/1q1P1bp1/4P3/n1p1P3/P5P1/1PBQ2K1/8 b - - 0 50

With aspiration enabled, it takes 7 seconds to find the best move, at ply 17.
With aspiration disabled, it takes 0 seconds, at ply 10!

Are there some known issues with aspiration windows and other search techniques? The cpw contains a page about PVS and AW, but if I disable PVS, the problem is still there.

The output while analyzing is below (chess22k-ex has AW disabled).
Very strange that the score with AW enabled goes up again at ply 11...

Code: Select all

chess22k:
 1/6	00:00	 102	4k	+1,03	Bf6xe5
 2/6	00:00	 284	3k	+1,03	Bf6xe5 Bc2xa4
 3/6	00:00	 526	5k	+1,03	Bf6xe5 Bc2xa4 Qb6xd6
 4/7	00:00	 878	7k	+1,03	Bf6xe5 Bc2xa4 Qb6xd6 Qd2xd6
 5/10-	00:00	 3k	20k	+0,83	Bf6xe5 d6-d7 Kg7-g8 d7-d8Q+ Qb6xd8 Qd2xd8+
 5/10-	00:00	 3k	22k	+0,63	Bf6xe5 d6-d7 Kg7-g8 d7-d8Q+ Qb6xd8 Qd2xd8+
 5/10	00:00	 4k	26k	+0,59	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3
 6/11	00:00	 6k	31k	+0,59	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 d7-d8Q
 7/12	00:00	 10k	48k	+0,59	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 d7-d8Q Bc3xd2
 8/13-	00:00	 15k	72k	+0,39	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 f7-f6 d7-d8Q
 8/13-	00:00	 19k	87k	+0,19	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 f7-f6 d7-d8Q
 8/13-	00:00	 34k	130k	-1,23	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 f7-f6 d7-d8Q
 8/14	00:00	 42k	139k	-1,40	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 Bc3-f6 Bc2xa4
 9/15	00:00	 66k	160k	-1,55	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 Bc3-f6 Bc2xa4 Qb6-b2+
 10/17+	00:00	 114k	216k	-1,35	Bf6-g5 Qd2xg5 Na4-c5 Qg5-f6+ Kg7-g8 Qf6-f1 Qb6xb2 Qf1xc4 Qb2xe5
 10/17	00:00	 122k	227k	-1,33	Bf6-g5 Qd2xg5 Na4-c5 Qg5-f6+ Kg7-g8 Qf6-f1 Qb6xb2 Qf1xc4 Qb2xe5
 11/20+	00:00	 187k	282k	-1,03	Bf6xe5 d6-d7 Na4-c5 Qd2-d5 Qb6xb2 d7-d8Q Qb2xc2+ Kg2-h3 Qc2-c3
 11/20+	00:00	 197k	295k	-0,83	Bf6xe5 d6-d7 Na4-c5 Qd2-d5 Qb6xb2 d7-d8Q Qb2xc2+ Kg2-h3 Qc2-c3
 11/20+	00:00	 220k	306k	-0,08	Bf6xe5 d6-d7 Na4-c5 Qd2-d5 Qb6xb2 d7-d8Q Qb2xc2+ Kg2-h3 Qc2-c3
 11/20+	00:00	 238k	325k	+0,59	Bf6xe5 d6-d7 Na4-c5 Qd2-d5 Qb6xb2 d7-d8Q Qb2xc2+ Kg2-h3 Nc5-d3
 11/20	00:00	 324k	381k	+1,12	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 Ba4-c2 Qb6-c6 Qc3-d2 Qc6-c7
 12/23	00:00	 471k	476k	+0,88	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 Ba4-e8 g6-g5 Qc3-d2 Qb6-c5
 13/25-	00:01	 562k	539k	+0,68	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 Ba4-e8 g6-g5 Qc3xc4 Qb6xb2+
 13/25	00:01	 740k	624k	+0,53	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 Ba4-e8 Qb6-d8 Be8-b5 Bd6-e5
 14/27+	00:01	 924k	705k	+0,83	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 Ba4-e8 Qb6-c5 Qc3-d2 Qc5-e5
 14/27+	00:01	 1.112k	779k	+1,03	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 Ba4-e8 Qb6-c5 Qc3-d2 Qc5-e5
 14/27	00:01	 1.527k	902k	+1,14	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 b2-b3 c4xb3 Ba4xb3 Qb6-a6
 15/29	00:01	 1.890k	985k	+1,11	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 b2-b3 c4xb3 Ba4xb3 Qb6-a6
 16/30	00:02	 2.576k	1.092k	+1,07	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 b2-b3 c4xb3 Ba4xb3 Qb6-a6
 17/32-	00:02	 3.295k	1.183k	+0,87	Bf6xe5 Bc2xa4 Be5xd6 Qd2-c3+ f7-f6 b2-b3 c4xb3 Qc3-c8 b3-b2
 17/34-	00:03	 4.619k	1.267k	+0,67	Bf6xe5 d6-d7 Na4-c5 d7-d8Q Qb6xd8 Qd2xd8 Be5xb2 Kg2-f3 Nc5-d3
 17/34-	00:04	 6.687k	1.345k	-0,75	Bf6xe5 d6-d7 Na4-c5 d7-d8Q Qb6xd8 Qd2xd8 Be5xb2 Kg2-f3 Nc5-d3
 17/34	00:07	 11.152k	1.423k	-1,31	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-e6 Bc2-b1 Qb6-d4 Qc1-c3 Qd4-d1
 18/34	00:08	 12.299k	1.438k	-1,31	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-e6 Bc2-b1 Qb6-d4 Qc1-c3 Qd4-d1

chess22k-ex:
 1/6	00:00	 102	4k	+1,03	Bf6xe5
 2/6	00:00	 284	2k	+1,03	Bf6xe5 Bc2xa4
 3/6	00:00	 526	3k	+1,03	Bf6xe5 Bc2xa4 Qb6xd6
 4/7	00:00	 878	5k	+1,03	Bf6xe5 Bc2xa4 Qb6xd6 Qd2xd6
 5/11	00:00	 4k	17k	+0,59	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3
 6/11	00:00	 6k	20k	+0,59	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 d7-d8Q
 7/12	00:00	 10k	25k	+0,59	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 d7-d8Q Bc3xd2
 8/16	00:00	 27k	45k	-1,40	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 Bc3-f6 Bc2xa4
 9/16	00:00	 53k	69k	-1,55	Bf6xe5 d6-d7 c4-c3 b2xc3 Be5xc3 Qd2-d5 Bc3-f6 Bc2xa4 Qb6-b2+
 10/17	00:00	 105k	114k	-1,33	Bf6-g5 Qd2xg5 Na4-c5 Qg5-f6+ Kg7-g8 Qf6-f1 Qb6xb2 Qf1xc4 Qb2xe5
 11/19	00:01	 171k	167k	-1,21	Bf6-g5 Qd2xg5 Na4-c5 Qg5-f6+ Kg7-g8 e5-e6 Nc5xe6 d6-d7 Qb6-d6
 12/26	00:01	 288k	254k	-0,87	Bf6-g5 Qd2xg5 Na4-c5 Qg5-f6+ Kg7-g8 Qf6-f1 Qb6xb2 Qf1xc4 Qb2xe5
 13/26	00:01	 542k	414k	-0,91	Bf6-g5 Qd2xg5 Na4-c5 Qg5-f6+ Kg7-g8 e5-e6 Nc5xe6 d6-d7 Qb6-d6
 14/26	00:01	 859k	571k	-1,16	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-d7 Bc2-a4 Nd7xe5 Qc1-d2 f7-f6
 15/28	00:01	 1.626k	821k	-1,29	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-d7 Bc2-a4 Nd7xe5 Qc1-d2 f7-f6
 16/30	00:02	 2.743k	998k	-1,34	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-d7 Bc2-a4 Nd7xe5 Qc1-d2 f7-f6
 17/30	00:03	 4.417k	1.142k	-1,10	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Kg7-g8 Bc2-b1 Nc5-d7 e5-e6 f7xe6
 18/32	00:05	 6.904k	1.286k	-1,19	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-d7 Bc2-a4 Nd7xe5 Qc1-d2 c4-c3
 19/35	00:06	 9.313k	1.364k	-1,12	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-d7 Bc2-a4 Nd7xe5 Qc1-d2 c4-c3
 20/38	00:08	 12.165k	1.422k	-1,12	Bf6-g5 Qd2xg5 Na4-c5 Qg5-c1 Nc5-d7 Bc2-a4 Nd7xe5 Qc1-d2 c4-c3

[Michael Sherwin]

Aspiration window should affect the time a search takes, not the result. If a search with an aspiration window falls outside the window the search is done with a bigger window or a full window until the result is inside the window. If your search is returning different results depending on if the window is deactivated or not then that reveals a bug.

Edit: Try clearing the hash before to see if it is a hash problem.

[elpapa]

Are you sure Bg5 is the best move?

Code: Select all

SF8 depth 39, multiPV=4:

Bxe5 -0.44
Bd8  -1.11
Bg5  -1.68
Nc5  -2.82

[sandermvdb]

Are you sure Bg5 is the best move?

Code: Select all

SF8 depth 39, multiPV=4:

Bxe5 -0.44
Bd8  -1.11
Bg5  -1.68
Nc5  -2.82

You are right, Bg5 is not the best move.
However it is still strange (bug?) that the outcome of the search is so different when the aspiration window is enabled or disabled: between ply 11-16, AW enabled even thinks it is ahead!

[hgm]

Indeed, this is very suspect. I always hate it when things like that happen in my own engines. Debugging it is tedious, and can easily mean a full day of hard work.

Note that with AW the score goes up at 11 ply for another move (Bf6xe5, instead of Bf6-g5). It could very well be that the searches agree on the score of Bg5, but you are sure they must disagree on the score of Bxe5. So the thing you want to know is how the search without AW though it could refute Bxe5. I always do that by priting the list of all searched moves and scores in all the nodes along the path I am interested in. In this case doing that both for the 11-ply search with and without AW, to see how they differ, and then extending the path one ply alog the move that is responsible for the difference.

E.g. at ply level 1 the search without AW must have had a move (say X) which scored above +1.21 after Bxe5; in the search with AW that same move X will certainly have been searched (as this was a PV node there), but cannot have scored better than -1.12. Then you go to comparing the scores in the node after Bxe5, X to see what causes that difference. Typically what was an all-node in one search will be a cut-node in the other, ad the cut-move will have been searched in both cases, and you can follow that. In the end you must come to something that explains the different scores. E.g. the all node could have failed to search the cut-move of the other, because of a bug. Or you got a hash hit in one with an erroneous score, perhaps due to a key collision or a hash bug. Or the moves are searched at different depths due to your extension/reduction scheme. It ca be a lot of work before you have followed the line 11 ply deep. And if you get to a hash hit you would haveto figure out whwre in the tree that hash entry was stored (i.e. the path that led to the node that stored it), and then (after checking this was indeed the same position) proceed stepping through the tree from there.

[sandermvdb]

I just noticed it is related to storing and retrieving upper- and lower-bound scores from the transposition table.

Tx hgm for your debugging approach
Investigation continues...

[CheckersGuy]

Hey guys,
I have a question about aspiration search as well and don't want to create another thread about it (Since this one is about aspiration search as well)

The implementation of PVS+ aspiration windows I found on the chessprogramming wiki seems to be a implementation for fail-soft. What`s the difference when implementing aspiration search with a fail-hard-framework ?

Would appreciate an explanation and/or pseudocode

[Stan Arts]

Hey guys,
I have a question about aspiration search as well and don't want to create another thread about it (Since this one is about aspiration search as well)

The implementation of PVS+ aspiration windows I found on the chessprogramming wiki seems to be a implementation for fail-soft. What`s the difference when implementing aspiration search with a fail-hard-framework ?

Would appreciate an explanation and/or pseudocode

There is no huge difference. But with fail soft you might get a score outside the window and with that a quicker guess as to the range of the new score. Let's say you open up your window in steps and we now find a mate. With fail soft you might return a mate score right away to center your window around saving you a few researches.
In practise as my fail soft engine Nemeton became more complex getting scores back from outside the window became increasingly rare.

[Henk]

Never been able to get aspiration search working correctly. If time is up there is no time for research and a bad move is returned. Trying to correct that never worked for Skipper. Perhaps transposition table got corrupt too by aspiration search (when time is up) I don't know

[op12no2]

Never been able to get aspiration search working correctly. If time is up there is no time for research and a bad move is returned. Trying to correct that never worked for Skipper. Perhaps transposition table got corrupt too by aspiration search (when time is up) I don't know

As I see it, if search returns <= alpha to the ID loop, by implication it didn't update the best move, so it's safe to use that best move if out of time. If search returns > beta it may also have updated the best move, but that seems OK to me.

As long as the TT holds the value type alpna, exact or beta then it should not get 'corrupt'; you just need to make the appropriate tests to use the TT value. e.g. if the TT says alpha x and x <= current alpha then bingo; it all naturally adapts to a shrinking window.