TT and Iterative Deepening

[kuket15]

I'm playing with TT and after some frustrating moments I've reached few reasonable results.
Unfortunately not everything works as I expected.

One of my tests to check the correctness of TT is the following:
1) Search at fixed depth (above the search output)

Code: Select all

 DEPTH  SCORE   TIME           NODES   MOVE
     1     50      0              41   b1c3
     2      0      0             193   b1c3
     3     50      0            1082   b1c3
     4      0      0            2661   b1c3
     5     40      0           22289   b1c3
     6      0      1           32851   b1c3
     7     35      9          352978   e2e4
     8      0      5          407536   e2e4
     9     30     17         1449283   e2e4
    10     20     65         4886609   e2e4

2) Make the best move found
3) Unmake the move
4) Search again at the same depth

Code: Select all

 DEPTH  SCORE   TIME           NODES   MOVE
     1     20      0               1   e2e4
     2     20      0               1   e2e4
     3     20      0               1   e2e4
     4     20      0               1   e2e4
     5     20      0               1   e2e4
     6     20      0               1   e2e4
     7     20      0               1   e2e4
     8     20      0               1   e2e4
     9     20      0               1   e2e4
    10     20      0               1   e2e4

If TT are ok I expect an "instant" search (I guess this is a necessary but not sufficient condition to prove TT correctness).


Now my doubts are quite simple to explain. In my scenario:

1) Search at fixed depth (same results posted above)
2) Search the opponent move.

Code: Select all

 DEPTH  SCORE   TIME           NODES   MOVE
     1    -20      0               1   b8c6
     2    -20      0               1   b8c6
     3    -20      0               1   b8c6
     4    -20      0               1   b8c6
     5    -20      0               1   b8c6
     6    -20      0               1   b8c6
     7    -20      0               1   b8c6
     8    -20      0               1   b8c6
     9    -20      0               1   b8c6
    10    -20    175        12761647   e7e5

If things go well until depth 9, at depth 10 the engine inspects a really huge number of nodes.
This is, I guess, because benefits of iterative deepening are lost (in my case my history / killer tables aren't filled at all).
To prove I'm right I've cleared the TT after the first search, and, as expected, visited nodes are much less (also SUM (nodes) < 12761647).

Code: Select all

 DEPTH  SCORE   TIME           NODES   MOVE
     1     10      0              45   b8c6
     2    -40      0             184   b8c6
     3     10      0            1115   b8c6
     4    -35      0            6140   g8f6
     5      0      0           30924   e7e5
     6    -35      1          151873   d7d5
     7      0      8          660983   e7e5
     8    -30     18         1409089   e7e5
     9    -20     41         3310374   e7e5
    10    -20     55         4001236   e7e5

Is this behaviour "correct" and in common engines things work this way?
I'm used to clear history and killer tables before every new search call.
With some adjustments I think I can reuse such tables in the next search to achieve early cut-off, but I'm not sure I'm following the "right way" to do things.

Thanks for any reply,

Luca

[H.G.Muller]

It is a bit hard to see what exactly goes on, because you don't print complete PVs but only the first move.

The results you show strike me as strange. Normally when you have searched e2e4 to 10 ply, the replies to it should have been searched to 9 ply, and stored like that in the TT. It seems from the search you do with empty TT that from d=7 on e7e5 should already be the best reply, so it should have been stored with d=9 in the TT. But when you do the search with the TT as left from the previous move, it seems that b8c6 was originally seen as best move with d=9.

[kuket15]

It is a bit hard to see what exactly goes on, because you don't print complete PVs but only the first move.

The results you show strike me as strange. Normally when you have searched e2e4 to 10 ply, the replies to it should have been searched to 9 ply, and stored like that in the TT. It seems from the search you do with empty TT that from d=7 on e7e5 should already be the best reply, so it should have been stored with d=9 in the TT. But when you do the search with the TT as left from the previous move, it seems that b8c6 was originally seen as best move with d=9.

I apologize for the quantity of engine output I'm posting. I tried to edit my previous post but I guess it's locked since a reply has been made.

Anyway these are the same results with the PV (actually almost the same, because meanwhile I made few changes).

First search

Code: Select all

 1  50    0              47 b1c3 
 2   0    0             201 b1c3 b8c6 
 3  50    0            1090 b1c3 b8c6 g1f3 
 4   0    0            2515 b1c3 b8c6 g1f3 g8f6 
 5  40    0           16704 b1c3 b8c6 g1f3 g8f6 d2d4 
 6   0    1           29146 b1c3 b8c6 g1f3 g8f6 d2d4 d7d5 
 7  35    5          300467 e2e4 b8c6 g1f3 g8f6 e4e5 f6e4 b1c3 
 8   0    5          306015 e2e4 b8c6 g1f3 g8f6 e4e5 f6g4 d2d4 d7d5 
 9  30   16         1487496 e2e4 b8c6 d2d4 d7d5 e4e5 e7e6 b1c3 g8e7 g1f3 
10  20   31         3126613 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 e4e5 f6e4 

Undo and search again

Code: Select all

 1  20    0               1 e2e4 
 2  20    0               1 e2e4 b8c6 
 3  20    0               1 e2e4 b8c6 d2d4 
 4  20    0               1 e2e4 b8c6 d2d4 e7e6 
 5  20    0               1 e2e4 b8c6 d2d4 e7e6 b1c3 
 6  20    0               1 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 
 7  20    0               1 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 
 8  20    0               1 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 
 9  20    0               1 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 e4e5 
10  20    0               1 e2e4 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 e4e5 f6e4 

Everything looks fine right now.

Search opponent reply (keeping TT filled)

Code: Select all

 1 -20    0               1 b8c6 
 2 -20    0               1 b8c6 d2d4 
 3 -20    0               1 b8c6 d2d4 e7e6 
 4 -20    0               1 b8c6 d2d4 e7e6 b1c3 
 5 -20    0               1 b8c6 d2d4 e7e6 b1c3 d7d5 
 6 -20    0               1 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 
 7 -20    0               1 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 
 8 -20    0               1 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 e4e5 
 9 -20    0               1 b8c6 d2d4 e7e6 b1c3 d7d5 g1f3 g8f6 e4e5 f6e4 
10 -20  139        13393060 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 f8b4 d4d5 b4c3 b2c3

The same search with initial empty TT

Code: Select all

 1  10    0              53 b8c6 
 2 -40    0             186 b8c6 b1c3 
 3  10    0            1119 b8c6 b1c3 g8f6 
 4 -35    0            7838 g8f6 e4e5 f6e4 b1c3 
 5   0    1           28004 e7e5 b1c3 g8f6 g1f3 b8c6 
 6 -35    5          168863 d7d5 e4d5 d8d5 b1c3 d5e5 g1e2 
 7   0   14          734343 e7e5 b1c3 b8c6 g1f3 f8c5 d2d3 g8f6 
 8 -30   12         1044246 e7e5 b1c3 b8c6 g1f3 f8c5 f1d3 g8f6 e1g1 
 9 -20   17         1784726 e7e5 b1c3 b8c6 g1f3 g8f6 d2d4 f8b4 c1g5 d7d6 
10 -20   42         4029653 e7e5 b1c3 b8c6 g1f3 g8f6 d2d4 f8b4 d4d5 b4c3 b2c3

I'm again missing if it's ok that visited nodes are less when TT is empty. Move score is the same, even if PV is different, so I believe are both fine.

I changed the source code of another open source chess engine and results are quite similar.

I'm confused again

[H.G.Muller]

Well, it is normal that when you change PV, it takes a comparatively large number of nodes. Because it has been searching the old PV move first, and apparently then had to search another PV move that became better.

The suspect thing is that 1... b8c6 seems to be in the TT with score -20 and depth 9, as shown when you do the search without clearing TT after 1. e2e4. Until d=9 you live from this single hash hit, and the search only uses a single node, the root. (You reset the node count between iterations?) I am not sure how you can report long PVs in that case. Do you store the PV of PV nodes in a hash table? Or do you retrieve it from the hash without counting nodes?

The real question, however, is how b8c6 could have gotten into the TT as best move for d=9. When you search after 1. e2e4 with empty TT it is clear that it abandons b8c6 already at d=4, and that it actually never gets a score of -20. The latter score is reached at d=9 (as expected), but it then comes from e7e5, not from b8c6.

So it seems that in storing the TT entry, a wrong move did get combined with the correct score. This problem seems to occur already within the first search: when this switches from b1c3 to e2e4 at d=7, the reply to e2e4 should have been a d=6 move (with score -35), and the reply search with empty TT shows that at d=6 the best black move is d7d5 (indeed with score -35). But instead your PV keeps repeating the b8c6 as second move, which was the expected reply against b1c3, but should never have been that against 1. e2e4. And it doesn't seem this is just a problem with how you print or retrieve the PV, but really how it is stored in the TT.

If the moves the TT recommends for searching first are all wrong, it is of course to be expected that using that info just slows the search down...

[kuket15]

The suspect thing is that 1... b8c6 seems to be in the TT with score -20 and depth 9, as shown when you do the search without clearing TT after 1. e2e4. Until d=9 you live from this single hash hit, and the search only uses a single node, the root. (You reset the node count between iterations?) I am not sure how you can report long PVs in that case. Do you store the PV of PV nodes in a hash table? Or do you retrieve it from the hash without counting nodes?

Yes, I reset node count between iterations and I use TT to recover the PV. Not sure what you mean when you say "do you retrieve it from the hash without counting nodes?".

The real question, however, is how b8c6 could have gotten into the TT as best move for d=9. When you search after 1. e2e4 with empty TT it is clear that it abandons b8c6 already at d=4, and that it actually never gets a score of -20. The latter score is reached at d=9 (as expected), but it then comes from e7e5, not from b8c6.

Here I'm lost again.

In the first search I can see b8c6 is the best reply to b1c3 from d=1 to d=6. I can also see b8c6 is the best reply to e2e4 from d=7 to d=10. Correct me if I'm wrong but I don't know if b8c6 is the best reply to e2e4 if I run a d=6 search only.
If my assertion is good, when I search the reply to e2e4, with empty TT, it's perfectly ok that b8c6 is not the best move at d=4.
Now at d=7 I search first d7d5 (found as best at d=6, but not the best move now) and, after that e7e5. Even if b8c6 is another best move for d=7 It doesn't raise alpha because score is the same, so I don't go deep there.
After that I always try e7e5 first and I find it is always the best move... Consider my evaluation function is very simple (material only), so there are many "best" moves for each node.

Are my thought correct?

[H.G.Muller]

So you are saying that b8c6 and e7e5 really have the same score from d=6 to d=9, and that it is just a coincidence which of the two is chosen as reply to e2e4? This can indeed not be excluded if the evaluation is rather course. But that means you are just unlucky that the move that turns out to be best at d=10 (e7e5) is not the one that was chosen as the preferred reply at d=7 of the original search, but b8c6 was preferred instead. Had it been the other way around then you would not have had to change moves at d=10 of the search for the next move, and the search would have required far fewer nodes.

Changing PV move is always expensive, and the higher the iteration that you do it, the more that counts in the total.

Internal Iterative Deepening makes the search more robust against move changes, by never starting a deep, completely uninformed search. I don't know if you already do that.

I also discovered that the normal way of doing ID or IID is not very robust against sudden score drops at high depth. It can then take excessively long to find an alternative move. The problem is that the search of the alternative thinks it is informed, as it finds nice cut moves in the TT. But the problem is that these cut moves were only good enough to keep the score below the old PV score, before it collapsed. With the new, much lower PV score, they usually are not good enough for a beta cutoff, and you have to find completely different refutations. I could then often speed up finishing the iteration from hours to minutes by just restarting the search, keeping the TT. The old PV move would then get the collapsed score already from d=1 on from the TT hit, but the bounds stored in the TT for the other moves would now not be good enough to get a hash cutoff, so their search would really start at d=1. This suggests the best way to do ID/IID is not

Code: Select all

for(depth=1; depth<MAX; depth++) {
  for(ALL_MOVES) {
    ...
    score = -Search(-beta, -alpha, depth-1);
    if(score >= beta) break; // cutoff
    ...
  }
}

but

Code: Select all

for(depth=1; depth<MAX; depth++) {
  for(ALL_MOVES) {
    ...
    for(i=1; i<= depth; i++)
      score = -Search(-beta, -alpha, i-1);
    if(score >= beta) break; // cutoff
    ...
  }
}

This would ensure that after change of alpha the search of a move always starts at depth 1. If the move was searched before and the bounds in the TT are still good enough the first few iterations of this would all be satisfied immediately from the TT, so it is not very expensive. If the stored bound is no longer good enough because of the alpha change, you would do a real search at the lowest possible depth to discover a plan for getting a sharper bound.

[kuket15]

Internal Iterative Deepening makes the search more robust against move changes, by never starting a deep, completely uninformed search. I don't know if you already do that.

Well, I'm not implementing IID, but I feel I should take a look at it (including the variation you suggested)
My next efforts, anyway, will be on a more solid evaluation function. I think PV will result more stable and such situations much less frequent.

And last, Thank you for your time Mr. Muller.