official-stockfish/Stockfish — pull request #83 by promaret (2014-10-30 18:39:03+00:00)
Title: Remove bias when choosing a TT entry to replace

When saving an entry to a TT cluster, the previous logic
would only overwrite the last cluster entry if it proved
less valuable than the previous ones, in addition to being
less valuable than the new entry. This bias caused the
first entry in a cluster to be overwritten and lost more
often that the last. Any bias here is detrimental to the
search: it reduces the effective size of the TT.

Entry 1: replaced 39.5 % of the time
Entry 2: 32.8 %
Entry 3: 27.6 %

From this, we deduce that the TT operates at 84.3% efficiency.

The patch removes the bias by scanning the cluster's entries
starting with any of them, pseudo-randomly (using key16 as
the sole source of randomness).

Another source of bias covered by the patch is the
identification of 'empty' slots. Previous code systematically
replaced entries with key16 = 0, which means that 1 entry
out of 65536 had a much shorter lifetime in the TT than the
others. This is solved by using genBound8 instead, as it
is never equal to 0 for non-empty entries.