Transposition Table updates in Stockfish

[Onno Garms]

Stockfish uses a rather simple update strategy in the transposition table: If an entry for the position is found, always overwrite.

This includes overwriting values with values with lower depth, and overwriting exact scores with upper or lower bounds. Other open source engines, such as Fruit and Crafty, have more complicated replacement schemes. I never compared them experimentally, but by code inspection the latter two seem much more plausible then the one in Stockfish. Also I would assume that Fabien and Bob did not implement their schemes without making sure that it is superior to the simplest one.

Have any experiments been made which scheme is the best? How much does this depend on the engine? Is the current simple scheme really the best for Stockfish?

[Eelco de Groot]

Stockfish uses a rather simple update strategy in the transposition table: If an entry for the position is found, always overwrite.

This includes overwriting values with values with lower depth, and overwriting exact scores with upper or lower bounds. Other open source engines, such as Fruit and Crafty, have more complicated replacement schemes. I never compared them experimentally, but by code inspection the latter two seem much more plausible then the one in Stockfish. Also I would assume that Fabien and Bob did not implement their schemes without making sure that it is superior to the simplest one.

Have any experiments been made which scheme is the best? How much does this depend on the engine? Is the current simple scheme really the best for Stockfish?

Not hindered by any knowledge what the code exactly does, I tried a few alternatives that seemed reasonable possibilities. However the results of what I thought were small changes were disastrous, probably because I missed something fundamental. I'm back to the old replacement scheme and I think it is very easy to break something here, which only shows up when the hashtables are totally saturated. I suspect Tord tested this code in Glaurung (well most of it?) and it is well designed, I'm not touching it, until I understand better what I did wrong. It is not that easy to improve.

Regards, Eelco

[Onno Garms]

Not hindered by any knowledge what the code exactly does, I tried a few alternatives that seemed reasonable possibilities. However the results of what I thought were small changes were disastrous, probably because I missed something fundamental.

Would be interesting to know if this fundamental thing is something special about the interaction of the Stockfish search with the hash table or if you did something that would have broken any engine.

By code inspection I thought that it was pretty clear what tt.cpp does. But of course I might be surprised when I start to modify it.

[michiguel]

Stockfish uses a rather simple update strategy in the transposition table: If an entry for the position is found, always overwrite.

This includes overwriting values with values with lower depth, and overwriting exact scores with upper or lower bounds. Other open source engines, such as Fruit and Crafty, have more complicated replacement schemes. I never compared them experimentally, but by code inspection the latter two seem much more plausible then the one in Stockfish. Also I would assume that Fabien and Bob did not implement their schemes without making sure that it is superior to the simplest one.

Have any experiments been made which scheme is the best? How much does this depend on the engine? Is the current simple scheme really the best for Stockfish?

I tested several things in my engine recently, and I was disappointed that some of my "supposedly smart" schemes did not improve anything at all. Of course, you may see the effects when memory is limiting, otherwise anything is ok. I would believe that a replace always scheme could be certainly improved, but I doubt it may mean much, particularly with the amount of RAM we are using nowadays.

I think there may be some engine dependence too. Nps and if you probe in quies() or not may change things a bit.

Miguel

[Onno Garms]

Of course, you may see the effects when memory is limiting, otherwise anything is ok. I would believe that a replace always scheme could be certainly improved, but I doubt it may mean much, particularly with the amount of RAM we are using nowadays.

Limited memory comes into play when it comes to selecting the least valuable entry to overwrite. It is important to store any new position even if it is less valuable than all of the replacement candidates.

My point however is about what to store when you already have the position in the transposition table. This occurs even when the table is not nearly full.

I think there may be some engine dependence too. Nps and if you probe in quies() or not may change things a bit.

ACK

[mcostalba]

We have tried many variations, but what is currently it seems is the best one or at least is not worse of more complicated schemes so, being ELO equal, we always adopt the simplest scheme.

Anyhow in the development branch we have committed this change:

Code: Select all

    --- a/src/tt.cpp
    +++ b/src/tt.cpp
    @@ -121,7 +121,7 @@ void TranspositionTable::store(const Key posKey, Value v, ValueType t, Depth d,
               continue;

           c1 = (replace->generation() == generation ?  2 : 0);
    -      c2 = (tte->generation() == generation ? -2 : 0);
    +      c2 = (tte->generation() == generation || tte->type() == VALUE_TYPE_EXACT ? -2 : 0);
           c3 = &#40;tte->depth&#40;) < replace->depth&#40;) ?  1 &#58; 0&#41;;

           if &#40;c1 + c2 + c3 > 0&#41;

that is needed because now we return from a TT hit also in PV nodes, see this thread for reference:

http://open-chess.org/viewtopic.php?f=5 ... &start=140

[mcostalba]

My point however is about what to store when you already have the position in the transposition table. This occurs even when the table is not nearly full.

Yes, we made this test: it is always better to overwrite even with a lower depth entry, this is because beta changes from one search to another. So it is totally unuseful to have a 20 depth entry with type lower bound and value 100 when current beta is 200. In this example it would be better for example to overwrite with a depth 5 entry but lower bound set at 300.

IMHO with very aggressive aspiration window it is more important that values are near current beta then the depth.

[rbarreira]

I thought Crafty also always replaces an entry with the same hash value if it finds one...

I just looked at the source code, and yeah, here's the comment on it:

* Pass 1: If any signature in the table matches the *
* current signature, we are going to overwrite this *
* entry, period. It might seem worthwhile to check *
* the draft and not overwrite if the table draft is *
* greater than the current remaining depth, but after *
* you think about it, this is a bad idea. If the *
* draft is greater than or equal the current remaining *
* depth, then we should never get here unless the *
* stored bound or score is unusable because of the *
* current alpha/beta window. So we are overwriting to *
* avoid losing the current result. *

[Sven]

I thought Crafty also always replaces an entry with the same hash value if it finds one...

I just looked at the source code, and yeah, here's the comment on it:

* Pass 1: If any signature in the table matches the *
* current signature, we are going to overwrite this *
* entry, period. It might seem worthwhile to check *
* the draft and not overwrite if the table draft is *
* greater than the current remaining depth, but after *
* you think about it, this is a bad idea. If the *
* draft is greater than or equal the current remaining *
* depth, then we should never get here unless the *
* stored bound or score is unusable because of the *
* current alpha/beta window. So we are overwriting to *
* avoid losing the current result. *

Fruit 2.1 does essentially the same. So I do not see the point of the OP, the Stockfish scheme does not differ substantially from that of Fruit or Crafty. There are subtle implementation details, for instance in the selection of the slot to be overwritten in case no slot is empty and the current position is not found, but the basic algorithm is nearly identical IMO.

Sven

[Onno Garms]

We have tried many variations, but what is currently it seems is the best one or at least is not worse of more complicated schemes so, being ELO equal, we always adopt the simplest scheme.

OK, then I'm not going to try again. The transposition table was never my main interest, I was just surprised to find something that simple in Stockfish.

Yes, we made this test: it is always better to overwrite even with a lower depth entry, this is because beta changes from one search to another. So it is totally unuseful to have a 20 depth entry with type lower bound and value 100 when current beta is 200. In this example it would be better for example to overwrite with a depth 5 entry but lower bound set at 300.

Good point, I never thought of that.