Transposition Table updates in Stockfish

[Onno Garms]

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

You are right for the current Crafty 23.4. I looked at Crafty 23.0 where I found:

* The underlying scheme here is that there are essentially two separate *
* transposition/refutation (hash) tables that are interleaved into one *
* large table. We have a depth-priority table where the draft of an entry *
* is used to decide whether to keep or overwrite that entry when a store *
* is done. We have a 2x larger always-store table where entries that *
* either (a) don't have enough draft to be stored in the depth-priority *
* table are stored or (b) entries overwritten in the depth-priority table *
* get pushed into the always-store table to avoid losing them completely. *

Looks like Bob now also thinks that overwriting is the best. One more reason for me not to try something else.

[Onno Garms]

Fruit 2.1 does essentially the same.

Fruit does not overwrite deeper entries:

Code: Select all

         if (min_value > -ValueInf && depth >= entry->min_depth) {
            entry->min_depth = depth;
            entry->min_value = min_value;
         }

         if (max_value < +ValueInf && depth >= entry->max_depth) {
            entry->max_depth = depth;
            entry->max_value = max_value;
         }

[bob]

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?

Crafty's replacement always replaces an entry on an exact match. It sounds to me like stockfish is doing the right thing there. There's a good reason for doing this. Remember, if you are storing over an existing entry with the same signature, you must have probed and hit when you started the search at this ply, yet the entry was not good enough to stop the search... So since it was useless, there is no reason to hang on to it just because it has a better draft or whatever... It makes more sense to overwrite a useless entry with something that might be more useful next time...

[Onno Garms]

Crafty's replacement always replaces an entry on an exact match.

Has that been introduced recently? If not, how does that relate to the comment in Crafty 23.0 that I posted?

[Mincho Georgiev]

About six months ago, I decided to play around with my hashing scheme.
Till then, I was replacing always - unconditionally. The part that stays the same now is that always replacement is still valid when direct hit occurred (I suppose that this is what Bob means by "exact match" and not connected to "EXACT value"). For the rest of the cases (when position not matching), I've added aging in order to select which one to replace (by draft or age).
I would like to say that it was little disappointing, that after all that I wasn't able to measure ANY elo gain at all (my test shows +3, +4 ELO which is a bit chaotic). So I guess it was not that important (at least in my case) what is done with the unmatched entries. BTW, I was testing with 2 tables before (1 draft preferred and 1 always replaceable), I think it comes from a Bruce Moreland's proposal, and still the unconditional always replacement was a lot better.

P.S. /just a thought/ It will be very interesting if some day we discover the main dependencies between the hashing and the rest of the program, because they most definitely exists, since we have "different strokes for different folks" regarding search modules and hashing schemes.

[bob]

Crafty's replacement always replaces an entry on an exact match.

Has that been introduced recently? If not, how does that relate to the comment in Crafty 23.0 that I posted?

That was a couple of years old. At that time, crafty did _always_ replace as done in Belle, effectively two tables, one depth-preferred, one always-store.

I changed that a good while back to do a more cache-friendly approach using a 64-byte bucket of 4 entries, and then picking the best one to replace. But it always replaces on a signature match, which was better and confirmed through testing.

[Sven]

Fruit 2.1 does essentially the same.

Fruit does not overwrite deeper entries:

Code: Select all

         if (min_value > -ValueInf && depth >= entry->min_depth) {
            entry->min_depth = depth;
            entry->min_value = min_value;
         }

         if (max_value < +ValueInf && depth >= entry->max_depth) {
            entry->max_depth = depth;
            entry->max_value = max_value;
         }

Partially correct. Fruit does some "update" of the entry if the key matches. You cannot be sure how much of the entry is kept and how much is changed. For instance, only the best move could be updated, or only the min_depth/min_value, or only the max_depth/max_value, or combinations of that. That means, in general Fruit overwrites parts of a matching entry but will keep data from a deeper search.

So the key point is that the Fruit algorithm is indeed not as simple as the Stockfish algorithm. My "essentially the same" may have been not precise enough

Sven

[Sven]

Crafty's replacement always replaces an entry on an exact match.

Has that been introduced recently? If not, how does that relate to the comment in Crafty 23.0 that I posted?

That was a couple of years old. At that time, crafty did _always_ replace as done in Belle, effectively two tables, one depth-preferred, one always-store.

I changed that a good while back to do a more cache-friendly approach using a 64-byte bucket of 4 entries, and then picking the best one to replace. But it always replaces on a signature match, which was better and confirmed through testing.

Just for the records: according to "diff" that happened from 23.0 to 23.1, where 23.1 seems to have appeared in Nov. 2009.

Sven

[Onno Garms]

Partially correct. Fruit does some "update" of the entry if the key matches. You cannot be sure how much of the entry is kept and how much is changed. For instance, only the best move could be updated, or only the min_depth/min_value, or only the max_depth/max_value, or combinations of that.

Sure. But if all of the move, the min value, and the max value are stored with larger depth, all will be kept and nothing will be stored.

[bob]

Crafty's replacement always replaces an entry on an exact match.

Has that been introduced recently? If not, how does that relate to the comment in Crafty 23.0 that I posted?

That was a couple of years old. At that time, crafty did _always_ replace as done in Belle, effectively two tables, one depth-preferred, one always-store.

I changed that a good while back to do a more cache-friendly approach using a 64-byte bucket of 4 entries, and then picking the best one to replace. But it always replaces on a signature match, which was better and confirmed through testing.

Just for the records: according to "diff" that happened from 23.0 to 23.1, where 23.1 seems to have appeared in Nov. 2009.

Sven

Sounds about right. 18 months +/- ago...