Transposition Table updates in Stockfish

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Transposition Table updates in Stockfish

Post by Onno Garms » Tue Apr 12, 2011 7:18 pm

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?

User avatar
Eelco de Groot
Posts: 4159
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Transposition Table updates in Stockfish

Post by Eelco de Groot » Tue Apr 12, 2011 7:44 pm

Onno Garms wrote: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
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Transposition Table updates in Stockfish

Post by Onno Garms » Tue Apr 12, 2011 8:30 pm

Eelco de Groot wrote: 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.

User avatar
michiguel
Posts: 6388
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Transposition Table updates in Stockfish

Post by michiguel » Tue Apr 12, 2011 8:37 pm

Onno Garms wrote: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

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Transposition Table updates in Stockfish

Post by Onno Garms » Tue Apr 12, 2011 8:55 pm

michiguel wrote: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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Transposition Table updates in Stockfish

Post by mcostalba » Tue Apr 12, 2011 9:05 pm

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Transposition Table updates in Stockfish

Post by mcostalba » Tue Apr 12, 2011 9:25 pm

Onno Garms wrote: 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
Posts: 900
Joined: Tue Apr 27, 2010 1:48 pm

Re: Transposition Table updates in Stockfish

Post by rbarreira » Tue Apr 12, 2011 9:41 pm

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
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Transposition Table updates in Stockfish

Post by Sven » Tue Apr 12, 2011 10:01 pm

rbarreira wrote: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

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Transposition Table updates in Stockfish

Post by Onno Garms » Tue Apr 12, 2011 10:23 pm

mcostalba wrote: 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.

Post Reply