Aspiration search + Hash table

[Franck Tempet]

Hello,

I have problem when i had aspiration search in my chess engine.

In this diagram for example :

[diag]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1[/diag]

Search with only hash table;

[-32500,32500]
info score cp 105 depth 1 nodes 8 pv a1b2
[-32500,32500]
info score cp 100 depth 2 nodes 25 pv a1b2 a7b7
[-32500,32500]
info score cp 105 depth 3 nodes 79 pv a1b2 a7b7 b2c3
[-32500,32500]
info score cp 105 depth 4 nodes 171 pv a1b2 a7b7 b2c3 b7c7
[-32500,32500]
info score cp 105 depth 5 nodes 345 pv a1b2 a7b7 b2c3 b7c7 c3d3
[-32500,32500]
info score cp 105 depth 6 nodes 560 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7
[-32500,32500]
info score cp 105 depth 7 nodes 819 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 8 nodes 1204 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 9 nodes 1563 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 10 nodes 2066 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 11 nodes 2546 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 12 nodes 3161 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 13 nodes 3767 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 14 nodes 4516 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 15 nodes 5256 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 16 nodes 6728 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500]
info score cp 105 depth 17 nodes 8060 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[-32500,32500] => [alpha, beta] for search depth 18
info score cp 230 depth 18 nodes 41352 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6
[-32500,32500]
info score cp 230 depth 19 nodes 56060 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6c5
[-32500,32500]
info score cp 220 depth 20 nodes 1081477 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6c5 f4e4
[-32500,32500]
info score cp 220 depth 21 nodes 10606010 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6c5 f4e4 d5d6
[-32500,32500]
info score cp 220 depth 22 nodes 13273129 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5a5 h5g4 a5b5 g4f4 b5c6 f4e4 c6d6 e4d4
[-32500,32500]
info score cp 220 depth 23 nodes 23453939 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7d8 c2c3 d8c7 c3d3 c7b7 d3e3 b7c7 e3d3 c7b7 d3e2 b7c7 e2d1 c7d7
[-32500,32500]
info score cp 220 depth 24 nodes 27432907 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5a5 h5g4 a5b5 g4f4 b5c6 f4e4 c6d6 e4d4 a4a5 f5f4
[-32500,32500]
info score cp 220 depth 25 nodes 44384388 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7c8 c2d2 c8d8 d2c3 d8c7 c3d3 c7b7 d3e3 b7c7 e3d3 c7b7 d3e2 b7c7 e2d1 c7d7
bestmove a1b1 ponder a7b7



Search with hash table + aspiration search ( + - 50 ) ;

[-32500,32500]
info score cp 105 depth 1 nodes 8 pv a1b2
[55,155]
info score cp 100 depth 2 nodes 25 pv a1b2 a7b7
[50,150]
info score cp 105 depth 3 nodes 79 pv a1b2 a7b7 b2c3
[55,155]
info score cp 105 depth 4 nodes 171 pv a1b2 a7b7 b2c3 b7c7
[55,155]
info score cp 105 depth 5 nodes 345 pv a1b2 a7b7 b2c3 b7c7 c3d3
[55,155]
info score cp 105 depth 6 nodes 560 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7
[55,155]
info score cp 105 depth 7 nodes 819 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 8 nodes 1200 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 9 nodes 1559 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 10 nodes 2061 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 11 nodes 2541 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 12 nodes 3156 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 13 nodes 3762 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 14 nodes 4511 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 15 nodes 5251 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 16 nodes 6475 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155]
info score cp 105 depth 17 nodes 7632 pv a1b2 a7b7 b2c3 b7c7 c3d3 c7b7 d3c3 b7c7
[55,155] => [alpha, beta] for search depth 18
info score cp 105 depth 18 nodes 13242 pv a1b2 a7a8 b2c3 a8b7 c3d3 b7c7 d3c3

Score in [ 55 , 155 ] => no research with a full window

[55,155] => [alpha, beta] for search depth 19 score is not in [55,155] => research with [ -infinty , +infinity ]

[-32500,32500]
info score cp 105 depth 19 nodes 959732 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7c7 c2b3 c7b7 b3c3 b7c7 c3d3 c7b7 d3e3 b7c7 e3f3 c7d7 f3e3




[55,155]
[-32500,32500]
info score cp 220 depth 20 nodes 6191683 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6c5 f4e4
[170,270]
info score cp 220 depth 21 nodes 8961380 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5c6 h5g4 c6d6 g4f4 d6c5 f4e4 c5c4
[170,270]
info score cp 220 depth 22 nodes 23881159 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5a5 h5g4 a5b5 g4f4 b5c6 f4e4 c6d6 e4d4
[170,270]
info score cp 220 depth 23 nodes 28965711 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7d8 c2c1 d8e7 c1b2 e7f6 b2b3 f6g6 b3c4 g6h5 c4b5 h5g4 b5c6 g4f4 c6d6 f4e4 d6c5
[170,270]
info score cp 220 depth 24 nodes 30734087 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7e7 c2d3 e7f6 d3c4 f6g6 c4b5 g6h5 b5a5 h5g4 a5b5 g4f4 b5c6 f4e4 c6d6 e4d4 a4a5 f5f4
[170,270]
info score cp 220 depth 25 nodes 44956833 pv a1b1 a7b7 b1c1 b7c7 c1d1 c7d7 d1c2 d7c8 c2d2 c8d7 d2c2 d7e7
bestmove a1b1 ponder a7b7


At the depth 18 the search with only hash table return the score 230 with the good move Rb1 , the search with hashtable + aspiration search return the score 105 with the bad move Rb2?

At the depth 19 the search with hashTable + aspiration search do a research with [ -infinity , +infinity] but the score is different as well ?

[Harald Johnsen]

There is nothing wrong here.
It's not that your search with aspiration is wrong it's more like your search with no aspiration was lucky.
This happens often is pawn endgame. Image that your engine finds a winning position during the search (lets say at depth 15) and stores the good scores and the good moves in the hash table) ; but the variation is not forced. Then, during the search (say at depth 14) you have a forced line where your search tranposes somewhere into the previous line (you have a TT hit where remaining depth == 10). So you where doing a search at depth 14 and you have the equivalent of a search of depth 14 + 10 == 24.

The difference is your move ordering ; note also that the pv you display is truncated, and there is no pawn capture in your pv so the score does not comes from your main search.

HJ.

[Franck Tempet]

Thanks Harald,

I have two new questions.


Why with aspiration for depth 19 the score of the first search is not in [55,155] and the research with [-infinity,+infinity] the score is 105 ?


I think i have a bug :

in the start position:

with no aspiration the search depth 8 :

[-32500,32500]
info score cp 62 depth 1 nodes 42 pv g1f3
[-32500,32500]
info score cp 0 depth 2 nodes 140 pv g1f3 g8f6
[-32500,32500]
info score cp 50 depth 3 nodes 1137 pv g1f3 g8f6 d2d4
[-32500,32500]
info score cp 4 depth 4 nodes 5080 pv e2e4 d7d5 b1c3 g8f6
[-32500,32500]
info score cp 39 depth 5 nodes 24254 pv e2e4 d7d5 e4d5 g8f6 f1b5
[-32500,32500]
info score cp 12 depth 6 nodes 94420 pv e2e4 d7d6 g1f3 g8f6 f1b5 b8c6
[-32500,32500]
info score cp 47 depth 7 nodes 613529 pv g1f3 g8f6 e2e3 d7d5 f1d3 e7e5 f3e5
[-32500,32500]
info score cp 14 depth 8 nodes 2641358 pv e2e4 e7e6 g1f3 d7d5 e4e5 b8c6 d2d4 g8e7
bestmove e2e4 ponder e7e6



With aspiration +-50 :
------------------------------

[-32500,32500]
info score cp 62 depth 1 nodes 42 pv g1f3
[12,112]
[-32500,32500]
info score cp 0 depth 2 nodes 204 pv g1f3 g8f6
[-50,50]
[-32500,32500]
info score cp 50 depth 3 nodes 1260 pv g1f3 g8f6 d2d4
[0,100]
info score cp 4 depth 4 nodes 4222 pv e2e4 d7d5 b1c3 g8f6
[-46,54]
info score cp 39 depth 5 nodes 24211 pv e2e4 d7d5 e4d5 g8f6 f1b5
[-11,89]
info score cp 12 depth 6 nodes 91289 pv e2e4 d7d6 g1f3 g8f6 f1b5 b8c6
[-38,62]
info score cp 47 depth 7 nodes 636832 pv g1f3 g8f6 e2e3 d7d5 f1d3 e7e5 f3e5
[-3,97]
info score cp 14 depth 8 nodes 2807753 pv e2e4 e7e6 g1f3 d7d5 e4e5 b8c6 d2d4 g8e7
bestmove e2e4 ponder e7e6

aspiration +- 60
-----------------------

[-32500,32500]
info score cp 62 depth 1 nodes 42 pv g1f3
[2,122]
[-32500,32500]
info score cp 0 depth 2 nodes 204 pv g1f3 g8f6
[-60,60]
info score cp 50 depth 3 nodes 1201 pv g1f3 g8f6 d2d4
[-10,110]
info score cp 4 depth 4 nodes 5143 pv e2e4 d7d5 b1c3 g8f6
[-56,64]
info score cp 39 depth 5 nodes 24317 pv e2e4 d7d5 e4d5 g8f6 f1b5
[-21,99]
info score cp 12 depth 6 nodes 94429 pv e2e4 d7d6 g1f3 g8f6 f1b5 b8c6
[-48,72]
info score cp 47 depth 7 nodes 611097 pv g1f3 g8f6 e2e3 d7d5 f1d3 e7e5 f3e5
[-13,107]
info score cp 14 depth 8 nodes 2637890 pv e2e4 e7e6 g1f3 d7d5 e4e5 b8c6 d2d4 g8e7


aspiration +-40
-----------------------

[-32500,32500]
info score cp 62 depth 1 nodes 42 pv g1f3
[22,102]
[-32500,32500]
info score cp 0 depth 2 nodes 204 pv g1f3 g8f6
[-40,40]
[-32500,32500]
info score cp 50 depth 3 nodes 1302 pv g1f3 g8f6 d2d4
[10,90]
[-32500,32500]
info score cp 4 depth 4 nodes 6739 pv e2e4 d7d5 b1c3 g8f6
[-36,44]
info score cp 39 depth 5 nodes 26506 pv e2e4 d7d5 e4d5 g8f6 f1b5
[-1,79]
info score cp 12 depth 6 nodes 98120 pv e2e4 d7d6 g1f3 g8f6 f1b5 b8c6
[-28,52]
info score cp 47 depth 7 nodes 605635 pv g1f3 g8f6 e2e3 d7d5 f1d3 e7e5 f3e5
[7,87]
info score cp 14 depth 8 nodes 2435881 pv e2e4 e7e6 g1f3 d7d5 e4e5 b8c6 d2d4 g8e7


Nodes for depth 8 ( aspiration +-40) < Nodes for depth 8 ( aspiration +-60) < Nodes for depth 8 without aspiration < Nodes for depth 8 ( aspiration +-50)

With aspiration +-50 my engine analyses more nodes than aspiration +-40 and more than aspiration +-60 and more than no aspiration, Aspiration +-50 does two searches for depth 2 and 3 only for a few nodes.


Thanks for your answers.

Franck.

[bob]

You are falling into a classic trap that will haunt you until you discover what is going on and change your methodology. It is easy to make a tiny change to a program and make a specific position run much faster or much slower, because of the resulting smaller or larger tree. But you don't win games based on a single position. You need to run hundreds and then look at the overall effect. Endgame positions like fine 70 are highly sensitive to _everything_. Usually just changing the hash size will greatly change the results, and often enough making the hash size larger will actually hurt the time to some specific depth. But when you look at the output, you might find you found a better move earlier in the search.

The moral: Don't use a single position to decide whether something works or not. It is far better to play lots of games with and without the change, but sometimes just running a large number of different test positions is enough...

[Harald Johnsen]

Why with aspiration for depth 19 the score of the first search is not in [55,155] and the research with [-infinity,+infinity] the score is 105 ?

I think i have a bug :

I don't think that there is a bug. I'm not used to window search, I only do pvs in my engine. What happens is that you do a re-search on a fail high (score > alpha) with the full windows and you get a fail low score (score <= alpha). When it's done on a non pv node a simple reason for that is because of extensions/reductions are not the same in pv and non pv nodes. Or you are cuttings on TT hit everywhere (pv & non pv) and since your window is different you are not re-searching the same things (note that when sorting your moves on history numbers you can never have the same move ordering in a re-search).

Nodes for depth 8 ( aspiration +-40) < Nodes for depth 8 ( aspiration +-60) < Nodes for depth 8 without aspiration < Nodes for depth 8 ( aspiration +-50)

With aspiration +-50 my engine analyses more nodes than aspiration +-40 and more than aspiration +-60 and more than no aspiration, Aspiration +-50 does two searches for depth 2 and 3 only for a few nodes.

Even if your root score was centered around the window (and that's not the case, your root score fluctuates a lot), this does not mean that the scores inside the search tree are centered on that window. Your window bounds will affect the rate of hash table cut off, the rate of new pv discovery, etc. It's a bit random, in parts of the tree your small window of 40 will cut a lot of branch, but in other parts a window of 60 will give less re-search when you loose or win the bishop pair, who knows.

HJ.